Feature Request: Sparse Merkle Tree about bcrypto HOT 2 OPEN

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

from bcrypto.

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.

from bcrypto.