merkle_patricia_tree

v0.2.5

merkle_patricia_tree v0.2.5 MerklePatriciaTree.Trie.Node

This module encodes and decodes nodes from a trie encoding back into RLP form. We effectively implement c(I, i) from the Yellow Paper.

TODO: Add richer set of tests, esp. in re: storage and branch values.

Link to this section Summary

Types

trie_node()

Functions

decode_trie(trie)

Decodes the root of a given trie, effectively inverting the encoding from c(I, i) defined in Eq.(179) fo the Yellow Paper

encode_node(trie_node, trie)

Given a node, this function will encode the node and put the value to storage (for nodes that are greater than 32 bytes encoded). This implements c(I, i), Eq.(179) of the Yellow Paper

Link to this section Types

Link to this type trie_node() 
trie_node ::
  :empty |
  {:leaf, [integer], binary} |
  {:ext, [integer], binary} |
  {:branch, [binary]}

Link to this section Functions

Link to this function decode_trie(trie) 
decode_trie(MerklePatriciaTree.Trie.t) :: trie_node

Decodes the root of a given trie, effectively inverting the encoding from c(I, i) defined in Eq.(179) fo the Yellow Paper.

Examples

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<128>>) iex> |> MerklePatriciaTree.Trie.Node.decode_trie() :empty

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<198, 130, 53, 103, 130, 111, 107>>) iex> |> MerklePatriciaTree.Trie.Node.decode_trie()

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<209, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128>>) iex> |> MerklePatriciaTree.Trie.Node.decode_trie()

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<196, 130, 17, 35, 128>>) iex> |> MerklePatriciaTree.Trie.Node.decode_trie()

Link to this function encode_node(trie_node, trie) 
encode_node(trie_node, MerklePatriciaTree.Trie.t) ::
  nil |
  binary

Given a node, this function will encode the node and put the value to storage (for nodes that are greater than 32 bytes encoded). This implements c(I, i), Eq.(179) of the Yellow Paper.

Examples

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db()) iex> MerklePatriciaTree.Trie.Node.encode_node(:empty, trie) <<>>

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db()) iex> MerklePatriciaTree.Trie.Node.encode_node({:leaf, [5,6,7], “ok”}, trie) [“5g”, “ok”]

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db()) iex> MerklePatriciaTree.Trie.Node.encode_node({:branch, [<<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>, <<>>]}, trie) [“”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db()) iex> MerklePatriciaTree.Trie.Node.encode_node({:ext, [1, 2, 3], <<>>}, trie) [<<17, 35>>, “”]