Tree-Folding part 1
This series is about approaching ZK research from a software-engineering perspective. We will be studying folding schemes by implementing “tree-folding” for protogalaxy using Sonobe, to answer some research questions.
Recursive ZK Proofs
When you verify a zk proof inside of another zk proof, that’s called a recursive zk proof. Although it sounds silly; perhaps like something Xzibit would say on Pimp My Ride, recursive proof composition is extremely useful!
By breaking up large computations into multiple smaller proofs and using recursion to aggregate them, ZK applications can exploit parallelism to decrease the proving latency. Recursive proofs are a necessity to generate validity proofs of the state transition function for private blockchains, since the STF requires verifying client-side proofs generated by users.
Recursive proofs are also used cleverly by succinct blockchains, like Mina, who include a validity proof for each block inside the next block’s proof, perpetually collapsing verification of the entire blockchain from genesis into one tiny zk proof.
Recursion can be naively implemented by implementing the proof system’s verifier as a circuit inside of itself, this is how STARK-based systems like SP1 and Risc0 work. However, with curve (and perhaps lattice) based proof systems, some more interesting optimizations exist.
Optimization to Recursion (Accumulation)
In HALO (2019), Bowe, Grigg, and Hopwood describe a proof system with an optimized recursion, achieved by utilizing two elliptic curves whose base field matches the other curve’s scalar field, allowing them to verify each other with native arithmetic (avoiding the overhead from emulating larger fields in smaller fields). Additionally, it exploits the homomorphic nature of IPA commitments to “accumulate” instances of recursion, “deferring” an expensive part of the proving process until after the recursion instances are accumulated.
Later, the idea of “accumulating” instances of proof systems and clever optimizations to recursion was built upon by the literature on folding schemes, notably Nova, which efficiently accumulates instances of proof systems for circuits defined as R1CS relations. Later, Protostar generalized it to arbitrary kinds of relations (PLONK, AIR, or CCS constraints).
After Protostar, Protogalaxy proposed an updated version of the folding scheme that supports folding > 2 instances of a circuit.
What is Folding?
The mathematics underlying folding schemes sits somewhere between the circuit and the proof system. As we’ll cover in this series, much of the folding scheme’s implementation lies in the circuit side, rather than the polynomial IOP or commitment scheme. It builds ontop of existing SNARK proof systems (Nova utilizes Spartan).
Below is the Augmented Circuit, from an implementation of Protogalaxy. Notice how the circuit definition includes F, the useful circuit supplied by the dev, z_0, the initial state of the recursive computation, and z_i, the newest state of the recursive computation. We will explore the remaining fields later in this blog series.
pub struct AugmentedFCircuit<C1: Curve, C2: Curve, FC: FCircuit<CF1<C1>>> {
pub(super) poseidon_config: PoseidonConfig<CF1<C1>>,
pub(super) pp_hash: CF1<C1>,
pub(super) i: CF1<C1>,
pub(super) i_usize: usize,
pub(super) z_0: Vec<CF1<C1>>,
pub(super) z_i: Vec<CF1<C1>>,
pub(super) external_inputs: FC::ExternalInputs,
pub(super) F: FC, // F circuit
pub(super) u_i_phi: C1,
pub(super) U_i: CommittedInstance<C1, true>,
pub(super) U_i1_phi: C1,
pub(super) F_coeffs: Vec<CF1<C1>>,
pub(super) K_coeffs: Vec<CF1<C1>>,
pub(super) phi_stars: Vec<C1>,
pub(super) cf1_u_i_cmW: C2, // input
pub(super) cf2_u_i_cmW: C2, // input
pub(super) cf_U_i: CycleFoldCommittedInstance<C2>, // input
pub(super) cf1_cmT: C2,
pub(super) cf2_cmT: C2,
}
Sonobe