Feature Request: Sparse Merkle Tree
- Dominant language
- JavaScript
- Stars
- 102
- Forks
- 40
- PR merge metrics
- No merged PRs in 30d
Description
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?
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading lib/mrkl.js to understand the existing Merkle-tree implementation and whether it can support the proposed wrapper. Clarify the API and storage callback requirements before implementation; done would mean an agreed sparse-tree feature covering indexed updates, reads, deletion, roots, inclusion and exclusion proofs, sequential pushes, and cache clearing.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript
- Domain
- cryptography
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100