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.

Prompt your AI

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

1. Basics & terminology

In one paragraph, explain the random oracle model to someone who knows what a hash function is. What's the gap between a real hash and a random oracle, and why do we usually pretend there isn't one?

2. Why it works (the mechanism)

Walk me through how the random oracle model is used in a security proof. Specifically, what does it mean for a proof to 'program the oracle' or 'observe the adversary's queries,' and why are these moves available in the model but not in reality?

3. Advanced — application & what's next

Read the Canetti–Goldreich–Halevi result that some schemes are secure in the ROM but insecure under any real hash. Argue why we should still treat ROM proofs as strong evidence of security in practice, and what kinds of constructions we should be cautious about even with a clean ROM proof (hint: contrived hash dependencies).

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