QED Proof is paused until further notice. The app, sign-in and new sign-ups are switched off for now.
QED Proof
Start free
Menu

Merkle tree

A tree of hashes in which each parent hashes its children, so one root hash commits to every item beneath it — the structure behind QED Proof's receipt log.

Also called: hash tree

In plain words

A Merkle tree hashes a list of items in pairs, then hashes those hashes in pairs, and so on until one hash is left: the root. Change any item and the root changes. Two useful properties follow. The root is a tiny commitment to the whole list, and you can prove one item is in the list with only about log₂(n) hashes, around 20 for a million items, instead of the whole list.

How QED Proof uses it

QED Proof's receipt log is an RFC 6962-style Merkle tree, the same construction Certificate Transparency uses for TLS certificates:

leaf_hash = SHA-256( 0x00 || JCS({ "body": body, "signature": signature }) )
node_hash = SHA-256( 0x01 || left || right )

The 0x00 and 0x01 prefixes separate leaves from interior nodes, which blocks attacks that pass off an interior node as a leaf. A leaf covers the body and its signature, so what's committed is exactly what was issued.

Proofs are served from a node store in O(log n), and the root is anchored on-chain every ten minutes.

Example

"Leaf 8 of 9" on a receipt means it sits at index 8 in a tree of 9 leaves, and its inclusion proof is the short list of sibling hashes that lead from it to the root.