acceleration-program
acceleration-program copied to clipboard
privacy-scaling-explorations
Proposal: Folding by hand (Nova by hand)
General Grant Proposal
- Project: Nova by Hand
Project Overview :page_facing_up:
Overview
Provide an article that explains the advantages of Nova's Folding Scheme mechanism compared to conventional recursive proofs and explains its primitives in an intuitive and in-depth, using many illustrations.
Project Details
Scope of readers
People who want to know how Nova folding works.
Article
- Outline
- Introduction to Nova
- Incremental Verifiable Computation
- Mechanisms and problems of ordinary Recursion
- Cycle of Curve in Recursion generally
- Nova
- Relaxed R1CS by Hand
- R1CS
- Relaxed R1CS
- Pedersen Commitment Scheme
- Committed Relaxed R1CS
- Folding Scheme for committed Relaxed R1CS
- (link to Python code snippets)
- Non-interactive Folding Schemes with a hash function
- Cycle of Curve in Nova
- Introduction to Nova
Not scope
- Polynomial Interactive Oracle Proof(Super Spartan), Augmented Circuit
Team :busts_in_silhouette:
Team members
Yugo
Discord: yugokoral
Github: https://github.com/yugocabrio
Team's experience
PSE ZK Summer Open Source Contribution Program fellow My contribution
Team Code Repos
https://github.com/yugocabrio/Folding_by_Hand
Development Roadmap :nut_and_bolt:
Overview
-
Total Estimated Duration: 8 weeks(4 milestones)
-
Full-time equivalent (FTE): 0.4-0.5
-
Starting Date: December 11th
-
Estimated delivery date: February 26th
-
Note: I would like to break 3 weeks to focus on the final exam at Univ between Milestones 2 and 3.
Milestone 1
- Estimated Duration: 2 weeks
- FTE: 0.4
- Starting Date: December 11th 2023
- Estimated delivery date: December 25th 2023
Contents
Introduction to Nova
- Incremental Verifiable Computation
- Mechanisms and problems of ordinary Recursion
- Cycle of Curve in Recursion generally
- Nova
1. Incremental Verifiable Computation
Explain Incremental Computation and Incremental Verifiable Computation with simple illustrations.
2. Mechanisms and problems of ordinary Recursion
Explain the mechanism of recursion or accumulation, for example, Halo2 or Plonky, briefly with diagrams. Also, discuss their disadvantages, such as the overhead of pairing in the snark verifier during proving.
3. Cycle of Curve in Recursion generally
Explanation of elliptic curve's subgroups defined on finite fields. Also, an explanation of the mismatch between the base field and the scalar field during recursion. Explain that using two elliptic curves, the scalar field of each curve is the base field of the other curve.
4. Nova
Explain Nova, which introduces a Folding scheme that compresses two R1CS (NP instances) into one. Briefly introduce the differences between Nova, Snagira, SuperNova, and HyperNova.
Milestone 2
- Estimated Duration: 2 weeks
- FTE: 0.4
- Starting Date: December 25th 2023
- Estimated delivery date: January 8th 2024
Contents
Relaxed R1CS by Hand
- R1CS
- Relaxed R1CS
- Pedersen Commitment Scheme
- Committed Relaxed R1CS
- Folding Scheme for committed Relaxed R1CS
- Python code snippets
1. R1CS
Explain how to construct the R1CS(Az◎Bz=Cz) from the equation x^2-5x+9=3, which has roots at x=2 and x=3. The reason I chose this is that I want to show the folding with different witnesses. Explain that simple folding with linear combination fails due to cross-term.
2. Relaxed R1CS structure
Explain the Relaxed R1CS(Az◎Bz=uCz+E) structure. Introduce folding the above R1CS by hand calculation while using Python's snippet.
3. Pedersen Commitment Scheme
Explain the additive homomorphism of the Pedersen commitment.
4. Committed Relaxed R1CS
Explain a committed R1CS that allows the Prover to compute computationally expensive error terms, including cross terms, instead of having the Verifier compute them and also realizes zero knowledge.
5. Folding Scheme for committed Relaxed R1CS
Explain the Interactive Folding scheme for Committed Relaxed R1CS. Explain what Prover and Verifier do and in what order they work.
Milestone 3
- Estimated Duration: 2 weeks
- FTE: 0.5
- Starting Date: January 29th 2024
- Estimated delivery date: February 12th 2024
Contents
- Non-interactive Folding Schemes with a hash function
- Cycle of Curve in Nova
1. Non-interactive Folding Schemes with a hash function
Explain the Fiat-Shamir transformation as a general idea and then how to apply it to the Non-Interactive Folding Scheme. In this case, the prover takes in the commitment of cross-term as a parameter of a random oracle.
2. The cycle of Curve in Nova
Explain how the cycle of the curve works in Nova. I will read and study the Revisiting Nova video or paper.
Milestone 4
- Estimated Duration: 2 weeks
- FTE: 0.5
- Starting date: February 12th 2024
- Estimated delivery date: February 26th 2024
Finish the incomplete tasks and review the article. In previous milestones, I will have prepared the initial versions of the handwritten illustrations. During this final milestone, I will refine and finalize these illustrations.
@NOOMA-42 @CPerezz
Based on your feedback, I have refined the content and timeline of the proposal. Please review the updated proposal at your convenience. Thank you.
