Capstok — learn by doing

Why this matters

The simplest concrete commitment scheme is $c = H(m \| r)$ where $H$ is a cryptographic hash. It's used everywhere — STARKs, Merkle trees, Fiat–Shamir transcripts, sealed-bid auctions — because it's fast, post-quantum-friendly, and has no trusted setup. But it's only secure under non-trivial assumptions about $H$ : collision resistance gives binding, and 'random-oracle-like' behaviour gives hiding. Spelling out exactly which property of $H$ buys which property of the commitment is the point of this task. Once you can do that, you can read every Merkle-based ZK paper and immediately see which assumptions are doing the work.

Demo

Let $H : \{0,1\}^* \to \{0,1\}^n$ be a cryptographic hash. Define $\text{Commit}(m, r) = H(m \| r)$ where $r$ is uniform in $\{0,1\}^\lambda$ . Binding follows from collision resistance of $H$ . Hiding follows from $H$ being a one-way function on the high-entropy input $m \| r$ — formally, modelled as a random oracle, $H(m \| r)$ is uniform and independent of $m$ .

c = H(m \,\|\, r),\ r \xleftarrow{\$} \{0,1\}^\lambda. \quad \text{Binding} \Leftarrow \text{collision-resistance of } H. \quad \text{Hiding} \Leftarrow H \text{ is a random oracle on } m \| r.

Try it yourself

Run the snippet and verify that without randomness $r$ , an attacker recovers a low-entropy message $m \in \{\text{yes, no, maybe}\}$ in three hash computations. Adding a 256-bit $r$ makes the same attack require $2^{256}$ work.
Implement a sealed-bid auction simulation: three bidders commit to bids, then reveal. Confirm that no bidder can change their bid after seeing others' commitments, and that no bidder learns others' bids before the reveal phase.
Try to break binding by brute force: generate commitments of random messages with random , and search for collisions. By the birthday bound you expect a collision around , so for SHA-256 () you'd need — confirm that 1M attempts find none.

Prompt your AI

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

1. Basics & terminology

In one paragraph, explain how SHA-256 with a 256-bit random nonce gives a usable commitment scheme. Why does the nonce matter — what attack works without it?

2. Why it works (the mechanism)

Walk me through the proofs that hash-based commitments are (a) computationally binding under collision resistance and (b) computationally hiding in the random-oracle model. Where exactly does each assumption show up in the reduction?

3. Advanced — application & what's next

STARKs use hash-based commitments throughout (Merkle trees of polynomial evaluations) and are therefore plausibly post-quantum, while Pedersen commitments are not. Explain *why* the post-quantum status differs, and what that buys you in practice (transparent setup, conjectured PQ security) at the cost of larger proofs.

References

2^{20}

2^{20}

// main.go
package main

import (
	"crypto/rand"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
)

func commit(m, r []byte) []byte {
	h := sha256.New()
	h.Write(m)
	h.Write(r)
	return h.Sum(nil)
}

func open(c, m, r []byte) bool {
	got := commit(m, r)
	if len(got) != len(c) {
		return false
	}
	for i := range got {
		if got[i] != c[i] {
			return false
		}
	}
	return true
}

func main() {
	// Honest flow
	m := []byte("pay alice 100 sats")
	r := make([]byte, 32) // 256-bit randomness
	rand.Read(r)
	c := commit(m, r)
	fmt.Printf("commitment : %s ...\n", hex.EncodeToString(c)[:32])
	fmt.Printf("open       : %v\n", open(c, m, r))

	// Without randomness, the scheme is NOT hiding (low-entropy m is brute-forceable).
	mLow := []byte("yes") // only a few likely messages
	sum := sha256.Sum256(mLow)
	cNoR := sum[:]
	// Attacker tries all small messages:
	for _, guess := range [][]byte{[]byte("yes"), []byte("no"), []byte("maybe")} {
		gs := sha256.Sum256(guess)
		if hex.EncodeToString(gs[:]) == hex.EncodeToString(cNoR) {
			fmt.Printf("Recovered low-entropy message without randomness: %s\n", guess)
			break
		}
	}
}

Run: go run main.go

Hash-based commitments