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
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.
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.
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.
The funding splits into a cost upon completion and a success reward; please see the linked sections of the proposal for their structure.
For more details, we strongly encourage reading the full proposal:
For additional insights, we also recommend studying our Proof of Concept implementation in Clojure and a Sub0 2022 MMB overview talk. We also gave a brief overview on AAG: Kusamarian AAG #147.
Thank you for reading. We look forward to your feedback!