51.线性PCP第二部分QAP

title: 51. 线性 PCP 第二部分 QAP tags: zk computation theory probabilistically checkable proof linear PCP QAP WTF zk 教程第 51 讲：线性 PCP 第二部分 QAP 在上一讲中，我们介绍了构建线性 PCP 的第一步：将计算问题转换为 R1CS。这一讲，我们将介绍如何进一步转换为 QAP，并利用它构造线性 PCP。 QAP 表示 QAP（Quadratic Arithmetic Program，二次算数程序）通过低度拓展将 R1CS 转换为多项式形式，让我们可以高效的验证证明，从而构造线性 PCP。如果你不熟悉低度拓展，可以参考 WTF zk 第 49 讲：PCP 。 1.1 QAP 定义 QAP 的本质就是将 R1CS 中的系数矩阵 $A, B, C$ 的每一列转换为多项式，方便我们验证。它的核心在于以下多项式等式： $$ \left( \sum{i=0}^{n} wi \hat{A{:i}} (x) \right) \cdot \left( \sum{i=0}^{n} wi \h...