Commitment Scheme

A commitment scheme is a two-phase cryptographic primitive that allows a party (the committer) to bind itself to a chosen value by producing a short commitment string — analogous to sealing a value in an envelope — that is later opened by revealing the original value and a randomness parameter, with the scheme satisfying two security properties: binding (the committer cannot change the value after committing) and hiding (the commitment reveals nothing about the value before opening). Commitment schemes are foundational building blocks for zero-knowledge proofs, secure multi-party computation, and blockchain protocols.

Content

• Commitment schemes were introduced to cryptography by Blum in 1983 as a mechanism for coin flipping over telephone, where neither party could cheat by learning the other’s choice before committing their own. The formal definition with hiding and binding properties was crystallised by Brassard, Chaum, and Crépeau in their 1988 work on minimum disclosure proofs. Pedersen commitments (1991), based on the discrete logarithm assumption, introduced perfectly hiding and computationally binding commitments from algebraic structures, enabling the first efficient zero-knowledge proofs for committed values without hash functions. Polynomial commitment schemes — particularly KZG commitments introduced in 2010 — enabled the “succinct” part of zk-SNARKs by allowing a proof system to commit to a polynomial and later evaluate it at a verifier-chosen point with a constant-size proof.
• Technically, a basic hash commitment works as follows: to commit to value v, the committer samples randomness r and computes c = H(v || r), publishing c; to open, the committer reveals (v, r), allowing the verifier to check H(v || r) == c. Collision resistance of H enforces binding; the randomness r ensures hiding. Vector commitments extend this to commit to an ordered vector of values with proofs of individual positions — Merkle trees achieve this logarithmically using Merkle Tree structures, while KZG polynomial commitments achieve constant-size proofs using pairing-based cryptography over elliptic curves. The Pedersen commitment C = g^v * h^r in a group where discrete logarithm is hard provides information-theoretic (perfect) hiding because any value can be opened from the same commitment by choosing the appropriate r.
• Commitment schemes appear in blockchain protocols throughout the transaction and consensus lifecycle. Bitcoin’s pay-to-script-hash (P2SH) is a hash commitment to a spending condition revealed only at redemption. Ethereum’s state is committed in a Merkle Patricia Trie whose root hash is published in each block header, enabling light client verification. Rollup systems commit to transaction batches via state roots posted to Layer-1, while validity proofs using KZG commitments underpin data availability sampling in Ethereum’s danksharding design. Commit-reveal patterns in smart contracts allow participants in auctions, randomness beacons, and voting protocols to submit commitments in an open phase and reveal them simultaneously, preventing front-running.
• In 2024–2025, commitment schemes are central to the zk-proof renaissance. The PLONK proving system, using KZG polynomial commitments, has been adopted by zkSync, Polygon zkEVM, and Scroll. Transparent commitment schemes not requiring a trusted setup — using hash-based commitments in FRI (Fast Reed-Solomon IOP) — underpin StarkWare’s STARK proof system. Lattice-based commitment schemes are in active research as post-quantum alternatives to pairing-based KZG. Commitment schemes also appear in threshold signature protocols, multi-party computation (MPC) for private key generation, and verifiable delay functions (VDFs) used for on-chain randomness in proof-of-stake consensus.