Tracking issue: Sparse Merkle tree implementations

[bobbinth]

Goal

We should add implementations of Sparse Merkle tree.

Details

Specifically, I'm thinking of the following variants:

• Simple SMT (could go into /merkle/simple_smt.rs module).
• Compact SMT (could go into /merkle/compact_smt.rs module).

References:

• Finish TSMT miden-vm#258
• Implement stdlib smt module for Word key/values miden-vm#373

MUST HAVE

Preview Give feedback

1. Migrate simple Sparse Merkle tree #21
   +0
   
2. Implement domain separation for compact sparse Merkle tree #35
   +0
   
3. Design compact Sparse Merkle tree #22
   +0
4. Replace mtree_cwm with mtree_clone miden-vm#762
   +0
   
5. pre-load the AdviceProvider with immutable SimpleSMT of all possible depth (1-64) miden-vm#763
   +0
   
6. Implement MerkleStore data structure #89
   +0
   
7. Integrate sparse Merkle tree in advice provider #38
   +0
8. Implement tiered compact sparse Merkle tree #36
   +0
   
9. Implement compact sparse Merkle tree in Miden assembly #37
   +0
   

NICE TO HAVE

Preview Give feedback

No tasks being tracked yet.

Working group:

@Al-Kindi-0, @bobbinth, @grjte, @vlopes11, @hackaugusto

Workflow

• Discussion should happen here or in the related sub-issues.
• PRs should only be merged by the coordinator, to ensure everyone is able to review.
• Aim to complete reviews within 24 hours.
• When a related sub-issue is opened:
  • add it to the list of sub-issues in this tracking issue
• When opening a related PR:
  • request review from everyone in this working group
• When a sub-issue is completed:
  • close the related issue with a comment that links to the PR where the work was completed

Coordinator: @vlopes11

Workflow

The working group coordinator ensures scope & progress tracking are transparent and accurate. They will:

• Merge approved PRs after all working group members have completed their reviews.
  • add the PR # to the relevant section of the current tracking PR.
  • close any completed sub-issue(s) with a comment that links to the PR where the work was completed
• Monitor workflow items and complete anything that slips through the cracks.
• Monitor scope to see if anything is untracked or unclear. Create missing sub-issues or initiate discussion as required.
• Monitor progress to see if there's anything which isn't moving forward. Initiate discussion as required.
• Identify PRs with especially significant changes and add @grjte and @bobbinth for review.