Merkle Tree

merkletree library / gem - build your own crypto hash trees; named after Ralph Merkle who patented hash trees in 1979 (the patent expired in 2002); grow your own money on trees

What's a Merkle Tree?

A Merkle tree or hash tree is a tree in which every leaf node is labelled with the hash of a data block and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures. [...]

The concept of hash trees is named after Ralph Merkle who patented it in 1979.

-- Wikipedia

Usage

Pass along all (leaf / data block) hashes as strings or packaged in an array. Example:

merkle = MerkleTree.new(
  'eb8ecbf6d5870763ae246e37539d82e37052cb32f88bb8c59971f9978e437743',
  'edbd4e11e69bc399a9ccd8faaea44fb27410fe8e3023bb9462450a0a9c4caa1b',
  '5ee2981606328abfe0c3b1171440f0df746c1e1f8b3b56c351727f7da7ae5d8d' )

# -or-

merkle = MerkleTree.new( [
  'eb8ecbf6d5870763ae246e37539d82e37052cb32f88bb8c59971f9978e437743',
  'edbd4e11e69bc399a9ccd8faaea44fb27410fe8e3023bb9462450a0a9c4caa1b',
  '5ee2981606328abfe0c3b1171440f0df746c1e1f8b3b56c351727f7da7ae5d8d' ])


puts merkle.root.value
# => '25fd59b79d70bbdf043d66a7b0fc01409d11b990e943bb46b840fbbddd5ab895'

pp merkle    ## pp (pretty print)

resulting in:

@root = #<MerkleTree::Node:0x46b55e0
   @left = #<MerkleTree::Node:0x46b6060
     @left = #<MerkleTree::Node:0x46b6870
       @left  = nil,
       @right = nil,
       @value = "eb8ecbf6d5870763ae246e37539d82e37052cb32f88bb8c59971f9978e437743">,
     @right = #<MerkleTree::Node:0x46b6810
       @left  = nil,
       @right = nil,
       @value = "edbd4e11e69bc399a9ccd8faaea44fb27410fe8e3023bb9462450a0a9c4caa1b">,
     @value = "c9de03ced4db3c63835807016b1efedb647c694d2db8b9a8579cbf0c5dcb5ab0">,
   @right= #<MerkleTree::Node:0x46b5ca0
     @left= #<MerkleTree::Node:0x46b6798
       @left  = nil,
       @right = nil,
       @value = "5ee2981606328abfe0c3b1171440f0df746c1e1f8b3b56c351727f7da7ae5d8d">,
     @right = #<MerkleTree::Node:0x46b6798
       @left  = nil,
       @right = nil,
       @value = "5ee2981606328abfe0c3b1171440f0df746c1e1f8b3b56c351727f7da7ae5d8d">,
     @value = "50963aa3b2047e0d58bb850fc12e5a324cf01061af55889389be72d3849e1d03">,
   @value="25fd59b79d70bbdf043d66a7b0fc01409d11b990e943bb46b840fbbddd5ab895">>

Use MerkleTree.compute_root for computing the root (crypto) hash without building a tree. Example:

merkle_root_value = MerkleTree.compute_root(
  'eb8ecbf6d5870763ae246e37539d82e37052cb32f88bb8c59971f9978e437743',
  'edbd4e11e69bc399a9ccd8faaea44fb27410fe8e3023bb9462450a0a9c4caa1b',
  '5ee2981606328abfe0c3b1171440f0df746c1e1f8b3b56c351727f7da7ae5d8d' )

# -or-

merkle_root_value = MerkleTree.compute_root( [
  'eb8ecbf6d5870763ae246e37539d82e37052cb32f88bb8c59971f9978e437743',
  'edbd4e11e69bc399a9ccd8faaea44fb27410fe8e3023bb9462450a0a9c4caa1b',
  '5ee2981606328abfe0c3b1171440f0df746c1e1f8b3b56c351727f7da7ae5d8d' ])


puts merkle_root_value
# => '25fd59b79d70bbdf043d66a7b0fc01409d11b990e943bb46b840fbbddd5ab895'

Transactions

Use MerkleTree.for or MerkleTree.compute_root_for for passing along transactions. Will use to_s on every transaction and use the resulting "serialized" string to (auto-) calculate the (crypto) hash.

Let's put the transactions from the (hyper) ledger book from Tulips on the Blockchain! on the ~~blockchain~~ merkle tree:

From To What Qty
Bloom & Blossom (†) Daisy Tulip Admiral of Admirals 8
Vincent Max Tulip Bloemendaal Sunset 2
Anne Martijn Tulip Semper Augustus 2
Ruben Julia Tulip Admiral van Eijck 2

(†): Grower Transaction - New Tulips on the Market!

merkle = MerkleTree.for(
  { from: "Bloom & Blossom", to: "Daisy",   what: "Tulip Admiral of Admirals", qty: 8 },
  { from: "Vincent",         to: "Max",     what: "Tulip Bloemendaal Sunset",  qty: 2 },
  { from: "Anne",            to: "Martijn", what: "Tulip Semper Augustus",     qty: 2 },
  { from: "Ruben",           to: "Julia",   what: "Tulip Admiral van Eijck",   qty: 2 } )

puts merkle.root.value
# => '703f44630117ef9b4ac20cb149ed8a0f06e4c3ed2a791e11e16a2fe7a7d0de3d'

# -or-

merkle_root_value = MerkleTree.compute_root_for(
  { from: "Bloom & Blossom", to: "Daisy",   what: "Tulip Admiral of Admirals", qty: 8 },
  { from: "Vincent",         to: "Max",     what: "Tulip Bloemendaal Sunset",  qty: 2 },
  { from: "Anne",            to: "Martijn", what: "Tulip Semper Augustus",     qty: 2 },
  { from: "Ruben",           to: "Julia",   what: "Tulip Admiral van Eijck",   qty: 2 } )

puts merkle_root_value
# => '703f44630117ef9b4ac20cb149ed8a0f06e4c3ed2a791e11e16a2fe7a7d0de3d'

Merkle Tree in the Real World

  • blockchain-lite - build your own blockchain with crypto hashes - revolutionize the world with blockchains, blockchains, blockchains one block at a time
  • You? Add your library / service

References

Programming Cryptocurrencies and Blockchains (in Ruby) by Gerald Bauer et al, 2018, Yuki & Moto Press

License

The merkletree scripts are dedicated to the public domain. Use it as you please with no restrictions whatsoever.