New paper: The Merkle Mountain Belt

General
1

Abstract:

Merkle structures are widely used as commitment schemes: they allow a prover to publish a compact commitment to an ordered list of items, and then efficiently prove to a verifier that is the -th item in it. We compare different Merkle structures and their corresponding properties as commitment schemes in the context of blockchain applications. Our primary goal is to speed up light client protocols so that, e.g., a user can verify a transaction efficiently from their smartphone.

For instance, the Merkle Mountain Range (MMR) yields a succinct scheme: a light client synchronizing for the first time can do so with a complexity sublinear in . On the other hand, the Merkle chain, traditionally used to commit to block headers, is not succinct, but it is incremental - a light client resynchronizing frequently can do so with constant complexity - and optimally additive - the structure can be updated in constant time when a new item is appended to list .

We introduce new Merkle structures, most notably the Merkle Mountain Belt (MMB), the first to be simultaneously succinct, incremental and optimally additive.
A variant called UMMB is also asynchronous: a light client may continue to interact with the network even when out of sync with the public commitment. Our Merkle structures are slightly unbalanced, so that items recently appended to receive shorter membership proofs than older items. This feature reduces a light client’s expected costs, in applications where queries are biased towards recently generated data.

LLM analysis of MMB with respect to neptune-cash

Title: Proposal: Replacing AOCL’s MMR with “Merkle Mountain Belts” (MMB) for O(1) Scalability

TL;DR:
A paper published this month (Nov 2025) introduces the Merkle Mountain Belt (MMB). This structure is a direct evolution of the Merkle Mountain Range (MMR) that offers O(1) append complexity and significantly cheaper witness updates for recent data. Integrating this into the Neptune Mutator Set’s Append-Only Commitment List (AOCL) could drastically reduce sync times for mobile wallets and improve prover generation speed.

1. The Current State: AOCL & MMR

Currently, Neptune’s Mutator Set relies on an AOCL backed by a Merkle Mountain Range (MMR) to store the commitment of every UTXO ever created.

  • Append Cost: O(\log n). As the chain grows, adding items involves “bagging” peaks which grows logarithmically.
  • Update Cost: To update a membership proof (witness) from Block N to Block N+100, the wallet must process the shifting peaks. For an MMR, this cost is relatively uniform regardless of the UTXO’s age.

2. The Upgrade: Merkle Mountain Belt (MMB)

The MMB changes how the “peaks” of the mountains are managed (using a strategy called “belting” and “lazy merges”).

  • Append Cost: O(1) (Constant Time). Appending a new item takes a constant number of hashes (average ~4) regardless of whether the chain has 1,000 or 1 billion items.
  • Update Logic: MMB introduces “Recent-Proof Bias.” The structure is intentionally slightly unbalanced so that recently added items have significantly shorter authentication paths than older items.

3. Why This Matters for Neptune

A. “Instant” Light Client Syncing (The Killer Feature)

The primary bottleneck for a Neptune light client (e.g., a mobile wallet) is maintaining the Mutator Set Membership Proof (MSMP). If a user goes offline for a month, their wallet must “fast-forward” their local witnesses to the current network tip.

  • With MMR: The cost to update a witness is generally uniform.
  • With MMB: Because of the “Recent-Proof Bias,” updating witnesses for recent UTXOs (e.g., change outputs or recent payments) becomes computationally trivial. The update algorithm for the “belt” portion of the structure is highly optimized.
  • Result: Mobile wallets would sync significantly faster and consume less battery, as the majority of spendable funds (which are often recent) sit in the “cheap” part of the data structure.

B. Faster zk-STARK Proving

In Neptune, the bottleneck for transaction speed is often the local generation of the zk-STARK proof.

  • The Optimization: The prover must hash the authentication path inside the STARK circuit.
  • The Gain: Since MMB provides shorter paths for recent items, the resulting arithmetic circuit for a standard transaction (spending recent funds) has fewer constraints.
  • Impact: This directly translates to faster proving times for the user, making the “click-to-send” experience snappier.

4. Implementation: A Drop-in Replacement

The beauty of this proposal is that it is isolated to the AOCL.

  • It does not require changing the Sliding Window Bloom Filter (SWBF).
  • It does not change the logic of how removal records are generated.
  • It simply replaces the underlying accumulator for the “Additions” list.

5. References & Resources

  • Paper: The Merkle Mountain Belt (Cevallos, Hambrock, Stewart - Nov 18, 2025)
  • Link: arxiv.org/abs/2511.13582

Recommendation for Architects:
I suggest investigating if the “Lazy Merge” logic of the MMB can be adapted to the Triton VM efficiently. If the hashing cost of the new “belting” strategy is comparable to the current peak-bagging, the asymptotic gains in sync speed for light clients make this a clear win for the network’s UX.