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.