Capstok — learn by doing

Why this matters

A commitment scheme is the cryptographic equivalent of sealing a value in a tamper-evident envelope: you publish the envelope (the commitment) without revealing the value, and later you can open it to prove what was inside. Every ZK proof system needs commitments, because the prover has to make claims about hidden values that the verifier will eventually check, and we need both that the prover can't change their mind (binding) and that the verifier learns nothing prematurely (hiding). These two properties are the entire interface; how you achieve them — via hashes, group exponentiations, or polynomial pairings — is implementation detail. The trap is treating 'commit' as an opaque primitive and never internalising that binding and hiding sit in tension (perfect binding implies only computational hiding, and vice versa). Understand the trade-off now and every later construction in this course will make sense.

Demo

A commitment scheme is a pair of algorithms $(\text{Commit}, \text{Open})$ . Commit takes a message $m$ and randomness $r$ and produces $c = \text{Commit}(m, r)$ . Open reveals $(m, r)$ and the verifier checks $c \stackrel{?}{=} \text{Commit}(m, r)$ . Hiding: $c$ reveals nothing about $m$ . Binding: no efficient adversary finds $(m, r), (m', r')$ with $m \neq m'$ and $\text{Commit}(m, r) = \text{Commit}(m', r')$ .

\text{Hiding: } \forall m_0, m_1:\ \text{Commit}(m_0, r) \stackrel{c}{\approx} \text{Commit}(m_1, r),\ r \xleftarrow{\$} \mathcal{R}.\\ \text{Binding: } \Pr_{\mathcal{A}}[\text{Commit}(m, r) = \text{Commit}(m', r'),\ m \neq m'] \leq \text{negl}(\lambda).

Try it yourself

Run the snippet and observe that the toy 'commitment' opens correctly to the original $m=42$ — and opens just as well to $m'=99$ with a different $r'$ . This scheme is perfectly hiding but not binding at all, demonstrating the tension between the two properties.
Repeat the experiment 1,000 times with random $m^{}$ values and confirm every one of them opens successfully. Real commitment schemes need a one-way function so this attack stops working.

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain hiding and binding to someone who has seen hash functions but never a commitment scheme. Use the sealed-envelope analogy and explain what specifically goes in the envelope and what stays outside.

2. Why it works (the mechanism)

Walk me through the formal hiding and binding games (the experiments an adversary plays), and why hiding has to be defined relative to a *distribution* on messages while binding is defined as a single existence claim.

3. Advanced — application & what's next

Explain the impossibility result: a commitment scheme cannot simultaneously be perfectly hiding *and* perfectly binding. Sketch the information-theoretic argument (a commitment has fixed bit-length, so either it determines $m$ exactly or it loses information about $m$).

References

'

m'

// main.go — run: go run main.go
// Toy commitment: c = (m + r) mod p — illustrative, NOT secure.
package main

import (
	"fmt"
	"math/big"
)

var p *big.Int

func commit(m, r *big.Int) *big.Int {
	result := new(big.Int).Add(m, r)
	return result.Mod(result, p)
}

func open(c, m, r *big.Int) bool {
	return commit(m, r).Cmp(c) == 0
}

func main() {
	// large Mersenne prime: 2^61 - 1
	p = new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 61), big.NewInt(1))

	// Use a fixed r for reproducibility (mirrors random.seed(0) + first randrange)
	r, _ := new(big.Int).SetString("1000000000000000003", 10)
	m := big.NewInt(42)

	c := commit(m, r)
	fmt.Println("commitment   :", c)
	fmt.Println("honest open  :", open(c, m, r))

	// Hiding: c is uniform over F_p when r is uniform, so c reveals 0 bits of m.
	// Binding failure: given any c, an adversary picks any m' and sets r' = c - m'.
	mPrime := big.NewInt(99)
	rPrime := new(big.Int).Sub(c, mPrime)
	rPrime.Mod(rPrime, p)
	fmt.Println("malicious open to", mPrime, ":", open(c, mPrime, rPrime)) // true!
}

Run: go run main.go

Commitment schemes — hiding and binding