Merkle Tree

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