Halo: Recursive Proof Composition without a Trusted Setup

The five-minute read

One action, walked through

1. A prover produces an inner-product proof of some step.
2. A second proof attests that the verifier of the first would have accepted, without the outer verifier redoing the whole check.
3. The deferred checks accumulate.
4. At the end, one verifier checks the accumulated argument.
5. Anyone who wants to verify a long chain of steps checks that one object, then trusts the recursion circuit.

The argument, unpacked

What has to be true

• The inner-product argument's assumptions hold in the groups being used.
• The curve cycle is the one the proofs expect. A mismatched curve is not a proof.
• The recursion circuit really verifies the inner verifier, including its edge cases.
• Transcripts are bound with Fiat-Shamir so a prover cannot replay challenges.

What happened after the paper

The Halo line fed Zcash's move away from per-circuit setups and influenced other recursive proof systems. Production clients diverged into Halo 2 and then into whatever those clients shipped. The 2019 paper is the citation for setup-free recursion of inner-product proofs, not for a shielded pool's current circuit.

What to check before you use the idea

• Is the deployment Halo or Halo 2?
• Which curve cycle is used?
• What exactly does the recursion circuit verify?
• Is there still a trusted setup hiding in a different part of the stack?

Terms

Recursive composition

A proof that attests to the checking of another proof, so verification can be folded.

Curve cycle

Two curves arranged so each can efficiently reason about the other's field.

The problem the paper names

SNARK recursion had wanted cycles of pairing-friendly curves and a setup. Halo tries to verify an inner-product argument inside another proof without those pairings.

What the design proposes

• Nested amortization of the inner-product argument.
• No trusted setup of the Groth16 kind.
• A cycle of curves still appears in the concrete instantiation. The cycle is an engineering object, not a slogan.

How the mechanism is specified

• The verifier does not re-run every previous proof. It checks one proof that claims those checks happened.
• A bug in the recursion circuit is a bug in every folded proof. The paper does not remove auditor duty.
• Zcash's later deployment path used this research. Orchard is not the 2019 PDF.

What this page does not treat as proven

• Recursion does not make the statement true. It compresses verification of whatever was proved.
• No trusted setup is not the same as no cryptographic assumption.
• Halo 2 changes the polynomial commitment. Do not mix the citations.

Why a venture studio still reads it

Ask what is inside the recursion: a step of a virtual machine, a transaction, or a claim about a reserve. Then ask who wrote the circuit that checks the inner proof.