Merkle Mountain Belt: Cost saving analysis + funding proposal V3

# Merkle Mountain Belt: Cost saving analysis + funding proposal V3[^prior-proposals] ![Groupe Logo noir@4x](https://hackmd.io/_uploads/Hkdh8Idw0.png =10%x) #### Cryp GmbH ##### Alfonso Cevallos, Robert Hambrock ## Table of Contents 0. [Intro](#Intro) 1. [Technical overview](#Technical-overview) a. [Main features of MMB](#Main-features-of-MMB) b. [Faster update times](#Faster-update-times) c. [Shorter membership proofs](#Shorter-membership-proofs) 2. [Fee savings](##Fee-savings) a. [Savings per transaction](#Savings-per-transaction) b. [Total savings](#Total-savings) 3. [The MMB data structure](#The-MMB-data-structure) a. [U-MMB](#Unbagged-MMB-U-MMB) b. [F-MMB](#MMB-with-forward-bagging-F-MMB) c. [MMB](#MMB-with-double-bagging-MMB) 4. [Timeframes](#Timeframes) a. [Research Timeframe](#Research-Timeframe) b. [Implementation Timeframe](#Implementation-Timeframe) 5. [Cost of Proposal](#Cost-of-Proposal) 6. [The future of our project](#The-successful-future-of-our-project) 7. [Team](#Team)  ## Intro Imagine this: by 2026, decentralized applications have gained a significant foothold in the world finances. With them, blockchain platforms such as Polkadot and Ethereum move millions of dollars worth of value every day, and a successful DOT🡘ETH bridge is one of the top five cross-chain bridges in use. To realize this future for Polkadot, the time is NOW to build the most efficient and secure bridge out there. Yet this might not happen if the related bridging costs remain as high as they are now[^discussions-on-current-cost]. We propose developing a brand new data structure called Merkle Mountain Belt (MMB), namely both its theoretical and implementation sides, that would replace the use of the Merkle Mountain Range (MMR) in the BEEFY protocol, which is in turn used by bridges like Snowbridge and Hyperbridge. This change will considerably reduce the size of the authentication proofs of cross-chain messages in DOT→ETH bridging,[^hyperbridge-operational-cost] thus reducing the transaction fees for users, with total estimated savings of 1-1.4 million dollars [per year](#Traffic-Estimate), at current prices. We also propose writing a research paper in collaboration with Alistair Stewart, Head of Research at Web3 Foundation, about the new data structure, to eventually be published in a top rated computer science conference. Polkadot has always been a thought leader in blockchain technology, being one of the few communities that pioneers top quality research, and not just bells and whistles. This proposal honors this Polkadot tradition. The MMR data structure is currently widely used across multiple blockchains, and improving it with MMB would heighten Polkadot's impact on and reputation within the wider ecosystem. The members of our [team](#Team) are highly qualified and have worked in Polkadot since pre-mainnet days. Our principal researcher Alfonso has a Ph.D. in mathematics and is a co-author of many Polkadot papers, including the [2020 overview paper](https://arxiv.org/abs/2005.13456). Our principal developer Robert has been one of the earliest stewards of the Polkadot-Ethereum bridge, going back to its initial W3F grant, design of protocols, and implementation. ## Technical overview :::info **TLDR of MMB & cost analysis:** The MMB data structure serves as a plug-in replacement for MMR, to produce BEEFY commitments, which among other use cases, are employed by the DOT🡘ETH bridges to authenticate messages. Over the next 5 years, MMB would [reduce the average authentication proof size of messages by over 40%](https://docs.google.com/spreadsheets/d/1PRea58H84NpxHeJirpl8KUikfqFLYvVr8l70OFrTxX4) compared to the current MMR implementation. From our gas and cost estimates, this corresponds to $1.10 of savings per transaction for bridge users.  ::: *See also the following presentation giving an MMB overview:* [Sub0 2022: BEEFY: How Make Proofs Smol?](https://www.youtube.com/watch?v=uCwXbD9v3ew) Balanced Merkle trees, hash chains, and Merkle Mountain Ranges (MMRs) are three examples of Merkle structures widely used in blockchain as *commitment schemes*: they allow full nodes to produce a compact *commitment* to some database $X$, and then produce a small *membership proof* (a.k.a. a Merkle proof) to show to a *verifier* that an item $x\in X$ is part of the committed database. These structures are used everywhere in blockchain and allow for an external entity to query and authenticate specific data efficiently, without having to follow consensus, download the full state, nor trust any one full node. The aforementioned structures have different properties, and one or other will be chosen depending on the specific use case. The right choice of Merkle structure can drastically reduce the corresponding data authentication costs. The Merkle Mountain Belt (MMB) is a new member of this family of Merkle structures, optimized specifically for the use case of BEEFY, the protocol designed for efficient DOT🡘ETH bridging: Via BEEFY, a smart contract on Ethereum periodically receives a digest of the current state of Polkadot, with a refresh rate in the order of minutes to a couple hours, so that bridge users can authenticate Polkadot events on Ethereum with the help of this digest. To oversimplify, we can say that if bridge users mostly care about Polkadot events from the very last block, then the most efficient commitment scheme would be a hash chain (a maximally unbalanced binary hash tree), while if they care about very old data, the most efficient scheme would be a balanced tree such as an MMR. The MMB is a "best of both worlds" structure whose performance is always comparable to the better of the two former schemes, for any possible distribution of queries. But crucially, it outperforms them both in the case that the stream of users' queries is concentrated on events that took place in the time range from the last minute to the last day.[^comparison] Let's get into details. ### Main features of MMB Consider an item list $X=(x_1, x_2, \cdots, x_n)$ onto which new items are constantly being appended. This could be one of many databases, such as XCMP messages, but in our primary use case items correspond to Polkadot relay chain blocks.[^mmr-leaf-content] MMB is a data structure built on top of $X$ that produces a compact commitment to it. Its features are: * faster (constant time) updates after each append, and * shorter membership proofs for recently appended items. | | Chain | MMR | MMB | | -------- | -------- | -------- | --- | | Update time per append | $O(1)$ | $O(\log n)$ | $O(1)$ | | Proof size of the $k$-th newest item | $O(k)$ | $O(\log n)$ | $O(\log k)$ | In this table, we assume $1\leq k\leq n$, where $n=|X|$ is the current number of items in list $X$, and $k$ is the recency of the item for which a user needs a membership proof. In our use case $k$ is typically low, say between $10$ and $500$, because users mostly care about recent events. On the other hand, keep in mind that Polkadot currently has north of $20$ million blocks produced, so we are dealing with a use case where $n$ quickly reaches the order of tens of millions.  For the sake of comparison, in the following analysis, we average $n$ over the first 5 years after anticipated MMB deployment within BEEFY on Polkadot, that is $10512000\leq n \leq 36792000$[^n-sampling-range]. ### Faster update times The main advantage of a hash chain (which is a maximally unbalanced tree) is that it takes a single hash computation to append a new item. On the other hand, MMR, and any other structure that attempts to maintain a balanced tree, will pay an update cost of $O(\log n)$ per append, as the new leaf is immediately buried deep in the tree. In our use case, MMR requires on average about $\frac{1}{2}\log_2 n \approx 12$ hash computations (and growing) per append. Surprisingly, MMB achieves a **constant** cost per append: between 3 and 5 hash computations regardless of the list size $n$. To do so, it maintains a slightly unbalanced structure, where recent leaves are more shallow, though not completely unbalanced as with a hash chain. In our use case, having a faster append time is important for block authors, who have to perfom the update on-chain and on the fly as they generate blocks. ### Shorter membership proofs However, the killer feature of MMB for our use case is its slightly unbalanced structure, which makes recently appended items have shorter membership proofs. This leads to lower operational costs because bridge users are more likely to care about recent events[^relayer-frequency]. In particular a message, such as a transfer request, will first be created on Polkadot, and then sent to Ethereum, and authenticated there with the help of the BEEFY commitment stored on the bridge. Users typically want to execute this second step as soon as possible, i.e., the next time the BEEFY commitment is updated on the bridge. Hence, in order to ensure user friendliness, we need two things: 1. Short intervals between commitment updates in the bridge. Popular cross-chain bridges update their commitment every 15 minutes to 30 minutes. This could be reduced to five minutes, or increased to a couple of hours, depending on the chosen trade-off between operational cost and user friendliness. 2. A structure, like MMB, that minimizes the membership proof size of items added recently, in the range from the last five minutes to the last couple of hours. <a id="proof-size-comparison"></a> | Recency | Chain | MMR | MMB | | -------- | -------- | -------- | --- | | 6 seconds ($k\leq1$) | $1$ | $11.10$ | $2.13$ | | 1 minute ($k\leq10$) | $5$ | $14.52$ | $4.96$ | | 5 minutes ($k\leq50$) | $25$ | $15.82$ | $7.84$ | | 15 minutes ($k\leq150$) | $75$ | $16.65$ | $9.95$ | | 30 minutes ($k\leq300$) | $150$ | $17.15$ | $11.31$ | | 1 hour ($k\leq600$) | $300$ | $17.65$ | $12.67$ | | 4 hours ($k\leq2400$) | $1200$ | $18.66$ | $15.41$ | | 24 hours ($k\leq14400$) | $7200$ | $19.95$ | $18.97$ | *Average proof size (in hashes) of an item appended at different recency values (time from the present), assuming that a new item is appended every 6 seconds (like Polkadot relay chain blocks in BEEFY). The results are averaged across ($10512000\leq n \leq 36792000$), i.e., the size of the list between 2-7 years of appending.*  We see that MMB produces shorter proofs in expectation than both MMR and a hash chain, for any commitment refresh rate between once per minute and once per day. <a id="MMBs-in-BEEFY"></a> ## Fee savings In an Ethereum bridge, a smart contract on Ethereum stores a commitment to Polkadot's state. Currently, this commitment is built with an MMR, where a new leaf is added for each Polkadot relay chain block, and in turn each leaf contains commitments to parachain headers. For Snowbridge, when a message goes over the bridge, either a user or a relayer has to authenticate it in the smart contract, by attaching an MMR proof and a header proof to the message: 1. The MMR proof shows that the MMR (whose root is held in smart contract) commits to a leaf, which in turns commits to a particular parachain header. 2. The header proof shows that this parachain header indeed contains the claimed content, such as a message. As the number of Polkadot blocks grows, so does the average size of the MMR membership proofs that have to be relayed to Ethereum. In contrast, in MMB the size of a membership proof is *independent* of the size of the structure -- its asymptotic behavior is instead governed by the recency of the corresponding leaf. As bridge users primarily care about recent events, MMB will offer much smaller membership proofs than MMRs on average. <a id="Cost-Estimate"></a> ### Savings per transaction We calculate the expected transaction cost saving from switching from MMR to MMB in the first 5 years after we conservatively expect the MMB upgrade to go live, namely Q2 2026. Since this is approximately 2 years after BEEFY got activated on Polkadot (February 2024), we'll average the MMR size over ($10512000\leq n \leq 36792000$), as done before in the [table above](#proof-size-comparison). To compare both schemes, we consider the membership proof of leaves up until the 150th most recent leaf. This value $k\leq150$ corresponds to querying a message that was created on Polkadot up to 15 minutes ago (+ 24 minutes; see note on RanDAO[^randao]). For $k\leq150$, the average MMR proof size, measured in hashes, is 16.65, against 9.95 for MMB proofs, hence MMB saves 6.7 hashes: a proof size reduction of over 40%. Via gas profiling from Snowfork's implementation, every additional hash in the membership proof of an MMR leaf adds approximately 2'568 gas of computation cost on Ethereum: [`Lederstrumpf/snowbridge/rhmb/profile-proof-item-gas-cost`](https://github.com/Snowfork/snowbridge/compare/main...Lederstrumpf:snowbridge:rhmb/profile-proof-item-gas-cost?expand=1#diff-ad43af2a8fe32a0a552c025fc1d86308adf4ee1e4d45f83070cce458c461c818R85-R87) Assuming a gas price of 23.87 GWEI (365 day SMA via [Glassnode](https://studio.glassnode.com/metrics?a=ETH&category=&chartStyle=column&ema=0&from_exchange=aggregated&m=fees.GasPriceMean&mAvg=365&mMedian=0&resolution=24h&s=1687097402&to_exchange=aggregated&u=1718633402&utm_campaign=woc_02_2023&utm_medium=insights_woc&utm_source=gn_insights&zoom=365)), and an ETH price of $2'696.79/ETH (365 day SMA via [Glassnode](https://studio.glassnode.com/metrics?a=ETH&category=Market&chartStyle=column&ema=0&from_exchange=aggregated&m=market.PriceUsdClose&mAvg=365&mMedian=0&resolution=24h&s=1687097402&to_exchange=aggregated&u=1718633402&utm_campaign=woc_02_2023&utm_medium=insights_woc&utm_source=gn_insights&zoom=365)), the cost per hash is 16.57 cents. Consequently, since an average proof size of a leaf in an MMR of depth up to $k\leq150$ is 16.65, the expected proof verification cost for such a leaf is $2.75. In contradistinction, with MMBs the expected proof size is 9.95, hence the cost goes down to $1.65. Using an MMB rather than an MMR for the BEEFY commitment thus would effect a saving of 6.7 hashes, or $1.10 per message sent to Ethereum.  For more calculation details and a 1000-day[^glassnode-maximum-range] SMA comparison, see the [Cost Analysis Spreadsheet](https://docs.google.com/spreadsheets/d/1PRea58H84NpxHeJirpl8KUikfqFLYvVr8l70OFrTxX4). ***Note:** These costs are saved by bridge users and -- in case of a subsidy -- the Polkadot treasury[^treasury]. In either case, these fees would otherwise just be burned on Ethereum, with no benefit toward the Polkadot ecosystem. This reduction in running costs will make the Polkadot🡘Ethereum bridge more competitive with other bridges, and ensure its short-term adoption and long-term upkeep.* <a id="Traffic-Estimate"></a> ### Total savings To estimate the transaction numbers we can expect for a successful DOT🡘ETH bridge once it is mature, we take as a proxy the mean monthly transaction volumes of the 5 most utilized bridges.  Our estimate is thus based on the assumption that at least one DOT🡘ETH bridge bridge is a success. This is the same reason we chose 15 minutes (+ 24 minutes ranDAO [^randao] for Snowbridge) as a reference latency, given that such latency is offered by competitors like Stargate and Optimism, and even lower for trusted bridging setups. A comparison, using data from 31 August 2024, is available here: [Cost Analysis Spreadsheet](https://docs.google.com/spreadsheets/d/1PRea58H84NpxHeJirpl8KUikfqFLYvVr8l70OFrTxX4). From it, we expect an average of 2'646 transactions per day, or 965'790 transactions per year. **Result:** *The estimated cost saving from switching from MMR to MMB is in the range of $1'069'000/year - $1'397'000/year.* **Note:** *On top of these expected savings for a bridge to Ethereum, MMB will also provide gas cost savings to bridges from Polkadot/JAM to Layer-2s such as Arbitrum and Base. A recent back-of-the-envelope analysis of these L2 gas cost savings is available [here](https://hackmd.io/@CrypGmbH/Cost-Saving-L2-Back-of-the-Envelope). Note that since this calculation is still preliminary and will require much deeper investigation to become robust, we opted not to incorporate these additional savings into our estimate above.* ## The MMB data structure This section assumes familiarity with data structures in general, and the Merkle Mountain Range (MMR) structure in particular. It explain the main differences in the construction of an MMB versus an MMR. ### Unbagged MMB (U-MMB) Consider a list $X=(x_1, x_2, \cdots, x_n)$ we want to commit to. As in MMR, we build $O(\log n)$ *mountains*, where each mountain has an associated size $s$ and is a complete binary tree holding $2^s$ leaves. Each leaf is labeled with the hash evaluation of an item in $X$, and each non-leaf is labeled with the hash evaluation of the concatenation of its children. ![MMB9](https://hackmd.io/_uploads/rkDvrCIDA.png) For instance, this is the MMB structure for $n=9$ (without bagging), with three mountains of sizes $2,2,0$, whose peaks are in gray. We say two mountains of equal size $s$ are *mergeable*, as they can be merged into a mountain of size $s+1$ by creating a new peak node as the parent of the two old peaks. We follow this rule: whenever we append a new item to list $X$, we add it as a mountain of size $0$ (i.e., a singleton), and if there are mergeable pairs of mountains at that point, we merge *exactly one* such pair: the rightmost one. ![image](https://hackmd.io/_uploads/rkyZbvQvA.png) For instance, here we see two append updates, with the new leaf in green and the new merge peak in gray. When appending $x_{10}$ we merge two mountains of size $0$ into one of size $1$, and when appending $x_{11}$ we merge two mountains of size $2$ into one of size $3$. In contrast, MMR follows the rule that any mergeable pair is merged immediately, which can lead to a domino effect of up to $O(\log n)$ merges after a single append. With our lazy merging rule, we make sure each append has constant complexity. But more importantly, we make mountains grow at a slow and steady rate, so that the $i$-th rightmost mountain is always of size $\Theta(i)$. In turn, this gives us the asymptotic behavior we want: the $k$-th most recent leaf is at distance $O(\log k)$ to its peak, regardless of the list size $n$. ### MMB with forward bagging (F-MMB) Next, we want to group or *bag* the mountains into a single structure -- a *mountain range* -- to create a single root that commits to the full list $X$. We add an upper layer of *bagging nodes*, where each node is the parent of one peak and the previous bagging node. ![image](https://hackmd.io/_uploads/BkbFWaEwC.png) In the figure we see two possible ways of bagging the same set of mountains: in a backward fashion on the left, and in a forward fashion on the right. In each case, the root is in brown, peaks in gray, and the symbol $\bullet$ represents a non-existent child node. Backward bagging is usually used in MMR: it leads to a more balanced structure because larger mountains (on the left) end up closer to the root, so items with a large leaf-to-peak distance are compensated with a short peak-to-root distance. However, we will embrace the imbalance of forward bagging, for two reasons. First, it preserves the property we want: that the $k$-th most recent leaf maintains an $O(\log k)$ depth, regardless of the list size $n$. This is because both the leaf-to-peak and peak-to-root distances will be $O(\log k)$. And second, with forward bagging most bagging nodes don't need to be updated after an append, as changes only happen near the rightmost end of the structure. This optimizes the append operation. ![image](https://hackmd.io/_uploads/SJO7LpEPC.png) E.g., here we see a series of append updates, if we use a forward bagging. For simplicity, we hide all non-peak mountain nodes, representing each mountain only by its peak labeled with its mountain size, and we place bagging nodes on a single horizontal level. The new leaf is in green, the merge peak in gray, and the updated bagging nodes in brown. It can be proved that, with forward bagging, only two bagging nodes need to be updated on average per append. However, in the worst case we still need to update $O(\log n)$ bagging nodes (i.e., most of them), namely when the mountains being merged are large, and far from the rightmost end of the structure. We need one final ingredient. ### MMB with double bagging (MMB) In the final version of MMB, we introduce a more complicated form of forward bagging that we call double bagging. Instead of grouping all mountains into a single range, we partition mountains into subsets, use forward bagging to group each subset into a range, and finally use an extra layer of forward bagging to group all mountain ranges into a *mountain belt*. ![image](https://hackmd.io/_uploads/Bkz6tDBv0.png) E.g., here is the final MMB structure for $n=1337$. There are $10$ mountains (represented only by their peaks) partitioned into $5$ mountain ranges, each range is forward bagged with rhombi nodes, and finally the $5$ ranges are forward bagged with circle nodes into one mountain belt, whose root is in brown. The point of splitting the mountains into several ranges is to ensure that each mergeable pair of mountains sits at the right end of a range. Hence, after a merge, we only need to update one bagging node in the affected range. And importantly, we also only need to update one or two bagging nodes in the outer bagging. This is because we always merge the rightmost mergeable pair, which has to be in either the rightmost or second rightmost range. In turn, this is by our range splitting rules: if there are no mergeable pairs to the right of the affected range, then there cannot be any range splits either. ![MMBs](https://hackmd.io/_uploads/BJLNCPHw0.png) Here we see a series of append updates in MMB. Again, the new leaf is in green, the merge peak in gray, and we color in brown all bagging nodes that need to be updated. Notice that at most $4$ bagging nodes are updated, even when we merge large mountains! Thus, we achieve a constant complexity for the append operation even in the worst case. The full structure will be presented in detail in the research paper, where we will show that we get all the properties we want: an append operation with a constant complexity, and a depth of $O(\log k)$ for the $k$-th most recent leaf, regardless of the list size $n$.  <a id="Timeframes"></a> ## Timeframes This funding request forks into a Research Track and an Implementation Track. The key deliverables are 1. a research paper, 2. a brief analysis of use cases for MMB in addition to BEEFY bridging, and 3. a Rust implementation of Merkle Mountain Belts integrated into a frame pallet, together with any necessary changes to Snowfork's BEEFY client necessary to accommodate: https://github.com/Snowfork/snowbridge/blob/main/contracts/src/BeefyClient.sol  ### Research Track --- #### M1. Preprint Paper: **12 weeks (108'000 CHF)** The primary milestone of the research track is completing a preprint paper on MMB currently in the works, and submitting it to a public repository such as arXiv. The timeframe for completion of this preprint is so short since a lot of the work has already been completed by the team members in collaboration with Alistair Stewart, for which we already received funding from Web3 Foundation, and we are not asking for any of this prior work to be funded again. Alistair Stewart will be a paper coauthor. As MMB is a novel data structure that does not appear in any textbook, this preprint will work as the go-to reference for developers. As such, its format will be clear and accessible, similar to the lecture notes of an undergraduate course on data structures. At the same time, its level of innovation and mathematical formalism will be worthy of publication in a top-level conference in computer science. Notice that the members of our team have several such top rated publications under their belts, and we are indeed planning to publish the paper in a follow-up proposal. The time budget estimate for this milestone is computed as follows: - Comparison to MMR: 3 weeks. A detailed analysis of both MMR and MMB, including several variants of both structures, such as altering the peak bagging method. The analysis includes the exact expected sizes of membership proofs, to find the terms hidden by the big-O notation. - Applications: 2 weeks. A summary of the most relevant applications of MMR currently in blockchain, and the precise benefits they would observe by switching to MMB. Examples are: cross-chain bridging (e.g., Polkadot), light-client protocols (e.g., [FlyClient](https://eprint.iacr.org/2019/226.pdf)), stateless architecture (e.g., [Minichain](https://www.sciencedirect.com/science/article/abs/pii/S0743731520302732)), and asynchronous accumulators (e.g., [this paper by Reyzin and Yakoubov](https://eprint.iacr.org/2015/718.pdf)). - Increment proofs: 2 weeks. These proofs allow an external entity to detect if an authority provides an incorrect MMB root, and trigger a slash if applicable, such as in the BEEFY protocol for the Ethereum bridge. Increment proofs are also needed, e.g., in the FlyClient protocol (where they are called subtree proofs). - Asynchrony: 2 weeks. An analysis of the asynchrony properties of MMB, as was done for MMR in Reyzin and Yakoubov's paper. This means, how to make an outdated proof remain valid against an updated root, and vice-versa. We prove MMB has strictly stronger properties than MMR, including the new "recent proof compatibility" property, which is very useful in distributed and stateless architectures. - Pseudocode and missing proofs: 2 weeks. - Finishing paper: 1 week. Bibliographical research of related work, introduction, conclusions, etc. #### M2. PoC implementation: **3 weeks (27'000 CHF)** It is common for research papers about new algorithms and data structures to include a proof-of-concept implementation, to show there are no hidden obstacles to its deployment. We will finish a Clojure implementation of MMB, make it publicly available as open source, and refer to it in the paper preprint. We highlight that this implementation is already at an advanced stage, hence the short time budget. It will be an invaluable tool for us as we build the (much more complex) Rust implementation of the library. Similarly, it will be a great pedagogical tool for developers who want to get familiar with MMB. The time budget estimate for this milestone is computed as follows: 1. Refactor implementation to facilitate specification process: 1 week. 2. Profiling and performance improvements: 2 weeks. *The Clojure implementation currently exhibits worse asymptotic behavior than we know is theoretically possible. Profiling and performance improvements here are restricted to only cover improvements that will also reflect in the specification and Rust implementation of the library.* Each milestone in the Research Track will be considered delivered when - It has been made publicly available, and - Its content has been greenlit by at least two members of the research team at Web3 Foundation. --- ### Implementation Track The current implementation of MMB is available here: <https://github.com/w3f/merkle-mountain-belt-clj> We propose developing a Rust library readily integrateable by relevant Rust pallets such as `pallet-beefy` to be used instead of [`nervosnetwork:merkle-mountain-range`](https://github.com/nervosnetwork/merkle-mountain-range). The library will be licensed under [Apache 2.0](https://www.apache.org/licenses/LICENSE-2.0.txt). **Note:** *Unlike in our [prior proposal](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2), this implementation omits forward-bagged MMBs and increment proofs, since they are not essential for Polkadot deployment: For Polkadot deployment, only one structural variant of MMB is required, and we reckon that double-bagged MMB is the best contender for this. Likewise, increment proofs are currently required for bridges only, and are not a key ingredient to JAM.* Our time estimate for the implementation of a production-ready MMB library on top of the existing MMR library from Nervos is 28 FTE weeks (i.e. about 6 months) of engineering: #### M3. Spec MMB implementation for porting to Rust: **2 weeks (18'000 CHF)** *In particular, this will cover interfaces required for integrations with other pallets (e.g. `pallet-beefy`) as currently provided by `pallet-mmr`* #### M4. Rust implementation: unbagged MMBs: **15 weeks (135'000 CHF)** 1. persistent storage backend: core: 4 weeks 2. append procedure: 2 weeks 3. persistent storage backend: pruning: 2 weeks 4. membership proofs (for U-MMBs only): 1 week 5. unit testing: 2 weeks 6. APIs & FFI: 1 week 7. documentation: 1 week 8. integration tests: 1 weeks 9. codebase cleanup & consistency checks in preparation for audit: 1 week #### M5. Rust implementation: bagged MMBs: **11 weeks (99'000 CHF)** 1. range nodes: 2 weeks 2. belt nodes: 2 weeks 3. membership proofs (double-bagged MMBs): 1 week 4. APIs & FFI: 1 week 5. documentation: 1 week 6. integration tests: 2 weeks 7. codebase cleanup & consistency checks in preparation for audit: 2 weeks Each one of the three milestones in the Implementation Track will be considered delivered when - It has been made publicly available, and - Its content has either been greenlit by at least two members of the Polkadot Technical Fellowship of rank II or higher, or been deployed within Polkadot or Kusama (implicit greenlighting). ## Cost of Proposal For the 15 weeks of research, we request 135'000 CHF, and for the 28 weeks of implementation, we request 252'000 CHF, totalling 387'000 CHF. However, we consider that the proposal merely being *completed* is much different than it being *economically net-positive*, and these outcomes should be rewarded distinctly. In fact, we see the potential for our project to be very successful. Hence, to put our money where our mouth is, we are willing to cut our payment to only 70% upon completion, with the rest paid only once it is economically net-positive for the Polkadot/JAM community. Explicitly, it will work as follows: Once M1 is delivered, the payment will be of $108'000\mbox{ CHF} \times 0.7 = 75'600\mbox{ CHF}$, and so on for each milestone. Hence, the total cost of the proposal upon completion of milestones 1 through 5 will be $387'000\mbox{ CHF} \times 0.7 = 270'900$ CHF. *The cost of each milestone will be due in USDC based on the [Swiss National Bank USD/CHF foreign exchange rate](https://www.snb.ch/en/the-snb/mandates-goals/statistics/statistics-pub/current_interest_exchange_rates) at the date of submission.* The remaining 30% of 387'000 CHF will only be paid if and when the Polkadot/JAM ecosystem's cost savings of MMB against MMR exceeds the sum of 387'000 CHF[^success-reward-calculation-method] -- corresponding to the full cost of completing milestones 1 through 5 -- and the to-be-determined audit cost. This threshold ensures that any success rewards paid cannot result in a net financial loss for the community. *This 30% portion, i.e., $387'000\mbox{ CHF} \times 0.3 = 116'100 \mbox{ CHF}$, will be due in DOT based on the [Swiss National Bank USD/CHF foreign exchange rate](https://www.snb.ch/en/the-snb/mandates-goals/statistics/statistics-pub/current_interest_exchange_rates), and the 7-day EMA of USD/DOT via [Subscan](https://polkadot.subscan.io/tools/price_converter) at the date of submission.* ## The (successful) future of our project We believe that the MMB project has the potential to be very successful, and bring lots of value to the community. Multiple criteria or conditions could be used to measure its success. For instance, in the previous section we proposed using the condition of being *economically net-positive* to trigger the full payment of this proposal's cost. Looking ahead, we plan to extend the MMB project with a follow-up proposal. This second proposal will target - *academic success*: publishing the paper in a top-rated computer-science conference, as well as - *engineering success*: publishing a robust and general-purpose MMB library, which will include several variants of the MMB structure, optimized for different applications beyond bridging, as well as increment proofs (required for slashing). Finally, we believe that the MMB project has the potential to become a *huge economic success*: reaching a point where the accrued cost savings it produces for the Polkadot/JAM community exceed the fixed cost of our proposal multiple times over. We consider it fair to reward such a level of success distinctly from the criteria mentioned above. Hence, if and when this point arrives, we intend to request retroactive funding from the Treasury that is in proportion to the economic upside it brought the Polkadot/JAM community. We expect that the practices around retroactive funding will still evolve substantially in the coming years, and we would align our requested rPGF funding with the practices the community has embraced by then. We note that we are in the unusual position of having a precise and sensible metric (MMB cost saving against MMR) to measure our proposal's impact. We also remark that such retroactive funding would give us a clear incentive to continue both maintaining and improving the efficiency of the MMB library, beyond the deliverables of a proposal. As experts in Polkadot bridges and authentication structures, we are confident we can bring further optimizations to MMB for years to come, leading to even more cost savings. This aligns our long-term incentives with those of the community. ## Team ### Alfonso Cevallos ![Tenerife2](https://hackmd.io/_uploads/HkkcEdMX1g.jpg =25%x) - Mathematics PhD from EPFL (2016). Postdoc at ETH Zurich, Switzerland (2017-2018). - Researcher at Web3 Foundation (2019-2024): focus on scalability, security and incentives of decentralized protocols. - Co-author of the [2020 Polkadot implementation paper](https://arxiv.org/abs/2005.13456). - [Co-designer](https://www.youtube.com/watch?v=OdbCgdQugKM) and [paper co-author](https://arxiv.org/abs/2004.12990) of Polkadot's Nominated Proof-of-Stake (NPoS). - [Paper co-author](https://arxiv.org/abs/2312.11408) on study about real-life security metrics in Polkadot validator elections. - [Paper co-author](https://eprint.iacr.org/2024/961) of ELVES block auditing, the basis of Polkadot's scalability. - Content creator and lecturer in several editions of the Polkadot Blockchain Academy. ### Robert Hambrock ![image](https://hackmd.io/_uploads/Bk49rOzQ1g.png) - Honours postgrad in Physics from UCT, South Africa (2016, with distinction). Worked primarily on [AdS/CFT correspondence](https://scholar.google.com/citations?user=rluJ3bAAAAAJ&hl=en&oi=ao). Visiting scientist at CERN 2017, 2018. - Ethereum CBC Casper: co-author of [Rust implemenation](https://gitlab.com/TrueLevel/casper/core-cbc) - switched over to primarily working on Polkadot ecosystem in Q1 2020 (also operate validator [🚂 Zugian Duck 🦆](https://insights.math-crypto.com/polkadot/15jrQX54HczCKJgtYYoKvzJ2kgyCyyA4kyvMv2bC8x9UtDpn/)) - at Web3 Foundation (2020-2022) as Quality Assurance Engineer and then Research Engineer, later at Parity (2022-2024) as Core Engineer on bridge team. - ETH bridge: various work over the years, e.g. on coordination of Snowfork's initial w3f grant, work on [subsampling protocol](https://hackmd.io/ohOt4jAPT8uu-soJXHUq0Q), [cross-chain slashing implementation](https://github.com/paritytech/polkadot-sdk/pull/1903), [session skipping](https://github.com/Snowfork/snowbridge/pull/1215), and [fallback governance proposal](https://hackmd.io/MlVt_yt9TQC8PvMZY8WCcQ) (part of Snowfork's [improvement roadmap](https://spinamp.mypinata.cloud/ipfs/QmZT1Q9QF45286CxM8qkDuGCr1VCkHQ1VCjFEe89khprH5)) - MMRs: fixed [security vulnerability](https://github.com/nervosnetwork/merkle-mountain-range/commit/8e333a23294008bb48c729581f229bb59cf4f95c) & implemented [ancestry proofs](https://github.com/paritytech/merkle-mountain-range/pull/1) - MMB PoC implementation in Clojure: [github.com:w3f/merkle-mountain-belt-clj](https://github.com/w3f/merkle-mountain-belt-clj) - MMB presentation: [Sub0 2022: BEEFY: How Make Proofs Smol?](https://www.youtube.com/watch?v=uCwXbD9v3ew)  ![favicon@4x](https://hackmd.io/_uploads/Bya9lnvmyl.png =15%x) ### Cryp GmbH - R&D consultancy founded 2019 in Biel, Switzerland - Specialises on cross-chain protocols - History of consulting for variety of both local (e.g. Web3 Foundation & SwissQuote) and international clients (e.g. Parity & Tari Labs) - Researched & implemented [BTC⇆XMR atomic swaps](https://github.com/farcaster-project) (successfully completed in Q1 2023 from Monero community's [CCS crowdfund grant](https://ccs.getmonero.org/proposals/h4sh3d-atomic-swap-implementation.html)). This has spawned a broad ecosystem for atomic swaps with Monero, such as [ETH⇆XMR](https://github.com/AthanorLabs/atomic-swap), [NMC⇆XMR](https://www.namebrow.se/name/d/atomic-trophy/), and various other pairs via [BasicSwap](https://github.com/tecnovert/basicswap/tree/master). [^hyperbridge-operational-cost]: For Hyperbridge, MMBs will also reduce the operational cost of the bridge, since consensus update proofs already prove membership of the last leaf in the MMR root commitment: https://github.com/polytope-labs/hyperbridge/blob/8e129796b4b7b0b8e7612625cc4d2592b0818b3b/evm/src/consensus/BeefyV1.sol#L167, https://github.com/polytope-labs/hyperbridge/blob/8e129796b4b7b0b8e7612625cc4d2592b0818b3b/evm/src/consensus/ZkBeefy.sol#L151 [^comparison]: For recent items, MMBs produce a membership proof that is on average at most one hash bigger than the corresponding proof with a hash chain. [^n-sampling-range]: 10 blocks per minute: `10*60*24*365*2=10512000`, `10*60*24*365*7=36792000`  [^relayer-frequency]: Relayers frequently prove inclusion of a message in a parachain header. In fact on Snowbridge, all messages on a particular channel have to be processed [sequentially](https://github.com/Snowfork/snowbridge/blob/c8ea65c5b54c8befc40910a367fb0edf3f528b33/contracts/src/Gateway.sol#L141-L149). Hence if relayers are working reliably, then only recent messages are unprocessed at any given time. [^mmr-leaf-content]: The MMR leaf in BEEFY contains various metadata such as the parent of the relay chain block, descriptors of the `nextAuthoritySet`, and the leaf version. The core data it commits to though is the root of all parachain headers: https://github.com/Snowfork/snowbridge/blob/c8ea65c5b54c8befc40910a367fb0edf3f528b33/contracts/src/BeefyClient.sol#L107-L123. How this `parachainHeadsRoot` is used for verifying cross-chain messages varies between bridge designs: When Snowbridge's Ethereum client receives an inbound cross-chain message, it checks that the message [is committed to in a parachain header](https://github.com/Snowfork/snowbridge/blob/c8ea65c5b54c8befc40910a367fb0edf3f528b33/contracts/src/Verification.sol#L108-L111), and that said parachain header is in turn [committed to in the BEEFY MMR root stored on-chain](https://github.com/Snowfork/snowbridge/blob/c8ea65c5b54c8befc40910a367fb0edf3f528b33/contracts/src/Verification.sol#L125-L128). When Hyperbridge's Ethereum client receives inbound cross-chain messages (`handlePostRequests`), they are checked for inclusion against a separate MMR root that commits to all ISMP requests and responses: https://github.com/polytope-labs/hyperbridge/blob/8e129796b4b7b0b8e7612625cc4d2592b0818b3b/evm/src/modules/HandlerV1.sol#L151-L157. [^treasury]: We support the idea of a subsidy from Treasury, especially at the beginning of a bridge operation, to help the bridge gain users. Yet in the long term, what will make the bridge achieve dominance in the market is having an intrinsically superior technology that minimizes both user & operational costs - this is what our MMB upgrade offers. [^randao]: After a new MMR/MMB root is relayed via [`submitInitial`](https://github.com/Snowfork/snowbridge/blob/main/contracts/src/BeefyClient.sol#L250-L301) on Snowbridge, there is a mandatory delay of at least 3 epochs, i.e. 19 minutes, before the BEEFY light client's storage is updated with the new root via [`submitFinal`](https://github.com/Snowfork/snowbridge/blob/main/contracts/src/BeefyClient.sol#L343-L391) due to [RanDAO biasability](https://eth2book.info/altair/part3/config/preset/#max_seed_lookahead). Hence, the overall latency of a message sent 15 minutes prior to the root update being initiated is over 30 minutes. [^glassnode-maximum-range]: This is the maximum averaging range on Glassnode. [^audit-cost]: Based on our current MMB implementation in Clojure, we have received a quote from Oak Security of 74'800 USD for auditing the Rust library (note this is for the full audit, so only a portion of this would be due for the first proposal's delivery). We reckon Oak Security is in an ideal position to audit the MMB implementation since they have already audited [various iterations of Snowbridge](https://github.com/oak-security/audit-reports/tree/main/Snowbridge) and are therefore very familiar with the usage context. [^success-reward-calculation-method]: At a high-level, for the case of Snowbridge, we can calculate the cost saving as follows: `gasSaving = gasCostPerProofItem * (proofItemsMMR(leafPosition, accumulatorSize) - proofItemsMMB)`, where `proofItemsMMR(leafPosition, accumulatorSize)` can be calculated as in [here](https://github.com/nervosnetwork/merkle-mountain-range/compare/master...Lederstrumpf:merkle-mountain-range:mmr_profile_proof_size), the `accumulatorSize` can be retrieved from [`BeefyClient.latestBeefyBlock`](https://github.com/Snowfork/snowbridge/blob/77b4c04e3663e0fabfb66b0a5c261e271fe9d2ec/contracts/src/BeefyClient.sol#L156-L157), the leafPosition can be determined from [`MMRLeaf.parentNumber`](https://github.com/Snowfork/snowbridge/blob/77b4c04e3663e0fabfb66b0a5c261e271fe9d2ec/contracts/src/BeefyClient.sol#L111-L112), and `proofItemsMMB` will just be the length of the MMB [`leafProof`](https://github.com/Snowfork/snowbridge/blob/77b4c04e3663e0fabfb66b0a5c261e271fe9d2ec/contracts/src/BeefyClient.sol#L348) once MMBs are deployed. [^discussions-on-current-cost]: The current cost of DOT→ETH bridging -- even with the recent decrease to ~6 DOT per transfer -- has been raised in the community as a growth painpoint for growth of Snowbridge usage. See for instance related discussions here: [1](https://polkadot.subsquare.io/referenda/1127), [2](https://x.com/Erwin_Schroedy/status/1831266621614145603), [3](https://x.com/ClaraVanStaden/status/1831426063551066292) [^prior-proposals]: Links: [V1 of proposal](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal) and [version tracking for changes](https://github.com/Cryp-GmbH/mmb-proposal/compare/original-proposal...final-state-original-referendum) since [original post](https://polkadot.polkassembly.io/post/2392) until [original referendum](https://polkadot.polkassembly.io/referenda/1317). [V2 of proposal](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V2) and [version tracking for changes](https://github.com/Cryp-GmbH/mmb-proposal/compare/final-state-original-referendum...main) since [original referendum](https://polkadot.polkassembly.io/referenda/1317). [^maintenance-scope]: Maintenance of the MMB library at least includes: 1. addressing bug reports, 2. addressing security issues of the library - in particular any coordinated vulnerability disclosures, and 3. ensuring the MMB library API remains compatible with Polkadot/JAM.