A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A commitment scheme lets a party commit to a value while keeping it hidden (hiding), with the guarantee that they cannot later change the committed value (binding). Think of sealing a value in an envelope: the envelope hides the value, and you cannot change it after sealing. Commitments have two phases: commit (produce a commitment c to value v) and reveal (open c to show v). Hash-based commitments (c = H(v || r) for random r) provide computational hiding and binding. Pedersen commitments (c = gv * hr) provide information-theoretic hiding with computational binding. Commitments are essential building blocks for zero-knowledge proofs, coin-flipping protocols, secure computation, and blockchain applications.
A commitment scheme is one of the most fundamental primitives in cryptography, enabling a party to "lock in" a value while keeping it secret, and later reveal it with proof that they haven't changed it. The protocol has two phases: in the commit phase, the committer produces a commitment c to a value v (like sealing v in an envelope). In the reveal phase, the committer opens c by revealing v and any randomness used, and anyone can verify that c was indeed a commitment to v. Two security properties must hold: hiding (the commitment reveals nothing about v to an observer) and binding (the committer cannot open c to a different value v').
The simplest construction is hash-based: c = H(v || r) where r is a random nonce. Revealing means sending v and r; verification checks that H(v || r) = c. Hiding holds because the random r makes c computationally indistinguishable from a random hash output (even if v comes from a small set). Binding holds because finding v' != v and r' with H(v' || r') = H(v || r) requires a hash collision — computationally infeasible. The Pedersen commitment (c = gv * hr in a group where log_g(h) is unknown) achieves information-theoretic hiding: for any c and any target v', there exists an r' making c = gv' * hr', so the commitment is consistent with every possible value — no computation can extract v. Binding is computational: opening to two different values would reveal log_g(h).
A fundamental impossibility result constrains the design space: perfect hiding and perfect binding cannot coexist. If the commitment is consistent with every value (perfect hiding), the committer could in principle find an alternative opening (breaking perfect binding, though this requires solving a hard problem). If the commitment uniquely determines the value (perfect binding), an unbounded adversary could find that value (breaking perfect hiding). Every scheme must choose one property to be information-theoretic and the other computational.
Commitments are ubiquitous in cryptographic protocols. Zero-knowledge proofs use commitments to let the prover lock in their responses before seeing the verifier's challenges (preventing cheating). Fair coin-flipping (Blum's protocol) uses commitments so neither party can bias the outcome. Secure computation protocols use commitments to enforce honest behavior. Blockchain applications use commitments extensively: Merkle trees (vector commitments for block contents), Pedersen commitments (hiding transaction amounts in confidential transactions), and polynomial commitments (KZG, used in blockchain proof systems). The humble commitment — "I've decided, but I'm not telling you yet" — is one of the most versatile building blocks in the entire cryptographic toolkit.