Interactive ZK Proofs and Proof Recursion Research

Mina Navigator Proposals
1

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

12th September, 2024
Current status: Funded
Funding Note: This proposal is approved for funding. We are happy to see quality research done on the proof system and explore the advancements in the space. This should provide more insight to other researchers/academics and developers. There is a low risk and medium impact associated with the proposal. The funding is in line with the work proposed.

4th September, 2024
Current status: Under Consideration.
Opened for community discussion on : 4th September,2024

1 Like
2

Title

Interactive ZK Proofs and Proof Recursion Independent Research at EPFL

Project Background

This project is a novel independent research initiative focused on advanced zero-knowledge proof systems, particularly interactive ZK proofs and proof recursion. The research will be conducted at École Polytechnique Fédérale de Lausanne (EPFL) in Switzerland, a world-renowned institution for cryptography and computer science.

The core of this project involves auditing several key classes at EPFL, including Alessandro Chiesa’s course on interactive proofs, as well as courses on computational complexity and information theory. The knowledge gained from these courses will be distilled and shared with the broader blockchain community through a series of weekly research posts. These posts will not only explain complex concepts in accessible terms but also include small code implementations to demonstrate practical applications.

Proposal Overview

Problem:

There is a significant knowledge gap within crypto, particularly in advanced zero-knowledge proof systems and their practical applications. This gap hinders the rapid advancement and adoption of cutting-edge technologies like Mina’s zkApps and recursive proof systems. The complexity of these topics often creates a barrier between academic research and real-world implementation, slowing down innovation and ecosystem growth.

Solution:

This research project proposes an intensive study program at EPFL, focusing on interactive ZK proofs, proof recursion, computational complexity, and information theory. The key aspect of this solution is the rapid distillation and dissemination of complex academic concepts into accessible, Mina-focused weekly research posts. These posts will include:

  1. Clear explanations of advanced ZK concepts
  2. Practical code implementations demonstrating applications in Mina’s ecosystem
  3. Insights into potential improvements for Mina’s zkApp platform and recursive proof systems

By framing all learnings around Mina’s technology, this project will create a direct pipeline from academic knowledge to practical advancements in the Mina ecosystem.

Impact:

This proposal will significantly enhance the Mina ecosystem in several ways:

  1. Knowledge Expansion: It will increase the collective understanding of advanced ZK concepts within the Mina community, fostering innovation and development.

  2. Developer Attraction: By providing accessible yet deep technical content, it will attract more developers to the Mina ecosystem.

  3. Technological Advancement: The research may lead to improvements in Mina’s core technology, particularly in zkApps and recursive proof systems.

  4. Ecosystem Growth: Enhanced knowledge and technology will encourage the creation of more complex and efficient applications on the Mina platform.

  5. Industry Leadership: Regular, high-quality research output will reinforce Mina’s position as a thought leader in the ZK and blockchain space.

Audience:

The target audience for this project includes:

  1. Mina developers seeking to deepen their understanding of ZK proofs and improve their zkApp development skills.
  2. Mina community members who want to understand the technical underpinnings of the platform.
  3. Potential adopters of Mina technology, including other blockchain projects and enterprises considering ZK solutions.
  4. The broader blockchain and cryptography community interested in the intersection of academic research and real-world blockchain applications.

Architecture & Design

The project will consist of a series of 12 weekly blog posts, each synthesizing knowledge from three key areas: interactive ZK proofs, computational complexity, and information theory. These posts will be tailored to Mina’s technology, providing a comprehensive foundation for understanding and advancing zkApps and recursive proof systems.

Here’s a tentative outline of the 12-week research post series:

  1. Week 1: Introduction to Interactive Proofs and Mina’s ZK Ecosystem
  2. Week 2: HyperNova and Proof Folding: Advancing Mina’s Recursive Proofs
  3. Week 3: Accumulation Schemes and Their Potential in Mina’s Architecture
  4. Week 4: Sumcheck Protocol and SuperSpartan IOP: Enhancing Mina’s Efficiency
  5. Week 5: Customized Constraint Systems and Arithmetization for Mina zkApps
  6. Week 6: Information Theoretical Basis of IOPs in Mina’s Context
  7. Week 7: Low-Degree Testing and Reed-Solomon Codes in Mina’s Proof Systems
  8. Week 8: Measuring Time-Space Complexity of Proofs in Mina’s Blockchain
  9. Week 9: Advanced IOP Protocols and Their Potential Mina Applications
  10. Week 10: Optimizing Recursive Proofs in Mina using Complexity Theory
  11. Week 11: Information-Theoretic Approaches to zkApp Optimization
  12. Week 12: Future Directions for Mina: Synthesizing Advanced ZK Concepts

Each post will include:

  • Theoretical explanations of the topic
  • Practical code examples relevant to Mina’s technology
  • Discussion of potential applications or improvements for Mina’s ecosystem

Vision:

The long-term vision for this project is to create a comprehensive, accessible resource that bridges the gap between cutting-edge academic research in ZK proofs and practical blockchain development. By the end of the 12 weeks, we aim to have:

  1. A cohesive series of posts that serve as a go-to resource for developers and researchers in the Mina ecosystem.
  2. A set of code implementations that demonstrate advanced ZK concepts applied to Mina’s technology.
  3. A foundation for further research and development in enhancing Mina’s zkApp platform and recursive proof systems.
  4. An engaged community of developers and researchers contributing to Mina’s technological advancement.

Production Timeline:

The production timeline for this project is as follows:

  • September 2023: Project kickoff, begin auditing courses at EPFL
  • September - December 2023: Weekly research posts published
  • December 2023: Final comprehensive report and code repository completed
  • January 2024 onwards: Ongoing engagement with the Mina community, potential for follow-up research or development projects

The goal is to have a complete set of research posts and accompanying code examples ready by the end of December 2023. However, the impact of this work on Mina’s ecosystem is expected to continue well beyond this timeline as developers and researchers build upon the knowledge shared.

Budget & Milestones

Deliverables:

  1. 12 weekly research posts on advanced ZK concepts applied to Mina’s technology
  2. Code implementations demonstrating key concepts, hosted on a public GitHub repository
  3. Final comprehensive report synthesizing the research findings and potential applications for Mina

Mid-Point Milestones:

By week 6 of the project:

  1. 6 weekly research posts published
  2. Initial code implementations for at least 3 key concepts
  3. Mid-point community feedback session to guide the direction of remaining research

Project Timeline:

3 months (September 2023 - December 2023)

Budget Requested:

31,250 MINA (equivalent to $15,000 at $0.48 per MINA)

Budget Breakdown:

  • Housing: 16,667 MINA ($8,000)
  • Living expenses: 10,417 MINA ($5,000)
  • Research materials and software: 4,166 MINA ($2,000)
  • Total: 31,250 MINA ($15,000)

Wallet Address:

B62qouYGdpXLJ5QomNQdGKTsrgkbVxLRfxmH3cwjXqpA9vci98QALtf

This budget will cover the researcher’s living expenses and necessary materials during the 3-month intensive study and research period at EPFL, enabling full focus on the project deliverables and Mina-specific applications of advanced ZK concepts.

Proposer Experience:

I am a computer scientist with a strong focus on Zero-Knowledge Proofs. My experience includes:

Team Members:

This is an individual research project. As the sole researcher, I will be responsible for:

  • Conducting the research and auditing courses at EPFL
  • Writing weekly research posts
  • Developing code implementations
  • Engaging with the Mina community

Achievements:

  1. Winner Chewing Glass award at ZK HACK Montreal for best technical project. SuperSpartan implementation.
  2. Developing a prototype STIR prover in Go
  3. Creating DEATH-Machine, a ZK game using Cairo circuits
  4. Implementing SkyBot, a Python-based system to manage AI social bots from Telegram
  5. Writing in-depth research articles on key ZK concepts:
    • “Sumcheck: The Queen of Algorithms”
    • “Proximity is What You Want”
    • “A (somewhat) gentle introduction to the FFT”
  6. Working as a ZK Research Engineer at Ingonyama, where I developed a GPU-accelerated PLONK Prover

Risks & Mitigations

Risks:

  1. Complex academic content may be challenging to translate into accessible blog posts.
  2. The rapid pace of research might lead to information overload or burnout.
  3. Unforeseen changes in EPFL course content or structure could impact the research plan.
  4. The cutting-edge nature of the research might lead to difficulties in finding immediate practical applications for Mina.

Mitigations:

  1. Regular feedback from the Mina community will be sought to ensure content remains relevant and understandable.
  2. A structured work schedule with built-in breaks will be maintained to prevent burnout.
  3. Flexibility in the research plan will allow for adjustments based on course content changes.
  4. Close collaboration with Mina developers will help identify the most promising areas for practical application.
3 Likes
3

This proposal is approved for funding. We are happy to see quality research done on the proof system and explore the advancements in the space. This should provide more insight to other researchers/academics and developers. There is a low risk and medium impact associated with the proposal. The funding is in line with the work proposed.

1 Like
4

Updates on my end:

Research:

  • I’m honing in on custom gates and lookups as my main focus for research. I think this will have the biggest impact and most closely corelates to the Mina roadmap.

  • I’ll send a link to the repo where I will be keeping the docs when it’s set up

Blog:

  1. x.com
  2. x.com

Code:

1 Like
5

Research Update

My research is converging on the intersection of coding theory and cryptographic proof systems, specifically exploring how fundamental primitives like Reed-Solomon codes can be leveraged to build more efficient and quantum-resistant verification systems. This direction is particularly compelling as it addresses both theoretical depth through novel mathematical structures and practical impact through improved efficiency - a critical consideration as distributed systems continue to scale.

Content:

  1. Introduction to Interactive Proofs and Mina
  2. Introduction to Gates and Circuits
  3. The Elegant Foundation: Plonkish Arithmetization
  4. Tools for Probabilistic Checkable Proofs
  5. Locally Testable Proofs: The PVP Problem
  6. Down the Rabbit-Hole: The Low-Degree Test
  7. Repeat-Accumulate-Accumulate (RAA) Codes
  8. Note on Foldable Codes

Research:

Recent breakthroughs in proof accumulation schemes and foldable codes have dramatically shifted our understanding of what’s possible in this space. Innovations like DeepFold and ARC have demonstrated that we can achieve significant efficiency improvements while maintaining security, and new theoretical frameworks for handling list-decoding bounds are pushing these systems closer to practical deployment.

Below is a shortlist of works I am currently studying in-depth.

Note for Community:

I recently attended MinaCon in Istanbul and was blown away by the amazing community. One of the best parts for me was the opportunity to explain zk research and proof systems to a general audience and hold a small workshop of Polynomial Commitment Schemes and IOPs.

2 Likes
6

Research Update

My research focus is on how advanced polynomial commitment schemes like BaseFold can be integrated to construct efficient and secure recursive zk-STARK protocols over binary fields. By leveraging random foldable codes, we address the challenges of recursive proofs in binary fields, achieving both theoretical advancements through novel mathematical frameworks and practical impact through enhanced efficiency and scalability. This direction is particularly compelling as it not only deepens our understanding of recursive proof systems but also meets the pressing needs of distributed systems to handle larger scales securely and efficiently—a critical consideration in the evolution of blockchain and beyond.

Link to research whitepaper.

Mina 2.0

The goal is to develop a next-generation blockchain protocol that builds upon Mina’s core strengths while dramatically improving scalability, efficiency, and functionality. Key components include:

1. Enhanced Recursive Proof System (EndGame)

  • Field-Agnostic Polynomial Commitments: Implementation of BaseFold scheme enables efficient commitments over binary fields, reducing proof sizes and computation overhead
  • Optimized Arithmetization: Custom AIR design for efficient binary field operations, particularly suited for blockchain-specific computations
  • Parallel Proof Generation: Scalable architecture supporting concurrent proof generation and verification
  • Batch Processing: Efficient aggregation of multiple proofs into a single succinct proof

. Scalability Improvements

  • Throughput Enhancement:
    • Parallel proof generation enables processing multiple transactions simultaneously
    • Batch proving reduces overall verification costs
    • Estimated 10-100x improvement in transaction processing capability
  • State Management:
    • Compressed state representations using efficient polynomial commitments
    • Stream-based proof generation for handling large state transitions
    • Memory-efficient verification through recursive composition

Research Roadmap

Given the scope and complexity of this system design, implementing the full prototype (Phase 2) extends beyond the current grant’s parameters. The prototype phase will require additional engineering resources and a dedicated team to properly execute. My recommendation is to use the current grant to fully develop and document the theoretical foundation (Phase 1), which will provide the necessary groundwork for future implementation efforts.

Phase 1: Theoretical Foundation (Current)

  • Complete system design
  • Optimize polynomial commitment scheme
  • Develop efficient arithmetization techniques

Phase 2: Prototype Development

  • Implement core components
  • Develop testing framework
  • Measure performance metrics
  • Iterate on design

Conclusion

This research represents a significant step toward Mina 2.0, combining theoretical innovation with practical implementation considerations. The proposed system maintains Mina’s core principles while substantially improving performance and scalability. Through careful integration of advanced cryptographic techniques and efficient implementation strategies, we aim to create a foundation for next-generation blockchain systems that are both theoretically sound and practically viable.

2 Likes
7

Research Conclusion

Today I’m super excited to announce the conclusion of my research project. Over the past three month’s I’ve focused on the foundations of interactive proofs, explored different constructions and frameworks, and wrapped everything up by designing a proof of concept blockchain called EndGame.

The design goal of EndGame is build on the existing Mina protocol while incorporating cutting edge accumulation schemes from the most recent literature. You can find the design specs for EndGame in the attached research paper.

My single biggest conclusion from this research is that Mina and Mina-like systems are the way forward for blockchains. I firmly believe that as other chains seeks to scale and achieve greater levels of succinctness they will progressively converge on the same basic tools used by Mina.

List of Posts

  1. Introduction to Interactive Proofs and Mina
  2. Introduction to Gates and Circuits
  3. The Elegant Foundation: Plonkish Arithmetization
  4. Tools for Probabilistic Checkable Proofs
  5. Locally Testable Proofs: The PVP Problem
  6. Down the Rabbit-Hole: The Low-Degree Test
  7. Repeat-Accumulate-Accumulate (RAA) Codes
  8. Note on Foldable Codes
  9. Mathematics for Multi-Processor Architecture: First Sketch
  10. ARC: Accumulation for Reed-Solomon Codes
  11. Mina and Ethereum’s Future: Convergent Evolution
  12. Rebuilding Mina with ARC
  13. Succinct Blockchains with Accumulation: A Path Forward

Research

This paper outlines EndGame, a succinct blockchain built on the ARC accumulation scheme for Reed-Solomon codes. The goal of this blockchain is achieve a high degree of parallelism and succinctness while maintaining design simplicity. I think we are at a point with zk and blockchain where it’s useful to be extremely ambitious - and try to find the absolute maximum performance achievable using the current state of the art. EndGame seeks to do that.

EndGame

I believe this research will be useful as Mina seeks to continually upgrade the tech stack and make the chain even more performant.

Conclusion

I want to extend a huge debt of gratitude to the entire Mina Foundation and the team that helped make this research possible. Especially to @Yasince @WillCove and @hgedia for great support. I’m very excited to continue working in the Mina ecosystem and can’t wait to see the protocol continue to evolve moving forward. Especially as we work to build increasingly performant zk building blocks into the core protocol.

1 Like