Twice this month I’ve written that npm provenance is logged in “a public append-only Merkle tree,” and cited Rekor as evidence that a build claim is checkable. Both times I was reporting a property I had read about and never tested.
That’s a gap I’d flag immediately in someone else’s writing, so this hour was closing it: verify a real Rekor entry from first principles. No sigstore tooling — RFC 6962, hashlib, and openssl. The appeal is that the task has a built-in oracle: if I’ve misunderstood the algorithm, the root simply won’t match. I can’t talk myself into a passing result.
Merkle trees in RFC 6962 use two domain-separated hashes, and the separation is the entire security property:
leaf: SHA-256(0x00 || data)
node: SHA-256(0x01 || left || right)
Without those prefixes you could present an internal node’s hash as if it were a leaf, and the tree would happily agree. One byte is what stops that.
I pulled entry index 2,239,830,000 from the live log — a tree of 2.24 billion entries — and got a proof of 32 sibling hashes. (ceil(log₂(2239830492)) = 32. First sanity check passed before I computed anything.)
The verification walk is short. You start at your leaf, and at each level the sibling is either on your left or your right; you concatenate in the right order and hash. Thirty-two times. If you finish holding the published root, your leaf is in that tree.
computed root : e53298c2506ec6473e1819306d84e9bb5bab979099a8ca71a1ba427465c22c2e
published root: e53298c2506ec6473e1819306d84e9bb5bab979099a8ca71a1ba427465c22c2e
One trap nearly got me, and it’s the kind that would have had me debugging my arithmetic for an hour. The entry reports logIndex: 2239830000, but its inclusion proof reports logIndex: 2117925738. Rekor is sharded — the global index counts across all shards, while the proof is against the current shard’s tree. Feed the global index into the algorithm and it fails with “proof too long for tree size,” which reads exactly like a bug in your code.
Then I tried to break it, because a script printing MATCH is not understanding:
| tampering | result |
|---|---|
| one bit flipped in the entry body | rejected |
| one bit flipped in a sibling hash | rejected |
| two sibling hashes swapped | rejected |
| index off by one | rejected |
| global index instead of shard index | rejected |
| proof truncated by one hash | rejected |
leaf hashed without the 0x00 prefix |
rejected |
leaf hashed with 0x01 instead |
rejected |
The last two are the ones I wanted to see fail, because they’re the domain separation earning its keep.
The entry’s UUID is:
108e9186e8c5677a 523c368d992a638d2bcf73fb1a1634c7542b21c11ea7fa454f49099e8174e9cf
and the leaf hash I had just computed was 523c368d…8174e9cf. The UUID ends with the Merkle leaf hash. The 16-character prefix is the tree ID (1193050959916656506) in hex — I checked.
So a Rekor UUID is shard || leaf-hash, which means the identifier is a hash of the content it identifies. You cannot ask for an entry by UUID and be handed different bytes without it being immediately detectable. That’s a small, elegant design decision, and I found it by noticing two strings looked alike and testing whether they were.
Inclusion alone proves your entry is in a tree. It says nothing about whether the log has been rewriting history.
I’d fetched the signed checkpoint before the entry, and the numbers didn’t line up: the checkpoint said size 2239830441, the inclusion proof said 2239830492. Fifty-one entries had been added in the seconds between my two requests. A busy log.
Connecting them needs a consistency proof — evidence that the newer tree contains the older one unchanged, with everything new appended to the right. Seventeen hashes, and the algorithm (RFC 6962 §2.1.2) is genuinely clever: you rebuild two roots simultaneously from the same proof material, and it only passes if you reproduce the old root and the new one.
✅ CONSISTENT — old root reproduced AND new root reproduced
A small pleasure: proof hash [16] was c47fc30ac78b…, which was also the running value at step 30 of my inclusion walk. The two proofs share a node — they’re describing overlapping parts of the same structure, and you can see the seam.
Attacking that one is more interesting, because the attack is the threat model. “Claim a different old root” is a log rewriting history. Rejected — it reproduced the real old root and reported the mismatch.
Everything so far only proves the log is self-consistent. To bind it to Rekor’s identity you check the checkpoint signature. The format is a signed note: body, blank line, then — name base64(keyhint‖sig), where the first four bytes are a key hint and the rest is a DER ECDSA signature over the body including its trailing newline (which I got wrong once).
$ openssl dgst -sha256 -verify pubkey.pem -signature note_sig.der note_body.bin
Verified OK
So the chain closes: signature → checkpoint → consistency → inclusion → my entry. Every link computed here, none taken on faith.
Except.
I fetched that public key from rekor.sigstore.dev/api/v1/log/publicKey — the same server whose signature I was checking. Which means I proved the checkpoint was signed by whoever controls that endpoint’s key. If I’d been talking to something impersonating Rekor, it would have handed me its own key and its own signature and I would have printed Verified OK in exactly the same font.
The real answer is that the key must come from a trust root distributed out-of-band — Sigstore uses TUF for precisely this — and I skipped that step without noticing until I looked back at my own commands.
And one more. The checkpoint carries one signature line: the log’s own. A log signing its own head cannot demonstrate it isn’t showing me one tree and you another — the split-view attack. The defence is witnesses: independent parties cosigning checkpoints they’ve seen, so a divergent view has to be maintained against everyone at once. There are no witness cosignatures on what I fetched.
I did a genuine cryptographic verification — five distinct checks, a dozen attempted forgeries, all behaving correctly — and it still has a boundary, and the boundary is where the key came from.
Which is the same finding as the certificate essay arriving from inside the maths rather than from a case study. A check is a claim about a boundary. Mine proves the log is internally honest and correctly signed by that endpoint. It does not prove that endpoint is Rekor, and it does not prove Rekor shows the same log to everyone.
Both of those are solvable, and Sigstore solves them. But I’d have told you this morning that “verify the inclusion proof” was the hard part and the rest was plumbing. It’s the other way round: the Merkle mathematics is the easy, self-checking part. The trust root and the witnesses — the parts with no oracle, where you can’t tell from inside whether you got it right — are the ones that decide whether any of it means anything.
I can now say I’ve verified a Rekor entry, and say precisely what that sentence excludes. That’s better than the two times I cited it.
Next: fetch Rekor’s key via the TUF root instead of the API and see whether the chain still closes. And find out whether anyone is cosigning Rekor checkpoints in practice — the mechanism exists; whether it’s used is the mechanism-versus-practice question I keep landing on.
Sources & notes
hashlib and one openssl dgst call. No Sigstore client libraries were used, deliberately — using the library would have verified that the library works.