# Merkle Mountain Range in o1js

**URL:** <https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642>\
**Category:** Mina Navigator Proposals\
**Created:** [October 29, 2024, 2:14pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642 "2024-10-29T14:14:58Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![hgedia](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/hgedia/32/1734_2.png) [@hgedia](https://forums.minaprotocol.com/u/hgedia)\
**Post date:** [October 29, 2024, 2:14pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/1 "2024-10-29T14:14:58Z")

</div>

This topic is to discuss the proposal submitted by @codekaya . Please see below for the details of the proposal and discussion.

**5th November, 2024**  
_Current status: Funded_  
_Funding Note: This proposal is approved for funding. MMR is a useful primitive in bridges.The delivery risk is low and the funding is in line with the proposed work. We measure the impact of this artifact to be high due to its applicability._

**30th October, 2024**  
_Current status: Under Consideration._  
_Opened for community discussion on 30th October._

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [October 29, 2024, 2:29pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/2 "2024-10-29T14:29:39Z")

</div>

# Implementation of Merkle Mountain Range in o1.js for zkApp Development

## Project Background

The Mina Protocol, known for its succinct blockchain design, enables developers to build scalable and efficient zkApps. However, handling large datasets within zkApps presents challenges due to the constraints of zk-SNARK circuits, which require fixed-size data structures and loops.  
Merkle Mountain Ranges (MMRs) are append-only data structures composed of a series of perfect binary trees (peaks). They allow efficient updates and verifiable proofs of inclusion, making them suitable for blockchain applications where data integrity and history are essential.  
This project aims to implement an MMR library in o1.js, the JavaScript library for developing zkApps on the Mina Protocol. The library will enable developers to manage large off-chain datasets while maintaining on-chain data integrity through cryptographic commitments.

## Proposal Overview

### Problem

Developers building zkApps on the Mina Protocol face limitations when handling large or dynamic datasets due to zk-SNARK circuit constraints. Existing data structures in o1.js do not efficiently support append-only logs or verifiable data history, hindering the development of applications requiring these features.

### Solution

The proposed solution is to develop a robust MMR library in o1.js that complies with zk-SNARK constraints. This library will provide:

- Efficient Off-chain Data Handling: Allowing large datasets to be managed off-chain while maintaining a verifiable commitment on-chain.
- Append-Only Structure: Enabling efficient data appends without restructuring the entire data structure.
- Inclusion Proofs: Providing mechanisms for generating and verifying proofs of inclusion for data elements.
- Developer-Friendly API: Offering an easy-to-use interface for integration into zkApps.

### Impact

The implementation of an MMR library in o1.js will significantly boost the Mina ecosystem by:

- Empowering Developers: Enabling the creation of more complex and data-intensive zkApps.
- Encouraging Adoption: Attracting developers from other ecosystems familiar with MMRs and off-chain data handling.
- Enabling New Use Cases: Facilitating applications like verifiable logs, blockchain-based storage solutions, and historical data tracking.
- Improving Tools: Contributing to the suite of tools available for zkApp development on Mina.

### Audience

- zkApp Developers: Developers building applications on the Mina Protocol who require efficient off-chain data management.
- Blockchain Enthusiasts: Individuals interested in advanced data structures and cryptographic primitives.
- The Mina Community: The broader community will benefit from boosted applications and tools.

* * *

## Architecture & Design

### Detailed Design/Architecture

The MMR library will be designed with the following components:

#### MMR Structure

- **Data Structure** : Implemented as a Struct with the following fields:
  - `leavesCount`: Tracks the number of leaf nodes in the MMR.
  - `elementsCount`: Tracks the total number of elements (including internal nodes).
  - `hashes`: An array storing node hashes indexed by their position.
  - `rootHash`: Stores the current root hash of the MMR.

#### Core Functions

- **append(data: Field)**:
  - Adds a new element to the MMR.
  - Updates peaks and recalculates the root hash using optimized algorithms.
  - Utilizes efficient methods for mapping leaf indices to element indices.

- **getProof(leafIndex: UInt64): Proof**:
  - Generates a proof of inclusion for a specific leaf.
  - The Proof structure contains necessary data to verify inclusion.

- **verifyProof(leaf: Field, proof: Proof): Bool**:
  - Verifies the inclusion proof of a leaf in the MMR.
  - Returns true if the proof is valid, false otherwise.

- **getProofs(leafIndices: UInt64[]): Proof[]**:
  - Generates proofs for multiple leaves.
  - Optimizes shared components to reduce redundancy.

- **verifyProofs(leaves: Field[], proofs: Proof[]): Bool**:
  - Verifies multiple inclusion proofs efficiently.

- **getPeaks(): Field[]**:
  - Retrieves the current peaks of the MMR.

- **bagThePeaks(peaks: Field[]): Field**:
  - Combines peaks into a single hash representing the MMR state.

- **calculateRootHash()**:
  - Recalculates the root hash based on the current state.

- **retrievePeaksHashes(peaksIndices: UInt64[]): Field[]**:
  - Retrieves hashes for given peak indices.

- **clear()**:
  - Resets the MMR to an empty state.

#### Utility Functions

- **Algorithms** :
  - Implement efficient methods for critical operations to boost performance.

- **countOnes(n: UInt64): UInt64**:
  - Counts the number of ones in the binary representation of n.

- **findPeaks(elementCount: UInt64): UInt64[]**:
  - Calculates peak positions in the MMR given the element count.

- **bintreeJumpRightSibling(elementIndex: UInt64): UInt64**:
  - Finds the index of the right sibling in the binary tree.

- **bintreeMoveDownLeft(elementIndex: UInt64): UInt64**:
  - Moves down to the left child in the binary tree.

- **getHeight(elementIndex: UInt64): UInt64**:
  - Determines the height of a node in the MMR.

- **allOnes(num: UInt64): Bool**:
  - Checks if a number’s binary representation consists of all ones.

- **pow2(exponent: UInt64): UInt64**:
  - Computes exponents of 2 efficiently.

- **bitLength(num: UInt64): UInt64**:
  - Calculates the number of bits needed to represent num.

- **mapLeafIndexToElementIndex(leafIndex: UInt64): UInt64**:
  - Maps a leaf index to the corresponding element index in the MMR.

- **mapElementIndexToLeafIndex(elementIndex: UInt64): UInt64**:
  - Maps an element index to the corresponding leaf index.

#### Algorithm Optimizations

- **Height Calculation** :
  - Utilize optimized for computing the height of nodes in the MMR.

- **Element and Leaf Mapping** :
  - Implement efficient mappings between leaf indices and element indices.

- **Append Function Optimization** :
  - Boost the append function for better performance and reduced circuit complexity.

* * *

## Vision

The long-term vision for this project includes:

- **Full Integration into o1.js** :
  - Contributing the MMR library to the official o1.js repository.

- **Community Adoption** :
  - Becoming a standard tool for zkApp developers on Mina.

- **Continuous Improvement** :
  - Regular updates to boost performance and add features based on community feedback.

- **Educational Resources** :
  - Providing tutorial and documentation to educate developers about MMRs and their use in zkApps.

### Existing Work

- **Current Implementation** :
  - An initial version of the MMR append function and helper methods has been developed.  
[Mina\_MMR](https://github.com/codekaya/Mina_MMR) (Github Link of the current implementation)

- **Documentation** :
  - Preliminary README and usage examples are available in the repository.

* * *

## Production Timeline

**Total Duration: 2 Months**

- **Week 1**
  - Finalize the design and architecture of the MMR library.
  - Set up the development environment and repository structure.
  - Begin implementing the core append function with optimized algorithms.

- **Week 2**
  - Complete the implementation of utility functions:
    - `countOnes`
    - `findPeaks`
    - `getHeight`
    - `bitLength`
    - Mapping functions between leaf and element indices.

  - Implement and test optimized algorithms for critical operations.

- **Week 3**
  - Develop the `getProof` and `verifyProof` functions.
  - Begin working on multiple proofs functions:
    - `getProofs`
    - `verifyProofs`

  - Write unit tests for the implemented functions.

- **Week 4**
  - Complete multiple proofs functions.
  - Implement `getPeaks`, `bagThePeaks`, and `calculateRootHash`.
  - Begin integrating the MMR library into a sample zkApp for testing.

- **Mid-Point Milestone (End of Week 4)**
  - Core functionality implemented and tested.
  - Optimized algorithms in place.
  - Initial documentation drafted.

- **Week 5**
  - Implement the `clear` function and finalize all remaining methods.
  - Optimize performance and reduce circuit size where possible.
  - Begin working on comprehensive documentation and developer guides.

- **Week 6**
  - Continue refining documentation.
  - Create usage examples and integration guides.

- **Week 7**
  - Prepare Step-by-step guides
  - Conduct internal testing and debugging.

- **Week 8**
  - Incorporate feedback and make necessary adjustments.
  - Finalize the library for production release.

* * *

## Budget & Milestones

### Deliverables

- **MMR Library in o1.js** :
  - Fully functional MMR implementation with optimized algorithms.

- **Proof Generation and Verification** :
  - Methods for generating and verifying inclusion proofs.

- **Documentation** :
  - Comprehensive guides, documentation, and usage examples.

- **Test Suite** :
  - Extensive tests covering all functionalities.

- **Mid-Point Milestones (End of Week 4)**
  - Core MMR functionality completed and tested.
  - Optimized algorithms implemented.
  - Initial documentation drafted.

* * *

## Project Timeline

**Total Duration: 2 Months**

### Budget Requested

- **Total** : 25,000 MINA

### Budget Breakdown

#### Development (60%): 15,000 MINA

- **Core Implementation (12,000 MINA)**:
  - Developing the primary MMR data structure functions (e.g., `append`, `getProof`, `verifyProof`).
  - Optimizing these functions to be zk-SNARK compatible within `o1.js`.
  - Making sure the algorithms operate with high efficiency and low circuit complexity.

- **Testing and Debugging (3,000 MINA)**:
  - Comprehensive unit testing of all functions and debugging.
  - Performance testing with large datasets and varied scenarios.

#### Documentation and Tutorial (10%): 2,500 MINA

- **Comprehensive Documentation (1,500 MINA)**:
  - Creating detailed documentation for all MMR library functions and use cases.
  - Providing technical explanations with example code.

- **Tutorial Creation (1,000 MINA)**:
  - Developing guides and sample scenarios for developers to use the MMR library.
  - Step-by-step instructions on integration with zkApps.

#### Project Management & Miscellaneous (30%): 7,500 MINA

- **Project Coordination and Milestone Tracking (5,000 MINA)**:
  - Managing project timelines, milestone tracking, and internal coordination.

- **Contingency Fund for Unforeseen Expenses (2,500 MINA)**:
  - Reserved budget for unexpected expenses, such as additional tools or consulting fees.

#### Wallet Address

- **MINA Wallet Address** : B62qrN2D9MJLxGoCn5uJ87Bz6YtmWPtMBqn9UXwhbYrVwwDfTGKijjr

* * *

## Team Info

### Proposer GitHub

- **[codekaya](https://github.com/codekaya) (Github Profile)**

### Team Members

- **Yusuf Kaya(Lead Developer)**
  - **Role** : Project lead, main developer.
  - **Experience** :
    - A computer engineer with extensive experience in blockchain development, particularly in zero-knowledge proofs.
    - Worked as a Cairo developer on StarkNet, gaining expertise in writing smart contracts and working with zk-STARKs.
    - Proficient in JavaScript and knowledgeable about cryptography concepts relevant to blockchain and zero-knowledge proofs.

* * *

## Risks & Mitigations

### Risks

- **Technical Complexity** :
  - Implementing MMRs within zk-SNARK constraints is challenging due to fixed-size loops and data structures.

- **Performance Constraints** :
  - Ensuring the library is efficient and does not lead to excessively large circuits.

- **Adoption Risk** :
  - Developers may be slow to adopt the new library without sufficient education and support.

### Mitigations

- **Technical Expertise** :
  - Leverage existing knowledge and consult with experts in zk-SNARKs and MMRs.
  - Conduct thorough testing and optimization.

- **Performance Optimization** :
  - Focus on efficient algorithm design.
  - Profile and optimize circuits to reduce size and proving time.

- **Community Engagement** :
  - Provide comprehensive documentation and support.
  - Engage with the community through tutorial and direct support to encourage adoption.

* * *

Thank you for considering this proposal. We are committed to improving the Mina ecosystem and empowering developers with robust tools for zkApp development.

---

<div class="post-metadata">

**Author:** ![ied](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/ied/32/2172_2.png) [@ied](https://forums.minaprotocol.com/u/ied)\
**Post date:** [October 30, 2024, 8:19am UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/3 "2024-10-30T08:19:48Z")

</div>

The implementation of MMR for O1js would be fantastic and highly beneficial. Integrating this structure would make verification and data tracking processes significantly more efficient. This, in turn, would provide developers with easier application development opportunities and improve the speed and reliability of the user experience. I believe this feature could be a critical step in enhancing Mina’s data consistency and reliability.

---

<div class="post-metadata">

**Author:** ![hgedia](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/hgedia/32/1734_2.png) [@hgedia](https://forums.minaprotocol.com/u/hgedia)\
**Post date:** [November 10, 2024, 6:19pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/4 "2024-11-10T18:19:50Z")

</div>

This proposal is approved for funding. MMR is a useful primitive in bridges.The delivery risk is low and the funding is in line with the proposed work. We measure the impact of this artifact to be high due to its applicability.

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [November 11, 2024, 7:40am UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/5 "2024-11-11T07:40:12Z")

</div>

**Progress Update - November 11, 2024**

Over the past few weeks, significant progress has been made on the implementation of the Merkle Mountain Range (MMR) library in o1.js for zkApp development on the Mina Protocol.

* * *

**Completed Milestones:**

1. **Implementation of Algorithms and Helper Functions:**

2. **Development of Core Functions:**

3. **Unit Testing:**

* * *

**Current Focus:**

- **Integrating MMR into a zk Program:**
  - **Challenges Addressed:**
    - Adapting the MMR to function within zk-SNARK circuits, which require fixed-size data structures and loops.
    - Handling dynamic elements of the MMR in a way that complies with zk-SNARK constraints.

  - **Progress:**
    - Refactoring the MMR library to fit into a zk program structure.
    - Modifying algorithms to operate within fixed-size parameters without losing functionality.

  - **Objective:**
    - To create a zk-SNARK-compatible MMR library that can be integrated into zkApps.

* * *

**Challenges and Solutions:**

1. **zk-SNARK Constraints:**

2. **Performance Optimization:**

3. **Data Structure Adaptation:**

* * *

**Next Steps:**

1. **Finalizing the zk Program Integration:**

2. **Documentation and Tutorials:**

3. **Sample zkApp Development:**

4. **Community Engagement:**

* * *

**Call for Feedback:**

We invite the community to provide feedback, ask questions, or make suggestions. Your input is invaluable in helping us refine the library and ensure it meets the needs of developers building on the Mina Protocol.

**Contact Information:**

- **GitHub Repository:** [Mina\_MMR](https://github.com/codekaya/Mina_MMR)
- **GitHub Profile:** [codekaya](https://github.com/codekaya)

Feel free to reach out or contribute to the repository. Together, we can enhance the tools available for zkApp development and drive innovation within the Mina community.

* * *

Thank you for your continued support and interest in this project. We look forward to sharing more updates soon.

---

<div class="post-metadata">

**Author:** ![ied](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/ied/32/2172_2.png) [@ied](https://forums.minaprotocol.com/u/ied)\
**Post date:** [November 14, 2024, 5:58am UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/6 "2024-11-14T05:58:31Z")

</div>

Congratulations, it’s exciting to see the progress.  
Do you need any other code package other than O1js to implement this?

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [November 14, 2024, 10:35am UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/7 "2024-11-14T10:35:02Z")

</div>

Thank you for your kind words and support!  
MMR library is implemented solely with **o1.js** , which provides all necessary cryptographic and zk-SNARK support. It covers all field elements and arithmetic needed for Mina zkApps, eliminating the need for additional math libraries.

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [November 28, 2024, 10:15pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/8 "2024-11-28T22:15:37Z")

</div>

**Progress Update - November 29, 2024**

Over the past few weeks, i have continued to make significant progress on the implementation of MMR library in o1.js for zkApp development on the Mina Protocol. I am pleased to share the latest updates on project’s status.

* * *

**Completed Milestones:**

1. **Improvement of Core Functions and Algorithms:**

2. **Strengthening Unit Testing Framework:**

3. **Attempted Integration into zk Program:**

* * *

**Current Focus:**

1. **Overcoming Integration Challenges:**

2. **Iterative Development and Testing:**

3. **Documentation of Findings:**

* * *

**Challenges and Solutions:**

1. **zk-SNARK Constraints:**

2. **Performance Optimization:**

3. **Data Representation:**

* * *

**Next Steps:**

1. **Continue Integration Efforts:**

2. **Performance Testing:**

3. **Prepare for Future Integration:**

* * *

**Reflection:**

The journey to integrate the MMR library into a zk program has proven to be more complex than initially anticipated. The inherent limitations of zk-SNARK circuits present significant challenges when working with dynamic data structures like the MMR. However, these challenges have provided valuable learning opportunities and have driven innovation in how we approach zero-knowledge proof development.

I remain committed to overcoming these obstacles and believe that the solutions i am exploring will not only benefit this project but also contribute to the broader knowledge base of zk-SNARK applications.

* * *

**Call for Feedback and Collaboration:**

I recognize that community collaboration is essential in tackling the challenges i face. I invite developers and experts in zk-SNARKs,zk proofs, and cryptographic data structures to provide input, suggestions, or assistance.

- **How You Can Help:**
  - **Review Our Code:**
    - Examine the GitHub repository and provide feedback or propose improvements.

  - **Share Expertise:**
    - If you have experience with similar integrations or zk-SNARK optimizations, your insights would be invaluable.

* * *

**Contact Information:**

- **GitHub Repository:** [Mina\_MMR](https://github.com/codekaya/Mina_MMR)
- **GitHub Profile:** [codekaya](https://github.com/codekaya)

* * *

**Closing Thoughts:**

The path to innovation often involves overcoming unexpected hurdles. I am confident that the lessons learned during this process will lead to a stronger, more versatile library that will serve the Mina developer community well. Thank you for your continued interest and support.

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [December 13, 2024, 6:38pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/9 "2024-12-13T18:38:33Z")

</div>

**Progress Update - December 13, 2024**

Over the last couple of weeks, I’ve been deep in the trenches working on making the MMR code fully compatible with zkSNARK constraints. The integration process has been more intricate than I initially expected, but I’m making steady headway.

**Highlights:**

1. **Advancing zkSNARK Compatibility:**  
I’ve continued refining the core functions and structures to fit within zkSNARK limitations. This mostly comes down to rethinking how the MMR’s inherently dynamic nature can be represented in a fixed-size, zero-knowledge-friendly format. It’s a balancing act between keeping the integrity of the MMR intact and making sure the proof circuits don’t blow up in complexity.

2. **Tutorials and Examples in Progress:**  
Alongside the coding work, I’ve started drafting a tutorial and a hands-on example app. My goal is to make it straightforward for other developers to pick up this MMR implementation and integrate it into their own zkApps. The tutorial will walk through the entire process, from setting up the environment and appending data, all the way through generating and verifying proofs inside a zk circuit.

**Current Challenges:**

- Constraining a dynamic structure like the MMR into a static-proof world continues to be tricky. I’ve been experimenting with setting upper bounds and carefully choosing which parts of the logic happen inside the proof and which can remain off-chain.
- Efficient hashing and encoding strategies that work nicely in a zero-knowledge setting have been another sticking point. I’m tweaking these to be as simple and clear as possible, while still maintaining security and correctness.

**Next Steps:**

- I’m planning to finalize the provable version of the MMR soon. Once I’m confident in the approach, I’ll run a final round of tests to ensure everything behaves as expected.
- I’ll continue polishing the tutorial and example zkApp so they’re ready for public consumption. Once those are available, I’ll share them widely and invite feedback from early adopters.
- After wrapping up this phase, I’m looking forward to hearing from other developers who try it out. Their feedback will be invaluable as I refine the library further.

In short, December has been about wrestling complexity into something manageable and documented. I’m making tangible progress each week, and I’m excited to share a working, well-explained solution soon. Stay tuned!

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [January 17, 2025, 9:22pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/10 "2025-01-17T21:22:12Z")

</div>

## Progress Update – January 18, 2025

I’m happy to share that the off-chain Merkle Mountain Range (MMR) library for o1.js is nearly finished— **completion is just a few days away**! Below is an overview of the recent progress, along with the key challenges that led to some delays, and how they’re being addressed.

* * *

### Near-Completion Status

1. **Core MMR Functionality**

2. **Circuit Integration**

3. **Example zkApp & Tests**

* * *

### Challenges & Delays

1. **Dynamic vs. Static Structures**

2. **Loop Unrolling & Circuit Size**

3. **Performance Tuning**

* * *

### Final Tasks (to be completed in the next few days)

1. **Last Round of Testing**

2. **Documentation & Example Release**

3. **Community Feedback & Launch**

* * *

### Conclusion

Despite the challenges of fitting a dynamic, large-scale MMR into a zero-knowledge circuit environment, the project is **days away** from full release. We’ve successfully reconciled off-chain scalability with an on-chain zk verification model, and the results should greatly simplify any developer’s path to integrating large data sets in Mina zkApps.

**Stay tuned** for the final repository updates, documentation, and example zkApp. I appreciate everyone’s patience and support as we near the finish line.

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [January 28, 2025, 12:19pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/11 "2025-01-28T12:19:20Z")

</div>

## Final Update – January 28, 2025

**I’m pleased to announce that the off-chain Merkle Mountain Range (MMR) library for o1.js is now complete and ready for widespread use.** Below is a summary of the work accomplished, the challenges overcome, and how you can integrate this MMR solution into your own zkApps on Mina.

* * *

### Project Recap

1. **Dynamic Off-Chain MMR, Minimal On-Chain State**

2. **Core Functionalities**

3. **Development Highlights**

* * *

### Key Challenges & Solutions

- **Adapting a Dynamic Structure to Fixed Circuits**  
Merkle Mountain Ranges grow over time, but zk circuits require fixed-size arrays and unrolled loops. We tackled this by:

- **Loop Unrolling & Circuit Limits**  
Functions like `countOnes`, `pow2`, and `getHeight` had to be rewritten with bounded loops to remain provable. This took extra time but now ensures that the code runs reliably within proof constraints.

- **Performance Optimization**  
We simplified heavy operations in proof generation to keep proving times short. Any step that could be reliably performed off-chain was moved off-chain, while only essential proof checks remain inside the circuit.

* * *

### Next Steps & How to Use

1. **Try the Demo**

2. **Integrate into Your zkApp**

3. **Tutorial & Documentation**

4. **Community Feedback**

* * *

### Conclusion

This marks the culmination of a multi-week (and at times challenging) effort to harmonize an inherently dynamic data structure with the fixed-size world of zk proofs. **By pushing most of the heavy lifting off-chain, we preserve Mina’s succinctness while enabling large-scale data applications.**

I want to extend my gratitude to everyone who followed these updates, shared feedback, or contributed ideas. The resulting MMR solution should be a helpful addition for developers looking to build more complex, data-rich zkApps on Mina. I look forward to seeing how the community adopts and extends this library—and I’m excited for the new use cases it will unlock.

**Happy coding!** If you have further questions or want to collaborate, don’t hesitate to reach out on GitHub ([`codekaya`](https://github.com/codekaya)) or in the Mina community channels.

Thank you all for your support and enthusiasm—here’s to a future of more powerful, scalable zkApps on Mina!

---

<div class="post-metadata">

**Author:** ![45930](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/45930/32/2154_2.png) [@45930](https://forums.minaprotocol.com/u/45930)\
**Post date:** [January 30, 2025, 8:18pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/12 "2025-01-30T20:18:05Z")

</div>

Hi codekaya, your implementation is not provable and doesn’t function in a proof on Mina.

```ts
import { Field, Provable, UInt64 } from 'o1js';
import { MerkleMountainRange } from './Mmr';

const mmr = new MerkleMountainRange();
const cs = await Provable.constraintSystem(() => {
  mmr.append(Field(1));
});

console.log(cs);

```

The output of this snippet is

```js
{
  rows: 0,
  digest: '4f5ddea76d29cfcfd8c595f14e31f21b',
  gates: [],
  publicInputSize: 0,
  print: [Function: print],
  summary: [Function: summary]
}

```

This means that there are 0 constraints on the code being executed. It’s clear in the implementation:

```ts
append(value: Field): {
    leavesCount: UInt64;
    elementsCount: UInt64;
    elementIndex: UInt64;
    rootHash: Field;
  } {
    // Increment elementsCount
    let elementsCount = this.elementsCount;
    const peaksIndices = findPeaks(elementsCount);
    let peaks = this.retrievePeaksHashes(peaksIndices);
  
    // Increment elementsCount
    elementsCount = elementsCount.add(UInt64.one);
    let lastElementIdx = elementsCount;
  
    const leafElementIndex = lastElementIdx;
  
    // Store the new value at the last index
    this.hashes[Number(lastElementIdx.toBigInt())] = value;
  
    // Add the new value to peaks
    peaks.push(value);
  
    let height = UInt64.zero;
  
    // Loop to update peaks and compute parent hashes
    while (
      getHeight(lastElementIdx.add(UInt64.one))
        .greaterThan(height)
        .toBoolean()
    ) {
      lastElementIdx = lastElementIdx.add(UInt64.one);
  
      // Ensure peaks has enough elements
      if (peaks.length < 2) {
        throw new Error('Not enough elements in peaks to pop');
      }
  
      const rightHash = peaks.pop()!;
      const leftHash = peaks.pop()!;
  
      const parentHash = Poseidon.hash([leftHash, rightHash]);
      this.hashes[Number(lastElementIdx.toBigInt())] = parentHash;
      peaks.push(parentHash);
  
      height = height.add(UInt64.one);
    }
  
    // Update elementsCount with the last index used
    this.elementsCount = lastElementIdx;
  
    // Bag the peaks to compute the final root hash
    const bag = this.bagThePeaks(peaks);
    const rootHash = this.calculateRootHash(bag, lastElementIdx);
    this.rootHash = rootHash;
  
    // Increment leavesCount
    this.leavesCount = this.leavesCount.add(UInt64.one);
  
    // Return the updated counts and root hash
    return {
      leavesCount: this.leavesCount,
      elementsCount: this.elementsCount,
      elementIndex: leafElementIndex,
      rootHash: this.rootHash,
    };
  }

```

- `findPeaks` uses a `while` loop, which cannot be written into a zk circuit
- `retrievePeaksHashes` uses dynamic indexing by converting UInt64 values into numbers. This also can’t be done in a circuit.
- When you bag the peaks in `const bag = this.bagThePeaks(peaks)`, you are referencing the variable `peaks`, but that variable has been built dynamically by using the `.push` method on the `Array` prototype. The dynamic array that you built can’t be used in a circuit. Only provable arrays can be used, as they have a fixed size.

The rest of the implementation has similar issued to the append method. This may be a valid _javascript_ MMR, but it does not work in a provable context.

---

<div class="post-metadata">

**Author:** ![codekaya](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/codekaya/32/2177_2.png) [@codekaya](https://forums.minaprotocol.com/u/codekaya)\
**Post date:** [January 31, 2025, 8:00am UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/13 "2025-01-31T08:00:14Z")

</div>

Thank you for your reply. This library constructs and updates the MMR off-chain, so it doesn’t need to be “provable” in that part. **Only the final root, which is stored on-chain, requires proof verification.** As explained in the [project README](https://github.com/codekaya/Mina_MMR/blob/d5bc3acc705fb0ba9ca5ef4ed374faaaf4cb6833/Readme.md), the **MMRContract** provides an on-chain `@method` (e.g., `verifyInclusion(...)`) that **is** provable. This on-chain logic confirms a presented leaf and inclusion proof correctly match the MMR’s off-chain root.

Hence, it’s expected that `constraintSystem(() => mmr.append(Field(1)))` yields zero constraints—full MMR construction is done off-chain, while the contract’s proof verification is what creates actual circuit constraints on-chain.

* * *

### Design Intent

- **Off-chain**

- **On-chain**

## Advantages of This Off-chain + On-chain Approach

1. **Scalability**
  - You can manage very large MMRs off-chain without blowing up circuit size or running into Mina’s strict constraints.

2. **Reduced On-chain Complexity**
  - The zkApp only needs to handle verification of a leaf’s membership, which keeps the circuit small and efficient.

3. **Lower Costs**
  - Minimizing on-chain data and computation reduces transaction fees and proving overhead.

4. **Flexibility**
  - Off-chain logic can handle arbitrary data structures, loops, and dynamic arrays—things that aren’t feasible in-circuit.

5. **Separation of Concerns**
  - Developers can build robust logging or historical data solutions off-chain, while still guaranteeing on-chain verifiability of any leaf in the MMR.

Feel free to reach out for additional questions or further discussion!

---

<div class="post-metadata">

**Author:** ![45930](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/45930/32/2154_2.png) [@45930](https://forums.minaprotocol.com/u/45930)\
**Post date:** [January 31, 2025, 4:11pm UTC](https://forums.minaprotocol.com/t/merkle-mountain-range-in-o1js/6642/14 "2025-01-31T16:11:30Z")

</div>

The design of a data structure where you can verify inclusion in a provable method, but you can’t verify state transitions is not very useful. Usually people want to do more than verify inclusion in a tree. They want to be able to edit the tree or update a leaf also, and on Mina they will want to be able to generate a proof that they executed that method correctly.

You can see in your smart contract the problem:

```ts
  /**
   * Public method to update the on-chain MMR root.
   * In a real app, you'd do permission checks or signatures.
   */
  @method async updateRoot(newRoot: Field) {
      // For now, we just store it. (You might require a signature, etc.)
      this.mmrRoot.set(newRoot);
  }

```

If we can’t prove that append is valid from one MMR root to another, then we have to accept any root as valid. This is a very limiting property for zkapp developers. Pretty much the only use case is a completely static tree, but in that case, why not use the built-in `MerkleTree` structure?