Capstok — learn by doing

Why this matters

The random oracle model (ROM) is the simplifying fiction that lets us prove security for protocols using hash functions. We pretend $H$ is a truly random function — a public oracle that returns independent uniform outputs on fresh inputs and consistent outputs on repeated ones — and prove the protocol secure assuming that. In reality $H$ is SHA-256 or Poseidon, which are emphatically not random functions, but the ROM tracks their security behaviour so well in practice that essentially every Fiat–Shamir-transformed ZK proof (i.e. every non-interactive ZKP you'll deploy) lives in this model. Knowing what the ROM does and doesn't justify is the line between proofs you can rely on and proofs that look fine until someone instantiates the hash. This is the last piece of toolkit you need before constructing real ZK arguments.

Demo

In the ROM, all parties (including adversaries) have query access to a public function $\mathcal{O} : \{0,1\}^* \to \{0,1\}^n$ chosen uniformly at random. The adversary's only knowledge of $\mathcal{O}$ is the set of input/output pairs it has queried so far. Security proofs exploit this: any output not yet queried is uniformly distributed and independent of everything else.

\mathcal{O} : \{0,1\}^* \to \{0,1\}^n,\ \mathcal{O} \sim \text{Uniform}(\text{functions } \{0,1\}^* \to \{0,1\}^n).\\ \Pr[\mathcal{O}(x) = y \mid x \text{ unqueried}] = 2^{-n}.

Try it yourself

Run the snippet. Verify that querying the oracle on the same input twice gives the same output, but two different inputs give independent uniform outputs.
Estimate, by experiment, the probability that two random 64-bit inputs collide under a 32-bit oracle. Run 10,000 pairs and count collisions; you should see roughly $10^4 / 2^{32} \approx 2 \times 10^{-6}$ — i.e. essentially none, matching the theoretical bound.
Implement a Fiat–Shamir transform of a toy 3-move $\Sigma$ -protocol (commit, challenge, response). Replace the verifier's random challenge with , and confirm the prover can no longer cheat by guessing the challenge — they're committed to the commitment first.

References

// main.go
// Lazy-sampling random oracle: simulate a 'truly random' hash by caching outputs.
package main

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

type RandomOracle struct {
	cache   map[string][]byte
	bytesOut int
	Queries int
}

func NewRandomOracle(outputBits int) *RandomOracle {
	return &RandomOracle{
		cache:    make(map[string][]byte),
		bytesOut: outputBits / 8,
	}
}

func (ro *RandomOracle) Query(x []byte) []byte {
	ro.Queries++
	key := string(x)
	if _, ok := ro.cache[key]; !ok {
		buf := make([]byte, ro.bytesOut)
		rand.Read(buf)
		ro.cache[key] = buf
	}
	return ro.cache[key]
}

func main() {
	O := NewRandomOracle(128)

	fmt.Printf("O(\"alice\") = %s\n", hex.EncodeToString(O.Query([]byte("alice"))))
	fmt.Printf("Same input  = %s\n", hex.EncodeToString(O.Query([]byte("alice")))) // consistent
	fmt.Printf("Diff input  = %s\n", hex.EncodeToString(O.Query([]byte("bob"))))   // uniform & independent
	fmt.Printf("Total queries (incl. repeats): %d\n", O.Queries)

	// Fiat-Shamir mini-demo: turn an interactive challenge into a non-interactive one
	// by hashing the transcript. ROM is what lets us prove this transformation safe.
	prefix := []byte("commitment_round_1=")
	nonce := make([]byte, 32)
	rand.Read(nonce)
	transcript := append(prefix, nonce...)
	challenge := O.Query(transcript) // in real life: SHA-256(transcript)
	fmt.Printf("Fiat-Shamir challenge: %s\n", hex.EncodeToString(challenge))
}

Run: go run main.go

Pretending the Hash Is Truly Random (Random Oracle Model)

Why this matters

Demo

Try it yourself

References