<h2 id="overview">Overview</h2>
<p>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</p>
<ol>
<li>a published research paper on MMBs</li>
<li>a Rust library implementing MMBs</li>
<li>the integration of MMBs into BEEFY</li>
</ol>
<p>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.</p>
<h2 id="technicaldescription">Technical description</h2>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<h2 id="costsavingforbeefy">Cost saving for BEEFY</h2>
<p>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.</p>
<p>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.</p>
<h2 id="fundingstructure">Funding structure</h2>
<p>The funding splits into a <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Cost-of-Proposal-upon-Completion"><em>cost upon completion</em></a> and a <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Success-Reward"><em>success reward</em></a>; please see the linked sections of the proposal for their structure.</p>
<h2 id="proposalcontent">Proposal Content</h2>
<p>For more details, we strongly encourage reading the <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2">full proposal</a>:</p>
<ol start="0">
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Intro">Intro</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#MMB-overview">MMB overview</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#MMBs-in-BEEFY">Cost saving analysis against MMRs</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#How-the-MMB-data-structure-looks-like">How the MMB data structure looks like</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Timeframes">Research &amp; Implementation Timeframes</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Cost-of-Proposal-upon-Completion">Cost of Proposal upon Completion</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Success-Reward">Success Reward</a></li>
<li><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Team">Team</a></li>
</ol>
<p>For additional insights, we also recommend studying our <a href="https://github.com/w3f/merkle-mountain-belt-clj">Proof of Concept implementation in Clojure</a> and a <a href="https://www.youtube.com/watch?v=uCwXbD9v3ew">Sub0 2022 MMB overview talk</a>. We also gave a brief overview on AAG: <a href="https://www.youtube.com/watch?v=kAGXyyAab-Q&amp;t=572s">Kusamarian AAG #147</a>.</p>
<p>Thank you for reading. We look forward to your feedback!</p>

## 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!

Treasury Proposal: Merkle Mountain Belts (MMBs)

- Problem Statement: Introducing Merkle Mountain Belts (MMBs) as a data structure upgrade for MMRs like BEEFY to enhance efficiency and cost savings for users of bridges like Snowbridge and Hyperbridge.
- Significance: MMBs offer a hybrid solution between hash chains and MMRs, providing cost savings of over 40% for BEEFY transactions, translating to millions of dollars in savings over 5 years.
- Proposed Solution: Implement MMBs through a research paper, Rust library, and integration into BEEFY on Polkadot.
- Expected Outcomes: Immediate cost savings for users of bridges, increased efficiency in data commitment, and millions of dollars saved in gas fees over 5 years.

#2392 Treasury Proposal: Merkle Mountain Belts (MMBs)

No Active Proposals