II Crypto Guide: Cryptographic primitives from scratch 3 Hash functions and the random oracle model 5 Pseudorandom functions, block ciphers, and format-preserving encryption

4 Commitment schemes

Two adversaries stalk this section, one on each side of a sealed envelope. Before the envelope is opened, the adversary is the peeker: the receiver, who holds the sealed commitment and tries to distinguish which of two candidate messages it contains—to read the bid before the auction closes, the vote before the tally. After the envelope has been delivered, the adversary is the equivocator: the sender, who tries to open the same commitment to a message other than the one sealed inside—to change the bid once the rival’s is public. A commitment scheme is the cryptographic sealed, tamper-evident envelope that defeats both: once delivered, the sender can no longer alter the message (binding), yet the recipient cannot read it until it is unsealed (hiding).

The primitive is the natural next step after hashing: the two constructions at the heart of this section, Pedersen and Sinsemilla, need nothing beyond the discrete-logarithm hardness of §2 and the nothing-up-my-sleeve generators that §3 showed how to derive, and nearly everything built later consumes them. Classical applications set the scene: coin-flipping over a telephone (each party commits to a bit before either reveals), zero-knowledge proofs (the prover commits to its secrets and proves statements about the sealed values), and verifiable secret sharing. Centrally for this volume, the polynomial commitments of §4.9 are the cryptographic engine of modern succinct argument systems, including the one deployed 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 the precise sense defined here.

The plan of the section follows the two adversaries. We first fix the syntax of a commitment scheme and the three models of who may be trusted to set it up. We then define hiding and binding as games in the tradition of §1.4, each in three quantitative flavours—perfect, statistical, computational—and prove that the two perfections are jointly unattainable: every scheme must choose which adversary to defeat unconditionally. The constructions that follow are ordered by increasing algebraic richness: hash-based commitments (opaque but transparent and plausibly post-quantum), the Pedersen commitment and its vector variant (perfectly hiding, computationally binding under discrete log, and—decisively—linear), Sinsemilla (a commitment whose internal operations are curve operations, built to be cheap inside a proof), then polynomial commitment schemes, contrasting the pairing-based KZG family with the inner-product family that Zcash deploys, and the bridge from commitments to arguments. A closing subsection returns to the classical application named above—secret sharing—and builds its verifiable form from coefficient commitments, for the threshold signatures of the FROST Guide.

4.1 The sealed envelope

The envelope metaphor repays being taken slowly, because each of its physical properties has an exact formal counterpart. The sender writes a message on a card, seals it in the envelope, and hands the envelope over. From that moment the receiver possesses the commitment: whatever the message was, it is now fixed—the sender cannot swap the card, because the envelope is in the receiver’s hands and any tampering would show. Yet the receiver learns nothing: the envelope is opaque. Later, at a time of the protocol’s choosing, the sender opens the envelope—in the formalism, transmits the message together with the randomness used to seal it—and the receiver checks that the revealed message is consistent with the envelope received earlier.

The two guarantees are directed at different parties and different times. Hiding protects the sender against a curious receiver during the window between commit and reveal; binding protects the receiver against a dishonest sender at reveal time. A scheme that is hiding but not binding is an envelope with a false bottom: private, but worthless as evidence. A scheme that is binding but not hiding is a glass envelope: tamper-evident, but no secret survives it. The games of §4.3 formalise exactly these two failure modes, and the theorem of §4.4 shows that against computationally unbounded adversaries one of the two protections must give way.

4.2 Syntax

Definition 4.1 (Commitment scheme).

A commitment scheme $\Pi$ for a message space $\mathcal{M}$ and randomness space $\mathcal{R}$ is a triple of algorithms $(\mathrm{Setup},\mathrm{Commit},\mathrm{Open})$ :

•

The algorithm $\mathrm{Setup}(1^{\lambda})$ is PPT (§1.1) and outputs public parameters $p p$ , which implicitly determine the message space $\mathcal{M}_{pp}$ and randomness space $\mathcal{R}_{pp}$ and are an implicit input to the remaining algorithms.
•

The algorithm $\mathrm{Commit}(pp,m;r)$ , for $m\in\mathcal{M}_{pp}$ and $r\in\mathcal{R}_{pp}$ , is deterministic given $r$ and outputs a commitment $c$ . We write $\mathrm{Commit}(pp,m)$ , without an explicit $r$ , for the probabilistic algorithm that samples $r\xleftarrow{\$}\mathcal{R}_{pp}$ uniformly and returns $r$ alongside $c$ .
•

The algorithm $\mathrm{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 $p p$ in the support of $\mathrm{Setup}(1^{\lambda})$ , all $m\in\mathcal{M}_{pp}$ , and all $r\in\mathcal{R}_{pp}$ ,

\mathrm{Open}\bigl{(}pp,\,\mathrm{Commit}(pp,m;r),\,m,\,r\bigr{)}=1.

The pair $(m,r)$ is called the opening (or decommitment) of $c$ . Every scheme in this volume is canonically opening: $\mathrm{Open}(pp,c,m,r)$ merely recomputes $\mathrm{Commit}(pp,m;r)$ and checks equality with $c$ . This is the adopted convention unless stated otherwise. For a canonically opening scheme correctness holds automatically, and a valid opening of $c$ is precisely a pair $(m,r)$ with $\mathrm{Commit}(pp,m;r)=c$ —a reformulation the proofs below use constantly.

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

A commitment scheme is used in two temporally separated phases. In the commit phase the sender transmits $c$ and nothing else; in the reveal phase the sender transmits the opening $(m,r)$ and the receiver runs $\mathrm{Open}$ . The two security properties attach to the two phases: hiding constrains what the receiver can learn after the commit phase, while binding constrains what the sender can do in the reveal phase. A third concern precedes both: the setup phase that produces $p p$ . Who runs $\mathrm{Setup}$ , and whether that party can be trusted, proves decisive for some of the constructions ahead (Remark 4.3).

Remark 4.3 (Three setup models).

Commitment schemes divide by how much trust their parameters demand.

1.

Common reference string (CRS). A trusted party runs $\mathrm{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) genuinely resides here.
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 even though the textbook presentation phrases $\mathrm{Setup}$ as sampling and discarding a secret.
3.

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

Transparent setup is highly desirable: a flawed or subverted trusted setup can silently destroy binding, as the KZG trapdoor demonstrates concretely in §4.9.

4.3 Hiding and binding

Both properties are games in the sense of Definition 1.15. The hiding game arms the peeker: she chooses the two candidate messages herself, receives a commitment to one of them, and must say which.

Definition 4.4 (Hiding game and hiding).

Let $\Pi$ be a commitment scheme and $\mathcal{A}=(\mathcal{A}_{1},\mathcal{A}_{2})$ an adversary. For $b\in\{0,1\}$ , the game $\mathsf{Hide}^{\mathcal{A}}_{\Pi}(\lambda,b)$ runs as follows.

1.

The challenger runs $pp\leftarrow\mathrm{Setup}(1^{\lambda})$ .
2.

The adversary $\mathcal{A}_{1}(pp)$ outputs two messages $m_{0},m_{1}\in\mathcal{M}_{pp}$ and state $s t$ .
3.

The challenger samples $r\xleftarrow{\$}\mathcal{R}_{pp}$ and computes $c=\mathrm{Commit}(pp,m_{b};r)$ .
4.

The adversary $\mathcal{A}_{2}(st,c)$ outputs a bit $b^{\prime}$ , which is the output of the experiment.

The hiding advantage of $\mathcal{A}$ is

\mathrm{Adv}^{\mathrm{hide}}_{\Pi}(\mathcal{A},\lambda):=\Bigl{|}\Pr\bigl{[}% \mathsf{Hide}^{\mathcal{A}}_{\Pi}(\lambda,0)=1\bigr{]}-\Pr\bigl{[}\mathsf{Hide% }^{\mathcal{A}}_{\Pi}(\lambda,1)=1\bigr{]}\Bigr{|}.

The scheme is computationally hiding if the advantage is negligible (§1.2) for every PPT $\mathcal{A}$ ; statistically hiding if it is negligible even for computationally unbounded $\mathcal{A}$ ; and perfectly hiding if it is exactly $0$ for every adversary and every $\lambda$ .

Proposition 4.5 (Distributional characterisation of hiding).

A commitment scheme $\Pi$ is perfectly hiding if and only if for every $p p$ in the support of $\mathrm{Setup}$ and every pair $m_{0},m_{1}\in\mathcal{M}_{pp}$ , the random variables

\mathrm{Commit}(pp,m_{0};r)\quad\text{and}\quad\mathrm{Commit}(pp,m_{1};r),% \qquad r\xleftarrow{\$}\mathcal{R}_{pp},

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 $\mathrm{Setup}$ probability could exhibit large distance without granting any adversary noticeable advantage.)

Proof.

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

The binding game arms the equivocator. He is not handed an honest commitment; he manufactures his own, together with two openings.

Definition 4.6 (Binding game and binding).

For a commitment scheme $\Pi$ and adversary $\mathcal{A}$ , the game $\mathsf{Bind}^{\mathcal{A}}_{\Pi}(\lambda)$ runs as follows.

1.

The challenger runs $pp\leftarrow\mathrm{Setup}(1^{\lambda})$ .
2.

The adversary $\mathcal{A}(pp)$ outputs a commitment $c$ and two openings $(m_{0},r_{0})$ and $(m_{1},r_{1})$ .
3.

The game outputs $1$ iff $m_{0}\neq m_{1}$ and $\mathrm{Open}(pp,c,m_{0},r_{0})=\mathrm{Open}(pp,c,m_{1},r_{1})=1$ .

The binding advantage of $\mathcal{A}$ is

\mathrm{Adv}^{\mathrm{bind}}_{\Pi}(\mathcal{A},\lambda):=\Pr\bigl{[}\mathsf{% Bind}^{\mathcal{A}}_{\Pi}(\lambda)=1\bigr{]},

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 $\lambda$ .

For a canonically opening scheme the binding game has a useful collision reformulation: for fixed $p p$ , two openings collide precisely when $\mathrm{Commit}(pp,m_{0};r_{0})=\mathrm{Commit}(pp,m_{1};r_{1})$ with $m_{0}\neq m_{1}$ . Perfect binding then says that distinct messages never share a commitment value at all—the message $m$ is a deterministic function of $c$ . Perfect binding is thus equivalent to the map $c\mapsto m$ being well defined on all attainable commitments, a formulation the counting argument of Remark 4.9 exploits.

Remark 4.7 (The asymmetry of the quantifiers).

The two games quantify over different objects. Hiding quantifies over what can be extracted from a single honestly produced commitment: the challenger seals the envelope, and the adversary only looks. Binding quantifies over what can be manufactured: the adversary builds an ambiguous commitment of its own choosing, under no obligation to follow $\mathrm{Commit}$ honestly. A scheme can be strong in one respect and weak in the other, and the two properties actively pull in opposite directions—the more commitment values a message can take (good for hiding), the more opportunities for two messages to share one (bad for binding). The next subsection makes this tension a theorem.

4.4 Incompatibility of perfect hiding and perfect binding

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

Let $\Pi$ be a canonically opening commitment scheme with $\lvert\mathcal{M}_{pp}\rvert\geq 2$ . If $\Pi$ 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 $p p$ in the support of $\mathrm{Setup}(1^{\lambda})$ and any two distinct messages $m_{0},m_{1}\in\mathcal{M}_{pp}$ . For a message $m$ , let

C_{m}:=\bigl{\{}\,\mathrm{Commit}(pp,m;r):r\in\mathcal{R}_{pp}\,\bigr{\}}

be the set of attainable commitments to $m$ , and let $D_{m}$ be the distribution of $\mathrm{Commit}(pp,m;r)$ for uniform $r$ . Perfect hiding makes $D_{m_{0}}$ and $D_{m_{1}}$ identical (Proposition 4.5); identical distributions have identical supports, so $C_{m_{0}}=C_{m_{1}}$ . Pick any $c$ in this common support. By definition of the supports there exist $r_{0},r_{1}\in\mathcal{R}_{pp}$ with

\mathrm{Commit}(pp,m_{0};r_{0})=c=\mathrm{Commit}(pp,m_{1};r_{1}),

and then $\bigl{(}c,(m_{0},r_{0}),(m_{1},r_{1})\bigr{)}$ wins the binding game: both openings are valid by canonical opening, and $m_{0}\neq m_{1}$ . The double opening exists for every attainable $p p$ ; an unbounded adversary finds it by enumerating $\mathcal{R}_{pp}$ , so it wins $\mathsf{Bind}$ with probability $1$ , giving $\mathrm{Adv}^{\mathrm{bind}}_{\Pi}=1\neq 0$ . □

Remark 4.9 (The impossibility as a counting fact).

Information-theoretically the theorem is a statement about how many bits the commitment carries. Perfect binding forces the map $c\mapsto m$ to be well defined, so $c$ determines $m$ completely: the commitment carries at least $\log_{2}\lvert\mathcal{M}\rvert$ 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 $\log_{2}\lvert\mathcal{M}\rvert=0$ , that is, $\lvert\mathcal{M}\rvert=1$ —when there is nothing to commit to. Every real scheme therefore chooses which property to make perfect (or statistical) and settles for the other being 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).

The choice is not merely aesthetic; it decides how the scheme fails if its assumption falls. 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 the day the assumption breaks, even for commitments published long before. Which failure is worse is a judgement about the application: whether integrity or long-term confidentiality is the greater concern. A ledger that publishes its commitments forever has reason to care about the second failure mode; a protocol whose soundness guards live funds has reason to care about the first.

4.5 Hash-based commitments

The simplest construction seals the envelope with a hash. Recall from §3 the two properties it needs: a hash function $H\colon\{0,1\}^{*}\to\{0,1\}^{n}$ is collision resistant (Definition 3.7) if no PPT adversary finds $x\neq x^{\prime}$ with $H(x)=H(x^{\prime})$ 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^{\prime}$ with $H(x^{\prime})=H(x)$ except with negligible probability.

Construction 4.11 (Hash commitment).

Let $H\colon\{0,1\}^{*}\to\{0,1\}^{n}$ be a hash function. The hash commitment has message space $\mathcal{M}=\{0,1\}^{*}$ and randomness space $\mathcal{R}=\{0,1\}^{\ell}$ for a randomness length $\ell=\ell(\lambda)$ (for example $\ell=2n$ ). Let $\mathsf{enc}(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

\mathrm{Commit}(m;r):=H\bigl{(}\mathsf{enc}(m,r)\bigr{)},

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 $\mathcal{A}$ wins the binding game: it outputs $c$ with valid openings $(m_{0},r_{0})$ , $(m_{1},r_{1})$ and $m_{0}\neq m_{1}$ , so $H(\mathsf{enc}(m_{0},r_{0}))=c=H(\mathsf{enc}(m_{1},r_{1}))$ . Injectivity of $\mathsf{enc}$ makes the two hash inputs distinct strings—this is exactly what the self-delimiting encoding buys; 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 $\mathcal{A}$ and outputs the pair $\bigl{(}\mathsf{enc}(m_{0},r_{0}),\;\mathsf{enc}(m_{1},r_{1})\bigr{)}$ wins the collision game with exactly the binding advantage of $\mathcal{A}$ , 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 $\operatorname{poly}(\lambda)$ and randomness length $\ell=\omega(\log\lambda)$ , the hash commitment is computationally hiding: an adversary making at most $q$ oracle queries has hiding advantage at most $q\cdot 2^{-\ell}$ .

Proof.

The challenge commitment is $c=H(\mathsf{enc}(m_{b},r))$ for uniform $r\in\{0,1\}^{\ell}$ . 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 $\mathsf{enc}(m_{b},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^{-\ell}$ , and the union bound (Math Guide, §“The union bound and a birthday calculation”) caps the probability of any hit by $q\cdot 2^{-\ell}$ . 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\cdot 2^{-\ell}$ , negligible for $\ell=\omega(\log\lambda)$ and polynomial $q$ . □

Remark 4.14 (Why the randomness is essential).

Dropping $r$ is fatal. The deterministic commitment $c=H(m)$ fails hiding for every low-entropy message space: to distinguish a commitment to $m_{0}$ from one to $m_{1}$ , the peeker simply hashes her two candidates and compares. Nothing about collision resistance or one-wayness prevents this—the attack never inverts anything. The salt $r$ contributes $\ell$ uniformly random bits, so the hash input is unpredictable even when the message is one of two known values. The same phenomenon renders deterministic encryption insecure for low-entropy plaintexts, and the same cure—randomisation—applies.

Remark 4.15 (Strength profile).

The hash commitment has two virtues. It is transparent: no trusted setup, indeed no parameters, and no algebraic structure for a subverted setup to poison. And it is plausibly post-quantum: generic quantum collision finding takes $\Theta(2^{n/3})$ queries against an $n$ -bit hash (Remark 2.31), so increasing the output length compensates for the loss. Its weakness is the flip side of its opacity: the commitment is an unstructured bit string. One cannot add two hash commitments and obtain a commitment to the sum of the messages; no algebraic relation on commitments reflects any relation on the committed values. The Pedersen construction repairs exactly this defect, at the price of resting on discrete log.

4.6 The Pedersen commitment

We change algebraic scenery. Let $\mathbb{G}$ be a cyclic group of prime order $q$ , written additively: for a point $P\in\mathbb{G}$ and scalar $a\in\mathbb{F}_{q}$ , the scalar multiple is $[a]P$ , with $[0]P=\mathcal{O}$ the identity, and $a\mapsto[a]P$ is a group homomorphism $\mathbb{F}_{q}\to\mathbb{G}$ . Concretely, $\mathbb{G}$ is the group of $\mathbb{F}_{p}$ -points of a prime-order elliptic curve (Math Guide, §“The group structure of $E(\mathbb{F}_{p})$ ”), and in this volume the Pallas curve of §2.6; but the only structural facts the constructions use are that $\mathbb{G}$ is isomorphic to $\mathbb{F}_{q}$ as a group and that discrete logarithms in $\mathbb{G}$ are hard. Formally, a group generator $\mathcal{G}$ on input $1^{\lambda}$ outputs $(\mathbb{G},q,G)$ with $q$ a $\Theta(\lambda)$ -bit prime and $G$ a generator, and the DLog assumption for $\mathcal{G}$ states that no PPT adversary, given $(\mathbb{G},q,G,[a]G)$ for uniform $a\xleftarrow{\$}\mathbb{F}_{q}$ , outputs $a$ except with negligible probability—Definition 2.2, transcribed additively as in §2.6.

Construction 4.16 (Pedersen commitment).

The algorithm $\mathrm{Setup}(1^{\lambda})$ runs $(\mathbb{G},q,G)\leftarrow\mathcal{G}(1^{\lambda})$ , samples $s\xleftarrow{\$}\mathbb{F}_{q}^{\times}$ , sets $H:=[s]G$ , outputs $pp=(\mathbb{G},q,G,H)$ , and discards $s$ . The message and randomness spaces are $\mathcal{M}=\mathcal{R}=\mathbb{F}_{q}$ , and

\mathrm{Commit}(pp,m;r):=[m]G+[r]H,

opened canonically.

The parameters are two generators $G$ and $H$ whose relative discrete logarithm $s=\log_{G}H$ is unknown to all parties, the committer included. Everything hinges on this one unknown scalar: knowledge of $s$ breaks binding (Remark 4.19), while perfect hiding, as the proof below shows, does not even require ignorance of $s$ . In deployment the sampled-and-discarded $s$ of the textbook presentation is replaced by deriving $H$ through hashing to the curve (Construction 3.24): 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=(\mathbb{G},q,G,H)$ ; since $s\in\mathbb{F}_{q}^{\times}$ , the point $H$ is not $\mathcal{O}$ . Because $\mathbb{G}$ has prime order, the nonzero $H$ generates $\mathbb{G}$ , so $r\mapsto[r]H$ is a bijection $\mathbb{F}_{q}\to\mathbb{G}$ . For uniform $r$ , therefore, $[r]H$ is uniform on $\mathbb{G}$ —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 $\mathbb{G}$ regardless of $m$ , so for any $m_{0},m_{1}$ 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 $\mathcal{G}$ , the Pedersen commitment is computationally binding. Concretely, from any adversary $\mathcal{A}$ that wins the binding game with probability $\varepsilon$ one constructs $\mathcal{B}$ computing discrete logarithms with probability $(1-1/q)\,\varepsilon\geq\varepsilon-1/q$ , in essentially the same running time.

Proof.

First the algebra. A double opening gives $[m_{0}]G+[r_{0}]H=[m_{1}]G+[r_{1}]H$ with $m_{0}\neq m_{1}$ , so

[m_{0}-m_{1}]G=[r_{1}-r_{0}]H.

The case $r_{1}=r_{0}$ is impossible: it would force $[m_{0}-m_{1}]G=\mathcal{O}$ , and since $G$ has order $q$ this means $m_{0}\equiv m_{1}\pmod{q}$ , contradicting $m_{0}\neq m_{1}$ in $\mathbb{F}_{q}$ . With $r_{1}-r_{0}$ invertible modulo the prime $q$ , the relation solves for the hidden discrete logarithm:

s=\log_{G}H=(m_{0}-m_{1})(r_{1}-r_{0})^{-1}\bmod q.

A double opening is the discrete log of $H$ .

Now the reduction. On a DLog challenge $(\mathbb{G},q,G,Q)$ , the algorithm $\mathcal{B}$ sets $H:=Q$ , hands $pp=(\mathbb{G},q,G,Q)$ to $\mathcal{A}$ , and, when $\mathcal{A}$ returns a double opening, outputs $(m_{0}-m_{1})(r_{1}-r_{0})^{-1}\bmod q=\log_{G}Q$ . One distribution gap needs accounting: in the real scheme $H=[s]G$ with $s\xleftarrow{\$}\mathbb{F}_{q}^{\times}$ , so $H$ is uniform on $\mathbb{G}\setminus\{\mathcal{O}\}$ , whereas the challenge $Q=[a]G$ has $a$ uniform on all of $\mathbb{F}_{q}$ , so $Q$ is uniform on all of $\mathbb{G}$ . The two distributions differ only on the event $Q=\mathcal{O}$ , of probability $1/q$ —their statistical distance is exactly $1/q$ —and on that event $\mathcal{A}$ cannot win anyway (with $H=\mathcal{O}$ the relation above forces $m_{0}=m_{1}$ ). Conditioned on $Q\neq\mathcal{O}$ , the simulation is perfect, so

\mathrm{Adv}^{\mathrm{dlog}}(\mathcal{B})=\Bigl{(}1-\tfrac{1}{q}\Bigr{)}\,% \mathrm{Adv}^{\mathrm{bind}}_{\Pi}(\mathcal{A})\;\geq\;\varepsilon-\tfrac{1}{q},

and $\mathcal{B}$ ’s overhead over $\mathcal{A}$ is a constant number of field operations. □

The same embed-and-extract pattern, scaled up to many generators, proves the vector generalisation (Theorem 4.23).

Remark 4.19 (Equivocation with the trapdoor).

Any party who knows $s=\log_{G}H$ can open a Pedersen commitment to any message. Given $c=[m]G+[r]H$ and a target $m^{\prime}$ , set

r^{\prime}:=r+(m-m^{\prime})\,s^{-1}\bmod q;

then $[m^{\prime}]G+[r^{\prime}]H=[m^{\prime}]G+[r]H+[(m-m^{\prime})]G=c$ . This trapdoor property is not a defect of the construction—it is precisely why discarding $s$ in $\mathrm{Setup}$ is mandatory, and it is a feature the theory exploits deliberately: zero-knowledge simulators use exactly this equivocation to open commitments consistently with a transcript produced out of order. The same phenomenon priced the setup models of Remark 4.3: a commitment scheme with a trapdoor is only as binding as the claim that nobody holds it.

Theorem 4.20 (Additive homomorphism).

For all $m_{0},m_{1},r_{0},r_{1}\in\mathbb{F}_{q}$ ,

\mathrm{Commit}(m_{0};r_{0})+\mathrm{Commit}(m_{1};r_{1})=\mathrm{Commit}(m_{0% }+m_{1};\,r_{0}+r_{1}),

and more generally, for all scalars $\alpha,\beta\in\mathbb{F}_{q}$ ,

[\alpha]\,\mathrm{Commit}(m_{0};r_{0})+[\beta]\,\mathrm{Commit}(m_{1};r_{1})=% \mathrm{Commit}(\alpha m_{0}+\beta m_{1};\,\alpha r_{0}+\beta r_{1}).

Proof.

Expand and regroup, using commutativity of $+$ in $\mathbb{G}$ , the identity $[a]P+[b]P=[a+b]P$ , and the linearity $[\alpha]([m]G+[r]H)=[\alpha m]G+[\alpha r]H$ of scalar multiplication:

	$\displaystyle[\alpha]\bigl{(}[m_{0}]G+[r_{0}]H\bigr{)}+[\beta]\bigl{(}[m_{1}]G% +[r_{1}]H\bigr{)}$	$\displaystyle=[\alpha m_{0}]G+[\beta m_{1}]G+[\alpha r_{0}]H+[\beta r_{1}]H$
		$\displaystyle=[\alpha m_{0}+\beta m_{1}]G+[\alpha r_{0}+\beta r_{1}]H.\qed$

Remark 4.21 (Value balancing: the homomorphism deployed).

The homomorphism is what makes Pedersen commitments the right tool for hidden arithmetic, and Zcash’s value balancing is the canonical deployment. Each transaction value $v_{i}$ is committed as $C_{i}=[v_{i}]G+[r_{i}]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 $v_{i}$ : the value components cancel in $\sum C_{\mathrm{in}}-\sum C_{\mathrm{out}}$ 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$ —value sums differing by a multiple of $q$ cancel too—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,\dots,2^{64}-1\}$ (the Action statement, protocol specification § 4.18.4; enforced by the note-commitment gadget’s ValueCanonicity gate), 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 $\mathsf{ValueCommit}(v;\mathsf{rcv})=[v]V+[\mathsf{rcv}]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 template the rest of the volume reuses repeatedly.

4.7 Pedersen vector commitments

A single group element can seal far more than a single scalar.

Construction 4.22 (Pedersen vector commitment).

On input $1^{\lambda}$ and a length $n=\operatorname{poly}(\lambda)$ , $\mathrm{Setup}$ outputs $(\mathbb{G},q)$ together with generators $G_{1},\dots,G_{n},H\xleftarrow{\$}\mathbb{G}\setminus\{\mathcal{O}\}$ , 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 $\mathbb{F}_{q}^{n}$ , the randomness space $\mathbb{F}_{q}$ , and for $\mathbf{m}=(m_{1},\dots,m_{n})$ ,

\mathrm{Commit}(pp,\mathbf{m};r):=\sum_{i=1}^{n}[m_{i}]G_{i}+[r]H\;=\;\langle% \mathbf{m},\,\mathbf{G}\rangle+[r]H,

where $\langle\mathbf{m},\,\mathbf{G}\rangle:=\sum_{i}[m_{i}]G_{i}$ is the multiscalar (mixed) inner product of the message vector with the generator vector $\mathbf{G}=(G_{1},\dots,G_{n})$ . Opening is canonical.

Theorem 4.23 (Properties of the vector commitment).

The Pedersen vector commitment is perfectly hiding, and computationally binding under the DLog assumption in $\mathbb{G}$ .

Proof.

Hiding. Exactly as in Theorem 4.17: for uniform $r$ the blinding term $[r]H$ is uniform on $\mathbb{G}$ , so the commitment is uniform on $\mathbb{G}$ regardless of the message vector.

Binding. A double opening with $\mathbf{m}\neq\mathbf{m}^{\prime}$ gives $\langle\mathbf{m},\,\mathbf{G}\rangle+[r]H=\langle\mathbf{m}^{\prime},\,% \mathbf{G}\rangle+[r^{\prime}]H$ , that is, a nontrivial discrete-log relation

\sum_{i=1}^{n}[m_{i}-m_{i}^{\prime}]\,G_{i}+[r-r^{\prime}]\,H=\mathcal{O}

with not all coefficients zero. The reduction $\mathcal{B}$ 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 $u_{i},w_{i}\xleftarrow{\$}\mathbb{F}_{q}$ for each $i$ and $u_{H},w_{H}\xleftarrow{\$}\mathbb{F}_{q}$ , sets

G_{i}:=[u_{i}]G+[w_{i}]Q,\qquad H:=[u_{H}]G+[w_{H}]Q,

and resamples any pair whose generator lands on $\mathcal{O}$ . Each result is uniform on $\mathbb{G}\setminus\{\mathcal{O}\}$ —the $[u_{i}]G$ term alone makes the pre-rejection point uniform on $\mathbb{G}$ —so the simulated parameters follow the real distribution. Crucially, the parameters reveal nothing about the $w$ -coordinates: for every candidate value of $w_{i}$ there is exactly one $u_{i}$ consistent with the observed $G_{i}$ , so conditioned on the adversary’s entire view the $w_{i}$ and $w_{H}$ remain independent and uniform. Write the recovered relation as $\sum_{i}[a_{i}]G_{i}+[a_{H}]H=\mathcal{O}$ with coefficient vector $(a_{1},\dots,a_{n},a_{H})\neq\mathbf{0}$ . Substituting the embeddings and collecting the $G$ - and $Q$ -components gives

c_{0}+c_{1}s\equiv 0\pmod{q},\qquad c_{0}=\sum_{i}a_{i}u_{i}+a_{H}u_{H},\quad c% _{1}=\sum_{i}a_{i}w_{i}+a_{H}w_{H}.

Since the coefficient vector is nonzero and the $w$ -coordinates are uniform and independent of it, $c_{1}$ is uniform on $\mathbb{F}_{q}$ , hence nonzero with probability $1-1/q$ ; in that case $s=-c_{0}\,c_{1}^{-1}\bmod q$ , and $\mathcal{B}$ outputs the challenge logarithm. Altogether $\mathrm{Adv}^{\mathrm{dlog}}(\mathcal{B})\geq(1-1/q)\,\mathrm{Adv}^{\mathrm{% bind}}(\mathcal{A})$ . □

Remark 4.24 (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 $q^{n}$ message vectors and only $q$ commitment values, so colliding openings exist in overwhelming abundance. This is exactly why binding is only computational—an unbounded adversary finds a colliding opening by solving the underlying discrete-log relation—and it is the trade-off of Theorem 4.8 made visible at the level of cardinalities: a compressing commitment cannot determine its message, so it might as well hide it perfectly.

Remark 4.25 (Linearity survives).

The vector commitment remains additively homomorphic in both message and randomness, componentwise: $\mathrm{Commit}(\mathbf{m};r)+\mathrm{Commit}(\mathbf{m}^{\prime};r^{\prime})=% \mathrm{Commit}(\mathbf{m}+\mathbf{m}^{\prime};\,r+r^{\prime})$ , by the same regrouping as Theorem 4.20. This linearity, applied to a committed vector against public coefficient vectors, is the foundation of the inner-product arguments of §4.9, which prove statements about $\langle\mathbf{m},\,\mathbf{b}\rangle$ for public $\mathbf{b}$ 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 fully linear Pedersen commitment sits an intermediate species: algebraic hash functions, collision-resistant hashes whose internal operations are elliptic-curve group operations. The point of the species is proof cost. A zero-knowledge circuit that must verify a hash evaluation pays for every internal operation; when those operations are curve additions in the very field the proof system works over, the verification is cheap, while collision resistance still reduces to the discrete logarithm. Sinsemilla, deployed in Zcash Orchard, is the archetype: a Pedersen-style hash over a sequence of message chunks. We build up to it through its ancestor.

Construction 4.26 (Pedersen hash).

Split the message $M$ into $k$ chunks $m_{1},\dots,m_{k}$ , each interpreted as a scalar in a bounded range, and fix $k$ independent generators $P_{1},\dots,P_{k}\in\mathbb{G}$ with unknown mutual discrete logarithms. Define

\mathsf{PedersenHash}(M):=\sum_{j=1}^{k}[m_{j}]P_{j}\;\in\;\mathbb{G}.

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.27 (Collision resistance of the Pedersen hash).

Suppose no efficient algorithm finds a nontrivial relation $\sum_{j}[a_{j}]P_{j}=\mathcal{O}$ with not all $a_{j}=0$ and each $\lvert a_{j}\rvert$ within the allowed chunk range—hardness that follows from DLog when the $P_{j}$ are independent uniform generators. Then $\mathsf{PedersenHash}$ is collision resistant.

Proof.

A collision $M\neq M^{\prime}$ , with chunk decompositions $(m_{j})$ and $(m_{j}^{\prime})$ , gives $\sum_{j}[m_{j}-m_{j}^{\prime}]\,P_{j}=\mathcal{O}$ with some coefficient $m_{j}-m_{j}^{\prime}\neq 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.23: set each $P_{j}=[u_{j}]G+[w_{j}]Q$ for the challenge $Q$ , and read the unknown logarithm off the recovered relation. □

The Pedersen hash needs one independent generator per chunk, which is costly for long inputs: the generator table grows linearly with the maximum message length. Sinsemilla reorganises the computation into an iterated two-operand form that reuses a small fixed generator table—shared by all chunk positions—while preserving the discrete-log collision reduction.

Construction 4.28 (Sinsemilla hash).

Split the message $M$ into pieces $m_{1},\dots,m_{k}$ , each of fixed width $w\leq 32$ bits, and identify a piece $v\in\{0,1\}^{w}$ with its integer value, bits read little-endian (the specification’s $\mathsf{LEBS2IP}$ ). The public parameters are a base point $Q\in\mathbb{G}$ and a table $S\colon\{0,1\}^{w}\to\mathbb{G}$ assigning to each possible piece value its own generator, both obtained by hashing to the curve. Write $\mathsf{GroupHash}(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\,\|\,\texttt{"-pallas\_XMD:BLAKE2b\_SSWU\_RO\_"}$ of §3.6 (protocol specification § 5.4.9.8)—and write $\mathrm{LE}_{32}(j)$ for the four-byte little-endian encoding of an integer $0\leq j<2^{32}$ . The table is

S(v):=\mathsf{GroupHash}\bigl{(}\texttt{"z.cash:SinsemillaS"},\,\mathrm{LE}_{3% 2}(v)\bigr{)},\qquad v\in\{0,1\}^{w},

with $2^{w}$ 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:=\mathsf{GroupHash}\bigl{(}\texttt{"z.cash:SinsemillaQ"},\,D\bigr{)}.

Both derivations are nothing-up-my-sleeve (Construction 3.24), so no party knows any discrete-log relation among $\{S(v)\}_{v}\cup\{Q\}$ (Remark 3.25). The deployed instantiation takes $w=10$ (the specification’s $k$ ) over Pallas: the sinsemilla crate fixes the two personalisation strings and derives $Q$ in HashDomain::new; the table ships precomputed as SINSEMILLA_S, and the crate’s test sinsemilla_s re-derives every entry from u32::to_le_bytes of the index—exactly $\mathrm{LE}_{32}$ ; the circuit loads that table as its lookup; protocol specification § 5.4.1.9. The hash iterates over the pieces with a running accumulator $\mathrm{Acc}\in\mathbb{G}$ :

\mathrm{Acc}_{0}:=Q,\qquad\mathrm{Acc}_{j}:=\mathrm{Acc}_{j-1}+\bigl{(}\mathrm% {Acc}_{j-1}+S(m_{j})\bigr{)}=[2]\mathrm{Acc}_{j-1}+S(m_{j}),

and outputs the point $\mathsf{SinsemillaHashToPoint}(M):=\mathrm{Acc}_{k}$ . The step costs two incomplete curve additions—first $\mathrm{Acc}_{j-1}+S(m_{j})$ , then the result plus $\mathrm{Acc}_{j-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 very few constraints. Unrolling the recurrence gives the closed form

\mathsf{SinsemillaHashToPoint}(M)=\sum_{j=1}^{k}\bigl{[}2^{\,k-j}\bigr{]}S(m_{% j})+\bigl{[}2^{k}\bigr{]}Q:

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

Proposition 4.29 (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 $\mathsf{SinsemillaHashToPoint}$ , on inputs for which its incomplete additions are defined, yields a nontrivial discrete-log relation among $\{S(v)\}_{v}\cup\{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.23 extended to $Q$ . The point hash is thus collision resistant under the DLog assumption in $\mathbb{G}$ , the exceptional cases of incomplete addition covered by the same reduction rather than excluded.

Proof sketch.

Let $M\neq M^{\prime}$ collide. Suppose first that they have the same piece count $k$ . Subtracting the unrolled forms cancels the $[2^{k}]Q$ terms and leaves

\sum_{j=1}^{k}\bigl{[}2^{\,k-j}\bigr{]}\bigl{(}S(m_{j})-S(m_{j}^{\prime})\bigr% {)}=\mathcal{O}.

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

c_{v}\;=\;\sum_{j\,:\,m_{j}=v}2^{\,k-j}\;-\;\sum_{j\,:\,m_{j}^{\prime}=v}2^{\,% k-j},

and the relation reads $\sum_{v}[c_{v}]\,S(v)=\mathcal{O}$ . Each $c_{v}$ is a difference of two subset-sums of the distinct powers $2^{k-1},\dots,2^{0}$ , hence an integer with $\lvert c_{v}\rvert<2^{k}$ . For admissible message lengths—those with $2^{k}$ below the group order $q$ , a finite design-time check—such a coefficient vanishes modulo $q$ only if it vanishes as an integer; and $c_{v}=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^{\prime}$ to coincide. Coincidence for every $v$ would force $M=M^{\prime}$ ; since $M\neq M^{\prime}$ , some $c_{v}\neq 0$ and the relation is nontrivial.

If instead the piece counts differ, say $k>k^{\prime}$ , the $Q$ -constants do not cancel: the relation acquires the coefficient $2^{k}-2^{k^{\prime}}$ 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.27.

Finally, 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 $[\alpha]\mathrm{Acc}_{j-1}+S(m_{j})=\mathcal{O}$ with $\alpha\in\{-1,1,2\}$ . Substituting the unrolled form of $\mathrm{Acc}_{j-1}$ makes this an explicit relation among $Q$ and the table generators, with coefficient $\alpha\,2^{\,j-1}\neq 0$ on $Q$ and all magnitudes at most $2^{k}$ —below the group order for admissible lengths. An input that merely triggers an exceptional case therefore hands over a nontrivial relation itself, 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 $\mathsf{SinsemillaHash}$ applies the Pallas coordinate extractor to $\mathsf{SinsemillaHashToPoint}(M)$ , returning its $x$ -coordinate rather than the point itself. Collision resistance survives the extraction: equal extracted $x$ -coordinates mean the two points are equal or are negatives of one another, and either signed equality yields the same kind of nontrivial generator relation as in the proof above. Second, the final piece is zero-padded to the piece width—the Pad iterator of the sinsemilla crate pads the message bits 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. This is exactly the property the protocol specification requires and no more (protocol specification § 5.4.1.9: collision resistance is demanded “between inputs of fixed length, for a given personalization input”); each personalisation domain hashes inputs of a single length, as the Merkle-tree hash $\mathsf{MerkleCRH}$ 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 step from hash to commitment is the Pedersen blinding term, verbatim.

Construction 4.30 (SinsemillaCommit).

Fix one further independent generator $H^{\prime}$ , hashed to the curve with its own domain string, so that no discrete-log relation between $H^{\prime}$ and $\{S(v)\}_{v}\cup\{Q\}$ is known. Define, for $r\xleftarrow{\$}\mathbb{F}_{q}$ ,

\mathsf{SinsemillaCommit}(m;r):=\mathsf{SinsemillaHashToPoint}(m)+[r]H^{\prime}.

Hiding is inherited from Pedersen verbatim: by the argument of Theorem 4.17, $[r]H^{\prime}$ is uniform on $\mathbb{G}$ 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 $\mathsf{SinsemillaHashToPoint}$ collision—excluded by Proposition 4.29—or a nontrivial discrete-log relation between $H^{\prime}$ and the hash generators.

Orchard’s note commitment $\mathsf{NoteCommit}$ instantiates exactly this map: the orchard crate derives it through the sinsemilla crate’s CommitDomain::commit (protocol specification § 5.4.8.4). Its key commitment $\mathsf{CommitIvk}$ composes the same map with $x$ -coordinate extraction—the specification’s $\mathsf{SinsemillaShortCommit}$ —returning a base-field element rather than a point.

Remark 4.31 (Why Sinsemilla exists: cost inside a proof).

Sinsemilla’s advantage is not speed outside a circuit—ordinary hashes are faster there—but 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, all Boolean choppings 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 chosen to lie in the very field the proof system already works over. The result is a collision-resistant hash and commitment—used for note commitments and Merkle trees in Orchard—simultaneously cheap to prove and grounded in the same discrete-log hardness as the surrounding protocol. The presentation here is the conceptual core; the Ironwood Guide takes up the concrete Orchard instantiation—its per-use personalisation strings and the in-circuit handling of incomplete addition.

4.9 Polynomial commitment schemes

The final refinement commits not to a value or a vector but to a function—a polynomial—and supports proving statements about its values. This is the primitive on which the succinct argument systems of §9 stand.

Definition 4.32 (Polynomial commitment scheme).

Fix a field $\mathbb{F}$ and a degree bound $d$ . A polynomial commitment scheme (PCS) is a tuple $(\mathrm{Setup},\mathrm{Commit},\mathrm{Open},\mathrm{Eval},\mathrm{Verify})$ :

•

The algorithm $\mathrm{Setup}(1^{\lambda},d)$ outputs public parameters $p p$ supporting degree at most $d$ ;
•

the algorithm $\mathrm{Commit}(pp,f;r)$ outputs a commitment $C$ to a polynomial $f\in\mathbb{F}[X]_{\leq d}$ , optionally with hiding randomness $r$ ;
•

the algorithm $\mathrm{Open}(pp,C,f,r)$ outputs a bit, verifying that $C$ commits to the whole polynomial $f$ ;
•

the algorithm $\mathrm{Eval}(pp,f,r,z)$ , for an evaluation point $z\in\mathbb{F}$ , outputs a claimed value $y=f(z)$ together with an evaluation proof $\pi$ ;
•

the algorithm $\mathrm{Verify}(pp,C,z,y,\pi)$ 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\neq y^{\prime}$ 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.33 (Rigidity, and why evaluation binding is separate).

Why should one short commitment support probing 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. Answering a different value at even a single point is the behaviour of a prover holding a different polynomial—there is no wiggle room between functions. But a warning is in order: an accepting evaluation proof is not an opening of $C$ , so evaluation binding does not follow from the binding of $\mathrm{Commit}$ . It is a separate cryptographic requirement, and 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 central design problem of a PCS is making the evaluation proof $\pi$ short and fast to verify; committing to the coefficient list with any old commitment is easy, and useless.

KZG: evaluation in the exponent

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

Construction 4.34 (KZG commitment).

Let $\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T}$ be groups of prime order $\lvert\mathbb{F}\rvert$ equipped with a nondegenerate bilinear pairing $e\colon\mathbb{G}_{1}\times\mathbb{G}_{2}\to\mathbb{G}_{T}$ (Example 2.9), with generators $G\in\mathbb{G}_{1}$ and $\hat{G}\in\mathbb{G}_{2}$ . The algorithm $\mathrm{Setup}$ samples a secret $\tau\xleftarrow{\$}\mathbb{F}$ , publishes the structured reference string

pp=\bigl{(}[\tau^{0}]G,\,[\tau^{1}]G,\,\dots,\,[\tau^{d}]G,\;\hat{G},\,[\tau]% \hat{G}\bigr{)},

and discards $\tau$ . The commitment to $f=\sum_{i=0}^{d}a_{i}X^{i}$ is evaluation in the exponent:

\mathrm{Commit}(pp,f):=\sum_{i=0}^{d}[a_{i}]\bigl{(}[\tau^{i}]G\bigr{)}=[f(% \tau)]G,

computable from $p p$ by anyone, without knowledge of $\tau$ .

Construction 4.35 (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):=\frac{f(X)-y}{X-z}\;\in\;\mathbb{F}[X]_{\leq d-1}

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

e\bigl{(}C-[y]G,\;\hat{G}\bigr{)}\;\stackrel{{\scriptstyle?}}{{=}}\;e\bigl{(}% \pi,\;[\tau]\hat{G}-[z]\hat{G}\bigr{)},

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

Proposition 4.36 (KZG evaluation binding, sketched).

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

Proof idea.

Two accepting proofs $\pi,\pi^{\prime}$ for distinct values $y\neq y^{\prime}$ at the same point $z$ satisfy the two pairing equations; subtracting them (in the exponent) gives $\pi-\pi^{\prime}=[(y^{\prime}-y)(\tau-z)^{-1}]G$ , so the forger’s output yields

\bigl{[}(\tau-z)^{-1}\bigr{]}G=\bigl{[}(y^{\prime}-y)^{-1}\bigr{]}(\pi-\pi^{% \prime}),

exactly the element the assumption declares infeasible. □

Remark 4.37 (The KZG trade).

What KZG buys: commitments and evaluation proofs of constant size (one group element each) and constant verification time (two pairings), all independent of the degree $d$ . What it costs is twofold. First, the setup is trusted in the strongest sense: the secret $\tau$ is a global trapdoor. Anyone who learns $\tau$ can forge accepting evaluation proofs for false statements—for any commitment $C$ , any point $z$ , and any desired value $y$ , the element $\pi:=[(\tau-z)^{-1}]\bigl{(}C-[y]G\bigr{)}$ passes the pairing check, no knowledge of any polynomial required. This is the promised demonstration that a subverted setup silently destroys binding (Remark 4.3); evaluation binding survives only if $\tau$ 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. Second, the construction requires pairing-friendly curves, a more delicate 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.38 (IPA-style polynomial commitment).

Let $\mathbf{G}=(G_{0},\dots,G_{d})$ and $H$ be transparent generators with unknown mutual discrete logs, derived from a public seed (Construction 4.22). Commit to $f=\sum_{i=0}^{d}a_{i}X^{i}$ by the Pedersen vector commitment of its coefficient vector $\mathbf{a}=(a_{0},\dots,a_{d})$ :

\mathrm{Commit}(pp,f;r):=\sum_{i=0}^{d}[a_{i}]G_{i}+[r]H=\langle\mathbf{a},\,% \mathbf{G}\rangle+[r]H.

No pairings, no trusted setup.

Evaluation is an inner product: writing $\mathbf{z}=(1,z,z^{2},\dots,z^{d})$ for the public vector of powers of the query point,

f(z)=\sum_{i=0}^{d}a_{i}z^{i}=\langle\mathbf{a},\,\mathbf{z}\rangle,

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 $L_{j}$ and $R_{j}$ ) to account for the mixed terms; after $\log_{2}(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.39 (Properties of the IPA-based PCS).

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

Proof idea.

Binding of the commitment itself is Theorem 4.23. 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 $\mathbf{a}$ 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 $\mathbf{G},H$ , contradicting DLog by the every-generator embedding. The $O(\log d)$ proof size is the halving recursion; the $O(d)$ verification is the final multiscalar multiplication over the unfolded generators. □

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

The two families mark out the design space. 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 precisely 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. Batching amortises the per-proof 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.41 (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 in new clothing. That is acceptable when the polynomial encodes only public data. Whenever it encodes secrets—as the witness polynomials of a zero-knowledge proof do—randomness is required: KZG is augmented with a blinding summand $[r][\gamma]G$ using an extra setup element $[\gamma]G$ , while the IPA commitment of Construction 4.38 already carries its $[r]H$ and is perfectly hiding by Theorem 4.23. 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

The polynomial commitment is where the section’s main line hands over to the proof systems of §9, and the hand-over can be stated in one paragraph. 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; evaluation proofs then convince the verifier that the committed polynomials satisfy the required identities, without the polynomials ever being revealed. Soundness is supplied by 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 are supplied by the commitment: the prover is locked to its polynomials before seeing the challenge, and the verifier handles only short commitments and proofs in place of the polynomials themselves. How this compilation is carried out in full—and what “argument of knowledge” precisely means—is the business of §9, whose SNARK compilation subsection develops the evaluation-argument role sketched here.

4.10 Secret sharing

The section opened by naming verifiable secret sharing among the classical applications of commitments; it closes by constructing it, because the threshold signatures of the FROST Guide stand on it and nothing below that volume otherwise provides it. The setting is a prime field $\mathbb{F}_{q}$ —in the sequel the scalar field of the group $\mathbb{G}$ of §4.6—and the tool is Lagrange interpolation (Math Guide, §“Lagrange interpolation”): a polynomial of degree at most $t-1$ over $\mathbb{F}_{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.42 (Shamir $t$ -of- $n$ secret sharing).

Fix a threshold $t$ and a party count $n$ with $1\leq t\leq n<q$ . To share a secret $s\in\mathbb{F}_{q}$ , the dealer samples coefficients $a_{1},\dots,a_{t-1}\xleftarrow{\$}\mathbb{F}_{q}$ independently and uniformly and forms

f(X):=s+a_{1}X+a_{2}X^{2}+\dots+a_{t-1}X^{t-1}\;\in\;\mathbb{F}_{q}[X],\qquad f% (0)=s,

a polynomial of degree at most $t-1$ with constant term the secret. Party $i\in\{1,\dots,n\}$ receives the share $s_{i}:=f(i)$ , sent privately; the identifiers $1,\dots,n$ are distinct nonzero elements of $\mathbb{F}_{q}$ because $n<q$ . Reconstruction from the shares of any set $I$ of $t$ parties is interpolation at $0$ :

s\;=\;f(0)\;=\;\sum_{i\in I}\lambda_{I,i}\,s_{i},\qquad\lambda_{I,i}:=\prod_{j% \in I,\;j\neq i}\frac{j}{j-i},

where $\lambda_{I,i}=\ell_{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,s_{i})_{i\in I}$ determine a unique polynomial of degree at most $t-1$ , which is $f$ , and the Lagrange formula $f(X)=\sum_{i\in I}s_{i}\,\ell_{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.43 (Perfect secrecy below the threshold).

Let $I$ be any set of at most $t-1$ identifiers. For every secret $s\in\mathbb{F}_{q}$ , the shares $(s_{i})_{i\in I}$ of Construction 4.42 are jointly uniform on $\mathbb{F}_{q}^{\lvert I\rvert}$ . 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 $\lvert I\rvert=t-1$ , since fewer shares are a projection of these. Fix $s$ and $I$ , and consider the map

\Sigma_{s}\colon\mathbb{F}_{q}^{t-1}\to\mathbb{F}_{q}^{t-1},\qquad(a_{1},\dots% ,a_{t-1})\mapsto\bigl{(}f(i)\bigr{)}_{i\in 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 $(y_{i})_{i\in I}$ , Lagrange interpolation through the $t$ points $(0,s)$ and $(i,y_{i})_{i\in I}$ produces a polynomial of degree at most $t-1$ with constant term $s$ , whose remaining coefficients are a preimage. So $\Sigma_{s}$ is a bijection—for every $s$ —and it carries the uniform distribution on coefficient vectors to the uniform distribution on $\mathbb{F}_{q}^{t-1}$ . The share vector is therefore uniform whatever the secret, and for any $s_{0}\neq s_{1}$ 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 half of a commitment (Proposition 4.5 in different clothing): the coalition’s view is a uniformly random point of $\mathbb{F}_{q}^{t-1}$ , consistent with every candidate secret through exactly one polynomial each. What Shamir sharing lacks is the binding half. Nothing stops a dishonest dealer from handing out 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 tell. Verifiable secret sharing repairs this by having the dealer commit to the polynomial.

Construction 4.44 (Feldman verifiable secret sharing).

Let $(\mathbb{G},q,G)$ be as in §4.6, so that $\mathbb{F}_{q}$ is the scalar field of $\mathbb{G}$ . The dealer shares $s$ as in Construction 4.42, with $f(X)=\sum_{k=0}^{t-1}a_{k}X^{k}$ and $a_{0}=s$ , and additionally broadcasts the coefficient commitments

\Phi_{k}:=[a_{k}]\,G\;\in\;\mathbb{G},\qquad k=0,\dots,t-1,

the coefficients in the exponent. Party $i$ , on receiving its private share $s_{i}$ , accepts it iff

[s_{i}]\,G\;\stackrel{{\scriptstyle?}}{{=}}\;\sum_{k=0}^{t-1}\bigl{[}i^{k}% \bigr{]}\Phi_{k}.

An honest share passes: since $a\mapsto[a]G$ is a homomorphism $\mathbb{F}_{q}\to\mathbb{G}$ , $\sum_{k}[i^{k}]\Phi_{k}=\sum_{k}[a_{k}i^{k}]G=[f(i)]G$ .

Proposition 4.45 (What the Feldman check certifies).

Because $G$ generates the prime-order group $\mathbb{G}$ , the map $a\mapsto[a]G$ is a bijection $\mathbb{F}_{q}\to\mathbb{G}$ , so the broadcast vector $(\Phi_{0},\dots,\Phi_{t-1})$ —however the dealer chose it—determines a unique polynomial $f^{*}(X):=\sum_{k}a_{k}^{*}X^{k}$ with $a_{k}^{*}=\log_{G}\Phi_{k}$ , of degree at most $t-1$ . Party $i$ ’s check passes iff $s_{i}=f^{*}(i)$ . Consequently every coalition of $t$ parties holding accepted shares reconstructs the same polynomial $f^{*}$ and the same secret $s^{*}=f^{*}(0)=\log_{G}\Phi_{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\mapsto[a]G$ . The right-hand side of the check equals $[f^{*}(i)]G$ by the homomorphism, so the equation $[s_{i}]G=[f^{*}(i)]G$ holds iff $s_{i}=f^{*}(i)$ . Accepted shares are thus evaluations of the one polynomial $f^{*}$ , and $t$ of them interpolate to it by uniqueness. □

In the language of this section, the vector $(\Phi_{k})_{k}$ is a perfectly binding commitment to the polynomial $f$ —the coefficient list committed entry by entry under the bijection $a\mapsto[a]G$ —and the share check is an evaluation check against it, verifiable by anyone because it is linear in the coefficients. Perfect binding costs hiding, as Theorem 4.8 demands.

Remark 4.46 (The leak, and where it is harmless).

Feldman sharing publishes $\Phi_{0}=[s]G$ . Secrecy below the threshold is no longer perfect: from the broadcast alone an unbounded adversary computes $s=\log_{G}\Phi_{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.43 and the $\Phi_{k}$ are then determined by interpolating in the exponent through $(0,[s]G)$ and the points $(i,[s_{i}]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 anyway; then $\Phi_{0}$ is the public key and nothing new escapes. When the secret must stay perfectly hidden, Pedersen verifiable secret sharing replaces each $\Phi_{k}$ by the Pedersen commitment $[a_{k}]G+[b_{k}]H$ of Construction 4.16, restoring perfect hiding at the price of computational binding—off this volume’s path and not constructed here. Threshold signing is the consumer: in the FROST Guide each signer holds a Shamir share of a signing key, the coefficient commitments broadcast during key generation are Feldman’s, and the Lagrange weights $\lambda_{I,i}$ recombine per-signer contributions into a single signature.