Merkle Tree
The aim of this post is to provide an overview of the basic Merkle Tree data structure and a jumping off point for more advanced topics related to Merkle Trees.
- Merkle tree basics
A Merkle Tree is a data structure that is used in Peer-to-Peer Networks. It is a binary tree in which the value of an inner node is the hash of its leaf nodes. The root node of that tree is called “Merkle root” or “root hash”
L1 — (Hashing) → [Hash 0–0]
L2 — (Hashing) → [Hash 0–1]
L3 — (Hashing) → [Hash 1–0]
L4 — (Hashing) → [Hash 1–1]
([Hash 0–0] + [Hash 0–1]) — (Hashing) → [Hash 0]
([Hash 1–0] + [Hash 1–1] ) — (Hashing) → [Hash 1]
([Hash 1] + [Hash 0])) — (Hashing) → [Top Hash]
- Audit proof
Audit proof: It’s the shortest list of additional nodes in the tree required to compute the root hash for that tree. If the root computed from the audit path matches the true root, then the audit path is a proof of membership for that leaf in the tree.
Imagine that we have to confirm that L3 data block is a part of our merkle tree. What do we need to confirm that? [Hash 1–1] and [Hash 0]:
Get KATSIARYNA TAUREL’s stories in your inbox
Join Medium for free to get updates from this writer.
L3 — (Hashing) → [Hash 1–0]
([Hash 1–0] + [Hash 1–1]) — (Hashing) → [Hash 1]
([Hash 1] +[Hash 0]) — (Hashing) → [Top Hash]
And after that check if [Top Hash] is correct for this merkle tree. How to do it? One of the peer-to-peer nodes that sends you this audit prood path ( [Hash 1–1] and Hash[0] ) will also send you the correct root hash of the tree.
- Consistency proof
Consistency Proof : This kind of proof is only applicable to append-only Merkle trees. It lets you verify that earlier versions of the tree are consistent with newer versions of the tree, that they’re in the same order, and that all new records come after all old records.
For example we have tree from three blocks of data: L1, L2, L3. The root hash of this tree is [Top Hash TREE#1] and we got it from two nodes:
[Hash 0] and [Hash 1–0]
Then we added a new block of data: L4. Now the root hash of our tree is [Top Hash TREE#2]. How can we confirm that earlier version of the tree are consistent with newer versions of the tree?
The answer is that we shoud be able to get previous root hash
[Top Hash TREE#1] from nodes of current tree. New version of tree still has [Hash 0] and [Hash 1–0] hashes in it so we still can get
[Top Hash TREE#1]
The idea is that you should always be able to replicate the root hash of your earlier version of the tree from the nodes of the older version.
RUBY GEM: https://rubygems.org/gems/hash-merkle-tree
MORE INFO: https://datatracker.ietf.org/doc/html/rfc6962
Contacts:
Github: https://github.com/tavrelkate
