aeternity / elixir-merkle-patricia-tree Goto Github PK

View Code? Open in Web Editor NEW

This project forked from exthereum/merkle_patricia_tree

10.0 17.0 6.0 191 KB

Elixir implementation of modified Merkle Patricia tree (trie)

License: MIT License

Elixir 100.00%

elixir-merkle-patricia-tree's Introduction

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.

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.DB.ETS.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

Fork it!
Create your feature branch (git checkout -b my-new-feature)
Commit your changes (git commit -am 'Add some feature')
Push to the branch (git push origin my-new-feature)
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.

elixir-merkle-patricia-tree's People

Contributors

Stargazers

Watchers

Forkers

stjordanis malroc kenspirit hansonkd isabella232 inomurko

elixir-merkle-patricia-tree's Issues

Test failed (Ethereum Common Tests, root hash)

Found by @grzegorz225

1) test Ethereum Common Tests (MerklePatriciaTreeTest)
     test/merkle_patricia_tree_test.exs:11
     Assertion with == failed
     code:  assert trie.root_hash() == test["root"] |> hex_to_binary
     left:  <<29, 106, 144, 207, 179, 208, 47, 233, 11, 118, 195, 7, 121, 115,
              10, 90, 195, 211, 88, 113, 206, 45, 251, 7, 107, 129, 67, 190, 5,
              54, 237, 167>>
     right: <<138, 173, 120, 157, 255, 47, 83, 139, 202, 93, 142, 165, 110, 138,
              190, 16, 244, 199, 186, 58, 93, 234, 149, 254, 164, 205, 110, 124,
              58, 17, 104, 211>>
     stacktrace:
       test/merkle_patricia_tree_test.exs:33: anonymous fn/3 in MerklePatriciaTreeTest."test Ethereum Common Tests"/1
       (stdlib) lists.erl:1263: :lists.foldl/3
       test/merkle_patricia_tree_test.exs:13: anonymous fn/2 in MerklePatriciaTreeTest."test Ethereum Common Tests"/1
       (stdlib) lists.erl:1263: :lists.foldl/3
       test/merkle_patricia_tree_test.exs:12: (test)

Readme adjustments

Readme should reflect that this repo is not Ethereum compatible and is for Aeternity blockchain. (We changed hash and maybe something else)

Also the Installation section should be adjusted.

Updating key when longer key exists

Root hash is wrong when we update a key when there exists a longer key:

Steps to reproduce:

db = MerklePatriciaTree.DB.ETS.random_ets_db()
trie1 = Trie.new(db)
trie2 = Trie.new(db)
trie1 = Trie.update(trie1, "key", "oldvalue")
trie1 = Trie.update(trie1, "key_loner", "loner_key_value")
trie1 = Trie.update(trie1, "key", "newvalue")
trie2 = Trie.update(trie2, "key", "newvalue")
trie2 = Trie.update(trie2, "key_loner", "loner_key_value")
trie1.root_hash == trie2.root_hash

Result: false

Expected result: true

I added a test that fails.

Note: Ethereum tests also fail - #10

test Check whether we actually check the hashes ;) (MerklePatriciaTreeProofTest)
test/proof_test.exs:67
Assertion with == failed
code: assert false == Proof.verify_proof(bogus_key, bogus_val, trie.root_hash(), bogus_proof)
left: false
right: true
stacktrace:
test/proof_test.exs:79: (test)