Feature Request: Sparse Merkle Tree

[tynes]

I think its possible to create a wrapper over lib/mrkl.js to create a sparse merkle tree with an easy to use API. This could be used to add commitments to all previous blocks in the block header, allowing for a Flyclient like construction. Light clients will be able to run even lighter as they will not need to index all previous blocks and can just keep the latest block indexed.

Potential API:

• Constructor with hashing algo, number of leaves
• Set an item at an index
• Delete an item at an index
• Get an item at an index
• Push an item to the next index, when the consumer doesn't want to manage the index and just wants to add items to a set
• Get root
• Get proof (inclusion/exclusion)
• Clear cache

It would also be cool to allow for passing custom read/write functions, similar to how bcoin has a custom createSocket function, so that different storage backends can be used/tested.

Is this something that you would consider for bcrypto?

[tynes]

Here are some various implementations that I have been able to find.

• https://github.com/google/trillian
• https://github.com/ethereum/research/tree/master/sparse_merkle_tree
• https://github.com/loomnetwork/plasma-cash/blob/master/server/test/SparseMerkleTree.js
• https://github.com/loomnetwork/plasma-cash/blob/master/server/contracts/Core/SparseMerkleTree.sol
• https://github.com/aergoio/SMT

[chjj]

A sparse merkle tree requires some kind of data management unless you're only going a few levels deep (unlikely).

The sparse merkle block commitment was an idea joseph and I had (as an alternative to the severely flawed way other projects are doing this). The basic notion is you allocate a sparse merkle tree 32 levels deep. You create an authenticated map of height(uint32) to hash. To get actual distribution at the leaves, you run the height through a perfect hash function before insertion (1 2 3).

32 bits is ~4.3 billion potential leaves, so that necessitates some kind of data management. This doesn't belong in bcrypto. It definitely justifies having its own repo.

We had an impl. of a sparse merkle tree to benchmark it against urkel a while ago. It's either in the urkel repo history or the btrie repo. If we decide to do this for handshake, I would probably just include it in the hsd repo.

edit: Also, note that this might be the only legitimate use-case for a sparse merkle tree in the blockchain space. It's far too slow to use for anything else.