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¶ ↑
-
splay_tree – A self-balancing binary tree with amortised access.
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¶ ↑
Copyright © 2019 Piotr Murach. See LICENSE.txt for further details.