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.
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.
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.
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.
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.
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:
Implementation of Algorithms and Helper Functions:
Algorithms Developed:
countOnes: Counts the number of ones in the binary representation of a number.
findPeaks: Calculates peak positions in the MMR given the element count.
getHeight: Determines the height of a node in the MMR.
bitLength: Calculates the number of bits needed to represent a number.
Mapping functions between leaf indices and element indices (mapLeafIndexToElementIndex and mapElementIndexToLeafIndex).
Development of Core Functions:
append(data: Field):
Allows adding new elements to the MMR efficiently.
Updates peaks and recalculates the root hash using optimized methods.
Proof Generation and Verification:
Implemented getProof(leafIndex: UInt64) to generate inclusion proofs.
Developed verifyProof(leaf: Field, proof: Proof) to verify the validity of proofs.
Extended functionality to handle multiple proofs with getProofs and verifyProofs.
MMR State Management:
Functions like getPeaks, bagThePeaks, and calculateRootHash are in place to manage and represent the MMR state accurately.
Unit Testing:
Comprehensive Test Suite:
Wrote unit tests covering all algorithms and core functions.
Test-Driven Development Approach:
Adopted TDD practices to identify and fix issues early in the development cycle.
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:
zk-SNARK Constraints:
Challenge:
zk-SNARKs impose strict limitations on data structures and loops, making it difficult to implement dynamic structures like MMRs.
Solution:
Refactored algorithms to use fixed-size arrays and loops.
Implemented padding and placeholder elements to accommodate variable data within fixed-size constructs.
Performance Optimization:
Challenge:
Ensuring that the MMR operations do not excessively increase the size of the zk-SNARK circuit, which would impact proving times.
Solution:
Optimized algorithms to minimize computational complexity.
Used efficient mathematical operations and avoided unnecessary computations within the circuit.
Data Structure Adaptation:
Challenge:
Mapping the inherently dynamic MMR data structure into the static nature required by zk-SNARKs.
Solution:
Designed custom data structures compatible with zk-SNARKs while maintaining the integrity and functionality of the MMR.
Employed techniques to simulate dynamic behavior within static constructs.
Next Steps:
Finalizing the zk Program Integration:
Complete the transformation of the MMR library into a fully functional zk program.
Ensure all core functions operate correctly within the zk-SNARK environment.
Documentation and Tutorials:
Begin drafting comprehensive documentation for the MMR library.
Create step-by-step tutorials and examples to aid developers in integrating the library into their zkApps.
Sample zkApp Development:
Develop a sample application that demonstrates the practical use of the MMR library within a zkApp.
Use this sample to test the library in real-world scenarios and gather performance metrics.
Community Engagement:
Prepare to share the progress with the Mina developer community.
Plan webinars or workshops to introduce the MMR library and gather feedback.
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.
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.
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.
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:
Improvement of Core Functions and Algorithms:
Refinement of Algorithms:
Optimized Existing Functions:
Improved the efficiency of countOnes, findPeaks, getHeight, and bitLength functions.
Improved the mapping functions between leaf and element indices for better performance.
Algorithm Testing:
Performed extensive testing to ensure all algorithms operate correctly with large datasets.
Identified and fixed edge-case issues that could affect the integrity of the MMR.
Development of Additional Helper Functions:
Created new utility functions to assist with data manipulation within the MMR.
Developed functions to handle specific scenarios encountered during integration attempts.
Strengthening Unit Testing Framework:
Comprehensive Test Coverage:
Expanded the test suite to cover more complex scenarios and edge cases.
Ensured that all core functions are accompanied by thorough unit tests.
Attempted Integration into zk Program:
Initial Integration Efforts:
Began integrating the MMR library into a zk program structure.
Refactored code to align with zk-SNARK constraints, such as fixed-size arrays and loops.
Challenges Encountered:
Dynamic Data Structures:
Faced difficulties adapting the inherently dynamic MMR into the static nature required by zk-SNARKs.
The need for fixed-size constructs conflicts with the variable size of the MMR as elements are appended.
Circuit Constraints:
Encountered limitations on circuit size and complexity, leading to performance bottlenecks.
Some functions increased the proving time beyond acceptable thresholds.
Progress Made:
Identified key areas where adjustments are needed to comply with zk-SNARK requirements.
Developed prototype versions of certain functions within the zk program context.
Gained a deeper understanding of the limitations and necessary adaptations for successful integration.
Current Focus:
Overcoming Integration Challenges:
Data Structure Adaptation:
Exploring methods to represent the MMR within zk-SNARKs using fixed-size constructs.
Considering the use of padding and pre-defined maximum sizes to simulate dynamic behavior.
Algorithm Optimization:
Revisiting algorithms to reduce computational complexity within the zk circuit.
Removing or simplifying operations that are costly in terms of circuit resources.
Expert Consultation:
Engaging with zk-SNARK experts and the Mina developer community to seek advice.
Iterative Development and Testing:
Prototype Iterations:
Developing small-scale prototypes to test the feasibility of proposed adaptations.
Using these prototypes to measure circuit size and proving times.
Performance Benchmarking:
Establishing benchmarks to assess the impact of changes on performance.
Aiming to find an acceptable balance between functionality and efficiency.
Documentation of Findings:
Recording Challenges and Solutions:
Documenting the challenges faced during integration and the steps taken to address them.
This documentation will be valuable for others attempting similar integrations.
Updating the Repository:
Keeping the GitHub repository up to date with the latest code and documentation.
Ensuring transparency and openness in the development process.
Challenges and Solutions:
zk-SNARK Constraints:
Challenge:
The fixed-size nature of zk-SNARK circuits makes it difficult to implement dynamic structures like the MMR.
Solution Approaches:
Fixed-Size MMR:
Define a maximum size for the MMR and use fixed-size arrays.
This limits the number of elements but complies with zk-SNARK constraints.
Recursive Proofs:
Investigate the use of recursive proofs to handle larger structures without exceeding circuit limitations.
This is a complex solution that may require additional research and development.
Performance Optimization:
Challenge:
Ensuring the MMR operations are efficient within the zk-SNARK environment to keep proving times practical.
Solution Approaches:
Algorithm Simplification:
Simplify algorithms to reduce the number of constraints they introduce into the circuit.
Selective Functionality:
Prioritize essential functions and defer non-critical features to off-chain computation.
Data Representation:
Challenge:
Representing the MMR data in a way that is compatible with the zk-SNARK field elements.
Solution Approaches:
Encoding Data:
Use field elements to encode data, ensuring compatibility with zk-SNARK computations.
Efficient Hashing:
Utilize hash functions optimized for zk-SNARKs to maintain data integrity without excessive overhead.
Next Steps:
Continue Integration Efforts:
Implement Proposed Solutions:
Apply the identified approaches to adapt the MMR to zk-SNARK constraints.
Focus on creating a minimal viable integration that can be expanded upon.
Collaborate with the Community:
Seek feedback from other developers who have faced similar challenges.
Participate in Mina Protocol forums and discussions to exchange ideas.
Performance Testing:
Measure Impact:
Quantify the effects of changes on circuit size and proving times.
Use this data to guide further optimization efforts.
Iterate Based on Results:
Refine algorithms and structures based on performance metrics.
Aim for an acceptable trade-off between functionality and efficiency.
Prepare for Future Integration:
Documentation and Planning:
Document the integration process, challenges, and solutions in detail.
Plan for eventual incorporation into zkApps once a viable solution is established.
Community Engagement:
Share progress updates with the Mina developer community.
Offer insights that may help others and invite collaboration.
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.
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.
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:
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.
I’ve also been exploring ways to minimize the cost of proving. Some of the earlier approaches introduced a bit too much overhead—so I’ve been pruning and simplifying certain operations. Each iteration gets a little closer to that sweet spot where the proofs remain practical.
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.
The example will be small but illustrative, showing developers exactly what the integration looks like in practice. Once done, it should make it a lot easier to understand how to slot the MMR code into their existing projects without getting lost in the details.
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!
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
Core MMR Functionality
Large Off-Chain Capacity: The MMR still supports a high MAX_ELEMENTS setting. I retained its ability to handle millions of leaves off-chain without compromising performance.
Inclusion Proofs: The append, proof generation, and proof verification processes have been thoroughly tested.
Circuit Integration
On-Chain Root Commitment: A minimal zkApp contract now demonstrates how to store and verify the MMR root on-chain.
Provable Functions: All essential subroutines (bitLength, pow2, countOnes, etc.) have been refactored to use unrolled loops and Provable.if statements, meeting zk-SNARK constraints.
Example zkApp & Tests
Comprehensive Testing: Edge cases (e.g., near capacity appends) have been checked, ensuring off-chain data integrity and on-chain verification correctness.
Showcase Repository: An example repo illustrating how to combine the off-chain MMR with on-chain root checks will be published once final refinements are done.
Challenges & Delays
Dynamic vs. Static Structures
Issue: The MMR naturally expands over time, whereas zk-SNARKs require fixed-size arrays and unrolled loops.
Impact: Determining how to handle large or “unbounded” data sets within a constrained circuit environment extended our development timeline.
Solution: We moved all large-scale storage and processing off-chain, keeping only the MMR root (a single Field) on-chain. This approach reduced circuit complexity drastically.
Loop Unrolling & Circuit Size
Issue: Functions like findPeaks or bitLength needed rewriting to avoid unbounded while loops. This unrolling introduced more lines of code and thorough retesting.
Impact: Each unrolled function had to be carefully verified, causing a slower development cycle than anticipated.
Solution: We completed each function’s conversion to unrolled logic, tested them extensively, and integrated them into the MMR flow without exceeding circuit constraints.
Performance Tuning
Issue: Some operations, if left naive, introduced excessive constraints, slowing proof generation.
Impact: The shift from flexible JavaScript arrays to fixed-size circuit constructs led to repeated refactoring.
Solution: Simplified or offloaded certain heavy tasks (e.g., large merges or full MMR scanning) to off-chain. Only minimal checks—like verifying the root—remain on-chain.
Final Tasks (to be completed in the next few days)
Last Round of Testing
Validate the combined off-chain + on-chain workflow, ensuring the final root matches for large batch appends.
Run performance benchmarks to confirm that circuit proving times remain acceptable.
Documentation & Example Release
Provide a tutorial-like repo showing how to build a big MMR off-chain, commit its root on-chain, and verify proofs in a zkApp.
Include troubleshooting guidance and best practices for expansions or adaptations.
Community Feedback & Launch
Announce the completed library on the Mina forum.
Invite feedback on any further optimizations or potential enhancements.
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.
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
Dynamic Off-Chain MMR, Minimal On-Chain State
The project’s core objective was to allow large Merkle Mountain Ranges to be built and updated off-chain, while storing only a single Field (the MMR root) on-chain.
This approach leverages Mina’s succinct model: we minimize circuit complexity by delegating heavy computations to off-chain code, then prove membership of any leaf via a short inclusion proof on-chain.
Core Functionalities
Append: Efficiently add leaves off-chain and maintain up-to-date hashes.
Proof Generation & Verification: Generate proof data off-chain, then verify it on-chain by reconstructing the root in-circuit.
Fixed-Size Circuit Adaptations: Key algorithms such as bitLength, getHeight, and findPeaks have been refactored with unrolled loops, ensuring they remain zk-SNARK-compatible.
Development Highlights
Performance Tuning: We carefully balanced off-chain vs. on-chain tasks to keep proof sizes manageable.
Robust Test Suite: Edge cases—like near-maximum append operations—were tested to validate reliability.
Documentation & Examples: A companion example shows how to combine the off-chain library with on-chain verification in a minimal zkApp contract.
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:
Keeping large data arrays and updates off-chain, and
Restricting the zk circuit to verifying minimal data (the root comparison).
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
Try the Demo
Check out the Mina MMR for a working example (index.ts). It demonstrates how to append leaves, commit the root on-chain using MMRContract.ts, and verify inclusion proofs.
Integrate into Your zkApp
Clone or fork the repository and integrate the MMR logic (Mmr.ts) into your project.
Store only the MMR root in your own smart contract’s state.
Off-chain, append or remove leaves, generate proofs, and submit them to your contract’s verification method.
Tutorial & Documentation
The repo’s README details setup instructions, usage examples, and best practices for building large MMRs off-chain.
A short tutorial is included to illustrate how to configure local testing with Mina.LocalBlockchain() and how to manage transactions for root updates.
Community Feedback
Your input is invaluable! If you encounter any edge cases, performance bottlenecks, or have ideas for enhancements, please open an issue on GitHub or post on the Mina forums.
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) 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!
This means that there are 0 constraints on the code being executed. It’s clear in the implementation:
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.
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, 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
Build and update the MMR (append leaves, compute internal hashes, etc.) in JavaScript/TypeScript with no circuit constraints.
Generate inclusion proofs (getProof(...)) without any need for circuit constraints.
On-chain
Store a single Field root in the zkApp state.
Expose a provable @method (like verifyInclusion(...)) to recompute part of the tree path from the leaf + siblings and confirm it matches the stored root. This is the part that is actually “provable” inside a Mina circuit.
Advantages of This Off-chain + On-chain Approach
Scalability
You can manage very large MMRs off-chain without blowing up circuit size or running into Mina’s strict constraints.
Reduced On-chain Complexity
The zkApp only needs to handle verification of a leaf’s membership, which keeps the circuit small and efficient.
Lower Costs
Minimizing on-chain data and computation reduces transaction fees and proving overhead.
Flexibility
Off-chain logic can handle arbitrary data structures, loops, and dynamic arrays—things that aren’t feasible in-circuit.
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!
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:
/**
* 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?