A commitment scheme is the digital equivalent of placing a value in a locked box and handing it to someone. The recipient cannot open the box (the commitment is “hiding”), and the person who locked the box cannot change what is inside (the commitment is “binding”). Later, the committer reveals the key, and the recipient verifies that the revealed value matches the commitment.
This simple abstraction is foundational to modern cryptography. Commitment schemes underpin zero-knowledge proofs, secure coin flipping, verifiable auctions, blockchain transaction privacy, and voting protocols. Ethereum’s EIP-4844 (Proto-Danksharding) uses KZG polynomial commitments for blob verification. Monero’s RingCT hides transaction amounts using Pedersen commitments. Every zk-SNARK and zk-STARK proof system relies on commitment schemes as a core building block.
The scheme is defined by two properties:
Hiding: Given a commitment C, a computationally bounded (or information-theoretically unbounded, depending on the scheme) adversary cannot determine the committed value v.
Binding: After producing C, the committer cannot find two different values v and v’ that both match C. Opening to a different value than what was committed is computationally infeasible (or information-theoretically impossible).
No commitment scheme can be both perfectly hiding and perfectly binding simultaneously – a fundamental result in cryptography proved by the impossibility of unconditional oblivious transfer. Every scheme must choose: perfectly hiding with computationally binding, or perfectly binding with computationally hiding.
Hash-Based Commitments
The simplest construction uses a cryptographic hash function H. To commit to a value v:
- Choose a random blinding factor r.
- Compute C = H(v || r).
- Publish C.
To open: reveal v and r. The verifier checks that C = H(v || r).
Hiding: The random blinding factor r ensures that C reveals no information about v, because for any v, the distribution of H(v || r) over random r is indistinguishable from random (assuming H is a random oracle).
Binding: Finding v’ and r’ such that H(v || r) = H(v’ || r’) requires finding a collision in H. For SHA-256, this requires approximately 2^128 operations – computationally infeasible.
Hash-based commitments are computationally hiding and computationally binding. They are also simple, efficient (a single hash computation), and require no public parameters. Their limitation is that they support no algebraic operations – you cannot add two hash commitments and get a commitment to the sum. This is where Pedersen commitments excel.
Pedersen Commitments
Pedersen commitments, introduced by Torben Pedersen in 1991, operate on elliptic curve groups (or any group where the discrete logarithm is hard).
Setup
Choose two generators G and H of an elliptic curve group such that no one knows the discrete logarithm of H with respect to G (i.e., no one knows d such that H = d * G). This can be achieved by deriving H from G using a hash function: H = HashToCurve(“generator_H”).
Commit
To commit to a value v with blinding factor r:
C = v * G + r * H
This is a point on the elliptic curve. The commitment is published.
Open
Reveal v and r. The verifier checks that C = v * G + r * H.
Properties
Perfectly hiding. For any value v, and for a uniformly random r, the commitment C = v * G + r * H is uniformly distributed over the curve group. An adversary with unlimited computational power cannot determine v from C.
Computationally binding. To open the commitment to a different value v’ != v, the committer must find r’ such that v * G + r * H = v’ * G + r’ * H, which implies (v - v’) * G = (r’ - r) * H, which implies the committer knows the discrete logarithm of H with respect to G. By assumption, this is infeasible.
Homomorphic Property
The key advantage of Pedersen commitments: they are additively homomorphic.
Given commitments C_1 = v_1 * G + r_1 * H and C_2 = v_2 * G + r_2 * H:
C_1 + C_2 = (v_1 + v_2) * G + (r_1 + r_2) * H
This is a valid commitment to v_1 + v_2 with blinding factor r_1 + r_2. No one needs to open C_1 or C_2 to compute a commitment to their sum.
This property enables confidential transactions in cryptocurrencies. In Monero’s RingCT, each transaction input and output amount is replaced by a Pedersen commitment. The difference between input commitments and output commitments must equal a commitment to zero (plus the fee), proving that inputs equal outputs without revealing any individual amount.
For a transaction with inputs a_1, a_2 and outputs b_1, b_2, fee:
C(a_1) + C(a_2) = C(b_1) + C(b_2) + C(fee)
A verifier checks this equality without knowing a_1, a_2, b_1, b_2, or fee. The homomorphic property makes this check a simple point addition.
Vector Commitments
A vector commitment scheme allows committing to a vector of values (v_1, v_2, …, v_n) with a single commitment C, and later opening individual positions i to reveal v_i with a proof that v_i is the correct value at position i.
Merkle Trees
The most widely used vector commitment. A Merkle tree hashes pairs of values recursively up to a single root hash. To prove that v_i is at position i, the prover provides the “authentication path” – the O(log n) sibling hashes needed to recompute the root. The verifier recomputes the root and checks it matches the commitment.
Merkle trees are the backbone of blockchain state verification. Ethereum’s state trie, Bitcoin’s transaction tree, and certificate transparency logs all use Merkle trees.
Proof size: O(log n) hashes. For n = 1 million entries with SHA-256, a proof is 20 hashes * 32 bytes = 640 bytes.
KZG Polynomial Commitments
Kate, Zaverucha, and Goldberg (KZG) commitments operate on polynomials rather than individual values. They commit to a polynomial p(x) of degree d with a single elliptic curve point, and proofs of evaluation at any point are a single curve point (48 bytes on BLS12-381).
Setup: Requires a trusted setup producing powers of a secret tau: [G, tauG, tau^2G, …, tau^d*G].
Commit: Given polynomial p(x) = a_0 + a_1x + … + a_dx^d:
C = a_0 * G + a_1 * (tau * G) + ... + a_d * (tau^d * G) = p(tau) * G
Prove: To prove that p(z) = y for some evaluation point z: Compute the quotient polynomial q(x) = (p(x) - y) / (x - z). The proof is pi = q(tau) * G.
Verify: Check the pairing equation:
e(C - y*G, H) = e(pi, tau*H - z*H)
KZG commitments achieve O(1) proof size and O(1) verification time, regardless of the polynomial degree. This makes them ideal for data availability sampling in Ethereum’s scaling roadmap, where validators must verify that transaction data is available without downloading all of it.
The Ethereum KZG ceremony (2023) generated the trusted setup parameters for EIP-4844. Over 141,000 participants contributed, producing the largest trusted setup in cryptographic history.
Commitment Schemes in Zero-Knowledge Proofs
Commitments are the engine that drives zero-knowledge proof systems. A ZK proof typically follows the pattern:
- Commit: The prover commits to certain values (witness elements, intermediate computations).
- Challenge: The verifier (or a hash function in non-interactive proofs) generates a random challenge.
- Respond: The prover computes a response that, together with the commitment and challenge, convinces the verifier.
The commitment step is essential for soundness: without it, the prover could choose their “committed” values after seeing the challenge, cheating the verifier. The binding property ensures the prover is locked in.
In PLONK (a widely used zk-SNARK system), the prover commits to the wire values and permutation polynomials using KZG commitments. The verifier checks evaluation proofs at random points. The entire proof consists of a handful of KZG commitments and evaluation proofs – approximately 400 bytes total.
In STARKs, commitments are Merkle roots of polynomial evaluations. The prover commits to polynomial evaluations over a large domain, and the verifier queries specific positions, checking consistency via Merkle authentication paths. No trusted setup is required, but proof sizes are larger (tens of kilobytes).
Practical Considerations
Commitment Malleability
Some commitment schemes are malleable: given a commitment C to an unknown value v, an adversary can produce a related commitment C’ to a related value v’. For Pedersen commitments, an adversary can compute C’ = C + delta * G, which commits to v + delta. This is the homomorphic property – useful for honest applications but potentially dangerous if a protocol assumes commitments are non-malleable.
Protocols that require non-malleability typically use hash-based commitments (which are non-malleable if the hash function is modeled as a random oracle) or add non-malleability proofs to Pedersen commitments.
Equivocable and Extractable Commitments
Equivocable commitments allow a simulator (in a proof of security) to create a commitment that can be opened to any value. This is needed for proving zero-knowledge: the simulator must be able to produce valid-looking transcripts without knowing the prover’s secret.
Extractable commitments allow an extractor (in a proof of soundness) to recover the committed value from the commitment. This is needed for proving that a cheating prover cannot produce valid proofs for false statements.
Pedersen commitments are equivocable (if you know the discrete log of H with respect to G, you can open to any value) and extractable (using knowledge-of-exponent assumptions or through rewinding in interactive protocols).
Batch Verification
When verifying many commitments simultaneously, batch verification techniques can reduce the total cost. For KZG commitments, multiple evaluation proofs can be checked with a single pairing computation using random linear combinations, reducing verification from O(n) pairings to O(1) pairings plus O(n) scalar multiplications.
The Stealth Cloud Perspective
Commitment schemes address a subtle challenge in zero-knowledge architecture: how does a user prove something about their data without revealing the data?
In Stealth Cloud’s Ghost Chat, the PII engine sanitizes prompts before they reach the server. But the server has no way to verify that sanitization occurred. The client could bypass the PII engine entirely and send raw, unsanitized prompts. In a trust-minimized architecture, “trust the client” is insufficient.
A commitment-based approach would work as follows: the client commits to the raw prompt (using a Pedersen or hash commitment), runs the PII engine, and then provides a zero-knowledge proof that the sanitized prompt is a valid PII-stripped version of the committed prompt. The server verifies the proof and the commitment without ever seeing the raw prompt.
This is computationally expensive with current technology – but it represents the architectural direction. Commitment schemes are the bridge between “end-to-end encryption where the server sees nothing” and “verifiable computation where the server can confirm properties of data it never observes.”
Stealth Cloud’s key management already operates on a form of commitment: the server stores a hash of the wallet address (a commitment to the identity) rather than the address itself. The binding property ensures the user cannot claim a different identity. The hiding property ensures the server cannot recover the address from the hash. The principle scales from identity management to computation verification, with commitment schemes as the mathematical glue.