# A Journey through the Building Blocks of Recursive Zero Knowledge Proofs

Recursive Zero Knowledge Proof systems have become a challenging contour in the world of proof of knowledge systems ever since Nir Bitansky, Ran Canetti, Alessandro Chiesa and Eran Tromer (BCCT12)published the seminal research paper on Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data (PCD) in 2012. When Alessandro Chiesa and team initially presented this concept as an alternative to Probabilistic Checkable Proof (PCP) based approach, it raised many eyebrows. PCP and linear PCP based approaches were mainstream in those days. This is the prelude to the later work by Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer and Madars Virza (BCTM15) on Scalable Zero Knowledge via Cycles of Elliptic Curves. Hence this inital work on recursive zero knowledge proof composition and bootstrapping has paved the way for the research and development in the scalable Zero Knowldge Proof systems.

This paper begins with a nice overview of Succinct Non-interactive Arguments (SNARG). SNARGS have become very interesting in the world of cryptography as they provide strong solutions to the problem of verifiably delegating computation. Prior to the emergence of recursive proof composition models, public verifiable SNARGs were limited to random oracle models or in models that require expensive offline processing. We should know that there are two types of verifications in the world of zero knowledge systems — public verifiers and designated verifiers.

It is important to understand the notion of complexity preserving SNARKs outlined in this paper. All practical purpose implementations of Zero Knowledge has to deal with the construct of complexity. It could be a complexity in computing privacy or measuring levels of anonymity or anything related to obfuscation or randomness etc. Hence complexity preserving SNARKs has indeed widened the context and construct of zero knowledge.

The concept of bootstrapping used in this paper is very significant. It says any natural SNARK could be bootstrapped to obtain a complexity preserving SNARK without the computationally expensive pre-processing SNARKs. In a pre-processing SNARK, verifier is allowed to conduct an expensive offline phase. There is time and space complexity involved in the resource allocation for prover and verifier. In the pre-processing SNARK, the size of common reference string is also larger.

As a result, this paper was a proposal to move beyond the limitations of pre-processing SNARKs to scalable SNARKs. Hence this approach envisioned a SNARKs that simultaneously enable the verifier to run fast and enable the prover to use an amount of resources that is as close as possible to those required by the original computation.

Eventually, the time and space complexity of generator and prover was considerably reduced in the transformation from pre-processing SNARK to scalable SNARKs. Please note that the concept of bootstrapping in cryptography was made popular and practical by Craig Gentry in his seminal paper on Fully Homomorphic Encryption in 2005.

It is important to note that the recursive composition of SNARKs has placed zero knowledge systems in a distributed environment setting itself. This distributed architecture consisted of the following interplay of components.

Bootstrapping a SNARK

Constructing proof carrying data (PCD) systems

PCD framework for complexity preserving SNARKS

We can understand the important components and sequence of this recursive composition of SNARKS with bootstrapping approach in a distributed setting in the following architecture diagram illustrated in this paper.

One of the ingenious inventions of this paper was a random access machine (RAM) that accepts input instance in a non-deterministic manner. This was modelled after the concept of incrementally verifiable computation (IVC) propounded by Valiant. IVC was an approach to transform a given computation into a new computation that after every step outputs its entire state to produce a proof of its correctness while preserving the time and space efficiency of the original computation. In his pioneering paper, Valiant showed that IVC can be used as a very efficient knowledge extractor for proof of knowledge systems. There is an interesting concept of targeted malleability interconnected to IVC. Targeted Malleability was proposed by D. Boneh, Segev, and Waters (BSW12) in their paper on homomorphic encryption for restricted computations. This paper outlines the use of SNARKs for limited repeated homomorphic operations.

Another important cryptographic primitive used in the construction of recursive SNARKs is proof carrying data (PCD) introduced by Alessandro Chiesa and Eran Tromer itself. PCDs are conceptualised as messages that are augmented by short proofs attesting the local properties, without incurring significant overhead in communication or computation.

Following Bootstrapping theorem outlined in this paper underpins the transformation driving the realisation of recursive SNARKs in its entirety.

Any publicly-verifiable SNARK can be efficiently transformed into a publicly-verifiable PCD system for distributed computations of constant depth or over paths of polynomial depth.

Any publicly-verifiable PCD system (for distributed computations of constant depth or over paths of polynomial depth) can be efficiently transformed into a complexity-preserving publicly-verifiable SNARK or PCD system.

There are a lot more interesting and ingenious cryptographic constructions int this paper such as RAM Compliance, Collision Resistant Hash functions, Dynamic Merkle Tree Hashing etc. This paper is a must read for every enthusiast of cryptography and practioner of Zero Knowledge Proofs. It has indeed helped me to get clarity on recurive SNARKs and study practical implementations in CODA and Horizen in detail. More about those implementations will be covered in articles in the future.