Recursive Zero-Knowledge Proofs: A Comprehensive Primer

Recently, there have been a number of exciting results concerning proof recursion. A sketch for Halo has suggested the possibility of proof recursion without a costly trusted setup, while Fractal has demonstrated the first instantiation of proof composition which is post-quantum secure. We’ll go into these results later after discussion what proof composition is, the technical challenges associated with achieving it, and how it ties into commonly used proof systems as Groth 16 and Bulletproofs.

Posted

Class Groups for Cryptographic Accumulators

Late last year Benedikt Bunz and Ben Fisch, both PhD students at Stanford University, released a paper along with Dan Boneh titled “Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains”. In it they use some basic group theory to build a dynamic accumulator, which allows for storing and deleting elements in addition to the use of both membership and non-membership proofs. It can be used to create a vector commitment data structure analogous to Merkle trees, with the main difference being that it allows for constant-sized inclusion proofs, where a Merkle tree has $O(\log n)$ sized inclusion proofs where $n$ is the number of elements being stored.

Posted