Class: MSSMT::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/mssmt/tree.rb

Overview

MS-SMT tree

Constant Summary collapse

HASH_SIZE =

The size of a SHA256 checksum in bytes.

32
MAX_LEVEL =

Depth of the MS-SMT(using SHA256)

HASH_SIZE * 8
LAST_BIT_INDEX =

Index of the last bit for MS-SMT keys

MAX_LEVEL - 1
MAX_SUM_VALUE =

Maximum sum value

0xffffffffffffffff

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(store: MSSMT::Store::DefaultStore.new) ⇒ Tree

Returns a new instance of Tree.



37
38
39
 
# File 'lib/mssmt/tree.rb', line 37

def initialize(store: MSSMT::Store::DefaultStore.new)
  @store = store
end

Instance Attribute Details

#store ⇒ Object (readonly)

Returns the value of attribute store.



15
16
17
 
# File 'lib/mssmt/tree.rb', line 15

def store
  @store
end

Class Method Details

.build_empty_tree ⇒ Array

Generate empty tree.

Returns:

  • (Array) 


23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/mssmt/tree.rb', line 23

def self.build_empty_tree
  tree = Array.new(MSSMT::Tree::MAX_LEVEL + 1)
  tree[MSSMT::Tree::MAX_LEVEL] = MSSMT::LeafNode.empty_leaf
  MSSMT::Tree::MAX_LEVEL.times do |i|
    branch =
      MSSMT::BranchNode.new(
        tree[MSSMT::Tree::MAX_LEVEL - i],
        tree[MSSMT::Tree::MAX_LEVEL - i]
      )
    tree[MSSMT::Tree::MAX_LEVEL - (i + 1)] = branch
  end
  tree.freeze
end

.empty_tree ⇒ Object 



17
18
19
 
# File 'lib/mssmt/tree.rb', line 17

def self.empty_tree
  @empty_tree ||= build_empty_tree
end

Instance Method Details

#delete(key) ⇒ Object

Delete the leaf node found at the given key within the MS-SMT.

Parameters:

  • key (String) —

    key with hex format.



87
88
89
 
# File 'lib/mssmt/tree.rb', line 87

def delete(key)
  store.root = insert(key, MSSMT::LeafNode.empty_leaf)
end

#get(key) ⇒ MSSMT::LeafNode

Get leaf node found at the given key within the MS-SMT.

Parameters:

  • key (String) —

    key with hex format.

Returns:



94
95
96
 
# File 'lib/mssmt/tree.rb', line 94

def get(key)
  walk_down(key)
end

#insert(key, leaf) ⇒ MSSMT::BranchNode

Insert a leaf node at the given key within the MS-SMT.

Parameters:

  • key (String) —

    key with hex format.

  • leaf (MSSMT::LeafNode) —

    leaf node.

Returns:

Raises:



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/mssmt/tree.rb', line 58

def insert(key, leaf)
  unless [key].pack("H*").bytesize == HASH_SIZE
    raise MSSMT::Error, "key must be #{HASH_SIZE} bytes"
  end

  prev_parents = Array.new(MSSMT::Tree::MAX_LEVEL)
  siblings = Array.new(MSSMT::Tree::MAX_LEVEL)
  walk_down(key) do |i, _, sibling, parent|
    prev_parents[MSSMT::Tree::MAX_LEVEL - 1 - i] = parent.node_hash
    siblings[MSSMT::Tree::MAX_LEVEL - 1 - i] = sibling
  end

  root =
    walk_up(key, leaf, siblings) do |i, _, _, parent|
      prev_parent = prev_parents[MSSMT::Tree::MAX_LEVEL - 1 - i]
      unless prev_parent == Tree.empty_tree[i].node_hash
        store.delete_branch(prev_parent)
      end
      unless parent.node_hash == Tree.empty_tree[i].node_hash
        store.insert_branch(parent)
      end
    end

  leaf.empty? ? store.delete_leaf(key) : store.insert_leaf(leaf)
  store.root = root
end

#merkle_proof(key) ⇒ MSSMT::Proof

Generate a merkle proof for the leaf node found at the given key.

Parameters:

  • key (String) —

    key with hex format.

Returns:



101
102
103
104
105
 
# File 'lib/mssmt/tree.rb', line 101

def merkle_proof(key)
  proof = Array.new(MAX_LEVEL)
  walk_down(key) { |i, _, sibling, _| proof[MAX_LEVEL - 1 - i] = sibling }
  MSSMT::Proof.new(proof)
end

#root_hash ⇒ String

Root hash of this tree

Returns:

  • (String) —

    root hash value.



43
44
45
 
# File 'lib/mssmt/tree.rb', line 43

def root_hash
  root_node.node_hash
end

#root_node ⇒ MSSMT::BranchNode

Get root node in tree.

Returns:



49
50
51
 
# File 'lib/mssmt/tree.rb', line 49

def root_node
  store.root.nil? ? Tree.empty_tree[0] : store.root
end

#valid_merkle_proof?(key, leaf, proof) ⇒ Boolean

Verify whether a merkle proof for the leaf found at the given key is valid.

Parameters:

Returns:

  • (Boolean) 


111
112
113
 
# File 'lib/mssmt/tree.rb', line 111

def valid_merkle_proof?(key, leaf, proof)
  root_hash == walk_up(key, leaf, proof.nodes).node_hash
end