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!