merkle_patricia_tree

merkle_patricia_tree v0.2.8 MerklePatriciaTree.Trie

MerklePatriciaTree CircleCI

Elixir implementation of Ethereum's Merkle Patricia Tries.

The encoding's specification can be found in the yellow paper or in the ethereum wiki under Appendix D.

The modified patricia merkle trie allows arbitrary storage of key, value pairs with the benefits of a merkle trie in O(n*log(n)) time for insert, lookup and delete.

This diagram is also very helpful in understanding these tries.

Installation

The easiest way to add MerklePatriciaTree to your project is by using Mix.

Add :merkle_patricia_tree as a dependency to your project's mix.exs:

defp deps do
  [
    {:merkle_patricia_tree, "~> 0.2.8"}
  ]
end

And run:

$ mix deps.get

Basic Usage

Use the MerklePatriciaTree module to create and build merkle patricia tries. You will be required to choose a storage database, and we currently support :ets and :leveldb. The follow example illustrates how to create an update a trie.

  ## Examples

    iex> trie =
    ...>    MerklePatriciaTree.Test.random_ets_db()
    ...>    |> MerklePatriciaTree.Trie.new()
    ...>    |> MerklePatriciaTree.Trie.update(<<0x01::4, 0x02::4>>, "wee")
    ...>    |> MerklePatriciaTree.Trie.update(<<0x01::4, 0x02::4, 0x03::4>>, "cool")
    iex> trie_2 = MerklePatriciaTree.Trie.update(trie, <<0x01::4, 0x02::4, 0x03::4>>, "cooler")
    iex> MerklePatriciaTree.Trie.get(trie, <<0x01::4, 0x02::4, 0x03::4>>)
    "cool"
    iex> MerklePatriciaTree.Trie.get(trie_2, <<0x01::4>>)
    nil
    iex> MerklePatriciaTree.Trie.get(trie_2, <<0x01::4, 0x02::4>>)
    "wee"
    iex> MerklePatriciaTree.Trie.get(trie_2, <<0x01::4, 0x02::4, 0x03::4>>)
    "cooler"
    iex> MerklePatriciaTree.Trie.get(trie_2, <<0x01::4, 0x02::4, 0x03::4, 0x04::4>>)
    nil

Contributing

  1. Fork it!
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create new Pull Request

Author

Geoffrey Hayes (@hayesgm) Ayrat Badykov (@ayrat555)

License

MerklePatriciaTree is released under the MIT License. See the LICENSE file for further details.

Link to this section Summary

Types

key()
root_hash()
t()

Functions

empty_trie_root_hash()

Returns the canonical empty trie.

get(trie, key)

Given a trie, returns the value associated with key.

into(next_node, trie)

Moves trie down to be rooted at next_node, this is effectively (and literally) just changing the root_hash to node_hash.

new(db, root_hash \\ "")

Contructs a new unitialized trie.

store(trie)
update(trie, key, value)

Updates a trie by setting key equal to value. If value is nil, we will instead remove key from the trie.

Link to this section Types

Link to this type

key()

key() :: binary() | [integer()]
Link to this type

root_hash()

root_hash() :: binary()
Link to this type

t()

t() :: %MerklePatriciaTree.Trie{
  db: MerklePatriciaTree.DB.db(),
  root_hash: root_hash()
}

Link to this section Functions

Link to this function

empty_trie_root_hash()

empty_trie_root_hash() :: root_hash()

Returns the canonical empty trie.

Note: this root hash will not be accessible unless you have stored the result in a db. If you are initializing a new trie, instead of checking a result is empty, it's strongly recommended you use Trie.new(db).root_hash.

Examples 

iex> MerklePatriciaTree.Trie.empty_trie_root_hash()
<<86, 232, 31, 23, 27, 204, 85, 166, 255, 131, 69, 230, 146, 192, 248, 110, 91, 72, 224, 27, 153, 108, 173, 192, 1, 98, 47, 181, 227, 99, 180, 33>>
Link to this function

get(trie, key)

get(MerklePatriciaTree.Trie.t(), MerklePatriciaTree.Trie.key()) ::
  binary() | nil

Given a trie, returns the value associated with key.

Link to this function

into(next_node, trie)

Moves trie down to be rooted at next_node, this is effectively (and literally) just changing the root_hash to node_hash.

Link to this function

new(db, root_hash \\ "")

new(MerklePatriciaTree.DB.db(), root_hash()) :: MerklePatriciaTree.Trie.t()

Contructs a new unitialized trie.

Examples

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(:trie_test_1)) %MerklePatriciaTree.Trie{db: {MerklePatriciaTree.DB.ETS, :trie_test_1}, root_hash: <<86, 232, 31, 23, 27, 204, 85, 166, 255, 131, 69, 230, 146, 192, 248, 110, 91, 72, 224, 27, 153, 108, 173, 192, 1, 98, 47, 181, 227, 99, 180, 33>>}

iex> MerklePatriciaTree.Trie.new(MerklePatriciaTree.Test.random_ets_db(:trie_test_2), <<1, 2, 3>>) %MerklePatriciaTree.Trie{db: {MerklePatriciaTree.DB.ETS, :trie_test_2}, root_hash: <<241, 136, 94, 218, 84, 183, 160, 83, 49, 140, 212, 30, 32, 147, 34, 13, 171, 21, 214, 83, 129, 177, 21, 122, 54, 51, 168, 59, 253, 92, 146, 57>>}

iex> trie = MerklePatriciaTree.Trie.new(MerklePatriciaTree.DB.LevelDB.init("/tmp/Sgt4V05yvi2BrhaBCZ9a"), <<1, 2, 3>>) iex> trie.root_hash <<241, 136, 94, 218, 84, 183, 160, 83, 49, 140, 212, 30, 32, 147, 34,

13, 171, 21, 214, 83, 129, 177, 21, 122, 54, 51, 168, 59, 253, 92,
146, 57>>

iex> {db, _db_ref} = trie.db iex> db MerklePatriciaTree.DB.LevelDB

Link to this function

store(trie)

Link to this function

update(trie, key, value)

update(
  MerklePatriciaTree.Trie.t(),
  MerklePatriciaTree.Trie.key(),
  ExRLP.t() | nil
) :: MerklePatriciaTree.Trie.t()

Updates a trie by setting key equal to value. If value is nil, we will instead remove key from the trie.