ZKP MOOC 第 9 课：基于线性 PCP 的 SNARKs

本次讲座由Yupeng Zhang主讲，主题为基于线性概率检查程序（PCP）的SNARKs（简洁非交互式知识论证）。讲座首先回顾了之前讲解的SNARKs的基本概念和构建方法，包括基于多项式承诺和错误纠正码的方案。接着，Zhang详细介绍了线性PCP的构建方法，强调了其在SNARKs早期实现中的重要性。

核心内容概括：

SNARKs的构建：讲座介绍了如何利用线性PCP构建SNARKs，特别是通过二次算术程序（QAP）来实现电路可满足性证明。
线性PCP的优势与劣势：线性PCP构建的SNARKs在实际应用中具有较短的证明大小和快速的验证时间，但也存在需要电路特定的可信设置和较慢的证明时间等缺点。

关键论据与信息：

证明大小与验证时间：例如，Groth 16构建的SNARK证明仅由三个群元素组成，实际大小约为100到200字节，验证时间少于1毫秒。
历史背景：线性PCP的研究始于2007年，最初由Ishai等人提出，随后发展出多种高效的SNARK构建方法。
QAP的构建：通过定义选择多项式（selector polynomials）和主多项式（master polynomial），将电路可满足性问题转化为多项式方程，从而实现SNARK的构建。
安全性与零知识：讲座中还讨论了如何确保恶意证明者无法伪造证明，以及如何通过引入随机化实现零知识证明。

总之，本次讲座深入探讨了基于线性PCP的SNARKs的构建方法、优势与挑战，并为后续的递归SNARKs的讨论奠定了基础。