Merkle tree implementation using the excellent and fast rust-powered ex_keccak library under the hood. If you'd like to know more about the basic algorithm, check out this great introductory talk.
The package can be installed
by adding merkle_fun to your list of dependencies in mix.exs:
def deps do
[
{:merkle_fun, "~> 0.6.0"}
]
endThere are multiple ways to implement a binary tree. We decided to use an array format approach to minimize storage requirements and make the sibling lookup easy. If it's been a while since you've done a basic data structures course, check out this refresher.
Wait a minute you say! Elixir doesn't have arrays? Well there is an Erlang implementation as well as a nice Elixir library. However, after thinking about the problem our use case didn't need updates. We build the tree and don't need to append further nodes. In such a case a tuple suits our read only needs perfectly. If we decide to add Merkle Mountain Ranges (in the future) we will need something with better append performance.
Initial leaf lookup is currently looking through the entire tree. Yeah I need to fix that.
- second pre-image attack
- unbalanced trees attack
- Make tree
- Make proof
- Validate proof
- Pretty Print tree
- Fast leaf look up
Thanks goes out to Rodger Maarfi (@acrite22) for pairing with me on this.
Documentation can be generated with ExDoc and published on HexDocs. Once published, the docs can be found at https://hexdocs.pm/merkle_fun.