MerklePatriciaTree

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.