merkle_patricia_tree

v0.2.5

merkle_patricia_tree v0.2.5 MerklePatriciaTree.Trie.Storage

Module to get and put nodes in a trie by the given storage mechanism. Generally, handles the function n(I, i), Eq.(178) from the Yellow Paper.

Link to this section Summary

Functions

get_node(trie)

Gets the RLP encoded value of a given trie root. Specifically, we invert the function n(I, i) Eq.(178) from the Yellow Paper

max_rlp_len()
put_node(rlp, trie)

Takes an RLP-encoded node and pushes it to storage, as defined by n(I, i) Eq.(178) of the Yellow Paper

store(rlp_encoded_node, db)

TODO: Doc and test

Link to this section Functions

Link to this function get_node(trie) 
get_node(MerklePatriciaTree.Trie.t) :: ExRLP.t

Gets the RLP encoded value of a given trie root. Specifically, we invert the function n(I, i) Eq.(178) from the Yellow Paper.

Examples

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<>>) …> |> MerklePatriciaTree.Trie.Storage.get_node() <<>>

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<130, 72, 105>>) …> |> MerklePatriciaTree.Trie.Storage.get_node() “Hi”

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<254, 112, 17, 90, 21, 82, 19, 29, 72, 106, 175, 110, 87, 220, 249, 140, 74, 165, 64, 94, 174, 79, 78, 189, 145, 143, 92, 53, 173, 136, 220, 145>>) …> |> MerklePatriciaTree.Trie.Storage.get_node() ** (RuntimeError) Cannot find value in DB: <<254, 112, 17, 90, 21, 82, 19, 29, 72, 106, 175, 110, 87, 220, 249, 140, 74, 165, 64, 94, 174, 79, 78, 189, 145, 143, 92, 53, 173, 136, 220, 145>>

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(), <<130, 72, 105>>) iex> MerklePatriciaTree.Trie.Storage.put_node([“AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA”], trie) <<141, 163, 93, 242, 120, 27, 128, 97, 138, 56, 116, 101, 165, 201,

165, 139, 86, 73, 85, 153, 45, 38, 207, 186, 196, 202, 111, 84,
214, 26, 122, 164>>

iex> MerklePatriciaTree.Trie.Storage.get_node(%{trie| root_hash: <<141, 163, 93, 242, 120, 27, 128, 97, 138, 56, 116, 101, 165, 201, 165, 139, 86, 73, 85, 153, 45, 38, 207, 186, 196, 202, 111, 84, 214, 26, 122, 164>>}) [“AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA”]

Link to this function max_rlp_len() 
max_rlp_len() :: integer
Link to this function put_node(rlp, trie) 
put_node(ExRLP.t, MerklePatriciaTree.Trie.t) :: binary

Takes an RLP-encoded node and pushes it to storage, as defined by n(I, i) Eq.(178) of the Yellow Paper.

NOTA BENE: we are forced to deviate from the Yellow Paper as nodes which are smaller than 32 bytes aren’t encoded in RLP, as suggested by the equations.

Specifically, Eq.(178) says that the node is encoded as c(J,i) in the second portion of the definition of n. By the definition of c, all return values are RLP encoded. But, we have found emperically that the n does not encode values to RLP for smaller nodes.

Examples 

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db())
iex> MerklePatriciaTree.Trie.Storage.put_node(<<>>, trie)
<<>>
iex> MerklePatriciaTree.Trie.Storage.put_node("Hi", trie)
"Hi"
iex> MerklePatriciaTree.Trie.Storage.put_node(["AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"], trie)
<<141, 163, 93, 242, 120, 27, 128, 97, 138, 56, 116, 101, 165, 201,
       165, 139, 86, 73, 85, 153, 45, 38, 207, 186, 196, 202, 111, 84,
       214, 26, 122, 164>>
Link to this function store(rlp_encoded_node, db) 
store(ExRLP.t, MerklePatriciaTree.DB.db) :: binary

TODO: Doc and test