You are in my Digital Garden.
Merkle Tree
Last modified: Dec 23rd, 2023
https://en.wikipedia.org/wiki/Merkle_tree
A binary tree of hashes. The single root hash verifies all the leaf hashes.
Balancing
Merkle trees must be balanced – the number of leaves must be a power of two. So what to do if you have a non-power-of-two number of data pieces to hash? There doesn’t seem to be an official view on this. Some options:
Duplicate nodes as needed, as you work your way up the tree:
ROOT
/ \
/ \
/ \
/ \
z1 z2
/ \ / \
/ \ / \
/ \ / \
y1 y2 y3 y3
/ \ / \ / \
/ \ / \ / \
x1 x2 x3 x4 x5 x5
/ \ / \ / \ / \ / \
a b c d e f g h i i
Bitcoin does this. Another representation and description of the same method is on this site. This can introduce a vulnerability however.
Another option is what Bittorrent does, which is to add a bunch of “filler hash” leaves until you get to a power of two. Each of these leaves has a hash value of all zeros.
Certificate Transparency uses a different strategy that doesn’t require creating dummy nodes like the two methods above. It’s defined in the RFC, but basically leaves after the nearest power-of-two are “promoted” up to the next level of the tree. See this example with 7 leaves:
hash
/ \
/ \
/ \
/ \
/ \
k l
/ \ / \
/ \ / \
/ \ / \
g h i j
/ \ / \ / \ |
a b c d e f d6
| | | | | |
d0 d1 d2 d3 d4 d5
This is called a “complete” binary tree according to Wikipedia.
That RFC section is also just a good guide to implementing a Merkle tree in general.
Merkle Mountain Range
An iteration on top of merkle trees by Peter Todd. Elements can easily be appended and pruned.
- First party docs
- Another explanation
- Minimizing Storage Using Merkle Mountain Ranges
- Another explainer with some better diagrams