Verifying the Clock in Parallel

The last three pages built the producer’s side of the clock. A Clock Made of Hashes showed why h = sha256(h) cannot be faked without doing the work; Stamping Events Into Time folded events in as sha256(state || event); Ticks, Slots, and Hashes-per-Tick gave the stream a cadence. In every one of those pages, the point was the same: building the chain is strictly sequential, so its length is honest proof that time passed.

This page is the other half of the deal — the half that makes the whole scheme pay off. Building the clock is slow and serial. Checking it is fast and parallel. A verifier replays the chain from genesis and redoes every hash the producer did — the same total work — yet it can spread that work across all its cores and finish in a fraction of the time, while a forger trying to fake the chain gets no such help. That asymmetry is why PoH is worth the trouble, and it is what we build up here, grounded in the real verify() function and its tamper tests in rust/solmini/src/poh.rs.

What “verify” actually has to prove

A verifier is handed two things: the genesis hash (the agreed starting state, sha256(seed)) and a list of Entry checkpoints the producer emitted. Each entry claims: “starting from wherever the previous entry ended, I did num_hashes hashes, and here is the resulting hash.” The verifier’s whole job is to decide whether every one of those claims is true.

Recall the checkpoint type from the previous pages:

pub struct Entry {
    pub num_hashes: u64,       // hashes done since the previous entry (>= 1)
    pub hash: Hash,            // the chain state right after this entry
    pub mixin: Option<Hash>,   // Some(x) if the last hash folded an event in
}

An entry is a sealed promise about a segment of the timeline. num_hashes is how much time the segment represents; hash is where the chain stood at the end of it; mixin says whether an event was recorded on the segment’s final hash. To verify the whole chain, the verifier reproduces every segment in turn and checks that its recomputed ending hash matches the one the producer wrote down.

Walking through verify()

Here is the entire verifier from the companion crate. It is short on purpose — the security argument has to fit in your head.

pub fn verify(start: Hash, entries: &[Entry]) -> bool {
    let mut cur = start;                       // begin at genesis
    for e in entries {
        if e.num_hashes == 0 {
            return false;                      // an entry with no work is not a checkpoint
        }
        match e.mixin {
            None => {
                // a tick: redo num_hashes bare hashes
                for _ in 0..e.num_hashes {
                    cur = hash_once(&cur);     // cur = sha256(cur)
                }
            }
            Some(mix) => {
                // a record: num_hashes - 1 bare hashes, then one mixin hash
                for _ in 0..e.num_hashes - 1 {
                    cur = hash_once(&cur);
                }
                cur = hash_with(&cur, &mix);   // cur = sha256(cur || mix)
            }
        }
        if cur != e.hash {
            return false;                      // recomputed hash disagrees -> reject
        }
    }
    true
}

Read it as three rules:

1. Start at genesis. cur begins at start, the same sha256(seed) the producer began from. Verifier and producer must agree on genesis; without a shared starting hash there is nothing to check.
2. Redo the exact work each entry claims. For a tick (mixin == None) the verifier does num_hashes bare hash_once calls. For a record (mixin == Some(mix)) it does num_hashes - 1 bare hashes and then one hash_with(&cur, &mix) — folding in the recorded event on the final hash, exactly as record() did on the producer side. This is why the entry carries the mixin: without it, the verifier could not reproduce the segment’s last step.
3. Compare, then advance. After redoing the segment, cur is what the verifier derived. If it does not equal e.hash — the value the producer claimed — the chain is rejected. If it matches, cur becomes the starting state for the next entry and the loop continues.

The num_hashes == 0 guard matters more than it looks. A zero-hash entry would represent “a checkpoint with no elapsed work,” which is a contradiction — it would let a forger insert boundaries for free. Every entry must cost at least one real hash.

   start ─►( redo e0.num_hashes )─►[cur]  ==? e0.hash   ─►
                                    │  match, cur := e0.hash
                                    ▼
         ─►( redo e1.num_hashes )─►[cur]  ==? e1.hash   ─►
                                    │  match, cur := e1.hash
                                    ▼
         ─►( redo e2.num_hashes )─►[cur]  ==? e2.hash   ─►  … all true → verify() == true

Notice what the verifier is not doing. It is not trusting any hash the producer wrote — it recomputes every one and only uses the recorded value as a target to compare against. The recorded hashes are claims; the recomputed hashes are proof.

Why verification is embarrassingly parallel

Here is the pivot. Producing the chain is serial because each hash needs the previous one as input — you literally cannot compute hash N+1 until you hold hash N. So the dependency chain runs the length of the whole stream and no core can help another.

But verification does not face that constraint, because of one design choice we made pages ago: every Entry records its own ending hash. And an entry’s ending hash is exactly the starting hash of the next segment. That means a verifier already knows, up front, both endpoints of every segment: the start (the previous entry’s hash) and the claimed end (this entry’s hash). It does not need to wait for segment i to finish before it can begin segment i+1 — it already has segment i+1’s starting point written down.

 entry:      e0                e1                e2                e3
 hash:      H0                H1                H2                H3
             │                 │                 │                 │
 segment:  [start..H0]       [H0..H1]          [H1..H2]          [H2..H3]
 core:       core 0            core 1            core 2            core 3
             │                 │                 │                 │
             └── recompute ────┴── recompute ────┴── recompute ────┘
                 and check         and check         and check
                 == H0?            == H1?            == H2? …

Each core is handed one segment: a starting hash, a num_hashes, an optional mixin, and a claimed ending hash. It redoes that segment’s hashes in isolation and reports one bit — did my recomputed end match the recorded end? If all segments pass on all cores, the chain verifies. The segments never talk to each other. This is the textbook shape of an embarrassingly parallel problem: no coordination, no shared state, just independent chunks and a final AND of the results.

The companion verify() above runs the segments in a plain loop for clarity. That is a presentation choice, not a limitation — the data structure permits full parallelism, and real Solana verifiers exploit it. What makes it possible is entirely the Entry.hash field pinning each boundary.

Under the hood — the sequential/parallel asymmetry, stated precisely

Let the chain contain T total hashes (total_hashes(&entries), the sum of every num_hashes). Then:

• Production cost: T hashes, strictly one after another. No parallelism is available, ever. Wall-clock time to produce ≈ T / rate_per_core.
• Verification cost: also T hashes — the verifier redoes exactly the same work (this is not a cheaper algorithm). But with K cores splitting the segments, wall-clock time to verify ≈ T / (K × rate_per_core).

So a verifier with K cores checks the chain roughly K times faster than it could have produced it. And the crucial part: a forger gets no such speedup. To fabricate a chain of length T, the forger must actually compute T sequential hashes — the production side is serial for the attacker too. There is no parallel shortcut to creating a valid chain, only to checking one. That is the whole leverage of Proof of History: honest verification rides on many cores, dishonest production is stuck on one.

By the numbers — K cores, same work, K× faster check

Suppose a slot’s worth of PoH contains T = 12,800,000 hashes and one core does 4,000,000 SHA-256 hashes/sec (illustrative — the real rate swings with the chip and SHA extensions):

   produce (serial, 1 core):   12,800,000 / 4,000,000              = 3.2 s
   verify  (serial, 1 core):   12,800,000 / 4,000,000              = 3.2 s   (same work!)
   verify  (parallel, 8 cores): 12,800,000 / (8 × 4,000,000)       = 0.4 s

Same 12.8M hashes either way — verification is not a cheaper computation. It is the same computation that happens to split across cores, so 8 cores check it 8× faster than one core could ever have built it. The forger, having to build a fresh serial chain, is stuck at the 3.2 s figure with no way to divide it.

The three trust properties, proven by tests

The reason to trust verify() is not the prose above — it is that the crate ships tests that try to cheat and get caught. Each test constructs a valid chain, breaks it in one specific way, and asserts that verify() returns false. Three distinct attacks, three distinct guarantees.

1. Tampering with a hash is caught

let mut entries = vec![poh.tick(4), poh.record(2, b"event"), poh.tick(4)];
entries[1].hash[0] ^= 0x01;                 // flip one bit of a recorded hash
assert!(!verify(genesis(seed), &entries));

Flip a single bit of any recorded hash and verification fails. The verifier recomputes that segment from the real starting state and gets the correct ending hash, which no longer equals the tampered value stored in entries[1].hash — so the comparison cur != e.hash fires. You cannot edit a recorded hash and have the chain still check out.

2. Reordering two events fails

let a = poh.record(3, b"event-A");
let b = poh.record(3, b"event-B");
assert!( verify(genesis(seed), &vec![a, b]));   // original order: valid
assert!(!verify(genesis(seed), &vec![b, a]));   // swapped:        invalid

Order is established by construction, so you cannot rewrite history by shuffling entries. Event A was mixed into the chain before event B, which means B’s recorded hash was derived from a state that already contained A. Swap the two entries and the verifier, replaying b first from genesis, computes a different hash than b.hash (which was produced after A). The swap breaks on the very first entry. This is the tamper-evidence that makes PoH a total order rather than a bag of timestamps.

3. A forged skip-ahead fails

let mut entry = poh.tick(1000);
entry.hash = [0xAB; 32];                    // a hash we *wish* were the answer
assert!(!verify(genesis(seed), &[entry]));

You cannot claim a long stretch of elapsed time without actually doing the hashes. Here the forger claims num_hashes = 1000 but supplies a fabricated ending hash instead of the one 1000 real hashes would produce. The verifier does the 1000 hashes for real, lands on the genuine value, and rejects the fake. There is no way to fast-forward the clock: to present a valid hash after 1000 ticks you must have computed all 1000, and that computation is exactly the serial work the forger was trying to skip.

Together these three tests cover the failure modes that matter for an ordering primitive: you can’t edit a recorded state (property 1), you can’t reorder events (property 2), and you can’t fabricate elapsed time (property 3). Everything a verifier needs to trust the clock reduces to these.

The strict-VDF caveat — parallelizable, not cheaper

It is tempting to hear “verification is fast” and conclude PoH is a verifiable delay function in the strong cryptographic sense — where checking is asymptotically cheaper than producing (a producer does T work, a verifier does O(log T) or O(1)). PoH is not that. Say the caveat plainly and keep it:

PoH verification does the same number of hashes as production. It is only parallelizable, not asymptotically cheaper. Its security rests entirely on SHA-256.

Two consequences follow. First, if SHA-256’s sequentiality assumption ever broke — if someone found a way to compute the N-th iterate of sha256 without doing N sequential hashes — the entire “count = elapsed time” guarantee collapses, because a forger could then fabricate elapsed time cheaply. PoH’s honesty is exactly as strong as SHA-256’s pre-image resistance and the absence of a shortcut through its iteration. Second, the verifier’s speed advantage is hardware, not math: it comes from having many cores, not from a cleverer algorithm. A single-core verifier does precisely as much work as the producer did (the crate’s total_hashes() equals poh.count() for exactly this reason). The leverage is real and sufficient — but it is the leverage of parallelism over a serial forger, nothing more.

The architect’s lens

• Why does it exist? Because a clock nobody can verify is worthless in a trustless network. PoH’s producer proves time passed by doing serial work; verify() exists so anyone can confirm that proof from the data alone, without asking the producer or trusting a wall clock.
• What problem does it solve? It lets the whole network confirm the order and elapsed time of events cheaply — spread across cores — instead of exchanging rounds of messages to agree on sequence, which is the throughput bottleneck the whole part exists to remove.
• What are the trade-offs? Verification does the same total hashing as production; you buy speed only through parallelism, not through a cheaper algorithm. And the guarantee is only as strong as SHA-256’s resistance to an iteration shortcut.
• When should I avoid it? When you actually need a strict VDF — verification asymptotically cheaper than production — PoH does not provide it; reach for a real VDF construction instead. And PoH orders events; it does not decide validity or finality, so never use it as consensus on its own.
• What breaks if I remove it? Without verifiable replay, PoH degenerates into “trust the producer’s timestamps,” which reintroduces exactly the distrust and messaging the clock was built to eliminate. The parallel verify() is what makes the clock a shared fact rather than one node’s claim.

Check your understanding

1. Walk through what verify() does for a single record entry (one where mixin is Some). How many bare hashes does it do, what is the final hash, and what does it compare against?
2. Verification redoes the same number of hashes the producer did, yet the network checks the chain far faster than any one node built it. Explain precisely how both statements are true at once.
3. Which field of Entry makes parallel verification possible, and why? What would go wrong if entries did not record their own ending hash?
4. Name the three trust properties the tests prove, and for each say which line of the attack breaks and which check in verify() catches it.
5. Someone claims PoH is a verifiable delay function where checking is asymptotically cheaper than producing. Correct them: what exactly is cheap about verification, what is not, and what single assumption underpins the whole guarantee?

Show answers

1. For a record entry, verify() does num_hashes - 1 bare hash_once calls (each cur = sha256(cur)), then one hash_with(&cur, &mix) that folds in the recorded mixin (cur = sha256(cur || mix)). The result in cur is the segment’s ending hash, which it compares against the entry’s recorded hash. If they differ, it returns false; if they match, cur carries forward as the next segment’s start.
2. The total work is identical: the verifier computes every hash the producer computed — there is no cheaper algorithm (total_hashes() == poh.count()). The wall-clock time differs because production is strictly serial (one dependency chain, no core can help) while verification splits into independent segments. With K cores the verifier finishes in ≈ T / K core-time, so it checks roughly K× faster than one core could have produced — same work, parallelized.
3. Entry.hash — each entry records its own ending hash, which is exactly the starting hash of the next segment. So a verifier already knows both endpoints of every segment up front and can recompute each on a separate core without waiting for the previous one. If entries did not record their ending hashes, a verifier would have to recompute the chain strictly in order (to learn each segment’s start), and verification would be as serial as production — the whole speedup would vanish.
4. (a) Tampering — flipping a bit of a recorded hash (entries[1].hash[0] ^= 0x01); caught because the recomputed cur no longer equals the tampered e.hash, tripping cur != e.hash. (b) Reordering — swapping entries a and b; caught because replaying b first from genesis yields a hash different from b.hash (which was derived after A), failing on the first entry. (c) Skip-ahead — claiming a long num_hashes with a fabricated hash (entry.hash = [0xAB; 32]); caught because the verifier does the real 1000 hashes and lands on the genuine value, not the fake.
5. It is not a strict VDF. What is cheap is only wall-clock time via parallelism — many cores splitting independent segments. What is not cheap is the algorithm: verification does the same total number of hashes as production, so a single-core verifier gets no discount. The whole guarantee rests on one assumption — SHA-256’s resistance to an iteration shortcut (you cannot compute the N-th iterate without doing N sequential hashes); if that broke, “hash count = elapsed time” would collapse.