bcoin-org / bcoin-org/bcrypto

Feature Request: Sparse Merkle Tree

Open
#25 2 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.