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.

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

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.
2 Likes