Check out the Issue Explorer
Looking to fund some work? You can submit a new Funded Issue here.
A sparse Merkle tree (SMT) is a data structure useful for storing a key/value map which works as follows. An empty SMT is simply a Merkle tree with 2^256 leaves, where every leaf is a zero value. Because every element at the second level of the tree is the same z2=hash(0, 0), and every element at the third level is the same z3=hash(z2, z2) and so forth this can be trivially computed in 256 hashes. From there, we can add or remove values by modifying values in place in the sparse Merkle tree, eg. to add the value 42 at position 3, we modify the second value the second level to v2=hash(0, 42), the first value at the third level to v3=hash(0, v2), the first value at the fourth level to v2=hash(v3, z3) (since at this point, the left subtree represents keys 0…3 and the right subtree represents keys 4…7 which are still all empty), and so forth up to the top. [source](https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751)
- the [given contract](https://github.com/leapdao/leap-contracts/blob/master/contracts/SparseMerkleTree.sol) implements a key length of 64 bit. extend this to 160 bits, so we can use addresses as keys.
- extend the unit tests to cover read / update / delete for all edge cases.
- separate SparseMerkleTree contract into contract and lib.
## Gain for the project
- allow to store maps in [ERC1948](https://github.com/ethereum/EIPs/pull/1948)
bounty gardener: @johannbarbie / 10%
bounty worker: @roleengineer / 75%
bounty reviewer: @johannbarbie / 15%