ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 8: FRI-based Polynomial Commitments and Fiat-Shamir (Justin Thaler)

8.2 FRI (Univariate) Polynomial Commitment

  • Recall: Univariate Polynomial Commitments
  • Initial Attempt from Lecture 4 (Merkle Tree)

  • Fixing the first problem (Want P time linear in degree, not field size)

    • Biger blowup factor -> more prover time, less verifier time, shorter proofs
    • The key subset: roots of unity

    • Example

  • Fixing the second problem
    • Merkle tree does not tell you any structure of the vertor at all
    • The (interactive) low-degree test: Folding Phase
      • Example
    • The (interactive) low-degree test: Query Phase
  • Back to the folding phase: more details
    • The (interactive) low-degree test: Folding Phase

    • Example
    • The (interactive) low-degree test: Folding Phase
  • Compare to Lecture 7