Each column is one possible commitment value c. The bar above the line counts the nonces that send bit 0 to c, the bar below counts those that send bit 1 there. Where only one colour reaches a column, seeing that c tells Bob the bit. Where both reach it, Alice could open it either way. The solid part of each bar is the overlap, min(D₀, D₁), and the faded part is the excess. The overlap adds up to exactly 1 − δ.
You are Bob. Alice is in another city and neither of you trusts the other. This is the real protocol, with SHA-256 and a 128-bit nonce.
With Alice cheats on, she waits for your call and then opens whichever bit makes her win, reusing her nonce. To get away with it she would need a second nonce that hashes to the same 256 bits under the other bit. The attack tab shows what that costs.
Find two nonces with h(0, n₀) = h(1, n₁) on the k-bit hash, nonces unlimited. Draw from both sides until the lists meet: the birthday paradox says this takes about √(π·2ᵏ) hashes.
Alice commits honestly with the scheme on screen. Bob tries all 2ʳ nonces under both bits and keeps the bits that fit.
Both attacks always succeed in the toy. At 256 bits of hash and 128 bits of nonce they still exist, but they take longer than the age of the universe. That gap is the whole escape from the trade-off: real commitments are secure against a bounded opponent, not an unlimited one.
In 1981 Manuel Blum asked how two people who don't trust each other could flip a fair coin over the telephone. If Alice flips and reports, she can lie. If Bob calls first, Alice hears the call before she reports. His answer was “Coin flipping by telephone” (CRYPTO 1981): Alice commits to a bit, Bob calls, Alice opens, and the coin is the XOR of the two. If either of them chooses at random, the XOR is a fair coin, whatever the other does.
A commitment is a sealed envelope made of arithmetic. It needs two properties. Hiding: Bob learns nothing about the bit from the envelope. Binding: Alice can't open it to a different bit later.
Shrink the scheme until it can be counted. A nonce is one of 2ʳ values, a commitment one of 2ᵏ. Count how many nonces send each bit to each value: that gives two histograms, D₀ and D₁, and they are the stage above.
Bob's best guess at the bit from c is right with probability (1 + δ)/2, where δ is the statistical distance:
Alice can lie about c exactly when both bits reach it. Call p the chance that an honest commitment lands on such a value. Every column where the bars overlap contributes min(D₀, D₁) to both quantities, and those minimums sum to 1 − δ. So for every scheme there is:
Perfect hiding (δ = 0) forces p = 1: every commitment opens both ways. Perfect binding (p = 0) forces δ = 1: Bob reads the bit straight off c. Shift is the first extreme, tag is the second, and hash sits in between, moving as you trade r against k.
The theorem is about an opponent with unlimited time. Real schemes give up one property against that opponent and keep it against anyone who has to do the work. A SHA-256 commitment with a long nonce is statistically hiding and computationally binding: the double openings exist, but finding one is a 2¹²⁸-step search. Pedersen's commitment (1991) makes the same trade with discrete logarithms in place of a hash.
This is the first page of a series on things that can be proven without being shown. The next one uses a commitment for every vertex of a graph to prove a graph has a 3-colouring without revealing a single colour.
The engine, commit.js, is the only copy of the maths, and the page and commit.selftest.mjs both import it: 11,170 checks. They cover SHA-256 against the NIST vectors and node's crypto; commitments that open only one way; Blum's coin fair whenever one side is uniform; p ≥ 1 − δ on 2,960 schemes, including 2,000 random functions; Bob's brute force agreeing with the census; and the mean cost of a double opening matching √(π·2ᵏ) at k = 8, 12 and 16.