class Scale::Types::TrieNode

Constants

BITMAP_LENGTH
EMPTY
NIBBLE_LENGTH
NIBBLE_PER_BYTE
NIBBLE_SIZE_BOUND

Public Class Methods

check(root, proof, key) click to toggle source
# File lib/scale/trie.rb, line 122
def self.check(root, proof, key)
  key = Key.new(key)

  nodes = proof.map {|node_data| 
    node = TrieNode::decode(Scale::Bytes.new(node_data)).value
    [node[:hash], node]
  }.to_h

  self.do_check(root, nodes, key)
end
decode(scale_bytes) click to toggle source
# File lib/scale/trie.rb, line 12
def self.decode(scale_bytes)
  hash = "0x#{Crypto::blake2_256(scale_bytes.bytes)}"
  first = scale_bytes.get_next_bytes(1).first
  if first == EMPTY
    TrieNode.new({})
  else
    v = first & (0b11 << 6)
    decode_size = -> {
      result = first & 255 >> 2
      return result if result < 63
      result -= 1
      while result <= NIBBLE_SIZE_BOUND
        n = scale_bytes.get_next_bytes(1).first
        return (result + n + 1) if n < 255 
        result += 255
      end
      return NIBBLE_SIZE_BOUND
    }

    if v == 0b01 << 6 # leaf
      nibble_count = decode_size.call
      # if nibble_count is odd, the half of first byte of partial is 0
      padding = (nibble_count % NIBBLE_PER_BYTE) != 0 
      first_byte_of_partial = scale_bytes.bytes[scale_bytes.offset]
      if padding && (first_byte_of_partial & 0xf0) != 0
        raise "bad format"
      end

      ### partial decoding
      partial_bytes = scale_bytes.get_next_bytes((nibble_count + (NIBBLE_PER_BYTE - 1)) / NIBBLE_PER_BYTE)

      ### value
      count = Compact.decode(scale_bytes).value
      value_bytes = scale_bytes.get_next_bytes(count)

      return TrieNode.new({
        hash: hash,
        node_type: "leaf",
        partial: {
          hex: partial_bytes.bytes_to_hex, 
          padding: padding
        },
        value: value_bytes.bytes_to_hex
      })
    elsif v == 0b10 << 6 || v == 0b11 << 6 # branch without mask || branch with mask
      nibble_count = decode_size.call

      ### check that the padding is valid (if any)
      # if nibble_count is odd, the half of first byte of partial is 0
      padding = nibble_count % NIBBLE_PER_BYTE != 0
      first_byte_of_partial = scale_bytes.bytes[scale_bytes.offset]
      if padding && (first_byte_of_partial & 0xf0) != 0 
        raise "bad format"
      end

      ### partial decoding
      partial_bytes = scale_bytes.get_next_bytes((nibble_count + (NIBBLE_PER_BYTE - 1)) / NIBBLE_PER_BYTE)

      ### value decoding
      if v == 0b11 << 6 # has value
        count = Compact.decode(scale_bytes).value
        value_bytes = scale_bytes.get_next_bytes(count)
      end

      ### children decoding
      children = []
      bitmap = U16.decode(scale_bytes).value
      NIBBLE_LENGTH.times do |i|
        has_child = (bitmap & (1 << i)) != 0
        children[i] = nil
        if has_child
          count = Compact.decode(scale_bytes).value
          if count == 32
            h = H256.decode(scale_bytes).value
            children[i] = h
          else
            inline = scale_bytes.get_next_bytes count
            children[i] = inline.bytes_to_hex
          end
        end
      end
      # debug
      # children.each_with_index do |child, i|
      #   if child.nil?
      #     puts "#{i}: NULL"
      #   else
      #     puts "#{i}: #{child}"
      #   end
      # end

      result = TrieNode.new({
        hash: hash,
        node_type: "branch",
        partial: {
          hex: partial_bytes.bytes_to_hex, 
          padding: padding
        },
        children: children
      })

      result[:value] = value_bytes.bytes_to_hex if value_bytes

      return result
    else
      puts "Not support"
    end

  end
end

Private Class Methods

do_check(hash, nodes, key) click to toggle source
# File lib/scale/trie.rb, line 134
def self.do_check(hash, nodes, key)
  if node = nodes[hash]
    if node[:children]
      position = key.next_nibble(node[:partial][:hex], node[:partial][:padding]).to_i(16)
      child = node[:children][position]
      return self.do_check(child, nodes, key)
    else
      return node[:value]
    end
  else
    raise "Fail"
  end
end