<h2 id="executivesummary">Executive Summary</h2>
<p>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</p>
<ul>
<li>a published research paper on MMBs, coauthored with Alistair Stewart (Head of Research at Web3 Foundation),</li>
<li>a Rust library implementing MMBs, and</li>
<li>the integration of MMBs into the BEEFY protocol.</li>
</ul>
<p>Once MMBs are deployed on Polkadot, this will have immediate cost savings - from our estimates <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Cost-savings-analysis-against-MMRs">1.0-1.4 million dollars per year</a> - for users of bridges like Snowbridge and Hyperbridge, as well as other potential applications within the Polkadot/JAM ecosystem.</p>
<h3 id="timeframe">Timeframe</h3>
<p>December 2024 - December 2025 for completion of all milestones.</p>
<h3 id="requestedfunds">Requested Funds</h3>
<ol>
<li>506'110 USDC until completion of all milestones,</li>
<li>additional 29'428.62 DOT once the savings accrued by the Polkadot/JAM ecosystem exceed the aggregate cost of the proposal, and</li>
<li>a 20-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 <em>not</em> 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).<br /><em>*: Specifically, as decided by community vote:&nbsp;</em>
<p><em>Of annual savings below $1.4M, we receive 30% as success reward. Of annual savings above $1.4m, we receive 20% as success reward.</em></p>
</li>
</ol>
<p>See the <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Cost-of-Proposal-upon-Completion">funding section in the full proposal for details and rationale</a>. All requested funds use the <a href="https://www.snb.ch/en/the-snb/mandates-goals/statistics/statistics-pub/current_interest_exchange_rates">Swiss National Bank USD/CHF foreign exchange rate</a> and the 7-day EMA of USD/DOT via <a href="https://polkadot.subscan.io/tools/price_converter">Subscan</a> at the date of submission (25. November 2024).</p>
<p>Preimage content can be verified against <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Proposal-Preimage">@MerkleMountainBelts/MMB-Proposal-Preimage</a>, most conveniently using <a href="https://dev.papi.how/extrinsics">dev.papi.how/extrinsics</a>.</p>
<h2 id="technicaldescription">Technical description</h2>
<p>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.</p>
<p>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.</p>
<p>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 <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Cost-savings-analysis-against-MMRs">cost savings analysis</a> focuses only on the latter use case.</p>
<p>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.</p>
<p><a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#What-the-MMB-data-structure-looks-like">More on the MMB structure here</a>.</p>
<h2 id="timelinepaymentdetails">Timeline &amp; Payment details</h2>
<p>Our proposal consists of 6 delivery milestones that we anticipate to deliver until December 2025. We will post regular updates of our progress on <a href="https://ogtracker.io/.">https://ogtracker.io/.</a></p>
<p><img src="https://hackmd.io/_uploads/BknZUvz7Jx.png" alt="image" /></p>
<p>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.</p>
<h2 id="theteam">The team</h2>
<p>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 <a href="https://arxiv.org/abs/2005.13456">2020 overview paper</a>. 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.</p>
<p>More details on ourselves and Cryp GmbH are available <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2#Team">here</a>.</p>
<h2 id="changesagainstoriginalproposal">Changes against original proposal</h2>
<p>Since our <a href="2392">original discussion post in July 2024</a>, we have made some material changes to it:</p>
<ul>
<li><a href="https://github.com/Cryp-GmbH/mmb-proposal/commit/fdfce71dcffb5ad2e12b4df8ba9503c0bbd9e9bb">Deferral of 30% of the proposal's cost to economically positive threshold</a>.</li>
<li><a href="fd5a7b1133bf3b8b7cbd1ca520257125588a5208">Switched to 7-day EMA</a> instead of the <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal#Cost-of-Proposal">original proposal's 30-day EMA</a>, given the marked price increase of DOT in the last week, which resulted in a <a href="https://polkadot.subscan.io/tools/price_converter?value=216904.276985743&amp;type=time&amp;from=USD&amp;to=DOT&amp;time=1732557600">31% reduction</a> 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.</li>
<li><a href="https://github.com/Cryp-GmbH/mmb-proposal/commit/c45a395bc0676aa290482ece67437e114bb83b7d">Added an audit quote from Oak Security</a>. 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.</li>
<li>Added a <a href="https://github.com/Cryp-GmbH/mmb-proposal/commit/9a0779e20cd8f208abd6c4cbbbf62955cd16f770">maintenance clause</a> for our included work on the MMB rust library even after its deliver.</li>
<li>Performed <a href="c7a8d419eac75852790f4061e01e374221a8325b">back-of-the-envelope analysis of L2 gas cost savings</a>.</li>
<li>Reduced the success reward as via feedback we received from AAG and a KusDAO poll.</li>
<li>Full version tracking against the original proposal is available <a href="https://github.com/Cryp-GmbH/mmb-proposal/compare/original-proposal&hellip;main">here</a>.</li>
</ul>
<p>We deeply thank everyone who provided their feedback and contributions that shaped these adjustments to the proposal, foremost the following individuals and teams:</p>
<ul>
<li>Raul Romanutti,</li>
<li>Saxemberg (preproposal feedback shared with consent <a href="https://drive.google.com/file/d/1t02YUwyuPYNZvk9xd4ouQQu8zrLs6A75/view?usp=sharing">here</a>),</li>
<li>Parity Bridge Team (in particular Adrian Acatangiu),</li>
<li>Snowfork Team (in particular Vincent Geddes and Aidan Musnitzky),</li>
<li>Hyperbridge team (in particular Seun Lanlege),</li>
<li>Oak Security, and</li>
<li>AAG regulars</li>
</ul>
<hr />
<p>For more details, we strongly encourage reading <a href="https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2">the full proposal</a>.</p>
<p>We also recommend studying our <a href="https://www.youtube.com/watch?v=uCwXbD9v3ew">Sub0 2022 MMB overview talk</a>, and our 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 and happy voting!</p>

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

Treasury Proposal: Merkle Mountain Belts (MMBs)

Treasury

Send a batch of dispatch calls and atomically execute them.
The whole transaction will rollback and fail if any of the calls failed.

May be called from any origin except `None`.

- `calls`: The calls to be dispatched from the same origin. The number of call must not
  exceed the constant: `batched_calls_limit` (available in constant metadata).

If origin is root then the calls are dispatched without checking origin filter. (This
includes bypassing `frame_system::Config::BaseCallFilter`).

## Complexity
- O(C) where C is the number of calls to be batched.

- **Problem Statement:** Introducing Merkle Mountain Belts (MMBs) as an upgrade to Merkle Mountain Ranges (MMRs) in the BEEFY protocol to enhance data structure efficiency.
- **Significance:** Expected cost savings of 1.0-1.4 million dollars per year for users of bridges like Snowbridge and Hyperbridge within the Polkadot/JAM ecosystem.
- **Proposed Solution:** Develop a Rust library implementing MMBs and integrate them into the BEEFY protocol.
- **Expected Outcomes:** Immediate cost savings for users, improved data access efficiency, and potential long-term rewards for the Polkadot/JAM ecosystem.

#1317 Treasury Proposal: Merkle Mountain Belts (MMBs)

No Active Proposals