merkle_patricia_tree

merkle_patricia_tree v0.2.8 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>>, ""]