Class: MerkleTree

Inherits:
Object
  • Object
show all
Defined in:
lib/merkle_tree.rb,
lib/merkle_tree/leaf.rb,
lib/merkle_tree/node.rb,
lib/merkle_tree/version.rb

Overview

A binary tree of one-time signatures known as merkle tree.

Defined Under Namespace

Classes: Leaf, Node

Constant Summary collapse

VERSION = 
"0.2.0"

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*messages, digest: MerkleTree.default_digest) ⇒ MerkleTree

Create a new Merkle Tree

Examples:

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

Parameters:

  • messages (Array[String]) —

    the message to digest

  • :digest (Proc) —

    the message digest algorithm



48
49
50
51
52
53
54
55
 
# File 'lib/merkle_tree.rb', line 48

def initialize(*messages, digest: MerkleTree.default_digest)
  @root   = Node::EMPTY
  @width  = 0
  @digest = digest
  @leaves = to_leaves(*messages)
  @width  = @leaves.size
  @root   = build(@leaves)
end

Instance Attribute Details

#digest ⇒ Object (readonly)

The one way hash function



26
27
28
 
# File 'lib/merkle_tree.rb', line 26

def digest
  @digest
end

#leaves ⇒ Object (readonly)

All the leaf nodes



16
17
18
 
# File 'lib/merkle_tree.rb', line 16

def leaves
  @leaves
end

#root ⇒ Object (readonly)

The tree root node



13
14
15
 
# File 'lib/merkle_tree.rb', line 13

def root
  @root
end

#width ⇒ Integer (readonly)

The number of tree leaves

Returns:

  • (Integer) 


23
24
25
 
# File 'lib/merkle_tree.rb', line 23

def width
  @width
end

Class Method Details

.default_digest ⇒ Proc

The default hash function using SHA 256

Returns:

  • (Proc) 


33
34
35
 
# File 'lib/merkle_tree.rb', line 33

def self.default_digest
  ->(val) { OpenSSL::Digest::SHA256.hexdigest(val) }
end

Instance Method Details

#add(*messages) ⇒ Object Also known as: <<

Add new message(s)

Examples:

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

Parameters:

  • messages (Array[String]) —

    the message to digest



134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/merkle_tree.rb', line 134

def add(*messages)
  nodes = to_leaves(*messages)
  nodes.each { |node| @leaves << node }
  @width = @leaves.size
  top_node = Node::EMPTY

  while root.height != top_node.height
    top_node = build(nodes)
    nodes = [top_node, top_node]
  end

  @root = Node.build(@root, top_node)
end

#auth_path(index) ⇒ Array[String,String]

Create an authentication path required to authenticate leaf with index

Parameters:

  • index (Integer)

Returns:

  • (Array[String,String]) —

    an array of direction and hash tuples



174
175
176
 
# File 'lib/merkle_tree.rb', line 174

def auth_path(index)
  traverse(root, index, [])
end

#build(nodes) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Calcualte the root value of this tree

Parameters:

  • nodes (Leaf) —

    the leaf nodes to build from



111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/merkle_tree.rb', line 111

def build(nodes)
  return Node::EMPTY if nodes.empty?

  if nodes.size == 1
    return nodes[0]
  end

  parent_nodes = nodes.each_slice(2).map do |left, right|
    right = left if right.nil? # Duplicate odd nodes
    Node.build(left, right, digest: digest)
  end
  build(parent_nodes)
end

#empty? ⇒ Boolean

Check if this tree has any messages

Returns:

  • (Boolean) 


76
77
78
 
# File 'lib/merkle_tree.rb', line 76

def empty?
  @root == Node::EMPTY
end

#height ⇒ Object

The tree height



83
84
85
 
# File 'lib/merkle_tree.rb', line 83

def height
  @root.height
end

#include?(message, index) ⇒ Boolean Also known as: member?

Verifies that an authentication path exists from leaf to root

Parameters:

  • message (String) —

    the message to hash

  • index (Integer) —

    the index of the message to be authenticated

Returns:

  • (Boolean) 


187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/merkle_tree.rb', line 187

def include?(message, index)
  return false if empty?

  leaf_hash = digest.(message)

  hash = auth_path(index).reverse_each.reduce(leaf_hash) do |h, (dir, sibling)|
    digest.(dir == :left ? sibling + h : h + sibling)
  end

  hash == root.value
end

#regeneration_path(index) ⇒ Node

The regeneration path from leaf to root

Returns:



216
217
218
 
# File 'lib/merkle_tree.rb', line 216

def regeneration_path(index)
  visit(@root, index, [@root])
end

#size ⇒ Object Also known as: length

The number of nodes in this tree



90
91
92
 
# File 'lib/merkle_tree.rb', line 90

def size
  @root.size
end

#subtree(index) ⇒ Node

Create subtree that contains message at index

Returns:

  • (Node) —

    the root node of the subtree



101
102
103
 
# File 'lib/merkle_tree.rb', line 101

def subtree(index)
  root.subtree(index)
end

#to_h ⇒ Object

Hash representation of this tree



248
249
250
 
# File 'lib/merkle_tree.rb', line 248

def to_h
  { root: root.to_h }
end

#to_leaves(*messages) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Convert messages to leaf data types

Parameters:

  • messages (Array[String]) —

    the message to digest



63
64
65
66
67
68
69
70
71
 
# File 'lib/merkle_tree.rb', line 63

def to_leaves(*messages)
  if messages.size.odd?
    messages << messages.last.dup
  end

  messages.each_with_index.map do |msg, pos|
    Leaf.build(msg, pos, digest: digest)
  end
end

#to_s(indent = "") ⇒ Object

String representation of this tree



255
256
257
 
# File 'lib/merkle_tree.rb', line 255

def to_s(indent = "")
  root.to_s(indent)
end

#traverse(node, index, path) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Traverse tree from root to leaf collecting siblings hashes

Parameters:

  • node (Node)
  • index (Integer)
  • path (Array)

Returns:

  • Array



158
159
160
161
162
163
164
 
# File 'lib/merkle_tree.rb', line 158

def traverse(node, index, path)
  return path if node.leaf? || node == Node::EMPTY

  path << node.sibling(index)

  traverse(node.subtree(index), index, path)
end

#update(message, index) ⇒ Leaf

Update a leaf at index position

Parameters:

  • message (String) —

    the new message to hash

  • index (Integer) —

    the index of the message to be rehashed

Returns:

  • (Leaf) —

    the updated leaf



231
232
233
234
235
236
237
238
239
240
241
242
243
 
# File 'lib/merkle_tree.rb', line 231

def update(message, index)
  return if empty?

  leaf_hash = digest.(message)

  regeneration_path(index).reverse_each do |node|
    if node.leaf?
      node.value = leaf_hash
    else
      node.update(digest)
    end
  end.last
end

#visit(node, index, path) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Visit all direct children collecting child nodes



203
204
205
206
207
208
209
 
# File 'lib/merkle_tree.rb', line 203

def visit(node, index, path)
  return path if node.leaf? || node == Node::EMPTY

  path << node.child(index)

  visit(node.subtree(index), index, path)
end