ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 7: Polynomial Commitments Based on Error-correcting Codes (Yupeng Zhang)

  • Recall: common paradigm for efficient SNARK
    • A polynomial commitment scheme + A polynomial interactive oracle proof (IOP) = SNARK for general circuits
  • Poly-commit based on error-correcting codes
    • Motivations:
      • Plausibly post-quantum secure
      • No group exponentiations (prover only uses hashes, additions and multiplications)
      • Small global parameters
    • Drawbacks:
      • Large proof size
      • Not homomorphic and hard to aggregate

7.1 Background on error-correcting codes

  • Error-correcting code
    • $[n,k,\Delta]$ code
      • Enc(m): Encode a message of size k to a codeword of size n
      • Rate: $\frac{k}{n}$: [0,1], as close to 1 as possible
      • Relative distance: $\frac{\Delta}{n}$ [0,1], as close to 1 as possible
        • Trade-off between the rate and the distance of a code
    • Linear code
      • Any linear combination of codewords is also a codeword
        • Encoding can always be represented as vector-matrix multiplication between 𝑚 and the generator matrix
        • Minimum distance is the same as the codeword with the least number of non-zeros (weight)
      • Example: Reed-Solomon Code