## Overview
We propose Merkle Mountain Belts (MMBs) as a novel data structure for upgrading MMRs, such as used in BEEFY. The final deliverables of this proposal are
1. a published research paper on MMBs
2. a Rust library implementing MMBs
3. the integration of MMBs into BEEFY

Once MMBs are deployed on Polkadot, this would have immediate cost savings - from our estimates in the millions of dollars - for users of bridges like Snowbridge and Hyperbridge.

## Technical description 

MMBs are a novel new data structure, from the same Merkle family as Merkle Mountain Ranges (MMRs) and hash chains. Like them, MMBs can be used to commit to a database and provide a compact proof of the existence of an item in it to a verifier.

To oversimplify, we can say that if most queries from verifiers are strictly for data from the latest block, then the most efficient commitment scheme would be a hash chain, while if queries tend to be for very old data, the most efficient scheme would be an MMR. The MMB is a "best of both worlds" structure whose performance is always comparable to the better of the two schemes - for any possible sampling distribution - but crucially, it outperforms them both in the case that queries are concentrated on events that took place in the time range from the last minute to the last day.

Lots of real-life databases have such a distribution of queries, and MMBs could reduce operational and access costs for them. Examples of use cases in Polkadot include XCMP messages and for cross-chain bridges the BEEFY commitment to all finalized blocks. Our cost savings analysis focuses only on the latter use case.

## Cost saving for BEEFY
While BEEFY is not the only potential use case for MMBs, the cost savings offered by MMBs for BEEFY should be sufficiently convincing in their own right: In BEEFY's particular use case, MMBs would on average save over 40% of leaf membership proof cost per transaction against MMRs. 

This would translate to over one dollar of savings per transaction in gas fees using long-term averages of gas and ETH prices. Over the next 5 years, as long as at least one BEEFY bridge is successful and has a reasonable amount of volume, we estimate cost savings in the millions of dollars.

## Funding structure

We intend to have the OpenGov treasury fund the research and success reward milestons, and intend to have the Technical Fellowship Committee (TFC) fund the implementation milestones. However, in particular since the TFC pipeline is not set in stone yet, we are open to input on this plan.

## Proposal Content
For more details, we strongly encourage reading the [full proposal](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal):

0. [Intro](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#Intro)
1. [MMB overview](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#MMB-overview)
2. [Cost saving analysis against MMRs](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#MMBs-in-BEEFY)
3. [How the MMB data structure looks like](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#How-the-MMB-data-structure-looks-like)
4. [Research & Implementation Timeframes](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#Timeframes)
5. [Success Reward Milestones](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#Success-Reward)
6. [Cost of Proposal](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#Cost-of-Proposal)
7. [Team](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#Team)

For additional insights, we also recommend studying our [Proof of Concept implementation in Clojure](https://github.com/w3f/merkle-mountain-belt-clj) and a [Sub0 2022 MMB overview talk](https://www.youtube.com/watch?v=uCwXbD9v3ew).

Thank you for reading. We look forward to your feedback!

- **Problem Statement & Audience:** Introducing Merkle Mountain Belts (MMBs) as a new data structure to enhance MMRs like BEEFY, targeting users of bridges like Snowbridge and Hyperbridge.
- **Significance:** MMBs offer potential cost savings in the millions of dollars for users of bridges like Snowbridge and Hyperbridge.
- **Proposed Solution:** Implementing MMBs through a published research paper, a Rust library, and integration into BEEFY.
- **Expected Outcomes:** Anticipated cost savings of over 40% in leaf membership proof cost per transaction against MMRs, translating to millions of dollars in savings over the next 5 years.

#2392 Treasury Proposal: Merkle Mountain Belts (MMBs)

No Active Proposals