Sparse/Incremental merkle tree, on-chain append

[HarryR]

Hi,

I am working on an incremental merkle tree, aiming to reduce the on-chain cost of adding items to it.

See my notes at: https://github.com/HarryR/ethsnarks/issues/16

• Python implementation https://github.com/HarryR/ethsnarks/blob/master/ethsnarks/merkletree.py

  The main problem is, if the merkle tree is built on-chain using on-chain storage for all of the nodes, then it is expensive (e.g. 750k gas for 29 levels). e.g. think of every database store costing money, and every database access costing money, but passing arguments to the program (e.g. a couple of proof paths) is much cheaper.

  Do you have any ideas about this?

[musalbas]

Do you need a key-value store or just a list of items? If the latter, have you seen the Merkle tree specified in RFC 6962 for Certificate Transparency (also known as Merkle Mountain Ranges)? You can add n nodes to the tree, and generate an O(log(n)) sized "Merkle Consistency Proof" that the new root is append-only.

[HarryR]

What I was doing is similar to MMR, but it allows you to append an item to an incremental merkle tree using the proof of the previous item which was added and a proof of the new item, while being able to skip duplicate path elements etc.

Image a verifier, which verifies that you have correctly added one item to an incremental merkle tree.

But the only state it stores is the proof of the last item which was added, and the current root.