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.
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.
A commitment scheme for a message space and randomness space is a triple of algorithms :
The algorithm is PPT (§1.1) and outputs public parameters , which implicitly determine the message space and randomness space and are an implicit input to the remaining algorithms.
The algorithm , for
The algorithm is deterministic and outputs a bit: (accept) or (reject).
Correctness requires that honestly produced commitments open:
for all in the support of , all
The pair is called the opening (or
decommitment) of . Unless stated otherwise, every scheme in
this volume is canonically opening:
recomputes and checks equality with
. For such a scheme correctness holds automatically, and a valid
opening of is precisely a pair with
In the commit phase the sender transmits and nothing else; in the reveal phase it transmits the opening and the receiver runs . A setup phase producing precedes both; who runs , 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.
Commitment schemes divide by how much trust their parameters demand.
Common reference string (CRS). A trusted party runs 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.
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 samples and discards a secret.
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).
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.
Let be a commitment scheme and
The challenger runs
The adversary outputs two messages
The challenger samples
The adversary outputs a bit , which is the output of the experiment.
The hiding advantage of is
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 for every adversary and every .
A commitment scheme is perfectly hiding if and only
if for every in the support of and every
pair
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 probability could exhibit large distance without granting any adversary noticeable advantage.)
Fix and
For a commitment scheme and adversary , the game runs as follows.
The challenger runs
The adversary outputs a commitment and two openings and .
The game outputs iff
The binding advantage of is
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 for every adversary and every .
For a canonically opening scheme and fixed , two openings collide,
that is, win the binding game, precisely when
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 . 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.
Let be a canonically opening commitment scheme with
Fix any in the support of and
any two distinct messages
be the set of attainable commitments to , and let be the
distribution of for uniform .
Perfect hiding makes and identical
(Proposition 4.5); identical
distributions have identical supports, so
and then
Information-theoretically the theorem counts the bits the commitment
carries. Perfect binding forces the map
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.
The simplest construction hashes the message together with fresh
randomness. It needs two properties from §3: a hash
function
Let
opened canonically. There are no nontrivial public parameters beyond the choice of —the scheme lives in the plain model of Remark 4.3.
If is collision resistant, the hash commitment is computationally binding.
Suppose wins the binding game: it outputs with
valid openings , and
Model as a random oracle (Definition 3.13). For
messages of length and randomness length
The challenge commitment is
The deterministic commitment
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 queries against an -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.
The Pedersen commitment works in a prime-order group rather than on bit
strings. Let be a cyclic group of prime order , written
additively: for a point
The algorithm runs
opened canonically.
The parameters are two generators and whose relative
discrete logarithm
The Pedersen commitment is perfectly hiding.
Fix any attainable
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
The algebraic relation comes first. A double opening gives
The case
A double opening therefore determines the discrete log of .
The reduction is as follows. On a DLog challenge , the
algorithm sets
and ’s overhead over is a constant number of field operations. □
Any party who knows
then
For all
and more generally, for all scalars
Expand and regroup, using commutativity of in , the
identity
Zcash uses the homomorphism for value balancing. Each transaction value
is committed as
We run the balance check of Remark 4.21 in a
group small enough to follow by hand. Take the primes
No discrete logarithm in is hard: trying the exponents in
turn gives
A transaction spends a note of value
| note | value | trapdoor | |
|---|---|---|---|
| spent | |||
| created | |||
| created |
Cancellation. The verifier divides the spent commitment by the
created ones and by the balance under ,
The exponents of cancel,
Wrap-around. Since
Range. Requiring each of
Prime order. Both theorems above use that is prime: the
hiding proof of Theorem 4.17 needs
A single group element can commit to a vector of scalars rather than a single scalar.
On input and a length
where
The Pedersen vector commitment is perfectly hiding, and computationally binding under the DLog assumption in .
Hiding. Exactly as in Theorem 4.17: for uniform the blinding term is uniform on , so the commitment is uniform on regardless of the message vector.
Binding. A double opening with
with not all coefficients zero. The reduction must
extract a single logarithm from a relation among
and resamples any pair whose generator lands on . Each
result is uniform on
Since the coefficient vector is nonzero and the -coordinates
are uniform and independent of it, is uniform on ,
hence nonzero with probability
The vector commitment is compressing: field elements (plus the randomness) map to a single group element, exponentially shorter than the message for large . Compression is incompatible with statistical binding for a counting reason: there are message vectors and only 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.
The vector commitment remains additively homomorphic in both message
and randomness, componentwise:
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.
Split the message into chunks
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.
Suppose no efficient algorithm finds a nontrivial relation
A collision
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.
Split the message into pieces
with entries shared by every instance, and the base point is personalised (§3.5) to the enclosing use—a byte string naming it, such as a note-commitment or Merkle-hash domain—by taking that string as the message:
Both derivations are nothing-up-my-sleeve
(Construction 3.24), so no party knows any
discrete-log relation among
and outputs the point
the integer coefficients are powers of two determined by position alone, and the message enters only through which generator each piece selects.
Model the table entries and the base point as
independent uniform generators (the nothing-up-my-sleeve
hash-to-curve derivation covers 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
Let
Regroup over the distinct table generators: for each value
and the relation reads
If instead the piece counts differ, say
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
The deployed hash differs from the point hash in two ways. First, the deployed applies the Pallas coordinate extractor to , returning its -coordinate. Collision resistance survives the extraction: equal -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.
Fix one further independent generator , hashed to the curve
with its own domain string, so that no discrete-log relation between
and
Hiding is inherited unchanged from Pedersen: by the argument of Theorem 4.17, is uniform on for uniform , so the commitment distribution is independent of , 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 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 -coordinate extraction—the specification’s —and returns a base-field element.
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.
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.
Fix a field and a degree bound . A polynomial commitment scheme (PCS) is a tuple :
The algorithm outputs public parameters supporting degree at most ;
the algorithm outputs a
commitment to a polynomial
the algorithm outputs a bit, verifying that commits to the whole polynomial ;
the algorithm , for an
evaluation point
the algorithm 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
, a point , and two accepting proofs for distinct claimed
values
A single short commitment can support queries at arbitrary points because polynomials are rigid: a nonzero polynomial of degree at most has at most roots (Math Guide, §“The Schwartz–Zippel lemma”), so two distinct polynomials of degree at most agree on at most 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 , so evaluation binding does not follow from the binding of ; 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.
The pairing-based scheme of Kate, Zaverucha, and Goldberg achieves constant-size proofs by encoding a secret evaluation point in the parameters.
Let
and discards . The commitment to
computable from by anyone, without knowledge of .
To prove
is a genuine polynomial precisely because
which, by bilinearity, is exactly the in-the-exponent form of the
polynomial identity
Evaluation binding of KZG rests on the -strong Diffie–Hellman assumption in the bilinear group: given the powers , it is infeasible to produce for any of one’s choosing.
Two accepting proofs
exactly the element the assumption declares infeasible. □
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 .
Its setup is trusted: the secret is a global trapdoor. Anyone
who learns can forge accepting evaluation proofs for
false statements—for any commitment , any point ,
and any desired value , the element
The transparent alternative commits to the coefficient vector with the Pedersen vector commitment and replaces the pairing check by a recursive argument.
Let
The construction uses no pairings and no trusted setup.
Evaluation is an inner product: writing
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 and
) to account for the mixed terms; after
The inner-product polynomial commitment has: transparent setup (public-coin parameters, no trapdoor); evaluation proofs of group elements; and -group-operation verification, batchable across proofs. Its binding and evaluation binding reduce to the discrete logarithm assumption in .
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
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 . 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.
As stated, the KZG commitment is binding but not hiding: it is a deterministic function of , 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 using an extra setup element , while the IPA commitment of Construction 4.39 already carries its 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.
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.
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 —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
Fix a threshold and a party count with
a polynomial of degree at most
where
Correctness of reconstruction is the interpolation theorem: the
points determine a unique polynomial of degree
at most
Let be any set of at most
It suffices to treat
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
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
Let be as in §4.6, so
that is the scalar field of . The dealer shares
as in Construction 4.43, with
the coefficients in the exponent. Party , on receiving its private share , accepts it iff
An honest share passes: since
Because generates the prime-order group , the map
Both claims are injectivity of
The vector is a
perfectly binding commitment to the polynomial —the
coefficient list committed entry by entry under the bijection
Feldman sharing publishes