class MerkleTree

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

Constants

VERSION

Attributes

digest[R]

The one way hash function

leaves[R]

All the leaf nodes

root[R]

The tree root node

width[R]

The number of tree leaves

@return [Integer]

@api public

Public Class Methods

default_digest() click to toggle source

The default hash function using SHA 256

@return [Proc]

@api public

# File lib/merkle_tree.rb, line 33
def self.default_digest
  ->(val) { OpenSSL::Digest::SHA256.hexdigest(val) }
end
new(*messages, digest: MerkleTree.default_digest) click to toggle source

Create a new Merkle Tree

@example

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

@param [Array] messages

the message to digest

@param [Proc] :digest

the message digest algorithm

@api public

# 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

Public Instance Methods

<<(*messages)
Alias for: add
add(*messages) click to toggle source

Add new message(s)

@example

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

@param [Array] messages

the message to digest
# 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
Also aliased as: <<
auth_path(index) click to toggle source

Create an authentication path required to authenticate leaf with index

@param [Integer] index

@return [Array]

an array of direction and hash tuples

@api public

# File lib/merkle_tree.rb, line 174
def auth_path(index)
  traverse(root, index, [])
end
build(nodes) click to toggle source

Calcualte the root value of this tree

@param [Leaf] nodes

the leaf nodes to build from

@api private

# 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?() click to toggle source

Check if this tree has any messages

@api public

# File lib/merkle_tree.rb, line 76
def empty?
  @root == Node::EMPTY
end
height() click to toggle source

The tree height

@api public

# File lib/merkle_tree.rb, line 83
def height
  @root.height
end
include?(message, index) click to toggle source

Verifies that an authentication path exists from leaf to root

@param [String] message

the message to hash

@param [Integer] index

the index of the message to be authenticated

@api public

# 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
Also aliased as: member?
length()
Alias for: size
member?(message, index)
Alias for: include?
regeneration_path(index) click to toggle source

The regeneration path from leaf to root

@return [Node]

@api public

# File lib/merkle_tree.rb, line 216
def regeneration_path(index)
  visit(@root, index, [@root])
end
size() click to toggle source

The number of nodes in this tree

@api public

# File lib/merkle_tree.rb, line 90
def size
  @root.size
end
Also aliased as: length
subtree(index) click to toggle source

Create subtree that contains message at index

@return [Node]

the root node of the subtree

@api public

# File lib/merkle_tree.rb, line 101
def subtree(index)
  root.subtree(index)
end
to_h() click to toggle source

Hash representation of this tree

@api public

# File lib/merkle_tree.rb, line 248
def to_h
  { root: root.to_h }
end
to_leaves(*messages) click to toggle source

Convert messages to leaf data types

@param [Array] messages

the message to digest

@api private

# 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 = "") click to toggle source

String representation of this tree

@api public

# File lib/merkle_tree.rb, line 255
def to_s(indent = "")
  root.to_s(indent)
end
traverse(node, index, path) click to toggle source

Traverse tree from root to leaf collecting siblings hashes

@param [Node] node @param [Integer] index @param [Array] path

@return Array

@api private

# 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) click to toggle source

Update a leaf at index position

@param [String] message

the new message to hash

@param [Integer] index

the index of the message to be rehashed

@return [Leaf]

the updated leaf

@api public

# 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) click to toggle source

Visit all direct children collecting child nodes

@api private

# 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