# MMB paper delivery

In [our proposal](https://hackmd.io/@MerkleMountainBelts/MMB-Funding-Proposal-V3#Research-Track) we offered to complete and include the following components in our [MMB paper draft](https://arxiv.org/abs/2511.13582):

- **Comparison to MMR:** 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.
**Delivery:** Please see Table 3, Table 5, and Figure 13 in Appendix C. We provide a detailed analysis and comparison of three variants of MMR and three variants of MMB: one unbagged variant and two bagged ones for each scheme. The conclusion is that our proposed schemes are superior (in terms of both worst-case and amortized performances) not only to MMB, but to possible variants of it that could be obtained by changing its bagging method. This proves that our proposed structures are intrinsically superior and different from MMR, and not just a derivation of it.

- **Applications:** 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), stateless architecture (e.g., Minichain), and asynchronous accumulators (e.g., the paper by Reyzin and Yakoubov).
**Delivery:** Please see Table 2 and Appendix A. We provide 5 strong use cases for MMB, in applications that currently use MMR. The main benefits of MMB in these applications for light clients are: faster resyncs after offline periods, handling shorter Merkle proofs in expectation, and cheaper scheme updates after an item append (in uses cases where a light client bears the cost of such update). All of these benefits result in smaller running costs and fees. As we mention in the Conclusions section, we are happy to report that we couldn't find *any* blockchain application where MMB would clearly be a worse choice than either MMR or a Merkle chain; hence, we can make the strong argument that MMB should be a *canonical* choice of Merkle structure in blockchain applications.

- **Increment proofs:** 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).
**Delivery:** Please see Section 6. In this section we formalize the concept of increment proofs for any Merkle structure -- which hadn't been done before, despite the fact that many light client protocols that currently use MMR are exploiting these proofs. Then, we prove that these proofs are smaller for MMB than for MMR: $O(\log k)$ vs $O(\log n)$.

- **Asynchrony:** 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 in particular the new "recent proof compatibility" property, which is very useful in distributed and stateless architectures.
**Delivery:** Please see the definition of recent proof compatibility, and Figure 3, in the Introduction, as well as Section 3.3. Also see the end of Appendix A, where we argue that this new asynchrony property is an improvement over a recent line of research about commitment schemes that exhibit low update frequency.

- **Pseudocode and missing proofs:**
**Delivery:** Please see Appendix B, as well as our GitHub repository with a proof-of-concept implementation, the link to which is given in that appendix.

- **Finishing paper:** Bibliographical research of related work, introduction, conclusions, etc.
**Delivery:** The Introduction includes all the relevant work related to Merkle structures used in blockchain, and Appendix A includes lots of relevant work related to light client protocols and potential use cases of MMR and MMB.

**Observations**:
- Please notice that Appendix B on algorithms focuses on proving that the U-MMB append operation can be performed in constant time. Other algorithms were not included since either they are similar to those in MMR, or their key properties are sufficiently justified in theory (in one of the paper's lemmas). However, as we develop the Rust implementation for our following project deliverables, we will, of course, add the corresponding pseudocodes to the paper, if we deem them to be of interest to the paper readers.