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.

Image by Tymon Oziemblewski from Pixabay

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.

Theorems of Recursion, Bootstrapping and Compliance in SNARKS
Mathematical Model of Proof Carrying Data

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.

Poetic Past. Digital Present. Ephemeral Future.