在zk-SNARKs中，将简单多项式转换为QAP有什么必要？

Question

来自Vitalik Buterin的博客- 二次算术程序:从零到英雄。

在博客中，选择了一个立方方程：x**3 + x + 5 == 35。假定这个方程是一个计算问题。由于zk不能直接应用于任何计算问题，我们最终将其转换为代数电路、R1CS、QAP、线性交互证明和zk。

最后，我们得到t:A.s * B.s — C.s即QAP。它被一个极小多项式z= (x-1)*(x-2)*(x-3)*(x-4)除以得到h即t= h*z => h=t/z。

我的问题是

1. 为什么初始三次多项式被转换成QAP？我们能不能不使用一个有多个实根的方程。最后，我们得到了一个高阶多项式(QAP)除以z。
2. 在得到QAP之后，在计算t/z时，它是如何得到提醒零的？三次方程与QAP的相关性是什么？

我对这个层次的数学还不太了解。虽然我理解所涉及的步骤，但我无法在这些步骤中获得逻辑意义。

Answer 1

在得到QAP之后，在计算t/z时，它是如何得到提醒零的？三次方程与QAP的相互关系是什么？

把门编号为1，2，3，4等，你会认为这个数字是点的x坐标。A矩阵的第一列是[0, 0, 0, 5]^T

每个元素对应于其中一个门。所以，如果你认为这些值是对应的y坐标。

所以你有4分(1,0), (2,0), (3,0), (4,5)。

利用拉格朗日插值，你可以得到通过这四个点的多项式。同样，您也可以找到B & C矩阵的第一列的多项式。

所以你得到你的A_1(x), B_1(x) & C_1(x)多项式&一直到A_6(x), B_6(x), C_6(x)

见证向量为S。

A(x).S + B(x).S = C(x).S

这如Buterin的图表所示

您可以创建一个新的多项式T(x) = A(x).S + B(x).S - C(x).S。

T(x)在x = [1, 2, 3, 4]有4个已知的根。

让Z(x) = (x-1)(x-2)(x-3)(x-4)

利用多项式提醒定理，在常数a的情况下，多项式P(x)除以x−a的余数等于P(a)。所以P(1), P(2), P(3), P(4)都等于0。

因此，当T(x)被每个(x-1), (x-2), (x-3), (x-4)除以时，剩下的就是0。

因此，当T(x)除以Z(x)时，剩余的是0

也就是说，当被除以时，它是完全可除的&没有余数。

为什么初始三次多项式被转换成QAP？我们能不能不使用一个有多个实根的方程。最后，我们得到了一个高阶多项式(QAP)除以z。

在计算机科学中，有两种计算模型--电路和图灵机.电路只需两个运算加法和乘法就可以表达大部分事物，从而降低了ZK证明的复杂性。如果您没有将原始程序夷为平地，也没有使用过电路，那么您还需要powerof操作&在其他计算中需要更多的操作。