The Zcash ArboretumII Crypto Guide
Contents
PDF
Theme

4 Commitment schemes

A commitment scheme lets a sender fix a message in a value, the commitment, and later reveal the message to a receiver: once the commitment is delivered, the sender can no longer alter the message (binding), yet the receiver cannot learn it until it is opened (hiding). This section defines commitment schemes, their setup models, and hiding and binding as games in the sense of §1.4; proves that no nontrivial scheme is both perfectly hiding and perfectly binding (Theorem 4.8); and constructs hash-based, Pedersen, Pedersen vector and Sinsemilla commitments, the pairing-based and inner-product polynomial commitments of §4.9, and verifiable secret sharing. The Pedersen and Sinsemilla commitments require only the discrete-logarithm hardness of §2 and the nothing-up-my-sleeve generators of §3, and most later constructions use them. In Orchard, the value commitments checked by binding signatures, the note commitments accumulated in Merkle trees and the witness polynomials of the Halo 2 proof system are all commitments in this sense; polynomial commitments are the cryptographic component of the succinct argument systems of §9, and verifiable secret sharing serves the threshold signatures of a later volume.

4.1 Commit and reveal

The sender computes a commitment to a message and transmits it. Later, at a time fixed by the protocol, the sender opens the commitment by transmitting the message together with the randomness used to compute it, and the receiver checks the revealed message against the commitment. Hiding protects the sender against the receiver between commit and reveal; binding protects the receiver against the sender at reveal time. Without binding a commitment is no evidence of the message; without hiding it keeps nothing secret. The games of §4.3 formalise the two properties.

4.2 Syntax

Definition 4.1 (Commitment scheme).

A commitment scheme Π for a message space ℳ and randomness space ℛ is a triple of algorithms (Setup,Commit,Open):

  • •

    The algorithm Setup(1λ) is PPT (§1.1) and outputs public parameters pp, which implicitly determine the message space ℳp⁢p and randomness space ℛp⁢p and are an implicit input to the remaining algorithms.

  • •

    The algorithm Commit(pp,m;r), for m∈ℳp⁢p and r∈ℛp⁢p, is deterministic given r and outputs a commitment c. We write Commit(pp,m), without an explicit r, for the probabilistic algorithm that samples r←$ℛp⁢p uniformly and returns r alongside c.

  • •

    The algorithm Open(pp,c,m,r) is deterministic and outputs a bit: 1 (accept) or 0 (reject).

Correctness requires that honestly produced commitments open: for all pp in the support of Setup(1λ), all m∈ℳp⁢p, and all r∈ℛp⁢p,

Open⁢(p⁢p,Commit⁢(p⁢p,m;r),m,r)=1.

The pair (m,r) is called the opening (or decommitment) of c. Unless stated otherwise, every scheme in this volume is canonically opening: Open(pp,c,m,r) recomputes Commit(pp,m;r) and checks equality with c. For such a scheme correctness holds automatically, and a valid opening of c is precisely a pair (m,r) with Commit(pp,m;r)=c.

Remark 4.2 (The two phases, and a third concern).

In the commit phase the sender transmits c and nothing else; in the reveal phase it transmits the opening (m,r) and the receiver runs Open. A setup phase producing pp precedes both; who runs Setup, and whether that party can be trusted, is decisive for some of the constructions below (Remark 4.3).

Figure 7 draws the three phases on a time axis, with the threat that each property meets.

Refer to caption
Figure 7: The three phases of Remark 4.2. In the setup phase, Setup produces the public parameters pp for both parties; who runs it, and whether that party is trusted, is fixed by the setup model (Remark 4.3). In the commit phase the sender (red), holding the secret (m,r), transmits c=Commit(pp,m;r) and nothing else; from that point until the reveal, hiding (blue) protects the sender against a receiver who tries to learn m from c. In the reveal phase the sender transmits the opening (m,r) and the receiver (green) runs Open; at that point binding (amber) protects the receiver against a sender who could open c to a second message.
Remark 4.3 (Three setup models).

Commitment schemes divide by how much trust their parameters demand.

  1. 1.

    Common reference string (CRS). A trusted party runs Setup and is assumed to erase the randomness behind it. The parameters have internal structure, and knowledge of the discarded randomness—the trapdoor—would break the scheme. Of the schemes treated in this section, only KZG (§4.9) requires this model.

  2. 2.

    Uniform random string (URS), or transparent setup. The parameters consist only of public coins: uniformly random group elements with no known relations among them. There is no trapdoor and no trusted party—anyone can re-derive the parameters from a public seed. This is the regime of the Pedersen and inner-product commitments below. A Pedersen generator derived by hashing to the curve (Construction 3.24) is transparent, although the textbook Setup samples and discards a secret.

  3. 3.

    Plain. No parameters at all, or only a standardised hash function—the home of the hash-based commitment below.

Transparent setup is preferable because a flawed or subverted trusted setup can silently destroy binding, as the KZG trapdoor shows (§4.9).

4.3 Hiding and binding

Both properties are games in the sense of Definition 1.15. In the hiding game the adversary is the receiver; in the binding game it is the sender.

Definition 4.4 (Hiding game and hiding).

Let Π be a commitment scheme and 𝒜=(𝒜1,𝒜2) an adversary. For b∈{0,1}, the game 𝖧𝗂𝖽𝖾Π𝒜(λ,b) runs as follows.

  1. 1.

    The challenger runs pp←Setup(1λ).

  2. 2.

    The adversary 𝒜1(pp) outputs two messages m0,m1∈ℳp⁢p and state st.

  3. 3.

    The challenger samples r←$ℛp⁢p and computes c=Commit(pp,mb;r).

  4. 4.

    The adversary 𝒜2(st,c) outputs a bit b′, which is the output of the experiment.

The hiding advantage of 𝒜 is

AdvΠhide⁢(𝒜,λ):=|Pr⁡[𝖧𝗂𝖽𝖾Π𝒜⁢(λ,0)=1]−Pr⁡[𝖧𝗂𝖽𝖾Π𝒜⁢(λ,1)=1]|.

The scheme is computationally hiding if the advantage is negligible (§1.2) for every PPT 𝒜; statistically hiding if it is negligible even for computationally unbounded 𝒜; and perfectly hiding if it is exactly 0 for every adversary and every λ.

Proposition 4.5 (Distributional characterisation of hiding).

A commitment scheme Π is perfectly hiding if and only if for every pp in the support of Setup and every pair m0,m1∈ℳp⁢p, the random variables

Commit⁢(p⁢p,m0;r)andCommit⁢(p⁢p,m1;r),r←$ℛp⁢p,

are identically distributed. It is statistically hiding if the statistical distance (Definition 1.6) between them is negligible. (Only the perfect clause is an equivalence: parameters of negligible Setup probability could exhibit large distance without granting any adversary noticeable advantage.)

Proof.

Fix pp and m0,m1, and write Dm for the distribution of Commit(pp,m;r) over uniform r. By the variational characterisation of statistical distance (Proposition 1.7), Δ(Dm0,Dm1) equals exactly the maximum advantage, over all decision procedures—efficient or not—of telling Dm0 from Dm1. An adversary who outputs the pair (m0,m1) on parameters pp and applies the optimal test therefore achieves hiding advantage Δ(Dm0,Dm1) whenever Setup produces pp; conversely no adversary can exceed the expectation of this quantity over pp. Advantage exactly 0 for all adversaries is thus equivalent to Δ=0—identical distributions—for every attainable pp and every pair, and negligible statistical distance yields negligible advantage for unbounded adversaries. This agreement of the game formulation with the distance formulation is the reason statistical hiding was defined through the unbounded-adversary game. □

Definition 4.6 (Binding game and binding).

For a commitment scheme Π and adversary 𝒜, the game 𝖡𝗂𝗇𝖽Π𝒜(λ) runs as follows.

  1. 1.

    The challenger runs pp←Setup(1λ).

  2. 2.

    The adversary 𝒜(pp) outputs a commitment c and two openings (m0,r0) and (m1,r1).

  3. 3.

    The game outputs 1 iff m0≠m1 and Open(pp,c,m0,r0)=Open(pp,c,m1,r1)=1.

The binding advantage of 𝒜 is

AdvΠbind⁢(𝒜,λ):=Pr⁡[𝖡𝗂𝗇𝖽Π𝒜⁢(λ)=1],

a search game in the sense of Definition 1.15. The scheme is computationally, statistically, or perfectly binding according as the advantage is negligible for every PPT adversary, negligible for every unbounded adversary, or exactly 0 for every adversary and every λ.

For a canonically opening scheme and fixed pp, two openings collide, that is, win the binding game, precisely when Commit(pp,m0;r0)=Commit(pp,m1;r1) with m0≠m1. Perfect binding is thus equivalent to the map c↦m being well defined on all attainable commitments, the formulation used in Remark 4.9.

Remark 4.7 (The asymmetry of the quantifiers).

Hiding quantifies over what can be extracted from a single commitment that the challenger computes and the adversary only observes. Binding quantifies over what can be manufactured: an ambiguous commitment of the adversary’s choosing, under no obligation to follow Commit. The two properties are in tension: the more commitment values a message can take, the better for hiding and the more opportunities for two messages to share one.

4.4 Incompatibility of perfect hiding and perfect binding

Theorem 4.8 (No scheme is perfectly hiding and perfectly binding).

Let Π be a canonically opening commitment scheme with |ℳp⁢p|≥2. If Π is perfectly hiding, then it is not perfectly binding: indeed, a computationally unbounded adversary wins the binding game with probability 1. Hence no nontrivial commitment scheme is simultaneously perfectly hiding and perfectly binding.

Proof.

Fix any pp in the support of Setup(1λ) and any two distinct messages m0,m1∈ℳp⁢p. For a message m, let

Cm:={Commit⁢(p⁢p,m;r):r∈ℛp⁢p}

be the set of attainable commitments to m, and let Dm be the distribution of Commit(pp,m;r) for uniform r. Perfect hiding makes Dm0 and Dm1 identical (Proposition 4.5); identical distributions have identical supports, so Cm0=Cm1. Pick any c in this common support. By definition of the supports there exist r0,r1∈ℛp⁢p with

Commit⁢(p⁢p,m0;r0)=c=Commit⁢(p⁢p,m1;r1),

and then (c,(m0,r0),(m1,r1)) wins the binding game: both openings are valid by canonical opening, and m0≠m1. The double opening exists for every attainable pp; an unbounded adversary finds it by enumerating ℛp⁢p, so it wins 𝖡𝗂𝗇𝖽 with probability 1, giving AdvΠbind=1≠0. □

Remark 4.9 (The impossibility as a counting fact).

Information-theoretically the theorem counts the bits the commitment carries. Perfect binding forces the map c↦m to be well defined, so c determines m and carries at least log2|ℳ| bits of information about the message. Perfect hiding forces the distribution of c to be independent of m: the commitment carries zero bits. The two demands are compatible only when log2|ℳ|=0, that is, |ℳ|=1. Every nontrivial scheme therefore makes one property perfect (or statistical) and the other computational. The Pedersen commitment of §4.6 is perfectly hiding and computationally binding; the hash-based commitment of §4.5, read in the random oracle model, is computationally binding (from collision resistance) and computationally hiding.

Remark 4.10 (Two regimes, two failure modes).

Which property is left computational determines how the scheme fails if its assumption is broken. If binding is only computational, an adversary with enough power—one able to compute discrete logarithms, say—could retroactively change a committed value, and the soundness of any protocol built on top degrades to a computational assumption. If hiding is only computational, such an adversary could retroactively learn a committed value: privacy degrades the same way, and everlasting secrecy is lost once the assumption is broken, even for commitments published long before. Which failure is worse depends on the application: a ledger that publishes its commitments permanently has reason to care about the second, a protocol whose soundness protects funds in circulation about the first.

4.5 Hash-based commitments

The simplest construction hashes the message together with fresh randomness. It needs two properties from §3: a hash function H:{0,1}∗→{0,1}n is collision resistant (Definition 3.7) if no PPT adversary finds x≠x′ with H(x)=H(x′) except with negligible probability, and preimage resistant (one-way) if, given H(x) for random x of appropriate length, no PPT adversary finds any x′ with H(x′)=H(x) except with negligible probability.

Construction 4.11 (Hash commitment).

Let H:{0,1}∗→{0,1}n be a hash function. The hash commitment has message space ℳ={0,1}∗ and randomness space ℛ={0,1}ℓ for a randomness length ℓ=ℓ(λ) (for example ℓ=2n). Let 𝖾𝗇𝖼(m,r) be an injective, self-delimiting encoding of the pair—for example a canonical length encoding of m, followed by m, followed by the fixed-length string r. Define

Commit⁢(m;r):=H⁢(𝖾𝗇𝖼⁢(m,r)),

opened canonically. There are no nontrivial public parameters beyond the choice of H—the scheme lives in the plain model of Remark 4.3.

Proposition 4.12 (Binding of the hash commitment).

If H is collision resistant, the hash commitment is computationally binding.

Proof.

Suppose 𝒜 wins the binding game: it outputs c with valid openings (m0,r0), (m1,r1) and m0≠m1, so H(𝖾𝗇𝖼(m0,r0))=c=H(𝖾𝗇𝖼(m1,r1)). Injectivity of 𝖾𝗇𝖼 makes the two hash inputs distinct strings—this is the purpose of the self-delimiting encoding; without it, a boundary shift could present distinct pairs as the same string. The adversary has therefore produced an H-collision, and the reduction that runs 𝒜 and outputs the pair (𝖾𝗇𝖼(m0,r0),𝖾𝗇𝖼(m1,r1)) wins the collision game with exactly the binding advantage of 𝒜, in essentially the same time. □

Proposition 4.13 (Hiding of the hash commitment, in the ROM).

Model H as a random oracle (Definition 3.13). For messages of length poly(λ) and randomness length ℓ=ω(logλ), the hash commitment is computationally hiding: an adversary making at most q oracle queries has hiding advantage at most q⋅2−ℓ.

Proof.

The challenge commitment is c=H(𝖾𝗇𝖼(mb,r)) for uniform r∈{0,1}ℓ. Because the oracle’s outputs are independent and uniform, c is a fresh uniform string—carrying no information about b—unless the adversary queries the oracle at the exact point 𝖾𝗇𝖼(mb,r). Before any such query the randomness r is information-theoretically hidden: the adversary’s view is independent of it. Each of the q queries therefore hits that point with probability at most 2−ℓ, and the union bound (Math Guide, §“The union bound and a birthday calculation”) caps the probability of any hit by q⋅2−ℓ. Conditioned on no hit, the adversary’s view is identically distributed in the two worlds b=0 and b=1, so the advantage is at most q⋅2−ℓ, negligible for ℓ=ω(logλ) and polynomial q. □

Remark 4.14 (Why the randomness is essential).

The deterministic commitment c=H(m) fails hiding for every low-entropy message space: to distinguish a commitment to m0 from one to m1, the adversary hashes its two candidates and compares. Neither collision resistance nor one-wayness prevents this, since the attack inverts nothing. The salt r contributes ℓ uniformly random bits, so the hash input is unpredictable even when the message is one of two known values. Deterministic encryption of low-entropy plaintexts fails in the same way, with the same remedy.

Remark 4.15 (Strength profile).

The hash commitment is transparent: it has no parameters and no algebraic structure that a subverted setup could exploit. It is plausibly post-quantum: generic quantum collision finding takes Θ(2n/3) queries against an n-bit hash (Remark 2.31), so increasing the output length compensates for the loss. Its weakness is opacity: the commitment is an unstructured bit string, so no algebraic relation on commitments reflects any relation on the committed values; the sum of two hash commitments is not a commitment to the sum of the messages. The Pedersen construction removes this defect at the price of resting on discrete log.

4.6 The Pedersen commitment

The Pedersen commitment works in a prime-order group rather than on bit strings. Let 𝔾 be a cyclic group of prime order q, written additively: for a point P∈𝔾 and scalar a∈𝔽q, the scalar multiple is [a]P, with [0]P=𝒪 the identity, and a↦[a]P is a group homomorphism 𝔽q→𝔾. Concretely, 𝔾 is the group of 𝔽p-points of a prime-order elliptic curve (Math Guide, §“The group structure of E(𝔽p)”), and in this volume the Pallas curve of §2.6; the constructions use only that 𝔾 is isomorphic to 𝔽q as a group and that discrete logarithms in 𝔾 are hard. Formally, a group generator 𝒢 on input 1λ outputs (𝔾,q,G) with q a Θ(λ)-bit prime and G a generator, and the DLog assumption for 𝒢 states that no PPT adversary, given (𝔾,q,G,[a]G) for uniform a←$𝔽q, outputs a except with negligible probability—Definition 2.2, transcribed additively as in §2.6.

Construction 4.16 (Pedersen commitment).

The algorithm Setup(1λ) runs (𝔾,q,G)←𝒢(1λ), samples s←$𝔽q×, sets H:=[s]G, outputs pp=(𝔾,q,G,H), and discards s. The message and randomness spaces are ℳ=ℛ=𝔽q, and

Commit⁢(p⁢p,m;r):=[m]⁢G+[r]⁢H,

opened canonically.

The parameters are two generators G and H whose relative discrete logarithm s=logGH is unknown to all parties, the committer included. Knowledge of s breaks binding (Remark 4.19); perfect hiding holds whether or not s is known. In deployment H is hashed to the curve (Construction 3.24), so nobody ever holds s and the setup is transparent (Remark 4.3).

Theorem 4.17 (Perfect hiding).

The Pedersen commitment is perfectly hiding.

Proof.

Fix any attainable pp=(𝔾,q,G,H); since s∈𝔽q×, the point H is not 𝒪. Because 𝔾 has prime order, the nonzero H generates 𝔾, so r↦[r]H is a bijection 𝔽q→𝔾. For uniform r, therefore, [r]H is uniform on 𝔾—and so is its translate [m]G+[r]H, for every message m: adding the fixed element [m]G permutes the group and leaves the uniform distribution invariant. The commitment distribution is uniform on 𝔾 regardless of m, so for any m0,m1 the two distributions coincide exactly, and every adversary’s advantage is 0 by Proposition 4.5. □

Theorem 4.18 (Computational binding under DLog).

If the DLog assumption holds for 𝒢, the Pedersen commitment is computationally binding. Concretely, from any adversary 𝒜 that wins the binding game with probability ε one constructs ℬ computing discrete logarithms with probability (1−1/q)ε≥ε−1/q, in essentially the same running time.

Proof.

The algebraic relation comes first. A double opening gives [m0]G+[r0]H=[m1]G+[r1]H with m0≠m1, so

[m0−m1]⁢G=[r1−r0]⁢H.

The case r1=r0 is impossible: it would force [m0−m1]G=𝒪, and since G has order q this means m0≡m1(modq), contradicting m0≠m1 in 𝔽q. With r1−r0 invertible modulo the prime q, the relation solves for the hidden discrete logarithm:

s=logG⁡H=(m0−m1)⁢(r1−r0)−1modq.

A double opening therefore determines the discrete log of H.

The reduction is as follows. On a DLog challenge (𝔾,q,G,Q), the algorithm ℬ sets H:=Q, passes pp=(𝔾,q,G,Q) to 𝒜, and, when 𝒜 returns a double opening, outputs (m0−m1)(r1−r0)−1modq=logGQ. One difference of distributions must be accounted for: in the real scheme H=[s]G with s←$𝔽q×, so H is uniform on 𝔾∖{𝒪}, whereas the challenge Q=[a]G has a uniform on all of 𝔽q, so Q is uniform on all of 𝔾. The two distributions differ only on the event Q=𝒪, of probability 1/q—their statistical distance is exactly 1/q—and on that event 𝒜 cannot win in any case (with H=𝒪 the relation above forces m0=m1). Conditioned on Q≠𝒪, the simulation is perfect, so

Advdlog⁢(ℬ)=(1−1q)⁢AdvΠbind⁢(𝒜)≥ε−1q,

and ℬ’s overhead over 𝒜 is a constant number of field operations. □

Remark 4.19 (Equivocation with the trapdoor).

Any party who knows s=logGH can open a Pedersen commitment to any message. Given c=[m]G+[r]H and a target m′, set

r′:=r+(m−m′)⁢s−1modq;

then [m′]G+[r′]H=[m′]G+[r]H+[(m−m′)]G=c. This trapdoor makes discarding s in Setup mandatory (Remark 4.3), and zero-knowledge simulators use the equivocation to open commitments consistently with a transcript produced out of order.

Theorem 4.20 (Additive homomorphism).

For all m0,m1,r0,r1∈𝔽q,

Commit⁢(m0;r0)+Commit⁢(m1;r1)=Commit⁢(m0+m1;r0+r1),

and more generally, for all scalars α,β∈𝔽q,

[α]⁢Commit⁢(m0;r0)+[β]⁢Commit⁢(m1;r1)=Commit⁢(α⁢m0+β⁢m1;α⁢r0+β⁢r1).
Proof.

Expand and regroup, using commutativity of + in 𝔾, the identity [a]P+[b]P=[a+b]P, and the linearity [α]([m]G+[r]H)=[αm]G+[αr]H of scalar multiplication:

[α]⁢([m0]⁢G+[r0]⁢H)+[β]⁢([m1]⁢G+[r1]⁢H) =[α⁢m0]⁢G+[β⁢m1]⁢G+[α⁢r0]⁢H+[β⁢r1]⁢H
=[α⁢m0+β⁢m1]⁢G+[α⁢r0+β⁢r1]⁢H.∎
Remark 4.21 (Value balancing: the homomorphism deployed).

Zcash uses the homomorphism for value balancing. Each transaction value vi is committed as Ci=[vi]G+[ri]H; a transaction balances iff the sum of its input values equals the sum of its output values. By Theorem 4.20, the verifier can check this without learning any vi: the value components cancel in ∑Cin−∑Cout precisely when the value sums agree modulo the group order q, in which case the difference equals [r]H for the net randomness r—a commitment to 0. Cancellation alone certifies balance only modulo q, and the deployed protocol closes the gap with range checks carried inside the proofs: the values of the notes (the shielded value records) spent and created by each Action (Orchard’s combined spend-and-output unit) are proved to lie in {0,…,264−1} (the Action statement, protocol specification § 4.18.4), the committed net value is the difference of two such values, and the number of summands is bounded, so the sums cannot wrap (§ 4.14). The prover does not reveal r; it proves knowledge of r by using [r]H as the verification key of a signature over the transaction—the binding signature, treated with the completed balance argument in §8.9. In deployed Orchard the instantiation is 𝖵𝖺𝗅𝗎𝖾𝖢𝗈𝗆𝗆𝗂𝗍(v;𝗋𝖼𝗏)=[v]V+[𝗋𝖼𝗏]R with hashed-to-curve generators V,R (protocol specification § 5.4.8.3); each Action publishes a commitment to its net value change, and the verifier folds the published commitments with a commitment to the transparent value balance to obtain the binding verification key. The homomorphism turns an arithmetic relation on hidden values into a group equation on public commitments, a pattern used throughout the rest of the volume.

Example 4.22 (Value balance and a wrap-around counterfeit in a group of order 1019).

We run the balance check of Remark 4.21 in a group small enough to follow by hand. Take the primes q=1019 and p=2q+1=2039. The group 𝔽p× is cyclic of order 2q (Math Guide, §“Cyclicity of the multiplicative group”), so it has exactly one subgroup 𝔾 of the prime order q (Math Guide, §“Cyclic groups”): the nonzero squares modulo p (Math Guide, §“Quadratic residues and the Euler criterion”). We write 𝔾 multiplicatively, as in §2: the multiple [a]P becomes the power Pa, and the group operation is multiplication modulo p. The squares g=4 and h=9 differ from 1 and so generate 𝔾, and Construction 4.16 becomes

C⁢(v;r):=gv⁢hrmodp.

No discrete logarithm in 𝔾 is hard: trying the q exponents in turn gives loggh=515. The example therefore shows the algebra of balance, not its security, which at deployed size rests on the order of Pallas, close to 2254 (§2.6).

A transaction spends a note of value v1=200 and creates two, of values v2=150 and v3=45; the remaining b=5 is its transparent value balance, so that v1=v2+v3+b. With the trapdoors ri below, the three commitments are

note value vi trapdoor ri Ci=C⁢(vi;ri)
spent 200 731 566
created 150 286 451
created 45 517 139

Cancellation. The verifier divides the spent commitment by the created ones and by the balance under g, gb=1024:

C1⁢(C2⁢C3)−1⁢g−b=1441=h947,947≡r1−r2−r3=−72(modq).

The exponents of g cancel, 200−150−45−5=0, and the residual is a commitment to zero. The difference r1−r2−r3 of the trapdoors is its discrete logarithm to the base h. The author of the transaction, who drew the three trapdoors, knows this logarithm without computing one; the binding signature of §8.9 proves that knowledge without revealing it.

Wrap-around. Since gq=1, the exponent of g matters only modulo q, and a value congruent to zero modulo q commits like zero: C(q;r)=hr=C(0;r) for every r. A prover who raises the change from 45 to 45+q=1064 and keeps its trapdoor publishes the same commitment, C(1064;517)=139, and the verifier obtains the same residual 1441=h947. Cancellation, and a binding signature under it, accept a transaction that creates 150+1064+5=1219 from a spent 200, minting q=1019.

Range. Requiring each of v1,v2,v3,b to lie in {0,…,28−1} rejects 1064, and every other wrap: the integer D=v1−v2−v3−b then satisfies |D|≤3⋅255=765<q, so D≡0(modq) forces D=0. The deployed protocol argues in the same way, with 64-bit values against an order near 2254.

Prime order. Both theorems above use that q is prime: the hiding proof of Theorem 4.17 needs h≠1 to generate the group, and the binding reduction of Theorem 4.18 inverts r1−r0 modulo q. In the whole group 𝔽p×, of order 2q, the square h generates only 𝔾, and hiding fails. With the generator 7 of 𝔽p× in place of g and the square h kept, Euler’s criterion gives c(p−1)/2=(−1)v for c=7vhr, so every commitment discloses the parity of its value. In a group of smooth order binding fails as well: Pohlig–Hellman (Theorem 2.19) computes loggh at a cost set by the largest prime factor of the order, and the committer then equivocates by Remark 4.19.

4.7 Pedersen vector commitments

A single group element can commit to a vector of scalars rather than a single scalar.

Construction 4.23 (Pedersen vector commitment).

On input 1λ and a length n=poly(λ), Setup outputs (𝔾,q) together with generators G1,…,Gn,H←$𝔾∖{𝒪}, sampled so that no nontrivial discrete-log relation among them is known to any party—in practice each generator is derived from a public seed by hashing into the curve, rejecting the identity if it occurs, a nothing-up-my-sleeve procedure (Construction 3.24) that makes the setup transparent. The message space is 𝔽qn, the randomness space 𝔽q, and for 𝐦=(m1,…,mn),

Commit⁢(p⁢p,𝐦;r):=∑i=1n[mi]⁢Gi+[r]⁢H=⟨𝐦,𝐆⟩+[r]⁢H,

where ⟨𝐦,𝐆⟩:=∑i[mi]Gi is the multiscalar (mixed) inner product of the message vector with the generator vector 𝐆=(G1,…,Gn). Opening is canonical.

Theorem 4.24 (Properties of the vector commitment).

The Pedersen vector commitment is perfectly hiding, and computationally binding under the DLog assumption in 𝔾.

Proof.

Hiding. Exactly as in Theorem 4.17: for uniform r the blinding term [r]H is uniform on 𝔾, so the commitment is uniform on 𝔾 regardless of the message vector.

Binding. A double opening with 𝐦≠𝐦′ gives ⟨𝐦,𝐆⟩+[r]H=⟨𝐦′,𝐆⟩+[r′]H, that is, a nontrivial discrete-log relation

∑i=1n[mi−m′i]⁢Gi+[r−r′]⁢H=𝒪

with not all coefficients zero. The reduction ℬ must extract a single logarithm from a relation among n+1 generators, and it does so by embedding its challenge in every generator. On challenge Q=[s]G, it samples ui,wi←$𝔽q for each i and uH,wH←$𝔽q, sets

Gi:=[ui]⁢G+[wi]⁢Q,H:=[uH]⁢G+[wH]⁢Q,

and resamples any pair whose generator lands on 𝒪. Each result is uniform on 𝔾∖{𝒪}—the [ui]G term alone makes the pre-rejection point uniform on 𝔾—so the simulated parameters follow the real distribution. Moreover, the parameters reveal nothing about the w-coordinates: for every candidate value of wi there is exactly one ui consistent with the observed Gi, so conditioned on the adversary’s entire view the wi and wH remain independent and uniform. Write the recovered relation as ∑i[ai]Gi+[aH]H=𝒪 with coefficient vector (a1,…,an,aH)≠𝟎. Substituting the embeddings and collecting the G- and Q-components gives

c0+c1⁢s≡0(modq),c0=∑iai⁢ui+aH⁢uH,c1=∑iai⁢wi+aH⁢wH.

Since the coefficient vector is nonzero and the w-coordinates are uniform and independent of it, c1 is uniform on 𝔽q, hence nonzero with probability 1−1/q; in that case s=−c0c1−1modq, and ℬ outputs the challenge logarithm. Altogether Advdlog(ℬ)≥(1−1/q)Advbind(𝒜). □

Remark 4.25 (Compression and the cardinality trade-off).

The vector commitment is compressing: n field elements (plus the randomness) map to a single group element, exponentially shorter than the message for large n. Compression is incompatible with statistical binding for a counting reason: there are qn message vectors and only q commitment values, so many colliding openings exist. Binding is therefore only computational—an unbounded adversary finds a colliding opening by solving the underlying discrete-log relation—and the trade-off of Theorem 4.8 appears at the level of cardinalities: a compressing commitment cannot determine its message, so perfect hiding costs it nothing further.

Remark 4.26 (Linearity of the vector commitment).

The vector commitment remains additively homomorphic in both message and randomness, componentwise: Commit(𝐦;r)+Commit(𝐦′;r′)=Commit(𝐦+𝐦′;r+r′), by the same regrouping as Theorem 4.20. This linearity, applied to a committed vector against public coefficient vectors, underlies the inner-product arguments of §4.9, which prove statements about ⟨𝐦,𝐛⟩ for public 𝐛 while revealing only a single committed group element.

4.8 Sinsemilla: an algebraic hash-based commitment

Between the opaque hash commitment of §4.5 and the linear Pedersen commitment lie the algebraic hash functions: collision-resistant hashes whose internal operations are elliptic-curve group operations. A zero-knowledge circuit verifying a hash pays for every internal operation, and curve additions in the field over which the proof system works are cheap, while collision resistance still reduces to the discrete logarithm. Sinsemilla, deployed in Zcash Orchard, is a Pedersen-style hash of this kind over a sequence of message chunks, constructed below from the Pedersen hash.

Construction 4.27 (Pedersen hash).

Split the message M into k chunks m1,…,mk, each interpreted as a scalar in a bounded range, and fix k independent generators P1,…,Pk∈𝔾 with unknown mutual discrete logarithms. Define

𝖯𝖾𝖽𝖾𝗋𝗌𝖾𝗇𝖧𝖺𝗌𝗁⁢(M):=∑j=1k[mj]⁢Pj∈𝔾.

This is the unblinded Pedersen vector commitment map used as a hash. The output is a group element; composing with a fixed encoding of group elements as bit strings yields an ordinary hash.

Proposition 4.28 (Collision resistance of the Pedersen hash).

Suppose no efficient algorithm finds a nontrivial relation ∑j[aj]Pj=𝒪 with not all aj=0 and each |aj| within the allowed chunk range—hardness that follows from DLog when the Pj are independent uniform generators. Then 𝖯𝖾𝖽𝖾𝗋𝗌𝖾𝗇𝖧𝖺𝗌𝗁 is collision resistant.

Proof.

A collision M≠M′, with chunk decompositions (mj) and (m′j), gives ∑j[mj−m′j]Pj=𝒪 with some coefficient mj−m′j≠0—a nontrivial relation with coefficients in the allowed range. The reduction from relation-finding to DLog is the every-generator embedding of Theorem 4.24: set each Pj=[uj]G+[wj]Q for the challenge Q, and read the unknown logarithm off the recovered relation. □

The Pedersen hash needs one independent generator per chunk, so its generator table grows linearly with the maximum message length. Sinsemilla iterates a two-operand step over a small fixed generator table shared by all chunk positions, and keeps the discrete-log collision reduction.

Construction 4.29 (Sinsemilla hash).

Split the message M into pieces m1,…,mk, each of fixed width w≤32 bits, and identify a piece v∈{0,1}w with its integer value, bits read little-endian (the specification’s 𝖫𝖤𝖡𝖲𝟤𝖨𝖯). The public parameters are a base point Q∈𝔾 and a table S:{0,1}w→𝔾 assigning to each possible piece value its own generator, both obtained by hashing to the curve. Write 𝖦𝗋𝗈𝗎𝗉𝖧𝖺𝗌𝗁(D,M) for the hash-to-curve pipeline of Construction 3.22 applied to the byte string M under the domain-separation tag built from the byte string D—for Pallas the RFC 9380 suite tag D∥"-pallas_XMD:BLAKE2b_SSWU_RO_" of §3.6 (protocol specification § 5.4.9.8)—and write LE32(j) for the four-byte little-endian encoding of an integer 0≤j<232. The table is

S⁢(v):=𝖦𝗋𝗈𝗎𝗉𝖧𝖺𝗌𝗁⁢("z.cash:SinsemillaS",LE32⁢(v)),v∈{0,1}w,

with 2w entries shared by every instance, and the base point is personalised (§3.5) to the enclosing use—a byte string D naming it, such as a note-commitment or Merkle-hash domain—by taking that string as the message:

Q:=𝖦𝗋𝗈𝗎𝗉𝖧𝖺𝗌𝗁⁢("z.cash:SinsemillaQ",D).

Both derivations are nothing-up-my-sleeve (Construction 3.24), so no party knows any discrete-log relation among {S⁢(v)}v∪{Q} (Remark 3.25). The deployed instantiation takes w=10 (the specification’s k) over Pallas, derives Q and the table as above with LE32 as the index encoding, and loads the table into the circuit as a lookup (protocol specification § 5.4.1.9). The hash iterates over the pieces with a running accumulator Acc∈𝔾:

Acc0:=Q,Accj:=Accj−1+(Accj−1+S⁢(mj))=[2]⁢Accj−1+S⁢(mj),

and outputs the point 𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁𝖳𝗈𝖯𝗈𝗂𝗇𝗍(M):=Acck. The step costs two incomplete curve additions—first Accj−1+S(mj), then the result plus Accj−1; no doubling is ever performed, and the addition formula is undefined when its operands are equal or are mutual negatives (Math Guide, §“Elliptic curves”)—and this pair of additions is the operation the circuit verifies in few constraints. Unrolling the recurrence gives the closed form

𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁𝖳𝗈𝖯𝗈𝗂𝗇𝗍⁢(M)=∑j=1k[2k−j]⁢S⁢(mj)+[2k]⁢Q:

the integer coefficients are powers of two determined by position alone, and the message enters only through which generator S(mj) each piece selects.

Proposition 4.30 (Collision resistance of Sinsemilla).

Model the table entries S(v) and the base point Q as independent uniform generators (the nothing-up-my-sleeve hash-to-curve derivation covers Q as well as the table). Then any collision in 𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁𝖳𝗈𝖯𝗈𝗂𝗇𝗍, on inputs for which its incomplete additions are defined, yields a nontrivial discrete-log relation among {S⁢(v)}v∪{Q}, and any input on which an incomplete addition is undefined yields one directly; either way a discrete logarithm follows via the every-generator embedding of Theorem 4.24 extended to Q. The point hash is thus collision resistant under the DLog assumption in 𝔾, the exceptional cases of incomplete addition covered by the same reduction rather than excluded.

Proof sketch.

Let M≠M′ collide. Suppose first that they have the same piece count k. Subtracting the unrolled forms cancels the [2k]Q terms and leaves

∑j=1k[2k−j]⁢(S⁢(mj)−S⁢(m′j))=𝒪.

Regroup over the distinct table generators: for each value v∈{0,1}w, the net coefficient on S(v) is

cv=∑j:mj=v2k−j−∑j:m′j=v2k−j,

and the relation reads ∑v[cv]S(v)=𝒪. Each cv is a difference of two subset-sums of the distinct powers 2k−1,…,20, hence an integer with |cv|<2k. For admissible message lengths—those with 2k below the group order q, a finite design-time check—such a coefficient vanishes modulo q only if it vanishes as an integer; and cv=0 forces, by uniqueness of binary expansions, the two subset-sums to be equal as sets of powers, that is, the positions carrying value v in M and in M′ to coincide. Coincidence for every v would force M=M′; since M≠M′, some cv≠0 and the relation is nontrivial.

If instead the piece counts differ, say k>k′, the Q-constants do not cancel: the relation acquires the coefficient 2k−2k′ on Q, nonzero and below the group order for admissible lengths, so the relation is again nontrivial. In either case, embedding a DLog challenge in every table generator and in Q recovers the challenge logarithm exactly as in Proposition 4.28.

It remains to treat the exceptional cases. An incomplete addition is undefined only when its operands are equal or are mutual negatives, so an input reaching one presents a coincidence [α]Accj−1+S(mj)=𝒪 with α∈{−1,1,2}. Substituting the unrolled form of Accj−1 makes this an explicit relation among Q and the table generators, with coefficient α 2j−1≠0 on Q and all magnitudes at most 2k—below the group order for admissible lengths. An input that merely triggers an exceptional case therefore yields a nontrivial relation directly, and the same embedding extracts the challenge logarithm from it; the protocol specification proves exactly this for the deployed instantiation (§ 5.4.1.9). □

The deployed hash differs from the point hash in two ways. First, the deployed 𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁 applies the Pallas coordinate extractor to 𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁𝖳𝗈𝖯𝗈𝗂𝗇𝗍(M), returning its x-coordinate. Collision resistance survives the extraction: equal x-coordinates mean the two points are equal or negatives of one another, and either signed equality yields the same kind of nontrivial generator relation as in the proof above. Second, the message bits are zero-padded to a multiple of the piece width before chunking, so two bit strings of different lengths within the same final piece present identical piece sequences, and the deployed hash claims collision resistance only between inputs of a fixed length for a given personalisation, exactly as the protocol specification § 5.4.1.9 requires (“between inputs of fixed length, for a given personalization input”). Each personalisation domain hashes inputs of a single length, as the Merkle-tree hash 𝖬𝖾𝗋𝗄𝗅𝖾𝖢𝖱𝖧 of §10 illustrates. The variable-length argument in the proof above applies to the piece-aligned point presentation, where the piece sequence is the message.

The commitment is obtained from the hash by adding the Pedersen blinding term unchanged.

Construction 4.31 (SinsemillaCommit).

Fix one further independent generator H′, hashed to the curve with its own domain string, so that no discrete-log relation between H′ and {S⁢(v)}v∪{Q} is known. Define, for r←$𝔽q,

𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖢𝗈𝗆𝗆𝗂𝗍⁢(m;r):=𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁𝖳𝗈𝖯𝗈𝗂𝗇𝗍⁢(m)+[r]⁢H′.

Hiding is inherited unchanged from Pedersen: by the argument of Theorem 4.17, [r]H′ is uniform on 𝔾 for uniform r, so the commitment distribution is independent of m, and the scheme is perfectly hiding. Binding rests on discrete log: two valid openings to distinct messages yield either a 𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖧𝖺𝗌𝗁𝖳𝗈𝖯𝗈𝗂𝗇𝗍 collision—excluded by Proposition 4.30—or a nontrivial discrete-log relation between H′ and the hash generators.

Orchard’s note commitment 𝖭𝗈𝗍𝖾𝖢𝗈𝗆𝗆𝗂𝗍 instantiates this map (protocol specification § 5.4.8.4). Its key commitment 𝖢𝗈𝗆𝗆𝗂𝗍𝖨𝗏𝗄 composes the same map with x-coordinate extraction—the specification’s 𝖲𝗂𝗇𝗌𝖾𝗆𝗂𝗅𝗅𝖺𝖲𝗁𝗈𝗋𝗍𝖢𝗈𝗆𝗆𝗂𝗍—and returns a base-field element.

Remark 4.32 (In-circuit cost of Sinsemilla).

Outside a circuit ordinary hashes are faster than Sinsemilla; its advantage is verification cost inside one. In a SNARK (§9) the prover re-expresses every computational step as polynomial constraints; a bit-oriented hash such as SHA-256, built from Boolean operations and modular additions foreign to the proof field, costs tens of thousands of constraints per evaluation, whereas Sinsemilla’s per-piece cost is a handful of curve operations in the field over which the proof system works. Orchard uses it for note commitments and Merkle trees: it is cheap to prove and rests on the same discrete-log hardness as the rest of the protocol. A later volume treats the concrete Orchard instantiation: its per-use personalisation strings and the in-circuit handling of incomplete addition.

4.9 Polynomial commitment schemes

A polynomial commitment scheme commits to a polynomial and supports proofs of statements about its values; the succinct argument systems of §9 are built on it.

Definition 4.33 (Polynomial commitment scheme).

Fix a field 𝔽 and a degree bound d. A polynomial commitment scheme (PCS) is a tuple (Setup,Commit,Open,Eval,Verify):

  • •

    The algorithm Setup(1λ,d) outputs public parameters pp supporting degree at most d;

  • •

    the algorithm Commit(pp,f;r) outputs a commitment C to a polynomial f∈𝔽[X]≤d, optionally with hiding randomness r;

  • •

    the algorithm Open(pp,C,f,r) outputs a bit, verifying that C commits to the whole polynomial f;

  • •

    the algorithm Eval(pp,f,r,z), for an evaluation point z∈𝔽, outputs a claimed value y=f(z) together with an evaluation proof π;

  • •

    the algorithm Verify(pp,C,z,y,π) outputs a bit, checking the evaluation proof against the commitment.

Beyond the hiding and binding of the underlying commitment (Definitions 4.4 and 4.6), a PCS must satisfy evaluation binding: no PPT prover can produce a commitment C, a point z, and two accepting proofs for distinct claimed values y≠y′ at z, except with negligible probability. Stronger schemes additionally satisfy extractability (proof of knowledge): from any successful prover one can extract an actual polynomial f of degree at most d consistent with all the evaluations it gets accepted.

Remark 4.34 (Rigidity, and why evaluation binding is separate).

A single short commitment can support queries at arbitrary points because polynomials are rigid: a nonzero polynomial of degree at most d has at most d roots (Math Guide, §“The Schwartz–Zippel lemma”), so two distinct polynomials of degree at most d agree on at most d points. A prover that answers a different value at even a single point behaves as one holding a different polynomial. However, an accepting evaluation proof is not an opening of C, so evaluation binding does not follow from the binding of Commit; each construction below proves it from its own assumption—a strong Diffie–Hellman assumption for KZG, discrete log via a folding extractor for the inner-product scheme. The design problem of a PCS is to make the evaluation proof π short and fast to verify; committing to the coefficient list with an arbitrary commitment scheme does not solve it.

KZG: evaluation in the exponent

The pairing-based scheme of Kate, Zaverucha, and Goldberg achieves constant-size proofs by encoding a secret evaluation point in the parameters.

Construction 4.35 (KZG commitment).

Let 𝔾1,𝔾2,𝔾T be groups of prime order |𝔽|, the first two written additively with generators G∈𝔾1 and G^∈𝔾2, equipped with a non-degenerate bilinear pairing e:𝔾1×𝔾2→𝔾T: an efficiently computable map with e([a]P,[b]Q)=e(P,Q)a⁢b for all P∈𝔾1, Q∈𝔾2, and a,b∈𝔽, and with e(G,G^)≠1. It is the pairing of Example 2.9 with its two arguments drawn from distinct groups. The algorithm Setup samples a secret τ←$𝔽, publishes the structured reference string

p⁢p=([τ0]⁢G,[τ1]⁢G,…,[τd]⁢G,G^,[τ]⁢G^),

and discards τ. The commitment to f=∑i=0daiXi is evaluation in the exponent:

Commit⁢(p⁢p,f):=∑i=0d[ai]⁢([τi]⁢G)=[f⁢(τ)]⁢G,

computable from pp by anyone, without knowledge of τ.

Construction 4.36 (KZG evaluation proof).

To prove f(z)=y, the prover uses the factor theorem: z is a root of f(X)−y, so the quotient

q⁢(X):=f⁢(X)−yX−z∈𝔽⁢[X]≤d−1

is a genuine polynomial precisely because f(z)−y=0. The proof is the commitment to the quotient, π:=[q(τ)]G, computed from the reference string. The verifier checks the single pairing equation

e⁢(C−[y]⁢G,G^)=?e⁢(π,[τ]⁢G^−[z]⁢G^),

which, by bilinearity, is exactly the in-the-exponent form of the polynomial identity f(τ)−y=q(τ)(τ−z).

Proposition 4.37 (KZG evaluation binding, sketched).

Evaluation binding of KZG rests on the d-strong Diffie–Hellman assumption in the bilinear group: given the powers [τi]G, it is infeasible to produce [(τ−z)−1]G for any z of one’s choosing.

Proof idea.

Two accepting proofs π,π′ for distinct values y≠y′ at the same point z satisfy the two pairing equations; subtracting them (in the exponent) gives π−π′=[(y′−y)(τ−z)−1]G, so the forger’s output yields

[(τ−z)−1]⁢G=[(y′−y)−1]⁢(π−π′),

exactly the element the assumption declares infeasible. □

Remark 4.38 (Costs and benefits of KZG).

The KZG scheme provides commitments and evaluation proofs of constant size (one group element each) and constant verification time (two pairings), all independent of the degree d. Its setup is trusted: the secret τ is a global trapdoor. Anyone who learns τ can forge accepting evaluation proofs for false statements—for any commitment C, any point z, and any desired value y, the element π:=[(τ−z)−1](C−[y]G) passes the pairing check, no knowledge of any polynomial required. This is the silent loss of binding under a subverted setup announced in Remark 4.3; evaluation binding survives only if τ is provably destroyed, in practice by a multi-party powers-of-tau ceremony whose trapdoor stays secret as long as at least one participant is honest. The construction also requires pairing-friendly curves, a more constrained and less efficient setting than the ordinary curves of §2.6. Binding is computational either way, resting on the bilinear assumption—consistent with Theorem 4.8.

The inner-product alternative

The transparent alternative commits to the coefficient vector with the Pedersen vector commitment and replaces the pairing check by a recursive argument.

Construction 4.39 (IPA-style polynomial commitment).

Let 𝐆=(G0,…,Gd) and H be transparent generators with unknown mutual discrete logs, derived from a public seed (Construction 4.23). Commit to f=∑i=0daiXi by the Pedersen vector commitment of its coefficient vector 𝐚=(a0,…,ad):

Commit⁢(p⁢p,f;r):=∑i=0d[ai]⁢Gi+[r]⁢H=⟨𝐚,𝐆⟩+[r]⁢H.

The construction uses no pairings and no trusted setup.

Evaluation is an inner product: writing 𝐳=(1,z,z2,…,zd) for the public vector of powers of the query point,

f⁢(z)=∑i=0dai⁢zi=⟨𝐚,𝐳⟩,

so proving an evaluation reduces to proving an inner-product relation about a committed vector against a public vector. The inner-product argument (IPA) proves it recursively: each round folds the two halves of the coefficient vector—and of the generator vector—into vectors of half the dimension by taking a random linear combination dictated by a verifier challenge, sending two group elements per round (the cross-term commitments Lj and Rj) to account for the mixed terms; after log2(d+1) rounds a single scalar remains, and the verifier checks one final equation tying it to the folded commitment and the folded generators.

Proposition 4.40 (Properties of the IPA-based PCS).

The inner-product polynomial commitment has: transparent setup (public-coin parameters, no trapdoor); evaluation proofs of O(logd) group elements; and O(d)-group-operation verification, batchable across proofs. Its binding and evaluation binding reduce to the discrete logarithm assumption in 𝔾.

Proof idea.

Binding of the commitment itself is Theorem 4.24. For evaluation binding and extractability, one shows the folding protocol is tree special-sound: from a suitable tree of accepting transcripts, branching over the verifier’s challenge at each round, an extractor works back up the recursion and computes a coefficient vector 𝐚 consistent with the commitment and the claimed inner product—a notion this sketch uses only informally and §9 defines precisely. Two distinct extracted openings of the same commitment would yield a nontrivial discrete-log relation among 𝐆,H, contradicting DLog by the every-generator embedding. The O(logd) proof size is the halving recursion; the O(d) verification is the final multiscalar multiplication over the unfolded generators. □

Remark 4.41 (KZG versus IPA, and the Halo lineage).

KZG gives constant proof size and constant verification, at the price of a structured trusted setup and pairing-friendly curves; the IPA gives transparent setup over a plain curve and rests on nothing beyond discrete log, at the price of logarithmic proofs and linear-time verification. The Halo 2 proof system deployed in Zcash Orchard builds on the inner-product family to avoid trusted setup, and recovers practical verification cost through batching: the deployed verifier folds the final multiscalar multiplications of many proofs into one shared multiexponentiation—each proof’s deferred check is scaled by a fresh random factor and accumulated, and a single combined check is evaluated once. This amortises group operations across a batch, though per-proof verifier work remains linear in d. The Halo lineage’s accumulation technique extends the same deferral across recursively composed proofs, one proof attesting to another’s deferred check—the capability the Pasta cycle of Remark 2.26 was designed to serve—but deployed Zcash does not use recursion: each Orchard proof is verified (in batch) directly.

Remark 4.42 (Hiding variants).

As stated, the KZG commitment is binding but not hiding: it is a deterministic function of f, so committing twice to the same polynomial is visible, and a low-entropy polynomial can be found by search—the failure of Remark 4.14. That is acceptable when the polynomial encodes only public data. When it encodes secrets, as the witness polynomials of a zero-knowledge proof do, randomness is required: KZG is augmented with a blinding summand [r][γ]G using an extra setup element [γ]G, while the IPA commitment of Construction 4.39 already carries its [r]H and is perfectly hiding by Theorem 4.24. The resulting regime is the perfect-hiding/computational-binding profile of Pedersen (Theorems 4.17 and 4.18), lifted from field elements to polynomials.

From commitments to arguments

A polynomial commitment scheme turns an information-theoretic proof object—a polynomial identity holding over a large field—into a succinct cryptographic argument. The prover commits to its witness polynomials, the verifier challenges at random points, and evaluation proofs show that the committed polynomials satisfy the required identities without revealing them. Soundness comes from Schwartz–Zippel (Math Guide, §“The Schwartz–Zippel lemma”): a nonzero polynomial of low degree is almost surely nonzero at a random point, so an identity that holds at the challenge almost surely holds identically. Binding and succinctness come from the commitment: the prover is bound to its polynomials before seeing the challenge, and the verifier handles only short commitments and proofs. The full compilation, and the precise meaning of “argument of knowledge”, are the subject of §9.

4.10 Secret sharing

Verifiable secret sharing is constructed here because the threshold signatures of a later volume depend on it and no earlier volume provides it. The setting is a prime field 𝔽q—in the sequel the scalar field of the group 𝔾 of §4.6—and the tool is Lagrange interpolation (Math Guide, §“Lagrange interpolation”): a polynomial of degree at most t−1 over 𝔽q is determined by its values at any t distinct points, and any t prescribed values at distinct points are attained by exactly one such polynomial.

Construction 4.43 (Shamir t-of-n secret sharing).

Fix a threshold t and a party count n with 1≤t≤n<q. To share a secret s∈𝔽q, the dealer samples coefficients a1,…,at−1←$𝔽q independently and uniformly and forms

f⁢(X):=s+a1⁢X+a2⁢X2+⋯+at−1⁢Xt−1∈𝔽q⁢[X],f⁢(0)=s,

a polynomial of degree at most t−1 with constant term the secret. Party i∈{1,…,n} receives the share si:=f(i), sent privately; the identifiers 1,…,n are distinct nonzero elements of 𝔽q because n<q. Reconstruction from the shares of any set I of t parties is interpolation at 0:

s=f⁢(0)=∑i∈IλI,i⁢si,λI,i:=∏j∈I,j≠ijj−i,

where λI,i=ℓi(0) is the Lagrange basis polynomial for the nodes I evaluated at 0, computable from the identifiers alone.

Correctness of reconstruction is the interpolation theorem: the t points (i,si)i∈I determine a unique polynomial of degree at most t−1, which is f, and the Lagrange formula f(X)=∑i∈Isiℓi(X) evaluated at X=0 gives the displayed sum. The coalition may be chosen after the shares are dealt, since the weights depend only on I.

Theorem 4.44 (Perfect secrecy below the threshold).

Let I be any set of at most t−1 identifiers. For every secret s∈𝔽q, the shares (si)i∈I of Construction 4.43 are jointly uniform on 𝔽q|I|. In particular their distribution does not depend on s: fewer than t shares are independent of the secret, and an adversary of unbounded power holding them has advantage exactly 0 at telling any two candidate secrets apart.

Proof.

It suffices to treat |I|=t−1, since fewer shares are a projection of these. Fix s and I, and consider the map

Σs:𝔽qt−1→𝔽qt−1,(a1,…,at−1)↦(f⁢(i))i∈I,

from the dealer’s coefficient vector to the coalition’s shares. It is injective: two coefficient vectors with the same shares give two polynomials of degree at most t−1 that agree at the t distinct points 0 (where both equal s) and I, hence are equal by uniqueness of interpolation, so the coefficient vectors coincide. It is surjective: for any target (yi)i∈I, Lagrange interpolation through the t points (0,s) and (i,yi)i∈I produces a polynomial of degree at most t−1 with constant term s, whose remaining coefficients are a preimage. So Σs is a bijection—for every s—and it carries the uniform distribution on coefficient vectors to the uniform distribution on 𝔽qt−1. The share vector is therefore uniform whatever the secret, and for any s0≠s1 the two share distributions coincide exactly; by the variational characterisation of statistical distance (Proposition 1.7) no procedure, efficient or not, distinguishes them. □

The theorem is the perfect hiding of a commitment, in the form of Proposition 4.5. Shamir sharing is not binding: a dishonest dealer can distribute values that lie on no common polynomial of degree at most t−1, so that different coalitions of t parties reconstruct different “secrets”, and a party receiving a share cannot detect this. Verifiable secret sharing has the dealer commit to the polynomial.

Construction 4.45 (Feldman verifiable secret sharing).

Let (𝔾,q,G) be as in §4.6, so that 𝔽q is the scalar field of 𝔾. The dealer shares s as in Construction 4.43, with f(X)=∑k=0t−1akXk and a0=s, and additionally broadcasts the coefficient commitments

Φk:=[ak]⁢G∈𝔾,k=0,…,t−1,

the coefficients in the exponent. Party i, on receiving its private share si, accepts it iff

[si]⁢G=?∑k=0t−1[ik]⁢Φk.

An honest share passes: since a↦[a]G is a homomorphism 𝔽q→𝔾, ∑k[ik]Φk=∑k[akik]G=[f(i)]G.

Proposition 4.46 (What the Feldman check certifies).

Because G generates the prime-order group 𝔾, the map a↦[a]G is a bijection 𝔽q→𝔾, so the broadcast vector (Φ0,…,Φt−1)—however the dealer chose it—determines a unique polynomial f∗(X):=∑kak∗Xk with ak∗=logGΦk, of degree at most t−1. Party i’s check passes iff si=f∗(i). Consequently every coalition of t parties holding accepted shares reconstructs the same polynomial f∗ and the same secret s∗=f∗(0)=logGΦ0, and a party handed an inconsistent share detects it alone and with certainty. The check certifies nothing about the value of s∗, which the dealer chooses freely.

Proof.

Both claims are injectivity of a↦[a]G. The right-hand side of the check equals [f∗(i)]G by the homomorphism, so the equation [si]G=[f∗(i)]G holds iff si=f∗(i). Accepted shares are thus evaluations of the one polynomial f∗, and t of them interpolate to it by uniqueness. □

The vector (Φk)k is a perfectly binding commitment to the polynomial f—the coefficient list committed entry by entry under the bijection a↦[a]G—and the share check is an evaluation check against it, verifiable by anyone because it is linear in the coefficients. Perfect binding comes at the expense of hiding, as Theorem 4.8 requires.

Remark 4.47 (Leakage of Feldman sharing).

Feldman sharing publishes Φ0=[s]G. Secrecy below the threshold is no longer perfect: from the broadcast alone an unbounded adversary computes s=logGΦ0. For an efficient coalition of t−1 parties the leak is exactly [s]G and nothing more: its entire view—shares and broadcast—is computable from [s]G and t−1 uniformly random field elements, because the shares are uniform by Theorem 4.44 and the Φk are then determined by interpolating in the exponent through (0,[s]G) and the points (i,[si]G). Recovering s from that view is the discrete-logarithm problem (Definition 2.2). The leak is acceptable exactly when s is itself a discrete-logarithm secret key whose public key [s]G is published regardless; then Φ0 is the public key and nothing new is revealed. When the secret must stay perfectly hidden, Pedersen verifiable secret sharing replaces each Φk by the Pedersen commitment [ak]G+[bk]H of Construction 4.16, restoring perfect hiding at the price of computational binding; this volume neither uses nor constructs it. Threshold signing uses the Feldman construction: each signer holds a Shamir share of a signing key, the coefficient commitments broadcast during key generation are Feldman’s, and the Lagrange weights λI,i recombine per-signer contributions into a single signature.