Class: Ethereum::Trie

Inherits:
Object show all
Includes:
Enumerable
Defined in:
lib/ethereum/trie.rb,
lib/ethereum/trie/nibble_key.rb

Overview

A implementation of Merkle Patricia Tree.

See Also:

Direct Known Subclasses

PruningTrie, TransientTrie

Defined Under Namespace

Classes: InvalidNode, InvalidNodeType, NibbleKey

Constant Summary collapse

NODE_TYPES = 
%i(blank leaf extension branch).freeze
NODE_KV_TYPE = 
%i(leaf extension).freeze
BRANCH_CARDINAL = 
16
BRANCH_WIDTH = 
BRANCH_CARDINAL + 1
KV_WIDTH = 
2
BLANK_NODE = 
"".freeze
BLANK_ROOT = 
Utils.keccak256_rlp('').freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(db, root_hash = BLANK_ROOT) ⇒ Trie

It presents a hash like interface.

Parameters:

  • db (Object) —

    key value database

  • root_hash (String) (defaults to: BLANK_ROOT) —

    blank or trie node in form of [key, value] or

    v0, v1, .. v15, v


37
38
39
40
 
# File 'lib/ethereum/trie.rb', line 37

def initialize(db, root_hash=BLANK_ROOT)
  @db = db
  set_root_hash root_hash
end

Instance Attribute Details

#db ⇒ Object (readonly)

Returns the value of attribute db.



28
29
30
 
# File 'lib/ethereum/trie.rb', line 28

def db
  @db
end

Instance Method Details

#[](key) ⇒ String Also known as: get

Get value from trie.

Parameters:

Returns:

  • (String) —

    BLANK_NODE if does not exist, otherwise node value



85
86
87
 
# File 'lib/ethereum/trie.rb', line 85

def [](key)
  find @root_node, NibbleKey.from_string(key)
end

#[]=(key, value) ⇒ Object Also known as: set

Set value of key.

Parameters:

Raises:

  • (ArgumentError) 


96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/ethereum/trie.rb', line 96

def []=(key, value)
  raise ArgumentError, "key must be string" unless key.instance_of?(String)
  raise ArgumentError, "value must be string" unless value.instance_of?(String)

  @root_node = update_and_delete_storage(
    @root_node,
    NibbleKey.from_string(key),
    value
  )

  update_root_hash
end

#clear ⇒ Object

clear all tree data



158
159
160
161
162
 
# File 'lib/ethereum/trie.rb', line 158

def clear
  delete_child_storage(@root_node)
  delete_node_storage(@root_node)
  @root_node = BLANK_NODE
end

#delete(key) ⇒ Object

Delete value at key.

Parameters:

  • key (String) —

    a string with length of [0,32]

Raises:

  • (ArgumentError) 


115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/ethereum/trie.rb', line 115

def delete(key)
  raise ArgumentError, "key must be string" unless key.instance_of?(String)
  raise ArgumentError, "max key size is 32" if key.size > 32

  @root_node = delete_and_delete_storage(
    @root_node,
    NibbleKey.from_string(key)
  )

  update_root_hash
end

#each(&block) ⇒ Object 



139
140
141
 
# File 'lib/ethereum/trie.rb', line 139

def each(&block)
  to_h.each(&block)
end

#find(node, nbk) ⇒ String

Get value inside a node.

Parameters:

  • node (Array, BLANK_NODE) —

    node in form of array, or BLANK_NODE

  • nbk (Array) —

    nibble array without terminator

Returns:

  • (String) —

    BLANK_NODE if does not exist, otherwise node value



172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/ethereum/trie.rb', line 172

def find(node, nbk)
  node_type = get_node_type node

  case node_type
  when :blank
    BLANK_NODE
  when :branch
    return node.last if nbk.empty?

    sub_node = decode_to_node node[nbk[0]]
    find sub_node, nbk[1..-1]
  when :leaf
    node_key = NibbleKey.decode(node[0]).terminate(false)
    nbk == node_key ? node[1] : BLANK_NODE
  when :extension
    node_key = NibbleKey.decode(node[0]).terminate(false)
    if node_key.prefix?(nbk)
      sub_node = decode_to_node node[1]
      find sub_node, nbk[node_key.size..-1]
    else
      BLANK_NODE
    end
  else
    raise InvalidNodeType, "node type must be in #{NODE_TYPES}, given: #{node_type}"
  end
end

#has_key?(key) ⇒ Boolean Also known as: include?

Returns:

  • (Boolean) 


143
144
145
 
# File 'lib/ethereum/trie.rb', line 143

def has_key?(key)
  self[key] != BLANK_NODE
end

#root_hash ⇒ Object Also known as: update_root_hash

Returns empty or 32 bytes string.

Returns:

  • empty or 32 bytes string

Raises:



45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/ethereum/trie.rb', line 45

def root_hash
  # TODO: can I memoize computation below?
  return BLANK_ROOT if @root_node == BLANK_NODE

  raise InvalidNode, "invalid root node" unless @root_node.instance_of?(Array)

  val = FastRLP.encode @root_node
  key = Utils.keccak256 val

  @db.put key, val
  SPV.grabbing @root_node

  key
end

#root_hash_valid? ⇒ Boolean

Returns:

  • (Boolean) 


72
73
74
75
76
 
# File 'lib/ethereum/trie.rb', line 72

def root_hash_valid?
  h = root_hash
  return true if h == BLANK_ROOT
  return @db.include?(h)
end

#set_root_hash(hash) ⇒ Object

Raises:

  • (TypeError) 


61
62
63
64
65
66
67
68
69
70
 
# File 'lib/ethereum/trie.rb', line 61

def set_root_hash(hash)
  raise TypeError, "root hash must be String" unless hash.instance_of?(String)
  raise ArgumentError, "root hash must be 0 or 32 bytes long" unless [0,32].include?(hash.size)

  if hash == BLANK_ROOT
    @root_node = BLANK_NODE
  else
    @root_node = decode_to_node hash
  end
end

#size ⇒ Object

Get count of all nodes of the trie.



151
152
153
 
# File 'lib/ethereum/trie.rb', line 151

def size
  get_size @root_node
end

#to_h ⇒ Object

Convert to hash.



130
131
132
133
134
135
136
137
 
# File 'lib/ethereum/trie.rb', line 130

def to_h
  h = {}
  to_hash(@root_node).each do |k, v|
    key = k.terminate(false).to_string
    h[key] = v
  end
  h
end