MerkleTree

A binary tree of one-time signatures known as merkle tree. Often used in distributed systems such as Git, Cassandra or Bitcoin for efficiently summarizing sets of data.

A binary tree originally developed to authenticate a large number of public keys with a single value, namely the root of the tree. The merkle root is usually available publicly. Each node in the tree contains a cryptographic hash of node values of its children. The N values/messages that need to be authenticated are placed at the N leaves of the tree. A leaf can store an arbitrary value, usually a public authentication key, that is a cryptographic hash of the value that needs to be authenticated. A leaf can be then verified by publicly available merkle tree root value and its authentication path.

Installation

Add this line to your application's Gemfile:

gem 'merkle_tree'

And then execute:

$ bundle

Or install it yourself as:

$ gem install merkle_tree

Contents

1. Usage

Create a new MerkleTree by passing all the messages to be hashed:

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4")

Then you can use the tree to verify if a message belongs:

merkle_tree.include?("L3", 2) # => true

Or change the message to a new content:

merkle_tree.update("L3*", 2)

You can also check the tree height:

merkle_tree.height # => 2

And how many nodes it has:

merkle_tree.size # => 7

Finally, you can print the contents of the tree to see all the signatures:

merkle_tree.to_s
# =>
# 63442ffc2d48a92c8ba746659331f273748ccede648b27f4eacf00cb0786c439
#   f2b92f33b56466fce14bc2ccf6a92f6edfcd8111446644c20221d6ae831dd67c
#     dffe8596427fc50e8f64654a609af134d45552f18bbecef90b31135a9e7acaa0
#     d76354d8457898445bb69e0dc0dc95fb74cc3cf334f8c1859162a16ad0041f8d
#   8f75b0c1b3d1c0bb2eda264a43f8fdc5c72c853c95fbf2b01c1d5a3e12c6fe9a
#     842983de8fb1d277a3fad5c8295c7a14317c458718a10c5a35b23e7f992a5c80
#     4a5a97c6433c4c062457e9335709d57493e75527809d8a9586c141e591ac9f2c

2. API

2.1 root

To access the root node of the merkle tree use the root method that will return the tree structure with all its children and their signatures.

For example, given a tree with 4 messages

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4")

A full tree of one-time signatures will be available:

merkle_tree.root
# =>
# MerkleTree::Node
#  @value="63442ffc2d48a92c8ba746659331f273748ccede648b27f4eacf00cb0786c439"
#  @left=MerkleTree::Node
#    @value="f2b92f33b56466fce14bc2ccf6a92f6edfcd8111446644c20221d6ae831dd67c"
#    @left=MerkleTree::Leaf
#      @value="dffe8596427fc50e8f64654a609af134d45552f18bbecef90b31135a9e7acaa0"
#    @right=MerkleTree::Leaf
#      @value="d76354d8457898445bb69e0dc0dc95fb74cc3cf334f8c1859162a16ad0041f8d"
#  @right=MerkleTree::Node
#    @value="8f75b0c1b3d1c0bb2eda264a43f8fdc5c72c853c95fbf2b01c1d5a3e12c6fe9a"
#    @left=
#     MerkleTree::Leaf
#      @value="842983de8fb1d277a3fad5c8295c7a14317c458718a10c5a35b23e7f992a5c80"
#   @right=MerkleTree::Leaf
#     @value="4a5a97c6433c4c062457e9335709d57493e75527809d8a9586c141e591ac9f2c"

Since the root is a node you can retrieve it's signature using the value call:

merkle_tree.root.value
# => "63442ffc2d48a92c8ba746659331f273748ccede648b27f4eacf00cb0786c439"

2.2 leaves

You can access all the leaves and their one-time signatures using the leaves method:

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4")

merkle_tree.leaves
# =>
# [
# <MerkleTree::Leaf @value="dffe8596...", @left_index=0, @right_index=0, @height=0>,
# <MerkleTree::Leaf @value="d76354d8...", @left_index=1, @right_index=1, @height=0>,
# <MerkleTree::Leaf @value="842983de...", @left_index=2, @right_index=2, @height=0>,
# <MerkleTree::Leaf @value="4a5a97c6...", @left_index=3, @right_index=3, @height=0>
# ]

2.3 subtree

To access a part of Merkle tree use subtree with the index of the one-time signature:

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4", "L5", "L6", "L7", "L8")

merkle_tree.subtree(2).to_h
# =>
# {
#   value: "63442ffc2d48a92c8ba746659331f273748ccede648b27f4eacf00cb0786c439",
#   left: {
#     value: "f2b92f33b56466fce14bc2ccf6a92f6edfcd8111446644c20221d6ae831dd67c",
#     left: { value: "dffe8596427fc50e8f64654a609af134d45552f18bbecef90b31135a9e7acaa0" },
#     right: { value: "d76354d8457898445bb69e0dc0dc95fb74cc3cf334f8c1859162a16ad0041f8d" }
#   },
#   right: {
#     value: "8f75b0c1b3d1c0bb2eda264a43f8fdc5c72c853c95fbf2b01c1d5a3e12c6fe9a",
#     left: { value: "842983de8fb1d277a3fad5c8295c7a14317c458718a10c5a35b23e7f992a5c80" },
#     right: { value: "4a5a97c6433c4c062457e9335709d57493e75527809d8a9586c141e591ac9f2c" }
#   }
# }

2.4 height

Every leaf in the tree has height 0 and the hash function of two leaves has height 1. So the tree has a total height of H if there is N leaves so that N = 2^H.

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4", "L5", "L6", "L7", "L8")

And since 8 = 2^3 then the height:

merkle_tree.height # => 3

2.5 size

You can check total number of tree nodes with size or length calls:

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4", "L5", "L6", "L7", "L8")
merkle_tree.size
# => 15

2.6 include?

You can verify that a leaf belongs to merkle tree, namely, there is an authentication path or merkle path from the leaf to the root. This operation is log2N where N is number of leaves.

Given a tree with 4 messages:

merkle_tree = MerkleTree.new("L1", "L2", "L3", "L4")

To check if a message L3 is contained in one of the one-time signatures, use the include? or member? method passing the message and position index:

merkle_tree.include?("L3", 2) # => true

Conversely, if the message is not part of one-time signature at position indexed:

merkle_tree.include?("invalid", 2) # => false
````

### 2.7 add

To add new messages to already existing tree use `add` or `<<` method. This action will create a new merkle root and increase tree height.

A merkle tree with 4 messages:

ruby merkle_tree = MerkleTree.new(“L1”, “L2”, “L3”, “L4”)

Will have the following properties:

ruby merkle_tree.leaves.size

=> 4

merkle_tree.height

=> 2

merkle_tree.size

=> 7

To add `L5` and `L6` messages do:

ruby merkle_tree.add(“L5”, “L6”)

This will expand tree to have:

ruby merkle_tree.leaves.size

=> 6

merkle_tree.height

=> 3

merkle_tree.size

=> 15

### 2.8 update

You can replace any merkle tree message with a new one using the `update` call, which accepts a new message as a first argument and the index of the message to replace.

For example, given the tree:

ruby merkle_tree = MerkleTree.new(“L1”, “L2”, “L3”, “L4”)

To update message from `L3` to `L3*` do:

ruby merkle_tree.update(“L3*”, 2)

=>

#<MerkleTree::Leaf @value=“e9a1dd00f5c5e848f6ca6d8660c5191d76ac5dd8867b7a8b08fb59c5ed2806db” … >

### 2.9 to_h

You can dump the whole structure of the tree with `to_h` method:

ruby merkle_tree = MerkleTree.new(“L1”, “L2”, “L3”, “L4”)

merkle_tree.to_h

=>

root: {

value: “63442ffc2d48a92c8ba746659331f273748ccede648b27f4eacf00cb0786c439”,

left: {

value: “f2b92f33b56466fce14bc2ccf6a92f6edfcd8111446644c20221d6ae831dd67c”,

left: { value: “dffe8596427fc50e8f64654a609af134d45552f18bbecef90b31135a9e7acaa0” },

right: { value: “d76354d8457898445bb69e0dc0dc95fb74cc3cf334f8c1859162a16ad0041f8d” }

},

right: {

value: “8f75b0c1b3d1c0bb2eda264a43f8fdc5c72c853c95fbf2b01c1d5a3e12c6fe9a”,

left: { value: “842983de8fb1d277a3fad5c8295c7a14317c458718a10c5a35b23e7f992a5c80” },

right: { value: “4a5a97c6433c4c062457e9335709d57493e75527809d8a9586c141e591ac9f2c” }

}

}

### 2.10 to_s

ruby merkle_tree = MerkleTree.new(“L1”, “L2”, “L3”, “L4”)

You can print merkle tree out to string:

ruby merkle_tree.to_s

=>

63442ffc2d48a92c8ba746659331f273748ccede648b27f4eacf00cb0786c439

f2b92f33b56466fce14bc2ccf6a92f6edfcd8111446644c20221d6ae831dd67c

dffe8596427fc50e8f64654a609af134d45552f18bbecef90b31135a9e7acaa0

d76354d8457898445bb69e0dc0dc95fb74cc3cf334f8c1859162a16ad0041f8d

8f75b0c1b3d1c0bb2eda264a43f8fdc5c72c853c95fbf2b01c1d5a3e12c6fe9a

842983de8fb1d277a3fad5c8295c7a14317c458718a10c5a35b23e7f992a5c80

4a5a97c6433c4c062457e9335709d57493e75527809d8a9586c141e591ac9f2c

### 2.11 `:digest`

By default the `SHA-256` is used to create one-time signatures using Ruby's `openssl` package. You can see different [OpenSSl::Digest](https://ruby-doc.org/stdlib-2.6.1/libdoc/openssl/rdoc/OpenSSL/Digest.html).  

To provide your own algorithm use the `:digest` keyword and as value a lambda that will produce message hash. For example, to use `SHA-512` message digest algorithm do:

ruby MerkleTree.new(“L1”,…, digest: -> (val) { OpenSSL::Digest::SHA256.hexdigest(val) })

“`

3. See Also

Development

After checking out the repo, run bin/setup to install dependencies. Then, run rake spec to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitHub at github.com/piotrmurach/merkle_tree. This project is intended to be a safe, welcoming space for collaboration, and contributors are expected to adhere to the Contributor Covenant code of conduct.

License

The gem is available as open source under the terms of the MIT License.

Code of Conduct

Everyone interacting in the MerkleTree project’s codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.

Copyright © 2019 Piotr Murach. See LICENSE.txt for further details.