This section states recursive proof composition and accumulation for
the inner-product argument; Orchard deploys neither. The protocol
specification uses Halo 2 for one purpose, to prove and verify Action
statements (protocol specification,
§ 4.1.13,
“Zero-Knowledge Proving System”), and requires every Action proof to be
valid
(§ 4.6,
“Action Descriptions”); the design proposal that introduced the pool
states that it makes no use of the proof system’s support for recursive
proofs (ZIP 224, under “Proving
system”). A verifier holding several proofs may still check them
together. The complete verification equation E i of each proof is a
multi-scalar multiplication over all d generators that should evaluate
to O (§3.8.1, “Batch verification”); for
independent uniform
Consider a computation iterated many times,
| z m = f (m) (z 0) := f (f (⋯ f (z 0) ⋯)), |
one step f applied m times to an initial state, and suppose a verifier wants to be sure that z m is the honest result without recomputing the m steps. Valiant’s incrementally verifiable computation asks for a proof of z m that is updated step by step, each update costing about one step’s worth of proving and the finished proof no larger than the proof of a single step. The more general setting, in which computations branch and merge and each step consumes the proofs of its predecessors, is the proof-carrying data of Chiesa and Tromer: every message in a distributed computation carries a proof that it was produced correctly from messages that themselves carried such proofs.
A PLONKish circuit (Definition 2.7) fixes its n rows,
its columns, its gates and the permutation σ , and the verifying
key is a deterministic function of these and the commitment parameters
(§4.1, “Key and witness”); for the Action circuit
The natural construction is recursive proof composition: proving,
inside one proof, that another proof verifies. Write V for the
verifier of a non-interactive argument (Crypto Guide, §“SNARKs:
succinct non-interactive arguments of knowledge”), and suppose its
algorithm is itself arithmetised, in the sense of §2,
into a PLONKish circuit of Definition 2.7, the
verifier circuit: its instance columns hold the statement and
its advice columns hold a proof, and its gates are satisfiable exactly
when V accepts that proof of that statement. At step
“
z i + 1 = f (z i) , and there exists a proof π i that the verifier circuit accepts for the statement of step i .”
The proof π i is advice of the step-
The classical instantiations meet that requirement badly, in two different ways.
Pairings in a circuit, and a ceremony. The pairing-based systems, Groth16, which Sapling deploys, and PLONK compiled with the KZG commitment (Crypto Guide, §“SNARKs: succinct non-interactive arguments of knowledge” for Groth16 and the bilinear pairing; §“Polynomial commitment schemes”, under “KZG: evaluation in the exponent”), have constant-size proofs and verifiers that run in time independent of the circuit. But those verifiers evaluate pairings, and a pairing lands in a target group that lives in an extension field F p e of the curve’s base field, of degree e equal to the curve’s embedding degree (Crypto Guide, §“Instantiation on elliptic curves; the Pasta curves”, the large-embedding-degree criterion). A circuit whose native arithmetic is one prime field must emulate arithmetic in another field with many gates per operation, so a pairing is costly to express inside a circuit. These particular systems also need a trusted setup, the ceremony that §3.8.1 contrasted with hashed generators.
A linear-time verifier. The transparent systems built on
the inner-product argument of §3 need no pairing and no
ceremony, but their verifier is linear in the size of the committed
vectors: the one multi-scalar multiplication
Halo, the construction of Bowe, Grigg and Hopwood (Halo: Recursive Proof Composition without a Trusted Setup) from which Halo 2 descends, defers the linear-time part of verification instead of recomputing it at every step, and uses the inner-product argument, in which no pairing occurs. Bünz, Chiesa, Mishra and Spooner formalised the deferral as an accumulation scheme (Proof-Carrying Data from Accumulation Schemes; BCMS20), the notion the next subsection defines; their Theorem 7.1 is quoted below, without proof, as Theorem 7.5.
The idea is to separate what a verifier must check at each step from what can be checked once, at the end of a chain. Fix a predicate Φ , a property of an input q decidable in polynomial time, for example “this inner-product opening is correct” of a transcript of Construction 3.2. An accumulation scheme replaces a sequence of checks of Φ by a sequence of accumulation steps and one run of a decider.
Let λ be the security parameter (Crypto Guide, §“Adversaries and the security parameter”) and Φ a predicate on inputs q . An accumulation scheme for Φ is a triple (P, V, D) of polynomial-time algorithms with access to a common random oracle, whose accumulators are bit strings.
The accumulation prover P , on input q and an old accumulator acc old , outputs a new accumulator acc and an accumulation proof π V .
The accumulation verifier V , on input (q, acc old, acc, π V) , outputs a bit; the bit 1 asserts that acc correctly accumulates q and acc old .
The decider D , on input an accumulator, outputs a bit; an accumulator is valid if D outputs 1 on it.
The scheme is complete if, whenever
| V (q, acc old, acc, π V) = 1 ∧ D (acc) = 1 ∧ (Φ (q) = 0 ∨ D (acc old) = 0) |
is negligible in λ .
The definition is that of BCMS20 (Section 4.1) with one input and one old accumulator per step; theirs admits any number of each and adds a generator and an indexer, which fix the public parameters and keys left implicit here. For recursion the size of an accumulator must also be bounded independently of the number of inputs accumulated into it (BCMS20, Definition 5.1).
Soundness carries the checks along a chain.
Let (P, V, D) be sound in the sense of
Definition 7.2, let acc 0 be valid, and let m
be polynomial in λ . For any efficient algorithm producing
If some q i violates Φ , then either
acc i is valid and step i exhibits the event of the
soundness definition, or some later step
The verifier of each step runs the accumulation verifier and never the decider. In a recursive chain the accumulation verifier runs inside the circuit of the step’s proof, so the argument also needs the knowledge soundness of each step’s proof, to recover what that circuit checked; BCMS20 prove the resulting proof-carrying data secure for computations of constant depth, which for a chain means constant length, because the extractor is applied recursively once per level (Theorem 5.2 and Remark 5.3).
For an inner-product polynomial commitment such a scheme is known under the hypothesis of Theorem 7.5 below, and it resolves the second obstacle of §7.1 where it arose: the verifier circuit runs the O (log d) part of the opening check, the rounds, the scalars and the small combinations of points, and accumulates the O (d) part, the claim about G (0) , into a running accumulator; the decider pays that multi-scalar multiplication once, at the end of the chain. The next subsection defines the accumulator, states the scheme as an interface theorem, and works the fold on the toy curve.
Everything the verifier of Construction 3.2 does to
decide the check (15), or its deployed
form (29), is logarithmic in d :
| G (0) = ⟨ s, G ⟩ = Commit (g (X ; u 1, ..., u k) ; 0), |
a multi-scalar multiplication of length d over all the generators, which §3.4 named the one linear step and recognised as the unblinded commitment to the polynomial g whose value the verifier had just computed cheaply. Verifying an Action proof as the consensus rules require includes that step for every proof; batch verification, recalled at the start of this section, evaluates one combined multiplication for the proofs of a batch, and the batch is verified and nothing survives it. Accumulation takes the same kind of linear combination and does something else with it: it carries the combined claim forward as data, unverified, and pays for it once at the end of a chain. Figure 19 sets the two side by side; the rest of this subsection is the right-hand panel, and none of it is deployed by Orchard.
The claim to be deferred has a fixed shape, and the accumulator is that shape written down.
An accumulator instance is a tuple
| Acc := (G (0), u 1, ..., u k) ∈ G × (F ×) k, |
a curve point and the k round challenges of one opening. It is valid if and only if
| G (0) = ⟨ s (u), G ⟩ = Commit (g (X ; u 1, ..., u k) ; 0), | (35) |
with s (u) and g the structured scalars and the
polynomial of Theorem 3.3, in the symmetric
normalisation of Construction 3.2. The deferred claim
concerns the unblinded commitment: the blinder of the opened
commitment was discharged by the [r ∗] H term
of (15), or the [f] H term of (29),
and plays no part in it. From here on the unary
The deployed analogue replaces s (u) and g by their forms in Remark 3.9; Proposition 7.6 and, with verifier-drawn challenges, the closure argument below hold for it verbatim, with Corollary 3.13 in place of Theorem 3.5, since they use only the linearity of the commitment, the degree of g and the knowledge soundness of the opening.
A verifier who is handed a point G (0) together with the challenges can complete the check (15) in O (log d) operations provided the tuple is valid; validity is precisely what he has not paid for. The scheme quoted next lets him defer that payment.
Let PC DL be the inner-product polynomial commitment of BCMS20 (Appendix A.2), for polynomials of degree below d over a group G of prime order, and suppose that PC DL is a polynomial commitment scheme in the random oracle model, its openings in particular being extractable. Then (BCMS20, Theorem 7.1) there is an accumulation scheme in the sense of Definition 7.2, in the random oracle model, for the predicate “this PC DL opening is correct”, whose accumulators are themselves PC DL openings, such that:
the accumulation prover P runs in time dominated by O (d) scalar multiplications in G ;
the accumulation verifier V runs in time dominated by O (log d) scalar multiplications in G ;
The theorem is quoted as an interface and not proved in this volume. Its hypothesis, the extractability of PC DL openings, is stated by BCMS20 as a conjecture from the binding of the Pedersen commitment, the extractor they record for the Fiat–Shamir-compiled opening running in superpolynomial time (BCMS20, Appendix A.3.2). The scheme PC DL is neither Construction 3.2, whose fold is symmetric, nor the deployed opening of Remark 3.9, which blinds every commitment and subtracts [v] G 0 where PC DL adds a multiple of its inner-product generator (the halo2 book’s Comparison to other work chapter); no theorem transferring it to either is proved here or cited, and in the classification of §1.2 that transfer, like accumulation over these curves, is designed-but-unspecified. What an accumulation step does for Construction 3.2, and why its random combination is sound, is worked out below at the level the volume proves things.
Consider a Halo 2 verifier circuit, expressed over the scalar field of one Pasta curve and verifying a proof produced over the other curve, an arrangement whose necessity §7.4 explains. At step i of a chain the circuit receives the previous proof π i − 1 , whose opening is an instance of Construction 3.2, and the accumulator Acc i − 1 exposed as a public input of π i − 1 , of which it uses the instance on the curve π i − 1 is committed on (see below), and does three things.
Run the succinct part. It recomputes the challenges u ′ of the opening from the transcript, evaluates g (x ; u ′) with O (k) scalar operations, and forms the left-hand side of (15) and every term of the right-hand side except the one on the final generator, here written G ′ (0) , with O (k) point operations. The point operations are native, since the points of π i − 1 have coordinates in the circuit’s field. The challenges, g (x ; u ′) and the scalar products lie in the scalar field of the curve π i − 1 is committed on, the other Pasta field; they are computed non-natively, or exposed as public inputs and checked by the next circuit of the chain, which is native to that field (“What the cycle does and does not buy” in §7.4; the halo2 book’s Recursion chapter).
Witness the expensive part. It does not compute G ′ (0) . The prover of the step supplies the claimed point as advice, and the circuit uses it to complete the check, which is then passed conditionally on the validity of the fresh tuple (G ′ (0), u ′) of that opening.
Accumulate. The step now holds two claims of the shape (35): the inherited instance (G (0), u) of Acc i − 1 and the fresh (G ′ (0), u ′) . For a challenge ρ derived by the random oracle from both tuples, the two reduce to the single claim
| G (0) + [ρ] G ′ (0) = Commit (g (X ; u) + ρ g (X ; u ′)) = ⟨ s (u) + ρ s (u ′), G ⟩, | (36) |
whose coefficient vector on the right anyone holding both challenge tuples can recompute. Proposition 7.6 shows that a false input survives the combination for at most one ρ . The step’s prover then opens the combined point at a fresh point, outside the circuit, and the circuit checks that opening succinctly as in item 1; the tuple the opening leaves behind is the new accumulator Acc i (over a 2-cycle, its instance on that curve), exposed as a public input of the proof π i the step produces. The paragraph “Closure: the prover-assisted step” below describes that opening.
Over a 2-cycle of curves (§7.4) the proofs alternate between the two curves, and the accumulator is a pair of instances, one per curve. The step that verifies a proof committed on one curve folds that proof’s fresh tuple into the instance on the same curve, which was last updated two steps earlier and forwarded unchanged by the intervening step, and it forwards the other curve’s instance in the same way, without point arithmetic. Figure 20 draws the chain. At its end a single multi-scalar multiplication of length d , run outside any circuit, checks the last accumulator and with it every opening in the history: for the scheme of Theorem 7.5 by Lemma 7.3.
The soundness of the fold (36) is one line of linear algebra in the group.
Let (G (0), u) and (G ′ (0), u ′) be two accumulator instances and ρ uniform in F , drawn after both are fixed. If both instances are valid, the folded equation (36) holds for every ρ . If at least one is invalid, it holds for at most one value of ρ , hence with probability at most 1 / | F | .
Set
| Δ + [ρ] Δ ′ = O . | (37) |
If both instances are valid,
The fold is run on the 97 -point curve and the four generators
The folded claim (36) is not an accumulator instance.
Its coefficient vector
Under the hypotheses of Theorem 3.5, let ρ , x ′ and
the opening’s challenges be drawn uniformly by the verifier, in this
order, ρ after the two tuples are fixed. There is an extractor
which, given rewindable access to a step prover accepted with
non-negligible probability, runs in expected polynomial time and outputs
either blinders
By Theorem 3.5 the opening yields a representation
| [c] Commit (g ; δ) + [r ∗] H = [c] Commit (g) + [r ∗ + c δ] H, |
so that opening satisfies the honest check with the blinder
Second, the opening leaves behind a deferred claim of the atomic form: it ends, as every opening does, in a point G ′′ (0) and challenges u ′′ that the verifier circuit witnesses rather than computes. The accumulator after the step is again one tuple. This is the accumulation step of BCMS20 (Section 7.1), which likewise derives the combining challenge and the fresh point by the random oracle from the tuples and the combined point; there the accumulator is the opening itself, and its succinct part runs at the next step. With ρ , x ′ and the opening’s challenges drawn by a verifier, the step’s soundness is Proposition 7.8. With random-oracle challenges, the step’s soundness is BCMS20’s Theorem 7.1 for PC DL under its conjectured extractability (Theorem 7.5); for Construction 3.2 it is designed-but-unspecified.
The deferred equation (35) is a claim of commitment equality, equivalently a claim about the value of one multi-scalar multiplication, for a coefficient vector s (u) that is public and structured: anyone holding the challenges can write it down. It is not itself an evaluation opening; no polynomial is being evaluated at any point when the decider runs, only a point recomputed and compared. The accumulation protocol reduces this claim, and carries it along the chain, through the prover-assisted opening just described, which turns each commitment equality into one evaluation claim at a fresh point and each opening back into one commitment equality. The Orchard verifier, once more, does none of this: it computes G (0) and compares.
The verifier circuit of §7.3 was “expressed over the scalar field of one Pasta curve and verifying a proof produced over the other”. This subsection explains why the two curves are needed, what the arrangement buys, and where Orchard already uses half of it.
A curve E over a prime field has two fields attached to it
(Math Guide, §“Base fields, scalar fields, and the Pasta
cycle”): the base field, in which its points’ coordinates lie
and in which the group law’s slopes, squarings and inversions are
computed, and the scalar field, the integers modulo the prime
order of its group, in which the scalars of [k] P live. Write E p
for a curve over F p and
Take a proof committed on E p . Its group elements, the column and
quotient commitments, the cross terms (L j, R j) and the deferred
point of its opening, are points of E p with coordinates in F p . The
in-circuit folding of §7.3 adds and scales such
points, which is base-field arithmetic in F p , so a verifier circuit
handles them natively only if its native field is F p . But a circuit
committed on E p is native to the scalar field F q : its
challenges, its structured scalars and every field operation of the
succinct part are F q -arithmetic. One curve would host both jobs
only if
The efficient resolution uses two curves that trade fields. A 2-cycle of elliptic curves is a pair (E p, E q) with
| # E p (F p) = q and # E q (F q) = p, |
both primes: the scalar field of each curve is the base field of the other. Then:
a circuit committed on E q has native field F p , the scalar field of E q ; and F p is the coordinate field of E p , so that circuit manipulates the points of a proof produced over E p natively, and verifies such a proof at the cost §7.3 counted, the proof’s scalars aside;
the proof that circuit produces is committed on E q , and its points have coordinates in F q , the native field of a circuit committed on E p ; so a circuit over F q handles its points natively in turn;
the proofs of a chain alternate between the two curves, each step handling its predecessor’s points natively (Figure 21).
The cycle makes the preceding curve’s coordinate arithmetic native; it does not identify the two scalar fields, which remain distinct primes. Challenges squeezed in the previous proof’s field and the scalars derived from them are F p -elements that the F q -native circuit must handle: they need compatible encodings across the two fields, range checks where an element of the larger field is carried in the smaller, and, where a genuine F p multiplication is unavoidable, non-native scalar arithmetic. Nor is the cycle a logical necessity. A single curve could verify its own proofs with non-native coordinate arithmetic throughout, at a cost of many gates per point operation multiplied by the O (log d) point operations of the succinct part; that is possible and substantially more expensive. The cycle is the efficient native design, not the only correct one.
The Pasta cycle of the Math Guide (§“Base fields, scalar
fields, and the Pasta cycle”; §“Pallas and Vesta assembled”) is a
2-cycle: Pallas is defined over F p Pallas with group order
p Vesta , and Vesta over F p Vesta with group order
p Pallas , both curves
| p Pallas | = 0x 40000000 00000000 00000000 00000000 224698 fc 094 cf91b 992 d30ed 00000001, | ||
| p Vesta | = 0x 40000000 00000000 00000000 00000000 224698 fc 0994 a8dd 8 c46eb21 00000001, |
the point (− 1, 2) lies on Pallas,
| t Pallas | = p Pallas + 1 − p Vesta = − 86663725065984043395317759, | ||
| t Vesta | = p Vesta + 1 − p Pallas = 86663725065984043395317761, |
each far inside the Hasse bound and neither equal to 1 : neither curve
is anomalous, as the Crypto Guide’s criterion requires. The two
traces sum to 2 , as they must for any 2-cycle, since
The Pasta cycle renders each step of §7.3 native. A proof committed on Vesta is produced by a circuit native to F p Pallas ; that circuit verifies the previous proof of the chain, committed on Pallas, whose group elements, the column and quotient commitments, the pairs (L j, R j) and the point of the Pallas accumulator instance it forwards, have coordinates in exactly F p Pallas , so the point arithmetic of the succinct checks and of the fold (36) is native. The next proof, committed on Pallas by a circuit native to F p Vesta , verifies the Vesta proof by the symmetric argument. This cross-curve alternation avoids non-native emulation of the preceding curve’s coordinate field; as “What the cycle does and does not buy” said, it does not eliminate the scalar-field conversions.
This is the part of the cycle in consensus. The Action circuit is native to F p Pallas and committed on Vesta (§3.8), and the statement it proves manipulates Pallas points: the note commitment cm , a Pallas point whose x -coordinate cmx is a public input; the randomised verification key rk ; and the net value commitment cv net , the last two exposed by their coordinates in the instance column of §4.2. Their coordinates lie in F p Pallas , the circuit’s native field, by the very coincidence the cycle is built on, so the circuit computes on them natively, with gates such as the incomplete-addition gate of §4.1.2. The protocol specification records the arrangement: Vesta for the proof system, Pallas for the application circuit, both curves designed to be efficiently implementable inside a circuit though only Pallas is so used (protocol specification, § 5.4.9.6, “Pallas and Vesta”); ZIP 224 says the same in the language of this subsection, that the proposal uses half of the cycle, Pallas being the curve embedded in Vesta’s circuits, and that the full cycle is left for future use (ZIP 224, under “Curves”). One direction of Figure 21 is thus in consensus today; the return arrow, and everything in this section that depends on it, is not.