ZKP10.2 Efficient Recursion via Statement Folding (Nova)

ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 10: Recursive SNARKs, Aggregation and Accumulation (Dan Boneh)

10.3 Efficient Recursion via Statement Folding: Nova, Supernova, and generalizations

• The difficulty with full recursion

  • Prover P needs to build a proof for a circuit C that runs the entire verification algorithm $V(vk,x,\pi )$.
    • Expensive: V needs to verify eval. proofs for a poly. commitment
      • Halo: takes eval proof verification out of C -> simpler C
      • Nova: takes (almost) all verification checks out of C -> even simpler C

• A folding scheme: compress two instances into one
  

  • To make Folding Prover non-interactive
    

• A folding scheme for R1CS

  • Recall: circuit to R1CS
    

  • A folding scheme: compress two instances into one
    

• relaxed R1CS
  

• Folding the two relaxed R1CS instances into one
  

  • Correctness
    

• Not good enough
  

• Recall: homomorphic commitment scheme
  

• Folding scheme for committed relaxed R1CS
  

• Putting folding to use
  • build an efficient IVC
    

• The key point
  

• Unfortunately … not so simple
  

• Prover’s work at each step
  

• Supernova
  

• Generalizations: Sangria[https://geometry.xyz/notebook/sangria-a-folding-scheme-for-plonk]