ZKP7.1 Polynomial Commitments Based on Error-correcting Codes (Background)

本文主要是介绍ZKP7.1 Polynomial Commitments Based on Error-correcting Codes (Background)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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
      

这篇关于ZKP7.1 Polynomial Commitments Based on Error-correcting Codes (Background)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---