class Ethereum::Trie

A implementation of Merkle Patricia Tree.

@see github.com/ethereum/wiki/wiki/Patricia-Tree

Constants

BLANK_NODE
BLANK_ROOT
BRANCH_CARDINAL
BRANCH_WIDTH
KV_WIDTH
NODE_KV_TYPE
NODE_TYPES

Attributes

db[R]

Public Class Methods

new(db, root_hash=BLANK_ROOT) click to toggle source

It presents a hash like interface.

@param db [Object] key value database @param root_hash [String] blank or trie node in form of [key, value] or

[v0, v1, .. v15, v]
# File lib/ethereum/trie.rb, line 36
def initialize(db, root_hash=BLANK_ROOT)
  @db = db
  set_root_hash root_hash
end

Public Instance Methods

[](key) click to toggle source

Get value from trie.

@param key [String]

@return [String] BLANK_NODE if does not exist, otherwise node value

# File lib/ethereum/trie.rb, line 84
def [](key)
  find @root_node, NibbleKey.from_string(key)
end
Also aliased as: get
[]=(key, value) click to toggle source

Set value of key.

@param key [String] @param value [String]

# File lib/ethereum/trie.rb, line 95
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
Also aliased as: set
clear() click to toggle source

clear all tree data

# File lib/ethereum/trie.rb, line 157
def clear
  delete_child_storage(@root_node)
  delete_node_storage(@root_node)
  @root_node = BLANK_NODE
end
delete(key) click to toggle source

Delete value at key.

@param key [String] a string with length of [0,32]

# File lib/ethereum/trie.rb, line 114
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) click to toggle source
# File lib/ethereum/trie.rb, line 138
def each(&block)
  to_h.each(&block)
end
find(node, nbk) click to toggle source

Get value inside a node.

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE @param nbk [Array] nibble array without terminator

@return [String] BLANK_NODE if does not exist, otherwise node value

# File lib/ethereum/trie.rb, line 171
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
get(key)
Alias for: []
has_key?(key) click to toggle source
# File lib/ethereum/trie.rb, line 142
def has_key?(key)
  self[key] != BLANK_NODE
end
Also aliased as: include?
include?(key)
Alias for: has_key?
root_hash() click to toggle source

@return empty or 32 bytes string

# File lib/ethereum/trie.rb, line 44
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
Also aliased as: update_root_hash
root_hash_valid?() click to toggle source
# File lib/ethereum/trie.rb, line 71
def root_hash_valid?
  h = root_hash
  return true if h == BLANK_ROOT
  return @db.include?(h)
end
set(key, value)
Alias for: []=
set_root_hash(hash) click to toggle source
# File lib/ethereum/trie.rb, line 60
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() click to toggle source

Get count of all nodes of the trie.

# File lib/ethereum/trie.rb, line 150
def size
  get_size @root_node
end
to_h() click to toggle source

Convert to hash.

# File lib/ethereum/trie.rb, line 129
def to_h
  h = {}
  to_hash(@root_node).each do |k, v|
    key = k.terminate(false).to_string
    h[key] = v
  end
  h
end
update_root_hash()
Alias for: root_hash

Private Instance Methods

decode_to_node(encoded) click to toggle source
# File lib/ethereum/trie.rb, line 238
def decode_to_node(encoded)
  return BLANK_NODE if encoded == BLANK_NODE
  return encoded if encoded.instance_of?(Array)

  RLP.decode(@db.get(encoded))
    .tap {|o| SPV.grabbing o }
end
delete_and_delete_storage(node, key) click to toggle source
# File lib/ethereum/trie.rb, line 254
def delete_and_delete_storage(node, key)
  old_node = node.dup
  new_node = delete_node(node, key)
  delete_node_storage(old_node) if old_node != new_node
  new_node
end
delete_branch_node(node, key) click to toggle source
# File lib/ethereum/trie.rb, line 385
def delete_branch_node(node, key)
  if key.empty?
    node[-1] = BLANK_NODE
    return normalize_branch_node(node)
  else
    new_sub_node = delete_and_delete_storage decode_to_node(node[key[0]]), key[1..-1]
    encoded_new_sub_node = encode_node new_sub_node

    return node if encoded_new_sub_node == node[key[0]]

    node[key[0]] = encoded_new_sub_node
    return normalize_branch_node(node) if encoded_new_sub_node == BLANK_NODE

    node
  end
end
delete_child_storage(node) click to toggle source
# File lib/ethereum/trie.rb, line 478
def delete_child_storage(node)
  node_type = get_node_type node
  case node_type
  when :branch
    node[0,BRANCH_CARDINAL].each {|item| delete_child_storage decode_to_node(item) }
  when :extension
    delete_child_storage decode_to_node(node[1])
  else
    # do nothing
  end
end
delete_kv_node(node, key) click to toggle source
# File lib/ethereum/trie.rb, line 402
def delete_kv_node(node, key)
  node_type = get_node_type node
  raise ArgumentError, "node type is not one of key-value type (#{NODE_KV_TYPE})" unless NODE_KV_TYPE.include?(node_type)

  node_key = NibbleKey.decode(node[0]).terminate(false)

  # key not found
  return node unless node_key.prefix?(key)

  if node_type == :leaf
    key == node_key ? BLANK_NODE : node
  else # :extension
    new_sub_node = delete_and_delete_storage decode_to_node(node[1]), key[node_key.size..-1]

    return node if encode_node(new_sub_node) == node[1]
    return BLANK_NODE if new_sub_node == BLANK_NODE

    raise InvalidNode, "new sub node must be array" unless new_sub_node.instance_of?(Array)

    new_sub_node_type = get_node_type new_sub_node

    case new_sub_node_type
    when :branch
      [node_key.encode, encode_node(new_sub_node)]
    when *NODE_KV_TYPE
      new_key = node_key + NibbleKey.decode(new_sub_node[0])
      [new_key.encode, new_sub_node[1]]
    else
      raise InvalidNodeType, "invalid kv sub node type #{new_sub_node_type}"
    end
  end
end
delete_node(node, key) click to toggle source

Delete item inside node.

If this node is changed to a new node, it's parent will take the responsibility to store the new node storage, and delete the old node storage.

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE @param key [Array] nibble key without terminator. key maybe empty

@return new node

# File lib/ethereum/trie.rb, line 374
def delete_node(node, key)
  case get_node_type(node)
  when :blank
    BLANK_NODE
  when :branch
    delete_branch_node(node, key)
  else # kv type
    delete_kv_node(node, key)
  end
end
delete_node_storage(node) click to toggle source

Delete node storage.

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE

# File lib/ethereum/trie.rb, line 465
def delete_node_storage(node)
  return if node == BLANK_NODE
  raise ArgumentError, "node must be Array or BLANK_NODE" unless node.instance_of?(Array)

  encoded = encode_node node
  return if encoded.size < 32

  # FIXME: in current trie implementation two nodes can share identical
  # subtree thus we can not safely delete nodes for now
  #
  # \@db.delete encoded
end
encode_node(node) click to toggle source
# File lib/ethereum/trie.rb, line 224
def encode_node(node)
  return BLANK_NODE if node == BLANK_NODE
  raise ArgumentError, "node must be an array" unless node.instance_of?(Array)

  rlp_node = FastRLP.encode node
  return node if rlp_node.size < 32

  hashkey = Utils.keccak256 rlp_node
  @db.put hashkey, rlp_node
  SPV.store node

  hashkey
end
get_node_type(node) click to toggle source

get node type and content

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE

@return [Symbol] node type

# File lib/ethereum/trie.rb, line 497
def get_node_type(node)
  return :blank if node == BLANK_NODE

  case node.size
  when KV_WIDTH # [k,v]
    NibbleKey.decode(node[0]).terminate? ? :leaf : :extension
  when BRANCH_WIDTH # [k0, ... k15, v]
    :branch
  else
    raise InvalidNode, "node size must be #{KV_WIDTH} or #{BRANCH_WIDTH}"
  end
end
get_size(node) click to toggle source

Get counts of (key, value) stored in this and the descendant nodes.

TODO: refactor into Node class

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE

@return [Integer]

# File lib/ethereum/trie.rb, line 209
def get_size(node)
  case get_node_type(node)
  when :branch
    sizes = node[0,BRANCH_CARDINAL].map {|n| get_size decode_to_node(n) }
    sizes.push(node.last.false? ? 0 : 1)
    sizes.reduce(0, &:+)
  when :extension
    get_size decode_to_node(node[1])
  when :leaf
    1
  when :blank
    0
  end
end
normalize_branch_node(node) click to toggle source
# File lib/ethereum/trie.rb, line 435
def normalize_branch_node(node)
  non_blank_items = node.each_with_index.select {|(x, i)| x != BLANK_NODE }

  raise ArgumentError, "node must has at least 1 non blank item" unless non_blank_items.size > 0
  return node if non_blank_items.size > 1

  non_blank_index = non_blank_items[0][1]

  # if value is the only non blank item, convert it into a kv node
  return [NibbleKey.new([]).terminate(true).encode, node.last] if non_blank_index == NibbleKey::NIBBLE_TERMINATOR

  sub_node = decode_to_node node[non_blank_index]
  sub_node_type = get_node_type sub_node

  case sub_node_type
  when :branch
    [NibbleKey.new([non_blank_index]).encode, encode_node(sub_node)]
  when *NODE_KV_TYPE
    new_key = NibbleKey.decode(sub_node[0]).unshift(non_blank_index)
    [new_key.encode, sub_node[1]]
  else
    raise InvalidNodeType, "invalid branch sub node type #{sub_node_type}"
  end
end
to_hash(node) click to toggle source

Convert [key, value] stored in this and the descendant nodes to hash.

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE

@return [Hash] equivalent hash. Hash key is in full form (Array).

# File lib/ethereum/trie.rb, line 516
def to_hash(node)
  node_type = get_node_type node

  case node_type
  when :blank
    {}
  when :branch
    hash = {}

    16.times do |i|
      sub_hash = to_hash decode_to_node(node[i])
      sub_hash.each {|k, v| hash[NibbleKey.new([i]) + k] = v }
    end

    hash[NibbleKey.terminator] = node.last if node.last.true?
    hash
  when *NODE_KV_TYPE
    nibbles = NibbleKey.decode(node[0]).terminate(false)

    sub_hash = node_type == :extension ?
      to_hash(decode_to_node(node[1])) : {NibbleKey.terminator => node[1]}

    {}.tap do |hash|
      sub_hash.each {|k, v| hash[nibbles + k] = v }
    end
  else
    # do nothing
  end
end
update_and_delete_storage(node, key, value) click to toggle source

TODO: refactor, abstract delete storage logic

# File lib/ethereum/trie.rb, line 247
def update_and_delete_storage(node, key, value)
  old_node = node.dup
  new_node = update_node(node, key, value)
  delete_node_storage(old_node) if old_node != new_node
  new_node
end
update_kv_node(node, key, value) click to toggle source

TODO: refactor this crazy tall guy

# File lib/ethereum/trie.rb, line 299
def update_kv_node(node, key, value)
  node_type = get_node_type node
  node_key = NibbleKey.decode(node[0]).terminate(false)
  inner = node_type == :extension

  common_key = node_key.common_prefix(key)
  remain_key = key[common_key.size..-1]
  remain_node_key = node_key[common_key.size..-1]

  if remain_key.empty? && remain_node_key.empty? # target key equals node's key
    if inner
      new_node = update_and_delete_storage(
        decode_to_node(node[1]),
        remain_key,
        value
      )
    else
      return [node[0], value]
    end
  elsif remain_node_key.empty? # target key includes node's key
    if inner
      new_node = update_and_delete_storage(
        decode_to_node(node[1]),
        remain_key,
        value
      )
    else # node is a leaf, we need to replace it with branch node first
      new_node = [BLANK_NODE] * BRANCH_WIDTH
      new_node[-1] = node[1]
      new_node[remain_key[0]] = encode_node([
        remain_key[1..-1].terminate(true).encode,
        value
      ])
    end
  else
    new_node = [BLANK_NODE] * BRANCH_WIDTH

    if remain_node_key.size == 1 && inner
      new_node[remain_node_key[0]] = node[1]
    else
      new_node[remain_node_key[0]] = encode_node([
        remain_node_key[1..-1].terminate(!inner).encode,
        node[1]
      ])
    end

    if remain_key.empty? # node's key include target key
      new_node[-1] = value
    else
      new_node[remain_key[0]] = encode_node([
        remain_key[1..-1].terminate(true).encode,
        value
      ])
    end
  end

  if common_key.empty?
    new_node
  else
    [node_key[0, common_key.size].encode, encode_node(new_node)]
  end
end
update_node(node, key, value) click to toggle source

Update item inside a node.

If this node is changed to a new node, it's parent will take the responsibility to store the new node storage, and delete the old node storage.

@param node [Array, BLANK_NODE] node in form of array, or BLANK_NODE @param key [Array] nibble key without terminator @param value [String] value string

@return [Array, BLANK_NODE] new node

# File lib/ethereum/trie.rb, line 274
def update_node(node, key, value)
  node_type = get_node_type node

  case node_type
  when :blank
    [key.terminate(true).encode, value]
  when :branch
    if key.empty?
      node.last = value
    else
      new_node = update_and_delete_storage(
        decode_to_node(node[key[0]]),
        key[1..-1],
        value
      )
      node[key[0]] = encode_node new_node
    end

    node
  else # kv node type
    update_kv_node(node, key, value)
  end
end