Commitment Schemes: Sealing a Value in a Digital Envelope

The core idea: two messages and two invariants

A commitment scheme is a two-phase protocol between a committer and a verifier. In the commit phase the committer picks a message m, draws fresh randomness r, computes c = Commit(m, r), and publishes c. In the later reveal (open) phase the committer discloses (m, r); the verifier recomputes and checks c ?= Commit(m, r).

Correctness is trivial — an honest opening always verifies. The security lives in two invariants that must hold simultaneously:

• Hiding. The commitment c leaks nothing about m. Formally, for any two messages m₀, m₁ the distributions Commit(m₀, ·) and Commit(m₁, ·) are indistinguishable. This protects the committer during the gap between commit and reveal.
• Binding. The committer cannot open c to two different messages. No efficient adversary can find (m, r) ≠ (m′, r′) with Commit(m, r) = Commit(m′, r′). This protects the verifier at reveal time.

Think of it as a physical envelope: sealed, the outside reveals nothing (hiding); once sealed, its contents can't be swapped (binding). The whole discipline of the field is building that envelope from math, and understanding that you can make one property information-theoretically perfect but never both.

The simplest construction — and why the salt is not optional

Given any collision-resistant hash H (SHA-256, BLAKE3), the canonical commitment is:

Commit(m, r):    r ← random 256-bit nonce
                 return H(m ‖ r)      // ‖ = length-prefixed concat

Verify(c, m, r): return c == H(m ‖ r)

Binding follows from collision resistance: two valid openings of the same c are literally a collision in H, which no efficient adversary should find. Hiding follows because r has high entropy, so H(m‖r) looks uniformly random (provable in the random-oracle model).

Now the classic trap. If you drop the salt and commit as c = H(m), binding still holds, but hiding collapses whenever the message space is small or guessable. A verifier who suspects m ∈ {"buy", "sell"} just hashes both candidates and matches — a two-entry dictionary attack. For a coin flip, m ∈ {0, 1}: the verifier trivially unmasks the bit. The nonce r is what turns a low-entropy message into a high-entropy input, making brute force infeasible over the 2²⁵⁶ nonce space. Salting is the difference between a commitment and a fingerprint. Always length-prefix or domain-separate the concatenation so that (m₁, r₁) and (m₂, r₂) can't collide by re-slicing the byte boundary.

Pedersen commitments: perfectly hiding and homomorphic

Hash commitments are only computationally hiding. For applications that need unconditional secrecy or additive structure, the standard is the Pedersen commitment (Torben Pedersen, 1991). Work in a cyclic group G of prime order q where the discrete-log problem is hard (a 256-bit elliptic curve like secp256k1 or Curve25519). Fix two generators g, h whose relative discrete log log_g(h) is unknown to everyone. Then:

Commit(m, r) = gᵐ · hʳ     (m, r ∈ ℤ_q, r uniform random)

• Perfectly hiding. For any m, the term hʳ is uniform over G, so c is uniform and independent of m — even an unbounded adversary learns nothing. Hiding here is information-theoretic, not just computational.
• Computationally binding. Opening c to (m, r) and (m′, r′) yields gᵐ⁻ᵐ′ = hʳ′⁻ʳ, which reveals log_g(h) — breaking discrete log. So binding rests on a hardness assumption.
• Additively homomorphic. Commit(m₁, r₁) · Commit(m₂, r₂) = Commit(m₁ + m₂, r₁ + r₂). You can add committed values without opening them — the property that makes confidential transactions and range proofs possible.

Notice the swap: Pedersen is perfectly hiding / computationally binding, while the hash scheme is (roughly) computationally hiding / computationally binding. This is no accident — it is forced by an impossibility result covered below.

Complexity analysis

Let n = |m| be the message length in bits and κ the security parameter (e.g. 256).

• Hash scheme. Commit hashes m‖r: Θ(n + κ) time, which is O(n) in practice, at hardware-accelerated ~1 GB/s. Verify is the same single hash, O(n). The commitment is a fixed O(κ) = 32 bytes regardless of n; the opening carries m plus a κ-bit nonce, so O(n + κ) space. Fixed-size output is a genuine feature: you can commit to a gigabyte and publish 32 bytes.
• Pedersen scheme. Commit is two scalar-by-point multiplications plus one group addition. Each mult is Θ(κ) point doublings/additions via double-and-add, so O(κ) group ops, or with a fixed-base window table O(κ / log κ). Concretely ~50–100 μs on a 256-bit curve — three to four orders of magnitude slower than a hash. The commitment is a single group element, O(κ) bytes.
• Vector commitments (Merkle tree). To commit to n values and later open any one, a Merkle tree gives O(n) build time, O(κ) root size, and O(κ log n) per-element opening proofs — the log n path of sibling hashes. Verifying one opening is O(log n) hashes. This is the workhorse behind blockchains and certificate transparency.

The dominant cost model is: hash commitments win on raw speed and size; Pedersen wins when you need homomorphism or perfect hiding; Merkle trees win when you must open one of many positions succinctly.

The impossibility: you can't have both perfectly

A recurring interview question: why not build a scheme that is both perfectly hiding and perfectly binding? It's provably impossible. Suppose perfect hiding: then for a given c, for every message m there must exist some randomness r with Commit(m, r) = c — otherwise the absence of a valid opening for m would statistically distinguish it, violating perfect hiding. But if every message has a valid opening of c, then a computationally unbounded committer can find those openings and equivocate — so binding cannot be perfect. The contrapositive gives the same wall from the other side.

• Perfectly hiding ⇒ only computationally binding (Pedersen sits here).
• Perfectly (statistically) binding ⇒ only computationally hiding (ElGamal-style commitments sit here).

So every real scheme picks which party gets the unconditional guarantee. Design rule of thumb: make hiding unconditional when the committed secret must stay private forever even against future quantum/compute (long-lived ballots, medical data); make binding unconditional when a cheating committer with huge resources must never be able to equivocate (money, consensus). This choice is the single most important decision in picking a commitment scheme.

Where commitments run at scale

Commitments are the plumbing under some of the most-used cryptographic systems:

• Coin flipping & fair randomness. Ethereum's RANDAO is a commit-reveal beacon: validators commit to random values, then reveal, and the XOR seeds block proposer selection. The commit phase stops anyone from choosing their contribution after seeing others'.
• Sealed-bid auctions & voting. Bidders commit to bids; after the deadline everyone reveals. Binding stops a bidder from changing their bid; hiding stops opponents from sniping. The same pattern underlies coercion-resistant e-voting.
• Zero-knowledge proofs. Sigma protocols and SNARKs use commitments as their first message ("commit, challenge, response"). Bulletproofs and Zcash lean on Pedersen commitments for confidential amounts; their homomorphism lets a verifier check that inputs = outputs without seeing values.
• Blockchains & transparency logs. A Merkle root is a vector commitment to a block's transactions or a log's entries; Certificate Transparency and Git commit hashes are binding commitments to whole histories.
• Verifiable secret sharing (VSS). Feldman/Pedersen VSS commits to polynomial coefficients so shareholders can verify their shares are consistent — the backbone of threshold signatures and DKG.

The standard references are Blum's 1981 coin-flipping paper, Pedersen's 1991 CRYPTO paper, and Goldreich's Foundations of Cryptography, Vol. 1, §4 for the formal definitions.

Pitfalls, edge cases, and variants

Commitments look trivial and break in subtle ways. The recurring failure modes:

• Missing or reused nonce. Committing H(m) over a small domain, or reusing r across two commitments, destroys hiding. Always draw fresh, CSPRNG randomness per commitment.
• Malleable concatenation. H(a ‖ b) without length-prefixing lets (a‖b) re-parse as (a′‖b′), admitting two openings — a binding break disguised as an encoding bug. Length-prefix every field.
• The selective-abort / non-reveal problem. A committer can simply refuse to open. Protocols must define a penalty (forfeit stake, treat as default bid) or use timed / non-interactive commitments so a value can be forced open after a delay.
• Binding vs. hiding mismatch. Using a computationally-hiding scheme for a secret that must survive decades of Moore's-law/quantum progress is a design error; prefer perfectly hiding (Pedersen) there.

Useful variants extend the two-message core:

• Trapdoor / equivocable commitments — a party holding a trapdoor can open to any value; essential for simulator-based proofs in the UC model.
• Vector & polynomial commitments — KZG commits to a degree-d polynomial in one group element with O(1)-size openings, powering PLONK and Ethereum's EIP-4844 blobs.
• Chameleon hashes — commitments with a trapdoor for controlled collisions, used in redactable signatures.

Hash-based vs. Pedersen commitments across the properties that matter

Property	Hash: c = H(m‖r)	Pedersen: c = gᵐhʳ
Hiding	Computational (random-oracle)	Perfect / unconditional
Binding	Computational (collision-resist)	Computational (discrete log)
Homomorphic	No	Yes: C(m₁)·C(m₂)=C(m₁+m₂)
Commit cost	O(|m|) hashing, ~1 μs	2 EC mults, ~50–100 μs
Commitment size	32 bytes (fixed)	32–48 bytes (one point)
Assumption	SHA-256 preimage/collision	Discrete log in group G