Thirty-Two Numbers — proving membership in a set of two billion

A transparency log can hold billions of entries. To prove one of them is really in there — and that nobody edited it afterwards — you don't need the log. You need your entry, and about log₂(n) hashes. Click a leaf and watch it fold.

leaf — tree size 16 proof length 4 hashes you'd need without it 16

Pick any leaf. The purple nodes are the only things the log has to hand you; the blue path is what you compute yourself.

your path (computed) the proof (given to you) never seen

step	sibling is	hash supplied	running value

computed root…

published root…

Proof length is log₂(n), so it barely grows. Rekor — the public log behind package provenance — held 2,239,830,492 entries when I checked it. Proving one entry's membership took 32 hashes: about a kilobyte. Doubling the log adds one number.

Hashes are real SHA-256, computed in your browser, with the domain separation from RFC 6962: a leaf is SHA-256(0x00 ‖ data), a node is SHA-256(0x01 ‖ left ‖ right). Those prefix bytes are what stop an internal node being passed off as a leaf. Sizes here are powers of two so the tree stays tidy; real logs handle ragged sizes with a little more bookkeeping.