This section constructs the inner-product polynomial commitment that opens the commitments of §2.9 at the verifier’s point. It states the problem, performs one halving step, recurses it into the full argument with both parties’ tables, gives the verifier’s closing computation, proves knowledge soundness under the discrete-logarithm assumption, proves honest-verifier zero knowledge of the masked opening, runs the running example’s polynomial through every round on a curve of prime order 97 , and in the last subsection gives the parameters, the normalisation, the opening, the bytes and the deferred check of the deployed Halo 2. Beyond the Math Guide, the section relies on these parts of the Crypto Guide: the Pedersen vector commitment (§“Pedersen vector commitments”), extractors and the tree extraction of Sigma-protocols (§“Knowledge soundness and extractors”, §“The Schnorr identification protocol”, §“Sigma-protocols”), the simulation paradigm (§“The simulation paradigm and zero knowledge”), hashing to a curve (§“Hashing to a curve point”) and the standing assumptions (§“Standing assumptions”). From this volume, the generic argument takes only the cue of §2.9; the toy reuses the running example’s advice polynomial and random point (§2.2, §2.4), restated where used; the last subsection takes the deployed circuit’s field from §1.2 and the advice, permutation, lookup and quotient objects from §2, and forward-references §4 for the row count and the remaining objects of the proof; the other references to §2 mark where the argument is used.
The prover holds a vector
| P = ⟨ a, G ⟩ + [r] H = ∑ i = 0 d − 1 [a i] G i + [r] H, |
the Pedersen vector commitment of a with blinder r under the
public generators
| ⟨ a, b ⟩ = ∑ i = 0 d − 1 a i b i = v . |
There is a trivial protocol: the prover sends a and r ; the
verifier recomputes P from them, which the binding of the commitment
makes a meaningful check, and then computes ⟨ a, b ⟩
himself. It costs
Convince the verifier that
⟨ a, b ⟩ = v for the vector a committed in P , using fewer than d group elements, and without revealing a .
Let
| p (x) = ∑ i = 0 d − 1 a i x i = ⟨ a, (1, x, x 2, ..., x d − 1) ⟩ . |
Evaluating a committed polynomial is therefore exactly the
problem above, with the public vector
The commitment is linear in the vector: adding two commitments commits
to the sum of their vectors, and scaling one by λ commits to
λ a (Crypto Guide, §“Pedersen vector
commitments”, the remark that linearity survives). The inner product is
linear in a too. But the two linear maps land in different
places, one in the group and one in the field, and by the hiding of the
commitment no public operation takes P to ⟨ a, b ⟩ .
A claim about a vector of length one is checked by sending the scalar and
its blinder.
The argument that follows reduces the length by halving. Each
halving step turns a claim about vectors of length 2 j into a claim of
the same shape about vectors of length 2 j − 1 , at a price of two group
elements, and after
Throughout, G is a cyclic group of prime order p and
Fix public generators
| R IPA := { ((P, x, v) ; (a, r)) : P = ⟨ a, G ⟩ + [r] H, v = ⟨ a, b (x) ⟩, a ∈ F d }, | ||
| b (x) := (1, x, ..., x d − 1), |
where (P, x, v) is the public statement and (a, r) the
witness. The condition
The following conventions hold from here to the end of §3.
The vector length is
Generators are indexed from 0 ,
The letter H names the blinding generator
The letter z is the running example’s opening point,
In the byte count of §3.8, a is the number of Actions, an integer, not the vector a .
A vector of length 2 j splits into its low half, the
first 2 j − 1 entries, and its high half, the last
2 j − 1 :
One halving step is called a fold. This subsection performs one fold on a vector of length d .
The commitment P says nothing about b or v . Bring them in:
after P is fixed, the verifier samples a further generator U
uniformly from
| C := P + [v] U . | (11) |
If the prover is honest,
Write
| ⟨ a, G ⟩ = ⟨ a lo, G lo ⟩ + ⟨ a hi, G hi ⟩, ⟨ a, b ⟩ = ⟨ a lo, b lo ⟩ + ⟨ a hi, b hi ⟩ . |
Let
| a ′ := u a lo + u − 1 a hi, G ′ := u − 1 G lo + u G hi, b ′ := u − 1 b lo + u b hi, | (12) |
entry by entry:
Expand ⟨ a ′, G ′ ⟩ using bilinearity of the mixed inner product (Math Guide, §“The mixed inner product with group elements”), one term per pair of halves:
| ⟨ a ′, G ′ ⟩ | = ⟨ u a lo + u − 1 a hi, u − 1 G lo + u G hi ⟩ | ||
| = u u − 1 ⟨ a lo, G lo ⟩ + u u ⟨ a lo, G hi ⟩ + u − 1 u − 1 ⟨ a hi, G lo ⟩ + u − 1 u ⟨ a hi, G hi ⟩ | |||
| = ⟨ a lo, G lo ⟩ + ⟨ a hi, G hi ⟩ ⏟ = ⟨ a, G ⟩ + u 2 ⟨ a lo, G hi ⟩ + u − 2 ⟨ a hi, G lo ⟩ . |
The two diagonal terms, low with low and high with high, have
weight
| ⟨ a ′, b ′ ⟩ = ⟨ a, b ⟩ + u 2 ⟨ a lo, b hi ⟩ + u − 2 ⟨ a hi, b lo ⟩ . |
The four cross inner
products ⟨ a lo, G hi ⟩ ,
⟨ a hi, G lo ⟩ ,
⟨ a lo, b hi ⟩ and
⟨ a hi, b lo ⟩ involve only the
halves, not u . The prover can therefore commit to them before
the challenge is drawn. She samples two fresh blinders
| L := ⟨ a lo, G hi ⟩ + [l] H + [⟨ a lo, b hi ⟩] U, R := ⟨ a hi, G lo ⟩ + [ρ] H + [⟨ a hi, b lo ⟩] U, | (13) |
each of the same three-part shape as C : a vector part on the generators, a blinder on H , and the matching scalar inner product on U . Only then does the verifier draw u .
Now add the cross terms to C with the weights the expansion produced and regroup by generator set:
| C + [u 2] L + [u − 2] R | = ⟨ a, G ⟩ + [r] H + [⟨ a, b ⟩] U | ||
| + u 2 (⟨ a lo, G hi ⟩ + [l] H + [⟨ a lo, b hi ⟩] U) | |||
| + u − 2 (⟨ a hi, G lo ⟩ + [ρ] H + [⟨ a hi, b lo ⟩] U) | |||
| = (⟨ a, G ⟩ + u 2 ⟨ a lo, G hi ⟩ + u − 2 ⟨ a hi, G lo ⟩) | |||
| + [r + u 2 l + u − 2 ρ] H + [⟨ a, b ⟩ + u 2 ⟨ a lo, b hi ⟩ + u − 2 ⟨ a hi, b lo ⟩] U | |||
| = ⟨ a ′, G ′ ⟩ + [r ′] H + [⟨ a ′, b ′ ⟩] U, |
where
| C ′ := C + [u 2] L + [u − 2] R = ⟨ a ′, G ′ ⟩ + [r ′] H + [⟨ a ′, b ′ ⟩] U . | (14) |
Compare the two sides of (14) with (11). The element C ′ has the same shape as C , over vectors of half the length: its G ′ -part is the folded coefficient vector, its H -part a blinder, and its U -coefficient the inner product of the folded vectors. The verifier can compute C ′ , G ′ and b ′ entirely on his own from C , L , R , u and the public data. The prover computes a ′ and r ′ . The claim about (a, b, G) of length d has been replaced by a claim about (a ′, b ′, G ′) of length d / 2 , and the exchange cost exactly two group elements and one field element of challenge. Figure 8 shows the fold and identity (14). Only completeness is claimed here; that a prover who cannot open C cannot open C ′ either is proved in §3.5.
When
| b ′ = u − 1 b lo + u x d / 2 b lo = (u − 1 + u x d / 2) (1, x, ..., x d / 2 − 1) : |
the folded evaluation vector is again a vector of powers of x , scaled
by the scalar
For the running example’s length, the halves are
| L | = [a 0] G 2 + [a 1] G 3 + [l] H + [a 0 x 2 + a 1 x 3] U, | ||
| R | = [a 2] G 0 + [a 3] G 1 + [ρ] H + [a 2 + a 3 x] U, |
and the folded vectors are
The folded claim of §3.2 has the shape of the original
claim, so it can be folded again. After
Let G be a cyclic group of prime order p in which the discrete
logarithm problem is hard (Crypto Guide, §“Standing
assumptions”), and let
Commitment. For
| Commit (p ; r) := ⟨ a, G ⟩ + [r] H ∈ G . |
Opening. To prove
Setup. The verifier samples U uniformly from
Rounds. For
The prover samples independent uniform
| L j | := ⟨ a lo (j), G hi (j) ⟩ + [l j] H + [⟨ a lo (j), b hi (j) ⟩] U, | ||
| R j | := ⟨ a hi (j), G lo (j) ⟩ + [ρ j] H + [⟨ a hi (j), b lo (j) ⟩] U . |
The verifier sends a uniform
Both parties fold by (12):
| G (j − 1) := u j − 1 G lo (j) + u j G hi (j), b (j − 1) := u j − 1 b lo (j) + u j b hi (j), | ||
| C (j − 1) := C (j) + [u j 2] L j + [u j − 2] R j ; |
the prover also folds
Final message. After round 1 every vector has length
one. Write
| r ∗ := r (0) = r + ∑ j = 1 k (u j 2 l j + u j − 2 ρ j) . |
Check. The verifier accepts if and only if
| P + [v] U + ∑ j = 1 k ([u j 2] L j + [u j − 2] R j) = ? [a] G (0) + [r ∗] H + [a ⋅ b (0)] U, | (15) |
where the left-hand side is C (0) and G (0) , b (0) are computed as §3.4 describes.
The round index descends so that round j begins with vectors of length 2 j ; round k is the first round and round 1 the last. The scheme instantiates the polynomial-commitment interface of the Crypto Guide (§“Polynomial commitment schemes”, the inner-product alternative), and the opening protocol is the inner-product argument of Bootle, Cerulli, Chaidos, Groth and Petit as refined in Bulletproofs by Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell, in the symmetric normalisation those papers use.
The honest prover always passes. By induction on the rounds,
| C (j) = ⟨ a (j), G (j) ⟩ + [r (j)] H + [⟨ a (j), b (j) ⟩] U for j = k, k − 1, ..., 0 : | (16) |
at
The prover sends two group elements per round and two field elements at
the end: 2 k group elements plus O (1) , against the
| step | receives / holds | computes and sends |
|---|---|---|
| setup | holds a , r , x , v ; receives U | sets a (k) := a , G (k) := G , b (k) := b (x) , r (k) := r |
| round j | vectors of length 2 j , split into halves | samples l j, ρ j ; sends L j , R j as in Construction 3.2 |
| receives u j | folds a (j − 1) = u j a lo (j) + u j − 1 a hi (j) , G (j − 1) , b (j − 1) ; r (j − 1) = r (j) + u j 2 l j + u j − 2 ρ j | |
| final | one entry each: a = a (0) , r ∗ = r (0) | sends a , r ∗ |
| step | receives / holds | computes and sends |
|---|---|---|
| setup | holds P , x , v , G , H | samples U and sends it; sets C (k) := P + [v] U |
| round j | receives L j , R j | samples u j ∈ F × and sends it; keeps (L j, R j, u j) ; optionally C (j − 1) := C (j) + [u j 2] L j + [u j − 2] R j |
| final | receives a , r ∗ | computes s and G (0) = ⟨ s, G ⟩ (one length- d multi-scalar multiplication), b (0) = g (x ; u 1, ..., u k) ( O (k) field operations), and checks (15) |
The check (15) needs two quantities the verifier has
not yet been told how to obtain cheaply: the final generator
G (0) and the final evaluation scalar b (0) . Folding
G round by round costs
For
| s i := ∏ l = 1 k u l (− 1) 1 − β l − 1 (the factor is u l when β l − 1 = 1 and u l − 1 when β l − 1 = 0) . | (17) |
Then, after the k folds of Construction 3.2,
| G (0) = ⟨ s, G ⟩ = ∑ i = 0 d − 1 [s i] G i, b (0) = ⟨ s, b (x) ⟩ = g (x ; u 1, ..., u k), | (18) |
where
| g (X ; u 1, ..., u k) := ∏ l = 1 k (u l − 1 + u l X 2 l − 1), | (19) |
a polynomial of degree
Follow one original generator G m through the folds. Claim: after the
rounds
For the closed form, expand the product (19): choosing from
the l -th factor either u l − 1 (when
At
The verifier’s closing work is now explicit. He evaluates
Evaluating g at x costs
This subsection shows that any prover that makes the verifier of
Construction 3.2 accept knows an opening
(a, r) of P with
Fix a level j with generator vector G (j) of length
2 j . A representation of an element
| Q = ⟨ x, G (j) ⟩ + [y] H + [w] U . |
Call the representation well formed at level j if its
U -coordinate is the inner product of its G -coordinates with
the round’s evaluation vector,
| Q = ⟨ (u − 1 a ′, u a ′), G ⟩ + [y] H + [w] U, | (20) |
and the lift preserves well-formedness, since
Fix one round of Construction 3.2 at level j : the
verifier’s element
| x ν = ν 2 x L + x C + ν − 2 x R, y ν = ν 2 y L + y C + ν − 2 y R, w ν = ν 2 w L + w C + ν − 2 w R . | (21) |
If the three given representations are well formed at level j , so is the recovered representation of C .
Write the three known representations as vectors
| [ν 2] L + C + [ν − 2] R = ⟨ x ν, G ⟩ + [y ν] H + [w ν] U, ν ∈ { u, u ′, u ′′ }, |
suggest the linear system
| M (X L X C X R) = (Y u Y u ′ Y u ′′), M := (u 2 1 u − 2 u ′ 2 1 u ′ − 2 u ′′ 2 1 u ′′ − 2), |
to be solved coordinate by coordinate. Multiplying the row of ν by
the nonzero scalar ν 2 turns it into (ν 4, ν 2, 1) , which
does not change the kernel. If
Let G be a group of prime order in which the discrete logarithm
problem is hard, and let G and H be uniform in
The proof is given at the level of this volume: the single-round step is Lemma 3.4, the tree is an induction on it, and the rewinding that supplies the sibling transcripts is the Crypto Guide’s (§“The Schnorr identification protocol”, the remark on extraction by rewinding, and §“Sigma-protocols”, the tree-extraction theorem cited there, which also gives the expected running time). The trees it assembles have children with pairwise distinct challenges (the Crypto Guide’s Definition “Tree special soundness”), while Lemma 3.4 needs pairwise distinct squares. A square has at most two square roots, so any five pairwise distinct challenges contain three with pairwise distinct squares: the rewinding assembles five children per node, and the extractor uses three of them. From a tree the extractor computes a witness or, at the root, a discrete-logarithm relation; that definition asks for a witness alone, and the difference is where the assumption enters.
Leaves. Rewind the prover to the moment after it sent (L 1, R 1) and obtain three accepting final messages (a, r ∗) for three
challenges u 1 with pairwise distinct squares. An accepting final
message is, by (15), a representation of C (0)
over (G (0), H, U) , namely (a ; r ∗ ; a b (0)) , and it is well
formed at level 0 : its U -coordinate is the inner product of a
with the length-one vector b (0) . Lift it to level 1
by (20):
One node. The three lifted leaves are well-formed
representations of the three folded elements
Induction. Rewind to the moment after (L 2, R 2) , obtain three
challenges u 2 with pairwise distinct squares, and under each of them
repeat the two steps above. That yields, after lifting to level 2 ,
three well-formed representations of the elements
The root, where the assumption enters. The root representation
says
| [w − v] U − [w ′ − v] U ′ + ⟨ x − x ′, G ⟩ + [y − y ′] H = O |
with the nonzero coefficient
The error. The figure does not come from a union bound over the
tree. At each node the extractor needs three siblings whose challenges
avoid O (1) values: ± ν for each earlier sibling’s challenge
ν , so that the squares stay pairwise distinct. Each of the
The theorem concerns the interactive protocol; the compiled argument is treated in §5. In the algebraic group model the extractor does not rewind for the representations at all: an algebraic prover hands them over with every group element it sends, and the tree collapses to a single transcript (§5, “The algebraic group model”). After the Fiat–Shamir transform has replaced the verifier’s challenges by hashes, the rewinding above must be re-proved against a prover who can query the hash adaptively and resume from any earlier transcript state (for one round, the Crypto Guide’s forking lemma, §“Security in the random oracle model and the forking lemma”; the multi-round case in §5), and its cost cannot be obtained by multiplying every node of the tree by an independent 1 / ε factor. Nor does the theorem restate the binding of the commitment itself: that a single P cannot be opened as two vectors is the Crypto Guide’s theorem, cited in §2.9 and not reproved here.
The extractor’s alternative output is a discrete-logarithm relation
among G , H and the verifier’s U , U ′ , so the argument is
binding as long as discrete logarithms are hard in G and the
generators are uniform; hashed generators are uniform when hash-to-curve
is modelled as a random oracle into G (Crypto Guide,
§“Hashing to a curve point”, Remark “Why NUMS generators are
binding-safe”), a hypothesis of Theorem 3.5. For the
deployed instance
the group is the Vesta curve (§3.8), and the
assumption that carries the argument is the discrete logarithm on
Vesta, the first of the Crypto Guide’s standing assumptions
(§“Standing assumptions”), against which the generic attacks cost
about 2 126 operations (§“Instantiation on elliptic curves; the
Pasta curves”); a quantum adversary running Shor’s algorithm lies
outside those assumptions, which fix a classical adversary. Suppose the
assumption fails: an algorithm computes discrete logarithms on Vesta.
Then it computes the logarithms
The extractor is run against an honest prover for the running example’s
vector
The transcript of one opening consists of group elements, challenges
and two final scalars. The group elements are hidden by the blinders:
the commitment blinder r makes P uniform in G whatever
a is (perfect hiding, Crypto Guide, §“The Pedersen
commitment” and §“Pedersen vector commitments”), and the round
blinders
The final scalar
| a (0) = ⟨ a, t ⟩, t i := ∏ l = 1 k u l (− 1) β l − 1 = s i − 1 ; at d = 4 : t = (u 1 u 2, u 1 − 1 u 2, u 1 u 2 − 1, u 1 − 1 u 2 − 1) . | (22) |
In the toy of §3.7, with challenges
| ⟨ (90, 61, 22, 24), (70, 22, 75, 79) ⟩ . |
One opening thus
hands the verifier one linear equation in the four secret coefficients;
every further opening of the same commitment under fresh challenges
hands him another, and d of them determine a outright.
Four openings of the same vector, with challenge pairs
The masked opening runs Construction 3.2 on a masked statement.
Mask. Before any folding, the prover samples a
polynomial
| S := Commit (s ; r s) = ⟨ m, G ⟩ + [r s] H . |
Challenge. The verifier sends a uniform
Opening. By linearity of the commitment (Crypto Guide, §“Pedersen vector commitments”, the remark that linearity survives),
| P + [ξ] S = Commit (p + ξ s ; r + ξ r s), | (23) |
a commitment to the coefficient vector
Final message and check. The prover sends the final
scalar
| P + [ξ] S + [v] U + ∑ j = 1 k ([u j 2] L j + [u j − 2] R j) = ? [c] G (0) + [f] H + [c ⋅ b (0)] U, | (24) |
which is (15) for the masked statement.
Completeness is that of Construction 3.2, since the
witness satisfies R IPA for the masked statement; the
mask leaves the opened value unchanged because
| (S ; L k, R k, ..., L 1, R 1 ; c, f) with the challenges (ξ, U, u k, ..., u 1) . |
The final scalar is the linear form (22), taken of the masked vector:
| c = ⟨ a + ξ m, t ⟩ = ⟨ a, t ⟩ + ξ ⟨ m, t ⟩ . | (25) |
In the toy, with
Let G have prime order p , and let the verifier draw ξ
uniformly from F , U uniformly from
Call a challenge tuple good if
In an honest run with good challenges, S and every L j , R j are
uniform and independent (fresh blinders), c is uniform and independent
of them (the mask), and f is the unique scalar that
makes (24) hold once everything else is fixed,
H generating G . The simulator produces the same distribution in the
reverse order, the way the Schnorr simulator chooses its commitment
after the challenge (Crypto Guide, §“Sigma-protocols”): it
draws the challenges as the verifier does, draws S , all L j and all
R j but R 1 uniformly from G , draws c and f uniformly from
F , and sets R 1 to the one point that
satisfies (24), namely
This argues one opening in isolation. The proof system opens many committed polynomials at once, under shared challenges, and the mask is one of several blinding devices it uses; whether the joint transcript reveals nothing is a separate question, addressed under “Zero knowledge: hiding the witness in Halo 2” in §4, where the mask, in the deployed form of §3.8, reappears as the last of those devices.
The toy opening commits the running example’s advice polynomial,
The vector a lives in F 97 4 , so the commitment group
must have order 97 : scalars of a prime-order group live in the field
of its order (Math Guide, §“Base fields, scalar fields, and
the Pasta cycle”), exactly as the deployed circuit’s field is the
scalar field of the deployed commitment curve. The group
| E : y 2 = x 3 + 3 over F 79, # E (F 79) = 97, |
counted point by point; 97 is prime, so the group is cyclic and every
point but O generates it, and its trace
The generators are derived from public labels by hashing to the curve,
as the deployed ones are: the label and a counter are hashed to a
candidate x -coordinate, and the counter is incremented until
| G 0 = (12, 25), G 1 = (17, 27), G 2 = (71, 26), | ||
| G 3 = (49, 10), H = (78, 9), U = (53, 26) . |
The hashed point U stands in for the verifier’s uniform sample of
Construction 3.2. No party chose any of them, so no
relation among them is known in advance; a single discrete logarithm
between two of them would give one, since
The prover holds
| P = [90] G 0 + [61] G 1 + [22] G 2 + [24] G 3 + [10] H = (39, 25) . |
The verifier holds P , the point
Tables 4 and 5 refill the rows of Tables 2 and 3 with numbers, listing each party’s inputs and computations; the verifier’s table never uses a .
| step | receives / holds | computes and sends |
|---|---|---|
| setup | holds a = (90, 61, 22, 24) , r = 10 , z = 20 , v = 59 ; receives U = (53, 26) | a (2) := a , G (2) := (G 0, G 1, G 2, G 3) , b (2) := (1, 20, 12, 46) , r (2) := 10 |
| round 2 | halves a lo = (90, 61) , a hi = (22, 24) ; b lo = (1, 20) , b hi = (12, 46) | samples l 2 = 44 , ρ 2 = 16 ; ⟨ a lo, b hi ⟩ = 6 , ⟨ a hi, b lo ⟩ = 17 ; sends L 2 = [90] G 2 + [61] G 3 + [44] H + [6] U = (74, 6) , R 2 = [22] G 0 + [24] G 1 + [16] H + [17] U = (38, 72) |
| receives u 2 = 52 ( u 2 − 1 = 28 ) | a (1) = 52 (90, 61) + 28 (22, 24) = (58, 61) ; b (1) = 28 (1, 20) + 52 (12, 46) = (70, 42) ; G (1) = ([28] G 0 + [52] G 2, [28] G 1 + [52] G 3) = ((54, 40), (30, 71)) ; r (1) = 10 + 52 2 ⋅ 44 + 28 2 ⋅ 16 = 95 | |
| round 1 | halves a lo = 58 , a hi = 61 ; b lo = 70 , b hi = 42 | samples l 1 = 12 , ρ 1 = 37 ; a lo b hi = 11 , a hi b lo = 2 ; sends L 1 = [58] G 1 (1) + [12] H + [11] U = (28, 25) , R 1 = [61] G 0 (1) + [37] H + [2] U = (39, 25) |
| receives u 1 = 20 ( u 1 − 1 = 34 ) | a (0) = 20 ⋅ 58 + 34 ⋅ 61 = 33 ; b (0) = 34 ⋅ 70 + 20 ⋅ 42 = 19 ; G (0) = [34] G 0 (1) + [20] G 1 (1) = (12, 25) ; r (0) = 95 + 20 2 ⋅ 12 + 34 2 ⋅ 37 = 40 | |
| final | a = 33 , r ∗ = 40 | sends a = 33 , r ∗ = 40 |
| step | receives / holds | computes and sends |
|---|---|---|
| setup | holds P = (39, 25) , z = 20 , v = 59 , G , H = (78, 9) | sends U = (53, 26) , a hashed point standing in for his sample; C (2) := P + [59] U = (47, 39) |
| round 2 | receives L 2 = (74, 6) , R 2 = (38, 72) | samples u 2 = 52 and sends it; keeps (L 2, R 2, 52) ; C (1) := C (2) + [52 2] L 2 + [28 2] R 2 = (72, 23) |
| round 1 | receives L 1 = (28, 25) , R 1 = (39, 25) | samples u 1 = 20 and sends it; keeps (L 1, R 1, 20) ; C (0) := C (1) + [20 2] L 1 + [34 2] R 1 = (54, 39) |
| final | receives a = 33 , r ∗ = 40 | s = (34 ⋅ 28, 20 ⋅ 28, 34 ⋅ 52, 20 ⋅ 52) = (79, 75, 22, 70) ; G (0) = [79] G 0 + [75] G 1 + [22] G 2 + [70] G 3 = (12, 25) ; b (0) = g (20 ; 20, 52) = (34 + 20 ⋅ 20) (28 + 52 ⋅ 12) = 19 ; right-hand side [33] G (0) + [40] H + [33 ⋅ 19] U = (54, 39) = C (0) : accept |
The verifier’s equation (15) closes: the left-hand side
Let the prover claim
The same P is then opened at the same z with the masked opening of
§3.6. The prover samples
Everything above holds for any prime-order group and any
The Orchard Action circuit does its arithmetic in F p Pallas ,
the base field of the Pallas curve, because the statement manipulates
Pallas points and their coordinates live there (§1.2;
Math Guide, §“Base fields, scalar fields, and the Pasta
cycle”). Its column polynomials therefore have coefficients in
F p Pallas , and a Pedersen commitment to such a vector needs a
group whose scalar field is F p Pallas : that group is the Vesta
curve, whose order is p Pallas (protocol specification,
§ 5.4.9.6,
“Pallas and Vesta”). The specification uses Halo 2 with the Vesta curve
to prove and verify the Action statement
(§ 4.1.13,
“Zero-Knowledge Proving System”), so every P , L j , R j , S and
G (0) of this section is a Vesta point and every scalar a Pallas
base-field element.
The other half of the Pasta cycle, Pallas’s scalar field being Vesta’s
base field, is needed only by the optional native recursion of
§7; Orchard’s verifier never uses it. The committed
polynomials have degree below the row count
The 2048 vector generators, the blinding generator H and the inner-product generator U are all outputs of hash-to-curve on one fixed domain-separation label, the vector generators indexed by their position and H and U by two further tags (Crypto Guide, §“Hashing to a curve point”, Construction “Nothing-up-my-sleeve generators”). With hash-to-curve modelled as a random oracle into G they are independent and uniform, and a relation among them yields a discrete logarithm on Vesta (the same section, Remark “Why NUMS generators are binding-safe”). No secret is generated in producing them, unlike the trapdoor of KZG (Crypto Guide, §“Polynomial commitment schemes”, under “KZG: evaluation in the exponent”), the point the closing subsubsection returns to. Because U is a fixed parameter rather than a verifier’s sample drawn after each P , the deployed opening re-randomises it per opening with a challenge ζ (“The deployed opening in full” below).
The interactive verifier of Construction 3.2 draws u j uniformly from F × , and the halo2 book’s Protocol Description excludes zero challenges. The deployed verifier is a hash (“Removing the verifier: the Fiat–Shamir transform” in §4), and the transcript of the halo2_proofs implementation squeezes every challenge, ξ , ζ and each u j , as a full field element with no rejection of zero. A zero u j would make the fold’s inversion fail, so the honest prover succeeds unless one of the k challenges is zero, an event of probability 1 / | F | per challenge, about 2 − 254 : completeness of the deployed argument is overwhelming, not literally perfect, in the sense fixed in §1.2.
The deployed opening, stated in full below, is the masked opening of
§3.6 with three changes. It folds with the weights
(1, u j − 1) on the coefficient vector and (1, u j) on b
and G , with cross terms
| g dep (X) | = ∏ i = 0 k − 1 (1 + u k − 1 − i X 2 i) | in its numbering, | (26) | |||
| g dep (X) | = ∏ l = 1 k (1 + u l X 2 l − 1) | in this volume’s, |
with structured scalars
The change of variables. The two folds are one argument. Run
both on the same vector, the same generators and the same evaluation
vector, with the deployed challenge of every round the square of the
symmetric one,
| a sym ′ | = u a lo + u − 1 a hi = u (a lo + u − 2 a hi) = u a dep ′, | ||
| G sym ′ | = u − 1 G lo + u G hi = u − 1 (G lo + u 2 G hi) = u − 1 G dep ′, | ||
| b sym ′ | = u − 1 b lo + u b hi = u − 1 (b lo + u 2 b hi) = u − 1 b dep ′, |
so
| a dep (j) = (∏ l > j u l) − 1 a sym (j), G dep (j) = (∏ l > j u l) G sym (j), b dep (j) = (∏ l > j u l) b sym (j), | (27) |
with u l the symmetric challenges of the rounds already run.
Each deployed factor of (26) is a symmetric factor
scaled,
| g dep = (∏ l = 1 k u l) g sym, s dep = (∏ l = 1 k u l) s sym, a dep (0) = (∏ l = 1 k u l) − 1 a sym (0), |
while G (0) and b (0) carry the product itself, so that
[a (0)] G (0) and a (0) b (0) agree in both normalisations,
and the two verifier equations coincide once each run attaches l j
and ρ j to the same cross product.
Table 6 prints both runs on the toy’s data and
keeps the blinder names instead, so the deployed run attaches each
blinder to the other cross product, and its equation differs from the
symmetric one only in the H -term (
| symmetric fold | deployed fold | relation | |
|---|---|---|---|
| round 2 : challenge | u 2 = 52 | u 2 = 52 2 = 85 | |
| cross terms sent | L 2 = (74, 6) , R 2 = (38, 72) | L 2 = (78, 70) , R 2 = (71, 26) | halves swapped |
| a (1) | (58, 61) | (72, 59) | 52 − 1 ⋅ |
| G (1) | ((54, 40), (30, 71)) | ((53, 53), (41, 6)) | 52 ⋅ |
| b (1) | (70, 42) | (51, 50) | 52 ⋅ |
| round 1 : challenge | u 1 = 20 | u 1 = 20 2 = 12 | |
| cross terms sent | L 1 = (28, 25) , R 1 = (39, 25) | L 1 = (43, 6) , R 1 = (70, 71) | halves swapped |
| a (0) | 33 | 85 | (52 ⋅ 20) − 1 = 70 − 1 ⋅ |
| G (0) | (12, 25) | (34, 53) | 70 ⋅ |
| b (0) | 19 | 69 | 70 ⋅ |
| structured scalars s | (79, 75, 22, 70) | (1, 12, 85, 50) | 70 ⋅ |
| g (20) | (u 1 − 1 + u 1 z) (u 2 − 1 + u 2 z 2) = 19 | (1 + u 1 z) (1 + u 2 z 2) = 69 | 70 ⋅ |
| aggregated blinder r ∗ | 40 | 33 | |
| verifier’s equation | (54, 39) = (54, 39) | (5, 72) = (5, 72) | same [a (0)] G (0) , a (0) b (0) |
The deployed fold changes the rows of the extractor’s linear system.
Fix one round at level j as in Lemma 3.4, but let the round fold the coefficient vector with the weights (1, u − 1) and the generator and evaluation vectors with the weights (1, u) ,
| a ′ := a lo + u − 1 a hi, G ′ := G lo + u G hi, b ′ := b lo + u b hi, |
with the cross terms named with the halves swapped relative to (13),
| L := ⟨ a hi, G lo ⟩ + [l] H + [⟨ a hi, b lo ⟩] U, R := ⟨ a lo, G hi ⟩ + [ρ] H + [⟨ a lo, b hi ⟩] U, |
and the folded commitment
The fold identity is the expansion of §3.2 with
the weights changed: the diagonal terms of
The two row shapes impose different hypotheses: two challenges
On the data of Example 3.6, the extractor with rows
(u − 1, 1, u) and the fold of Lemma 3.10
branches over its own challenges:
The deployed opening is the masked opening of §3.6 with
the deployed fold, a further challenge ζ , and the claimed value
moved into the commitment. Let
Mask. The prover samples s (X) with
Two challenges. The verifier sends a uniform ξ , and then a uniform ζ .
The masked commitment. Both parties replace P by
| P ′ := P + [ξ] S − [v] G 0, | (28) |
which, by linearity of the commitment (Crypto Guide,
§“Pedersen vector commitments”, the remark that linearity
survives), commits with blinder
| a ′ := a + ξ m − v e 0 |
of the polynomial
Rounds. The parties run the k rounds on (a ′, G, b (x)) with the fold of Lemma 3.10, weights (1, u j − 1) on the coefficients and (1, u j) on generators and evaluation vector, and with the U -coordinates of the cross terms scaled by ζ :
| L j | := ⟨ a hi ′ (j), G lo (j) ⟩ + [l j] H + [ζ ⟨ a hi ′ (j), b lo (j) ⟩] U, | ||
| R j | := ⟨ a lo ′ (j), G hi (j) ⟩ + [ρ j] H + [ζ ⟨ a lo ′ (j), b hi (j) ⟩] U ; |
the verifier accumulates
Final message and check. The prover sends the final
scalars
| P + [ξ] S − [v] G 0 + ∑ j = 1 k ([u j − 1] L j + [u j] R j) = ? [c] G (0) + [c ⋅ b (0) ⋅ ζ] U + [f] H, | (29) |
where
Completeness is the invariant (16) again, with
a ′ in place of a , the value 0 in place of v , and
every U -coordinate scaled by ζ ; the final U -coordinate is
The final scalar is the linear form of (22) for this fold, taken of the masked vector:
| c = ⟨ a + ξ m − v e 0, t ⟩ = ⟨ a − v e 0, t ⟩ + ξ ⟨ m, t ⟩, t i = ∏ l : β l − 1 = 1 u l − 1, | (30) |
the coefficient side folding with the inverse weights of the generator
side as always. Unmasked, the deployed fold leaks this form as the
symmetric one does (Remark 3.7):
four deployed openings of (90, 61, 22, 24) without the mask, with
challenge pairs
| (S ; L k, R k, ..., L 1, R 1 ; c, f) with the challenges (ξ, ζ, u k, ..., u 1) . |
Let G have prime order p , and let the verifier draw
The proof of Proposition 3.8, with the deployed
t and with (29) in place
of (24). Call a challenge tuple good if
The toy’s P of §3.7 is opened at
| step | prover | verifier |
|---|---|---|
| mask | samples m = (66, 23, 23, 88) , for which s (20) = 0 , and r s = 95 ; sends S = ⟨ m, G ⟩ + [95] H = (70, 71) | receives S ; sends ξ = 29 , then ζ = 12 |
| masked vector | a ′ = a + 29 m − 59 e 0 = (5, 49, 10, 54) ; ⟨ a ′, b (20) ⟩ = 0 ; blinder f := 10 + 29 ⋅ 95 | P ′ := P + [29] S − [59] G 0 |
| round 2 | halves a lo ′ = (5, 49) , a hi ′ = (10, 54) ; l 2 = 44 , ρ 2 = 92 ; cross terms ⟨ a hi ′, G lo ⟩ = [10] G 0 + [54] G 1 = (34, 53) , ⟨ a hi ′, b lo ⟩ = 23 , ⟨ a lo ′, G hi ⟩ = [5] G 2 + [49] G 3 = (54, 39) , ⟨ a lo ′, b hi ⟩ = 83 ; sends L 2 = (34, 53) + [44] H + [12 ⋅ 23] U = (17, 52) , R 2 = (54, 39) + [92] H + [12 ⋅ 83] U = (47, 40) | sends u 2 = 85 ( 85 − 1 = 8 ); keeps (L 2, R 2, 85) ; P ′ (1) := P ′ + [8] L 2 + [85] R 2 = (64, 5) |
| folds a ′ (1) = (5, 49) + 8 (10, 54) = (85, 93) , b (1) = (1, 20) + 85 (12, 46) = (51, 50) , G (1) = (G 0 + [85] G 2, G 1 + [85] G 3) = ((53, 53), (41, 6)) ; f = 10 + 29 ⋅ 95 + 8 ⋅ 44 + 85 ⋅ 92 = 73 | ||
| round 1 | halves a lo ′ = 85 , a hi ′ = 93 ; l 1 = 95 , ρ 1 = 56 ; cross terms [93] G 0 (1) = (58, 8) , 93 ⋅ 51 = 87 , [85] G 1 (1) = (24, 9) , 85 ⋅ 50 = 79 ; sends L 1 = (58, 8) + [95] H + [12 ⋅ 87] U = (46, 13) , R 1 = (24, 9) + [56] H + [12 ⋅ 79] U = (24, 70) | sends u 1 = 12 ( 12 − 1 = 89 ); keeps (L 1, R 1, 12) ; P ′ (0) := P ′ (1) + [89] L 1 + [12] R 1 = (5, 72) |
| folds c = a ′ (0) = 85 + 89 ⋅ 93 = 20 , b (0) = 51 + 12 ⋅ 50 = 69 , G (0) = G 0 (1) + [12] G 1 (1) = (34, 53) ; f = 73 + 89 ⋅ 95 + 12 ⋅ 56 = 82 | ||
| final | sends c = a ′ (0) = 20 , f = 82 | g (20) = (1 + 12 ⋅ 20) (1 + 85 ⋅ 20 2) = 69 ; s = (1, 12, 85, 50) , G (0) = ⟨ s, G ⟩ = (34, 53) ; left: P ′ + [85 − 1] L 2 + [85] R 2 + [12 − 1] L 1 + [12] R 1 = (5, 72) ; right: [20] G (0) + [20 ⋅ 69 ⋅ 12] U + [82] H = (5, 72) : accept; with v ′ = 60 : left (67, 31) ≠ (5, 72) : reject |
Let G , G and H be as in Theorem 3.5, and
let U be a fixed generator, uniform in
The extractor branches over two values
Rounds. Fix ξ and
The challenge ζ . Under one ξ , the values ζ 1 and
ζ 2 give representations (x 1 ; y 1 ; ζ 1 w 1) and
(x 2 ; y 2 ; ζ 2 w 2) of the same P ′ over
(G, H, U) . If they differ, their difference is a nontrivial
relation among G , H and U . Otherwise
The challenge ξ . The values ξ 1 and ξ 2 follow the
same S and give
The error. Beyond the O (log d / | F |) of the rounds, the two
branchings at the root and the exclusion of
An Orchard proof is a byte string. The proofs of the
| kind | count | bytes | what it is |
| Per-Action block, once per Action | |||
| point | 10 | 320 | advice column commitments, one per advice column |
| point | 3 | 96 | permuted lookup input commitments A ′ , one per lookup (Construction 2.14) |
| point | 3 | 96 | permuted lookup table commitments S ′ , one per lookup (Construction 2.14; unrelated to the mask commitment S ) |
| point | 3 | 96 | permutation running-product commitments: the 15 equality-enabled columns in chunks of 7 (§2.6) |
| point | 3 | 96 | lookup running-product commitments, one per lookup |
| scalar | 1 | 32 | instance column evaluation at x |
| scalar | 25 | 800 | 25 = 5 ⋅ 2 + 5 ⋅ 3 advice evaluations, one per queried rotation of each advice column (§4.4) |
| scalar | 8 | 256 | permutation product evaluations: 3 products at x and ω x , the first 2 also at ω − 6 x , the rotation to the boundary row n − n blind − 1 of Remark 2.17, with n blind = 5 blinding rows (§4.6) |
| scalar | 15 | 480 | lookup evaluations: product at x and ω x ; A ′ at x and ω − 1 x ; S ′ at x |
| total | 2272 | 22 points and 49 scalars | |
| Shared block, once per bundle | |||
| point | 1 | 32 | random polynomial commitment: a random polynomial added to blind the quotient (the complete protocol, §4) |
| point | 8 | 256 | quotient chunk commitments: constraint degree d max = 9 , so d max − 1 = 8 chunks of degree below n (Theorem 4.7) |
| scalar | 29 | 928 | fixed column evaluations at x , one per fixed column |
| scalar | 15 | 480 | permuted-label polynomial evaluations at x , one per equality-enabled column (Construction 2.10) |
| scalar | 1 | 32 | random polynomial evaluation at x |
| point | 1 | 32 | multipoint polynomial commitment: the one polynomial into which every query collapses (Construction 4.4) |
| scalar | 5 | 160 | multipoint evaluations: the value of each query group’s combined polynomial at the reduction’s fresh challenge point, one per distinct set of query points; five sets (§4.4) |
| point | 1 | 32 | IPA: the blinding commitment S |
| point | 22 | 704 | IPA: the k = 11 pairs (L j, R j) |
| scalar | 2 | 64 | IPA: the final scalars c and f |
| total | 2720 | 33 points and 52 scalars | |
The verifier of this section is logarithmic everywhere but in one
place. He reads
The consensus rules require each Action proof to be valid for the
verifying key of the Orchard circuit (protocol specification,
§ 4.6,
“Action Descriptions”); validity includes the
check (29) with its multi-scalar multiplication of
length d , and the specification composes no proofs, so the verifier
pays that multiplication itself rather than passing it on. Several
proofs can share it (Crypto Guide, §“Polynomial commitment
schemes”, Remark “KZG versus IPA, and the Halo lineage”). Written as
one multi-scalar multiplication that must evaluate to O ,
equation (29) has
Let G have prime order, let
Fix i with
Because G , U and H are shared, their terms merge, and b
equations combine into one multi-scalar multiplication of
The generators are outputs of a public hash-to-curve map on fixed inputs
(this subsection, “Generators from a hash”); the scheme has no trapdoor
and requires no trusted setup, unlike KZG, whose trapdoor permits
forgeries (Crypto Guide, §“Polynomial commitment schemes”, under
“KZG: evaluation in the exponent”). The price is the
In a recursive verifier, a circuit that verifies a proof, the
multi-scalar multiplication