Consider Mountain Merkle Belt(s)

### Feature description

Based on [arXiv:2511.13582v1](https://arxiv.org/abs/2511.13582v1) (the MMB paper)

* * *

## 1. Why MMB: expected benefits

The current MMR design in `miden-crypto` is a [textbook](https://docs.grin.mw/wiki/chain-state/merkle-mountain-range/) **append-only Merkle Mountain Range**: leaves appended rightward, perfect trees of equal height merge, peaks represent the frontier. It is [succinct and incremental](https://eprint.iacr.org/2019/226) but its update cost scales linearly with the number of overlapping peaks touched during an append — effectively **amortised O(log n) per leaf, but with O(log n) hash recomputations per append on average and peak rewrites proportional to the number of trees merged**.

**MMB claims to be simultaneously succinct, incremental, and _optimally additive_** — no prior Merkle structure achieves all three at once. Here is what that means for Miden's use case:

| Property | Current MMR | MMB (claimed) | Why it matters for Miden |
|---|---|---|---|
| **Update cost (append)** | `O(k)` where `k` = number of merged trees (worst-case `O(log n)`) | **`O(1)`** amortised append — a constant number of node recalculations regardless of tree merges | Cheaper block production per L2 block. Fewer hash cycles in the VM per append. |
| **First-sync (full state)** | `O(n)` leaves to download and verify | **Sublinear** — the NMC (non-membership chain) lets a new node verify inclusion against a compact summary without downloading all leaves | Dramatically faster cold-start sync for a new Miden client. |
| **Resync after N blocks offline** | `O(N)` delta data, proportional to history | **Constant-size** — the dynamic-summary structure allows a client to catch up by exchanging only a few Merkle paths plus the current summary | Clients that disconnect briefly reconnect cheaply. |
| **Proof size for recent items** | `O(log n)` regardless of recency | **Shorter for recent entries** — the belt structure biases proof length toward recent leaves | Note inclusion proofs for recent notes are smaller, reducing calldata. |
| **Asynchronous sync (UMMB variant)** | Not supported — `PartialMmr::apply()` requires a sequential delta | **Supported** — the UMMB variant allows a full node to derive a client's summary without interaction | Unlocks trust-minimised light clients that don't need to "speak" to the node — just read broadcast summaries. |
| **Commitment binding** | `hash_peaks()` hashes peak values *without* binding forest shape (`#863` risk) | The structure inherently ties shape and values via the mountain-order-summary, making structural collisions harder | Eliminates the `hash_peaks()` binding worry — shape cannot be omitted. |

> **Key takeaway:** MMB's `O(1)` append is the headline result for a STARK-based L2 where block production already pushes the proving bottleneck. Sublinear first-sync and constant-size resync are the headline results for client UX.

* * *
## 2. Construction sketch
This section gives enough mechanical detail to identify what maps onto and what would need to change in the current `miden-crypto/src/merkle/mmr/` code.

### 2.1 What MMB changes vs MMR
The paper models the mountain belt as a **sequence of "strata"** — layers of balanced Merkle trees whose roots form an ordered sequence called the **mountain-order-summary**. The key insight is:

- **Append** does not merge trees all the way to the peaks; it inserts the new leaf into the correct level of the belt and adjusts a _constant number_ of adjacent strata nodes.

- **Proof construction** reads the mountain-order-summary plus a few belt layers, yielding shorter paths for recent positions.

- **Snapshot / summary** produces a compact (poly-log) digest that supports non-membership (& therefore sublinear first-sync).

### 2.2 Mapping to current types

| Current MMR type | Nearest MMB concept | Notes |
|---|---|---|
| `Forest` | Bitmask of strata occupancy | The `Forest` (usize bitfield) encodes tree sizes; in MMB the bitmask notion is similar but strata are ordered differently — the belt extends rightward rather than merging tallest trees. |
| `MmrPeaks` | Mountain-order-summary | The current `MmrPeaks` stores a `Vec` of peak hashes + `Forest`. MMB's summary is a *sequence of stratum roots* that is never merged into peaks — it stays flat and additive. |
| `MmrDelta` | Strata-delta | Current delta carries new peaks + auth nodes; an MMB delta would carry only the changed stratum nodes plus a pointer to the added leaf. |
| `PartialMmr` | Client-side belt view | The current `PartialMmr` tracks a subset of leaves plus their auth paths through the peaks. An MMB partial view would track leaves through the belt layers, with shorter auth paths for recent items. |
| `MmrProof` | Belt membership proof | Current proof has `peak_index + MerklePath`. An MMB proof would include belt layer paths + stratum index, with length biased by recency. |
| `InOrderIndex` | Belt position | The in-order indexing currently maps to a forest of perfect trees; MMB's belt ordering is a sequence of strata where each level has a known capacity. |
### 2.3 `hash_peaks()` changes

`hash_peaks()` **— which currently hashes only** `peaks` **values without binding** `forest` **shape — becomes safer because the mountain-order-summary ties shape and values together via the stratum ordering**. The current `flatten_and_pad_peaks()` zero- padding to 16-word minimum would be replaced by a stratum-root serialization that already encodes stratum heights.

### 2.4 Sync flow (MMB vs current)

**Current SyncMMR flow** (from the audit guide):
```
Client peaks (trusted)
→ prove target header from peaks
→ get_delta(from_forest, to_forest)
→ apply(delta)
→ peaks post-apply == chain commitment?
→ add(target_header.commitment())
→ persist
```

**MMB sync flow** (sketch):

```
Client summary (trusted)
→ prove target header from summary (sublinear — no need to verify all intermediate peaks)
→ request stratum-delta (constant-size)
→ apply stratum-delta to belt view
→ summary post-apply == chain commitment? (shape is bound inherently)
→ add(target_header) — belt append is O(1)
→ persist
```

The critical UX benefit: **the client never needs to re-download or verify the peak evolution for the whole skipped range** — just the stratum nodes that changed, which is constant-size.

* * *
## 3. Backward-compatibility and evolution

### 3.1 Safe deployment: opt-in via a new type family

The existing types (`Mmr`, `PartialMmr`, `MmrDelta`, `MmrPeaks`, `MmrProof`) should **not** be replaced in-place. Instead, introduce a parallel family:

```
MmrBelt — full belt (replaces Mmr on the node side)
PartialMmrBelt — client-side belt view (replaces PartialMmr)
MmrBeltDelta — wire delta (replaces MmrDelta)
BeltSummary — mountain-order-summary (replaces MmrPeaks)
BeltProof — belt membership proof (replaces MmrProof)
ForestBelt — stratum occupancy bitmask (extends Forest)
```

**Miden nodes** can serve both the legacy `SyncChainMmr` protocol and a new `SyncChainMmrBelt` protocol simultaneously. Clients that upgrade see sublinear sync; legacy clients continue using the old path.

### 3.2 Wire protocol evolution

The current `sync_chain_mmr` RPC returns `block_range + mmr_delta`. A v2 endpoint (`sync_chain_mmr_belt`) would return `block_range + belt_delta + belt_summary`. The client's `ChainMmrInfo` would gain a `belt_delta` field alongside or instead of `mmr_delta`.

### 3.3 The lag invariant is preserved

MMR's one-block lag (block `N` inserts `commitment(block N-1)`) applies identically to the belt structure: the belt summary produced after processing block `N-1` becomes the chain commitment of block `N`. No semantic change to `BlockHeader` or `PartialBlockchain::new()` is needed.

### 3.4 VM semantics

The `miden-vm` crate's `mmr.masm` and associated VM tests currently mirror MMR append semantics. An MMB variant (`mmr_belt.masm`) would need to be written, tested, and confirmed independently against the Rust implementation before the VM can consume belt proofs. The VM team should wait for a reference implementation before starting this work.

## 4. Comparison with the current system

### 4.1 Concrete differences

| Dimension | Current MMR | MMB | Impact |
|---|---|---|---|
| **Append complexity** | `O(k)` merges per append where `k` ≤ number of leading 1-bits in the forest. For a forest at 2^20 leaves, `k` can be up to 20 — rewriting a full rightmost peak subtree. | `O(1)` — a constant number of stratum-node updates regardless of history. | Direct saving in block-proposal prover time. |
| **Proof construction** | `O(log n)` hash computations, same for any leaf. | Shorter for recent positions belt-wise; worst-case is still `O(log n)` but average is lower when most queries target recent history. | Smaller note-inclusion proofs for recent notes. |
| **Client re-sync (offline N blocks)** | Must download `O(N)` peak deltas + auth node data. | Constant-size stratum-delta, regardless of `N`. | Clients that disconnect briefly catch up with a single round-trip. |
| **Full-sync for new client** | Must download and verify all `n` leaves sequentially (or trust a checkpoint). | Sublinear — verifies inclusion against a compact summary without downloading all leaves (via NMC). | Revolutionary for mobile/browser clients. |
| **Asynchronous light client** | Not possible — `PartialMmr::apply()` is sequential and requires ordered deltas. | Possible (UMMB) — a full node derives the client's summary without interaction; the client just reads broadcast summaries. | Trust-minimised light clients without bidirectional RPC. |
| **Commitment soundness** | `#863` risk: `hash_peaks()` hashes only peak values, not forest shape. Two forests with different histories but identical peak values would collide. | The mountain-order-summary inherently binds shape — strata roots encode both value and position. | Stronger security guarantee at the commitment layer. |
| **Implementation maturity** | Battle-tested; hardened via `#812`, `#857`, `#1789`; audited in cross-repo SyncMMR guide. | Research paper only; no production reference impl exists yet. | Adoption requires significant engineering investment. |

### 4.2 Where MMB is _not_ obviously better

| Area | Why MMB may not help |
| --- | --- |
| **Peak-verification overhead** | Current `MmrPeaks::verify()` is already cheap (one Merkle path). MMB's proof verification reads belt layers, which may be more complex for the verifier. |
| **Complexity per proof** | The belt structure adds indirection — for very old leaves, the proof may not be shorter than a standard MMR proof. |
| **Storage footprint** | The belt layers may require storing more strata nodes than the MMR's peak-only storage, depending on belt depth. |
| **Cursor logic** | The `Forest` bitmask arithmetic is elegantly simple. MMB's stratum indexing and belt-height calculus is more complex and error-prone. |

MMB guarantees that the number of hash recomputations per append is _independent of history_, which no previous Merkle structure (including MMR, BHRDs, or log-structured forests) achieves.

* *

## 5. Resources and open questions

### 5.1 Required reading
| Resource | Why |
|---|---|
| [arXiv:2511.13582v1](https://arxiv.org/abs/2511.13582) — MMB paper | The primary source. Read the full construction in §3 and the UMMB variant in §4. |
| `miden-crypto/src/merkle/mmr/*.rs` | The current implementation that MMB would parallel. Start with `forest.rs`, `full.rs`, `partial.rs`, `peaks.rs`, `delta.rs`. |
| `miden-node/rpc.proto` | The wire-protocol definition; will need a v2 `SyncChainMmrBelt` message. |
| `miden-client/rpc/domain/sync.rs` | The client-side model that currently drops `block_range` — a cross-repo seam MMB needs to fix. |

### 5.2 Open questions for deeper analysis

1. **What is the exact belt-depth parameter for Miden?** MMB has a tunable "stratum width" parameter that trades append cost against proof length. For Miden's ~1s block time, what belt depth keeps append overhead negligible while giving short proofs for recent notes?

2. **How does the UMMB async variant interact with the lag invariant?** The paper's asynchronous sync mechanism lets a full node derive a client's summary. Is the one-block lag still necessary, or does UMMB remove it? If removed, the chain commitment changes semantics — a migration path is needed.

3. **Does MMB's mountain-order-summary fix** `#863` **completely?** The paper claims the summary binds shape and value. Does this match Miden's security model, or is domain-separated hashing per stratum still advisable? (See VM issue `#2996` on domain-separated leaf hashing.)

4. **What is the storage overhead?** The belt structure needs to keep multiple stratum node layers rather than a single peak vector. For a 100M-block chain, how many additional nodes must be stored on the node side versus the current MMR?

5. **Can the VM consume belt proofs with the same instruction count?** The `mmr.masm` MMR stdlib uses the `Forest` bit manipulation for mountion-range arithmetic. MMB's stratum indexing may need different VM primitives. A prototype in Rust must precede any MASM work.

### 5.3 Risks

- **Immature spec:** MMB is a single pre-print. The construction may change in a revised version, or may have hidden flaws that surface during implementation.

- **Complexity cost:** The belt structure is significantly more complex than the elegant `Forest` bitmask. Bugs in stratum indexing could cause sync failures that are hard to debug.

- **VM proving cost:** If belt-proof verification in the VM requires more cycles than current MMR proof verification, the benefit of shorter proofs may be negated.

- **Team distraction:** A full MMB implementation would distract from the current SyncMMR hardening work (`#1885`, `#2037`, `#2039`) which is actively improving the existing protocol's safety. MMB adoption should be timed after the current audit issues are resolved.

* * *
## Appendix: Current MMR codebase summary
### Existing MMB implementations

The only public reference implementation is [w3f/merkle-mountain-belt-clj](https://github.com/w3f/merkle-mountain-belt-clj) by Web3 Foundation — a Clojure library implementing both single- and double-bagging variants.