Merkle Tree
2022-10-15An introduction to Merkle Trees, explaining their hash-based data structure, benefits for efficient data comparison, and real-world applications in P2P networks, cryptocurrencies, and distributed computing, with a Ruby implementation example.
What is Merkle Tree
- a tree-like data structure
- every leaves is labelled with the hash of a data block
- every node is labelled with the cryptographic hash of the labels of its child nodes
Why you need Merkle Tree
- faster to check the equality between different objects
- save more time & spaces to calculate checksums
Real-world example
- P2P
- Crypto Currency
- Distribution Computing
PoC
In this example, MerkleNode
class is implemented in Ruby.
This class describes each node of Merkle Tree. This class implements ==(other)
, meaning that instances of this class can be compared like first == second
.
If you look into the implementation of ==(other)
, you can find how each node is compared. It checkes if hashed value are equal or not, and it traverses down the tree until it reaches leaves or find inequal pairs.
Implementation
require 'digest'
class MerkleNode
include Enumerable
attr_reader :left, :right, :data, :hashed
def initialize(left, right, data = nil)
@left = left
@right = right
@data = data
@hashed = hash_data(data)
end
def each(&block)
block.call(data)
if left?
left.each(&block)
end
if right?
right.each(&block)
end
end
def leaf?
left.nil? && right.nil? && !data.nil?
end
def node?
!leaf?
end
def left?
!left.nil?
end
def right?
!right.nil?
end
def ==(other)
hashed == other.hashed
end
private
def hash_data(data)
if leaf?
hash(data)
elsif node?
hash(map(&:hash).reduce(&:+))
end
end
def hash(d)
seed = d.to_s
Digest::SHA256.digest(seed)
end
end
Unit test
In this unit test, let's define three different Merkle Tree instances.
First and second tree have same values at each nodes. We expect that first == second
returns true
. The third tree is also instantiated with different values. We expect that third
is not equal with either of first
nor second
require_relative './spec_helper'
require_relative '../lib/merkle_tree'
describe 'MerkleTree' do
first = MerkleNode.new(
MerkleNode.new(
MerkleNode.new(nil, nil, 1),
MerkleNode.new(nil, nil, 2),
),
MerkleNode.new(
MerkleNode.new(
MerkleNode.new(nil, nil, 3),
MerkleNode.new(nil, nil, 4),
),
MerkleNode.new(nil, nil, 5),
),
)
second = MerkleNode.new(
MerkleNode.new(
MerkleNode.new(nil, nil, 1),
MerkleNode.new(nil, nil, 2),
),
MerkleNode.new(
MerkleNode.new(
MerkleNode.new(nil, nil, 3),
MerkleNode.new(nil, nil, 4),
),
MerkleNode.new(nil, nil, 5),
),
)
third = MerkleNode.new(
MerkleNode.new(
MerkleNode.new(nil, nil, 1),
MerkleNode.new(nil, nil, 2),
),
MerkleNode.new(
MerkleNode.new(
MerkleNode.new(nil, nil, 3),
MerkleNode.new(nil, nil, 4),
),
MerkleNode.new(nil, nil, 0),
),
)
describe '==' do
it do
expect(first == second).to eq true
expect(first == third ).to eq false
expect(second == third ).to eq false
end
end
end