Halo: Recursive Proof Composition without a Trusted Setup

01 Claim ledger

What the paper is allowed to say

Each row is a sentence already in the study. The status is the same on every row: a model claim, not a live measurement.

1. Claim 01 · Paper model

   Recursion was stuck on pairings

   To verify a SNARK inside a SNARK you needed a curve cycle and, often, a setup. Halo targets the inner-product argument used by Bulletproofs, which has no such setup, and shows how to nest it.

2. Claim 02 · Paper model

   Amortisation is the trick

   The expensive part of the inner-product verifier is not re-run from scratch at every level. It is deferred and combined. That deferral is the paper. It is also where an implementation bug would hide.

3. Claim 03 · Paper model

   A curve cycle still shows up

   The concrete construction uses two curves whose fields fit each other's groups. That is not a trusted setup. It is a constraint on which curves can be used, and it is part of the engineering risk.

4. Claim 04 · Paper model

   Halo 2 is a sequel

   Halo 2 changes the polynomial commitment and the circuit language. Zcash's later work sits closer to that sequel. Citing Halo for a Halo 2 deployment is a version error.

02 Three cuts

Observation, model, falsifier

A desk does not stop at the summary. Each claim is cut three ways, using only this study's own assumptions and checks. Nothing here is a new figure.

1. 01 Recursion was stuck on pairings

   Observation

   What the study says

   To verify a SNARK inside a SNARK you needed a curve cycle and, often, a setup. Halo targets the inner-product argument used by Bulletproofs, which has no such setup, and shows how to nest it.

   Model

   What has to hold

   The inner-product argument's assumptions hold in the groups being used.

   Falsifier

   What would retire it

   Which curve cycle is used?

2. 02 Amortisation is the trick

   Observation

   What the study says

   The expensive part of the inner-product verifier is not re-run from scratch at every level. It is deferred and combined. That deferral is the paper. It is also where an implementation bug would hide.

   Model

   What has to hold

   The inner-product argument's assumptions hold in the groups being used.

   Falsifier

   What would retire it

   Which curve cycle is used?

3. 03 A curve cycle still shows up

   Observation

   What the study says

   The concrete construction uses two curves whose fields fit each other's groups. That is not a trusted setup. It is a constraint on which curves can be used, and it is part of the engineering risk.

   Model

   What has to hold

   The curve cycle is the one the proofs expect. A mismatched curve is not a proof.

   Falsifier

   What would retire it

   Which curve cycle is used?

4. 04 Halo 2 is a sequel

   Observation

   What the study says

   Halo 2 changes the polynomial commitment and the circuit language. Zcash's later work sits closer to that sequel. Citing Halo for a Halo 2 deployment is a version error.

   Model

   What has to hold

   The recursion circuit really verifies the inner verifier, including its edge cases.

   Falsifier

   What would retire it

   Is the deployment Halo or Halo 2?

03 Sequence

One action, as an operating tape

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

04 Load-bearing

The argument, and where a pitch drops it

1. Compression is not truth

   The cut

   Recursion lets a chain keep a short witness of a long computation. If the circuit that verifies the inner proof is wrong, every folded proof inherits the mistake efficiently. Audit cost moves to the recursion circuit and stays there.

   Why it carries weight

   If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.

   Where it is dropped

   Recursion does not make the statement true. It compresses verification of whatever was proved.

2. No setup is a real distinction

   The cut

   Compared with Groth16 recursion stories, Halo removes a ceremony. It does not remove cryptographic assumptions, curve choices, or the need to implement Fiat-Shamir correctly.

   Why it carries weight

   If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.

   Where it is dropped

   Recursion does not make the statement true. It compresses verification of whatever was proved.

05 Register

What has to be true

• Model · Not re-measured

  The inner-product argument's assumptions hold in the groups being used.

• Cryptography · Not re-measured

  The curve cycle is the one the proofs expect. A mismatched curve is not a proof.

• Model · Not re-measured

  The recursion circuit really verifies the inner verifier, including its edge cases.

• Model · Not re-measured

  Transcripts are bound with Fiat-Shamir so a prover cannot replay challenges.

06 Divergence

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.

A later client, parameter set, or reward formula is a different object. Cite this paper for the mechanism. Cite a primary release for the network. This desk has not re-run the proof.

07 Pre-mortem

What to check before you use the idea

1. Kill test 1Is the deployment Halo or Halo 2?
2. Kill test 2Which curve cycle is used?
3. Kill test 3What exactly does the recursion circuit verify?
4. Kill test 4Is there still a trusted setup hiding in a different part of the stack?
5. 0 of 4 marked on this browser. A mark is a reading note, not a pass, a rating, or a recommendation.

08 Anatomy

The paper, in the order a builder needs

09 Lexicon

Terms, opened into the record

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.

10 Repository

Every linked record on this page

Underlined words open a page that already exists: a concept, a protocol profile, a failure record, or another paper. If a word is not underlined, this desk does not have a record for it.

11 Related

The next papers, as theses

• Bulletproofs · 2018

  Bulletproofs: Short Proofs for Confidential Transactions and More

  Range proofs whose size grows logarithmically, with no trusted setup. They made confidential amounts practical to verify. They are not, by themselves, a private payment system.

• PLONK · 2019

  PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

  A SNARK with a universal and updatable structured reference string. One setup can serve many circuits. The proofs are larger than Groth16, and there is still a setup.

• Zexe · 2020

  Zexe: Enabling Decentralized Private Computation

  A model for private computation over records. Each record has a birth predicate and a death predicate. A transaction proves that some records died and others were born, without showing which, or showing the data.