Thread by @tracecrypto1

ZK Fundamentals:

What is proof aggregation, recursion, and composition?

Proof Aggregation, Recursion, and Composition are 3 distinct concepts that are often confused.

Each one involves combining multiple zk proofs together to achieve the best performance for zk applications.

Proof Aggregation involves batching many proofs together into a single proof.

Each input proof is verified as part of the aggregation proof, meaning that the single output proof demonstrates the validity of all the inputs.

Proof aggregation is primarily used to condense data by combining many proofs into one.

Verifying the one proof verifies all of them, which saves gas and on-chain verification time.

The technique is used in privacy applications like @Poseidon_ZK, where each user generates a zk proof locally for their specific transaction and passes it to an aggregator, who then posts a single proof on chain.

Proof Recursion is the idea of verifying a proof within another proof.

Recursion can overlap with aggregation. However, recursion often involves many steps of proving in a chain, while aggregation may only involve a single recursive step.

The simplest example of proof recursion is the layer 1 ZK blockchain @MinaProtocol.

At each block, Mina verifies the correctness of the previous block and performs some state transition, while generating a proof of that state transition’s correctness.

Therefore, the entire history of the blockchain can be verified by verifying the latest block.

Proof Composition is the idea of mixing and matching different types of proofs together.

It can compose small proofs for dedicated purposes together to prove general-purpose statements.

One example is the CP-SNARK that uses a “commit and prove” design to achieve proof composition.

Different proofs have different tradeoffs.

STARKs have fast provers, but require larger proofs and a longer verification time.

SNARKs have slower provers, but are quicker to verify.

With proof composition, we can chain a STARK into a SNARK to get the benefits of STARK proving times and SNARK verification times.

Proof aggregation, recursion, and composition can often be combined into a single efficient protocol.

For example, zkTree is a new technique by @PolymerDAO for generating a tree of ZKPs.

eprint.iacr.org/2023/208.pdf

The tree can be used to take many proofs and aggregate them into one to be efficiently verified on-chain.

zkTree uses plonky2 proofs because of their fast recursion and then converts them into a single small Groth16 proof because of its cheap verification.

In summary, proof aggregation, recursion, and composition are techniques for combining multiple proofs together to get the best performance out of zk applications.