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