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{\mathdollar } \{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.

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

Why this matters

Demo

Try it yourself

References