Emerging Epochs for Proof Carrying Data and Incrementally Verifiable Computation

Proof Carrying Data is a a cryptographic paradigm promising new pathways in blockchain bridges and blockchain data availability proofs. It charts out new terrains of verifiable computing in heterogeneous environments. The original concept of Proof-carrying data (PCD) was introduced by Chiesa and Tromer. It is defined as a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations defined on directed acyclic graphs, while every intermediate state of the computation can be verified efficiently. It generalizes incrementally verifiable computation (IVC) which enables a possibly infinite computation defined on path graphs such that the correctness can be verified efficiently at any point. This approach eliminates the high memory needs of a monolithic blockchain.

Historically, IVC and PCD were built from a recursive proof systems. However, this requires embedding the proof verifier inside the statement being proved at every step, and this introduces a considerable overhead. An alternative approach was proposed that leverages a technique known as folding. The idea is to “fold” the proof verification work at every step into the SNARK verification of all previous steps. The final folded statement is verified at the end of the computation.

Reductions of knowledge (RoK) introduced by Kothapalli and Parno is an interesting concept used in the construction of folding schemes. RoK comes into play because folding schemes often involve proving knowledge of witnesses (data that satisfies a specific condition) for multiple instances of a problem. There can be multiple instance-witness relations. A reduction of knowledge itself is a protocol between prover and verifier.

A folding technique can be realized utilizing the reduction of knowledge protocols to achieve their efficiency. Folding schemes often involve proving knowledge of witnesses for several instances of a problem. Instead of proving knowledge of individual witnesses for each instance, RoK allows the prover to demonstrate knowledge of a witness for a single, combined instance that represents all the original instances.

Thus, folding schemes aim to combine multiple instances of a computation into a single proof for verification. A key challenge is ensuring the correctness of the "folded" proof without revealing the details of the individual computations. Earlier folding techniques used additive homomorphic property of specific commitment schemes. The first lattice cryptography based folding scheme has been invented by Dan Boneh and Binyi Chen recently in which the security assumptions depends on the Module Short Integer Solution (MSIS) problem.