NOOMA-42
commented
1 year ago Hi I'm looking for the reviewer now. It might take a while
Closed yugocabrio closed 6 months ago
NOOMA-42
commented
1 year ago Hi I'm looking for the reviewer now. It might take a while
NOOMA-42
commented
1 year ago Hi @yugocabrio , @CPerezz Will review this proposal.
yugocabrio
commented
11 months ago @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.
CPerezz
commented
11 months ago LGTM!
NOOMA-42
commented
6 months ago completed
General Grant Proposal
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
Not scope
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
Contents
Introduction to 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
Contents
Relaxed R1CS by Hand
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
Contents
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
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.