Treasury Proposal: Merkle Mountain Belts (MMBs)

Executive Summary

We propose Merkle Mountain Belts (MMBs) as a novel data structure for upgrading Merkle Mountain Ranges (MMRs), such as used in BEEFY. The final deliverables of this proposal are

a published research paper on MMBs, coauthored with Alistair Stewart (Head of Research at Web3 Foundation),
a Rust library implementing MMBs, and
the integration of MMBs into the BEEFY protocol.

Once MMBs are deployed on Polkadot, this will have immediate cost savings - from our estimates 1.0-1.4 million dollars per year - for users of bridges like Snowbridge and Hyperbridge, as well as other potential applications within the Polkadot/JAM ecosystem.

Timeframe

December 2024 - December 2025 for completion of all milestones.

Requested Funds

506'110 USDC until completion of all milestones,
additional 41'504 DOT once the savings accrued by the Polkadot/JAM ecosystem exceed the aggregate cost of the proposal, and
a 30% reward share of the saving incurred over 10 years from the moment the economic impact of our proposal is net-positive for the Polkadot/JAM ecosystem (note: this variable funding is not requested within this proposal, but will be requested in followup referenda once the saving threshold is reached, substantiated by calculation of the actual saving incurred via on-chain data).

See the funding section in the full proposal for details and rationale. All requested funds use the Swiss National Bank USD/CHF foreign exchange rate and the 30-day EMA of USD/DOT via Subscan at the date of submission (25. November 2024).

Preimage content can be verified against @MerkleMountainBelts/MMB-Proposal-Preimage, most conveniently using dev.papi.how/extrinsics.

Technical description

Merkle Mountain Belts (MMBs) are a novel type of Merkle structure, from the same family that contains Merkle Mountain Ranges (MMRs) and hash chains. Like them, MMBs can be used to commit to a large database, and provide a compact proof of existence of a data entry to a verifier. This allows, e.g., users to quickly authenticate a transaction.

To oversimplify, we can say that if most user queries are for data from the latest handful of blocks, then the most efficient structure would be a hash chain, while if queries tend to be for very old data, the most efficient structure would be an MMR. The MMB structure is "the best of both worlds" with a performance that is always comparable to the better of the two previous structures --for any possible query recency-- and it considerably outperforms them both when users query data that was generated between the last minute and the last day.

In lots of real-life applications, we naturally observe a recency bias, where users' queries are concentrated over recent events, and MMBs are specifically designed to reduce the operational and data access costs for them. Examples of use cases in Polkadot include XCMP messages, and the BEEFY commitment to all finalized blocks, which is used in cross-chain bridges. Our cost savings analysis focuses only on the latter use case.

More precisely, while MMR attempts to maintain a balanced tree, MMB maintains a slightly unbalanced tree, so that the leaves of recently generated data are closer to the root. In a cross-chain bridge, for example, a user's fee for a message (and its Merkle proof) is proportional to the message's depth in the tree, so reducing this depth means less fees.

Timeline & Payment details

Our proposal consists of 6 delivery milestones that we anticipate to deliver until December 2025. We will post regular updates of our progress on https://ogtracker.io/.

We show in the image our projected delivery dates. We establish a conservative staggered payment schedule, wherein the payment for each milestone is executed a few weeks after its expected delivery. Naturally, this payment schedule can be modified in the future, in case we do not deliver a milestone before its scheduled payment. Notice in particular that 30% of the proposal's cost is only to be paid once the library's aggregate savings for the ecosystem have exceeded our proposal's cost. We expect this to occure before December 2027; we have scheduled the corresponding payment for a conservative July 2028.

The team

The members of our team are highly qualified and have worked in Polkadot since pre-mainnet days. Our principal researcher Alfonso Cevallos has a Ph.D. in mathematics and is a co-author of many Polkadot papers, including the 2020 overview paper. Our principal developer Robert Hambrock has been one of the earliest stewards of the Polkadot-Ethereum bridge, going back to its initial W3F grant, design of protocols, and implementation.

More details on ourselves and Cryp GmbH are available here.

Changes against original proposal

Since our original discussion post in July 2024, we have made some material changes to it:

Deferral of 30% of the proposal's cost to economically positive threshold.
Switched to 7-day EMA instead of the original proposal's 30-day EMA, given the marked price increase of DOT in the last week, which resulted in a 31% reduction of our proposal's DOT payout portion. While we think the 30-day EMA would be more appropriate since the corresponding payout is scheduled over three years into the future (July 2028), this change reflects our conviction in Polkadot.
Added an audit quote from Oak Security. Note that an audit would be covered by a separate proposal once the library is mostly ready and the audit's scope is well-defined.
Added a maintenance clause for our included work on the MMB rust library even after its deliver.
Performed back-of-the-envelope analysis of L2 gas cost savings.
Full version tracking against the original proposal is available here.

We deeply thank everyone who provided their feedback and contributions that shaped these adjustments to the proposal, foremost the following individuals and teams:

Raul Romanutti,
Saxemberg (preproposal feedback shared with consent here),
Parity Bridge Team (in particular Adrian Acatangiu),
Snowfork Team (in particular Vincent Geddes and Aidan Musnitzky),
Hyperbridge team (in particular Seun Lanlege),
Oak Security, and
AAG regulars

For more details, we strongly encourage reading the full proposal.

We also recommend studying our Sub0 2022 MMB overview talk, and our brief overview on AAG: Kusamarian AAG #147.

Thank you for reading and happy voting!