定义

分类

性质

事物的性质是指该事物和其他事物区分的本质属性,即每个该事物都一定会有相同的性质,但是符合相同性质的不一定是该事物

历史

应用

解决区块链隐私问题

    区块链将所有交易信息都放在了链上,即区块链的共识依靠区块链上的交易,而形成共识需要每个人都将交易下载下来并验证交易是正确的,因此区块链本身并不存在保密性。
    如果使用零知识证明,可以在不泄露交易的情况下让别人验证交易是正确的。具体即是,每个矿工将自己的交易的零知识证明放到链上,而不是将交易直接放到链上。由于零知识证明的性质,如果证明正确则认为交易正确。

解决区块链可扩展性问题

比特币的验证速度是一秒钟五个交易,而在现实中如此长的验证时间,是无法进行交易的,即如果使用比特币完成交易,需要在超市等待很长时间。如果使用零知识证明,可以将交易批量打包,即将一千个交易打包,但是只生成一个证明,这便大大减少了块的大小,增加了验证速度,也使得加密货币从线上走到线下成为了可能。

构建零知识证明

特殊情形

多项式承诺

定义

• 承诺是一个公共值,它与提交者提供的原始信息绑定,提交者不会泄露消息。提交者需要打开此承诺并将消息发送到验证者,以验证承诺与消息之间的关系。
  例如：PC可以被视为对某个多项式P的承诺,提交者可以证明多项式的值满足P(z)=a,而不会揭示多项式P。（个人理解,有一个多项式P,使用承诺可以在不泄露P的具体情况下,证明P(z)=a）
• 多项式承诺是一种最直观的零知识证明情形。

多项式点值承诺

如果公布多项式,则代表信息已经泄露,如何在不泄露具体信息的情况下,证明f®的值确实等于c呢？看起来确实无解。

实用多项式点值承诺

存在的问题

  证明者可能并不知道他所宣称的p(x),他可以先算一下t=t(r ),然后选择一个随机值h,由此计算出p=t*h。因为等式是成立的,所以也能通过验证者的校验。 因为证明者知道随机点x=r,他可以构造出一个任意的多项式,这个任意多项式与t®*h®在r处有共同点。

解决方法

• 证明者不可以直接得到验证者查询的随机数
• 必须约束这个多项式阶数在一定范围内

多项式批承诺

多项式承诺的零知识证明

• PLONK
• 交互式证明
• DARK
• Stark（low degree cost）

前置知识

• 质数和模运算
• 拉格朗日插值
• 群
• 域
• 生成元
    通过对生成元的操作,可以遍历整个群,即将有限域里面的所有数写成指数形式。
• 双线性映射（Bilinear map）
    在数论中,一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素之函数,并且该函数对每个参数都是线性的。例如矩阵乘法

性质：设V,W和X是在同一个基础域F上的三个向量空间。双线性映射是函数。
B:VxW->X // 这是一个映射关系
使得对于任何W中w,映射v->B(v,w)是从V到X的线性映射,
并且对于任何V中的v,映射w->B(v,w)是从W到X的线性映射。
换句话说,如果保持双线性映射的第一个参数固定,并留下第二个参数可变,结果的是线性算子,如果保持第二个参数固定也是类似的。即保持一个参数不变,则另一个参数和结果呈线性关系。
从这里看出,双线性映射即是线性映射的升维,由此也可以推算出三线性映射,及多线性映射的定义。

KZG

  KZG多项式承诺是Kate, Zaverucha 和 Goldberg 等人在 2010 年发表的 Polynomial Commitments 论文提出的对多项式进行承诺的一种方案. 目前而言, 区块链上许多项目准备使用 KZG 多项式承诺解决一些特定问题, 例如 EIP-4844 以及零知识证明相关项目.
论文点击此处
Univariate polynomial commitment 单变量多项式承诺

可信设置

  在使用KZG多项式承诺之前, 需要先进行可信设置(Trust setup). 在这个步骤中, 首先生成无人知晓的s,s∈Fr,并计算sⁱ⋅G₁和sⁱ⋅G₂,i=1,…,随后销毁s.

• s为无人知晓的私钥,在计算出 sⁱ⋅G₁和sⁱ⋅G₂之后立即销毁
• sⁱ⋅G₁ 和 sⁱ⋅G₂ 公开, 每个人都知道

卡特承诺

  多项式可以表达为以下结构f(x) = a₀⋅x⁰ + a₁⋅x¹ + a₂⋅x² … + aₙ⋅xⁿ
  因此我们假设该多项式的承诺为C = f(s)⋅G₁ = a₀⋅s⁰⋅G₁ + a₁⋅s¹⋅G₁ + a₂⋅s²⋅G₁ … + aₙ⋅sⁿ⋅G₁
虽然 s 的值无人知晓, 但 sⁱ⋅G₁ 是公开的, 所以我们可以计算出 C. 根据公式可知 C 是椭圆曲线上的一点, 因此 C 的一个重要特征是 C 的大小是固定的, 与多项式的嵌入度无关.

• 公开的参数：p,g
• 密钥：s
• 公钥：$g,g^s,g^(s^2),g^(s^3),...,g^(s^d)$
  1.prover -> commitment g^f(s)
  2.verifier -> evaluation point a
  3.prover -> v=f(a) proof=$g^q(s)$所以证明者还要将零知识的证明方法发给验证者,用以验证。
  

复杂度问题

• 承诺：O(1)
• 证明时间：O(d)
• 证明大小：O(1) ~100 bytes
• 验证：O(1) 0.3ms

一般情形

Generic ZKP

• 将任意的zkp都放到电路上

PLONK

• Plonk circuit to constraint system
  Gate constraint

PLONK工作原理

  PLONK的一个关键要素是,将问题的形式从“给我一个值x,我给你一个特定的程序p,这样当x作为输入进行计算的时候,我给你一些具体的结果Y”变成了“给我一组值”,这个就和zk-snark中的QAP一样。（从这里看是从给一个值扩展到了给一组值）
程序P可以是很多东西,例如可以是“给我这个数独的解决办法”,这个程序你可以通过设置P为一个数独验证再加上一些初始值来进行编码并且设置Y的值为1,并且输入X的值,这样就是一个有效的数独解决办法了。
这种方式把P视为一个带有加法和乘法的逻辑门电路,并且把该电路转换成一个方程组,其中变量是所有导线上的值,每一个门都有一个方程。
例如：下面是方程组$P(x)=x^3+x+5$的逻辑电路图。

我们可以将电路的线和门标记出来,如下图所示：

在电路图中我们可以发现,我们有两种类型的约束,一种是门约束（在同一个门上的方程如a1*b1=c1）,一种是复制约束（关于电路不同地方的线相等的说法,如a0=a1=b1=b2=b3或者c0=a1）
我们可以通过这个创建一个方程组,并最终简化为一个多项式方程来表示这个电路。

$$\begin{aligned} \left(Q_{L_{i}}\right) a_{i}+\left(Q_{R_{i}}\right) b_{i}+\left(Q_{O_{i}}\right) c_{i}+\left(Q_{M_{i}}\right) a_{i} b_{i}+Q_{C_{i}}=0 \end{aligned}$$

其中$Q_{L_{i}}=1,Q_{R_{i}}=1, Q_{M_{i}}=0, Q_{O_{i}}=-1, Q_{C_{i}}=0$
从上面可以看出,一条线的每一端,以及一组线中的每条线显然必须有相同的值,且对应着一个不同的变量；到目前为止,没有任何东西能强迫一个门的输出与另一个门的输入相同。（我们称之为“复制约束”）。
当然,PLONK有一种复制约束的办法,这个留待之后讨论。现在面临一个问题,验证者想证明满足所有$x_{a_i}, x_{b_i}$和$x_{c_i}$的值的方程,是很难的事情。这仍然是一个大问题,但这个与“为这个程序找到一个满意的输入”不同,它是一个结构化的大问题,因此我们可以使用数学工具进行压缩。

线性系统到多项式

多项式作为一个数学工具,将大量的数据封装成为了一个整体。通常,我们会将多项式用系数形式进行表达。如：$y=x^3-5x^2+7x-2$
但是我们可以把多项式用“表格形式”来表达。例如,我们可以把上面的多项式是度小于4的表格(-2,1,0,1)在坐标(0,1,2,3)的结合。

接下来,相同形式的许多方程组可以重新解释为多项式上的单个方程。例如,假如我们有方程组：

$$\begin{aligned} \begin{array}{l}{2 x_{1}-x_{2}+3 x_{3}=8} \\ {x_{1}+4 x_{2}-5 x_{3}=5} \\ {8 x_{1}-x_{2}-x_{3}=-2}\end{array} \end{aligned}$$

让我们以求值形式定义四个多项式：L( x )是度数小于3的多项式,其在坐标（0,1,2)处的计算结果为(2,1,8),并在该坐标处M(x)处的计算结果是(-1,4,-1),R(x)的结果是(3,5,-1)且O(x)的结果是（8,5,-2）（可以以这种方式直接定义多项式是;可以使用拉格朗日插值转换为系数形式）。现在,考虑以下等式：

$$\begin{aligned} L(x) \cdot x_{1}+M(x) \cdot x_{2}+R(x) \cdot x_{3}-O(x)=Z(x) H(x) \end{aligned}$$

在这个等式中,L(x)简单表示为(x-0)(x-1)(x-2)的最小（非琐碎）多项式,该多项式计算域(0,1,2)并返回0。该等式的一个解($x_1=1,x_2=6,x_3=4,H(x)=0$)也是原方程组的解,除非原方程组并不需要H(x)。在这种情况下,$H(X)$为0,但是在更复杂情况下,H的值不为0
所以现在我们知道,我们可以在少量的数学对象（多项式）中表示大量的约束。但是在我们上面做的表示门线约束的方程中,$x_1,x_2,x_3$变量在每个方程中都是不同的。同样的,我们可以通过使变量本身成为多项式而不是常数的方式来处理这个问题。这样我们得到了：

$$\begin{aligned} Q_{L}(x) a(x)+Q_{R}(x) b(x)+Q_{O}(x) c(x)+Q_{M}(x) a(x) b(x)+Q_{C}(x)=0 \end{aligned}$$

和上面一样,每一个Q多项式是一个参数,该参数可以从被验证的程序中生成,并且a,b,c多项式由用户来提供输入。

复制约束

现在,让我们回到 "连接 "电线的问题上。到目前为止,我们所拥有的只是一堆关于不相干的值的不相干方程,这些方程独立地容易满足：常数门可以通过将值设置为常数来满足,加法和乘法门可以简单地通过将所有导线设置为零来满足!为了使问题真正具有挑战性（实际上代表了原始电路中编码的问题）,我们需要添加一个方程来验证 “复制约束”：例如
a(5)=c(7),c(10)=c(12)等等。这需要一些巧妙的技巧。
我们的策略是设计一个“坐标对累积器”,该多项式p(x)的工作原理如下。首先,让X(x)和Y(x)成为两个代表x和y点数值对的多项式（例如(0,-2),(1,1),(2,0),(3,1),你可以能设置X(X)=x,$Y(x)=x^3-5x^2+7x-2$）.
我们的目标是让p(x)可以表示所有给出的点,因此p(0)从1开始,p(1)代表第一个点,P(2)代表第二个,等等。我们随机选择两个常量$v_1,v_2$,并且使用约束p(0)=1和$p(x+1)=p(x)(v_1+X(x)+v_2Y(x))$在域(0,1,2,3)上构建$p(x)$。
例如,让$v_1=3$且$v_2=2$,我们可以得到

  我们发现p(4)=-240.现在考虑用X(x)=x来进行替代,我们设$X(x)=\frac{2}{3}x^3-4x^2+\frac{19}{3}x$（这样多项式在(0,1,2,3)的值是(0,3,2,1)）如果你运行同样的程序,你会发现你也能得到p(4)=-240。这并不是一个巧合（实际上,如果你从特别大的域里面随机选择$v_1$和$v_2$,它也不会发生这样的巧合）
但是,因为Y(1)=Y(3),所以如果你交换X的值（1,1）和(3,1),你并不会该改变点集,且因为累加器编码了一个集合（因为乘法并不关心顺序）,所以最后的值回事一样的。
现在我们可以看到我们将用于证明复制约束的基本技术。首先考虑一个简单情况,即我们只证明一组线内的复制约束（例,我们想证明a(1)=a(3)）我们可以做两个坐标累加器：一个是X(x)=x和Y(x)=a(x),以及Y(x)=a(x)但是X’(x)是计算为转换（或以其他方式重新排列）每个复制约束中的值的排列的多项式；
在a(1)=a(3)时,这意味着排列组合可能以03214开始…第一个累加器可以压缩为((0,a(0)),(1,(a(1))),(2,a(2)),(3,a(3)),(4,a(4)))…第二个累加器可以压缩为((0,a(0)),(1,(a(1))),(2,a(2)),(3,a(3)),(4,a(4)))…两者能够得到相同结果的唯一方法是a(1)=a(3)
为了证明a,b,c之间的约束,我们使用同样的程序,但是将所有三个多项式中的点“累积"在一起。我们设定每个a,b,c的值一个X的坐标值(例,a由$X_a(x)=x$确定,$,b$由$X_b(x)=n+x$确定,$c$由$X_c(x)=2n+x$确定.)为了证明在不同线组之间跳跃的复制约束,被替代的X坐标被分为三个集合之间的排列组合. 例如,如果我们想证明n=5时,a(2)=b(4),那么$X'_a(x)$的值为{0,1,9,3,4}且X’_b(x)的值为{5,6,7,8,2}。总有,X’_a(x),X’_b(x),X’_c(x)也被称为$\sigma_a(x)$,$\sigma_b(x)$和$\sigma_c(x)$。
那么,我们将在程序的一次运行中代替检查平等性（如,检查之前的p(4)=p’(4),我们将检查每一侧的三个不同运行的乘积：

$$\begin{aligned} p_{a}(n) \cdot p_{b}(n) \cdot p_{c}(n)=p_{a}^{\prime}(n) \cdot p_{b}^{\prime}(n) \cdot p_{c}^{\prime}(n) \end{aligned}$$

三者的乘积p(n)每侧的评估累积了a,b,c在每侧一起运行,因此这允许我们执行与以前相同的检查,除了我们现在不仅可以检查三组导线之一内的位置之间的复制约束a,b,c,也可以在一组线和另一组之间检查。
这就是复制约束的全部内容了！

整合所有后

实际上,所有这些数学运算不是在整数上完成的,而是在素数域完成的；在”模块化数学插曲“一节,了解什么是素数域。另外,出于数学上的原因,阅读和理解这篇关于FFT实现的文章,我们将使用$\omega$在$\omega: 1, \omega, \omega ^2....\omega ^{n-1}$领域,而不是用以下方式来表示导线指数。这不会改变数学,只是坐标对累加器约束检查方程从
$p(x + 1) = p(x) \cdot (v_1 + X(x) + v_2 \cdot Y(x))$转变成 $p(\omega \cdot x) = p(x) \cdot (v_1 + X(x) + v_2 \cdot Y(x))$而不是使用$0..n-1$,$n...2n-1$,$2n..3n-1$作为坐标对,我们使用g是领域中一些随机的高阶元素时的\omega ^,$g \cdot \omega ^2$和$g^2\omega ^2$
$emsp;$emsp;现在让我们写下我们需要检查的所有等式。首先时主要的门电路满足度检查：

$$\begin{aligned} Q_{L}(x) a(x)+Q_{R}(x) b(x)+Q_{O}(x) c(x)+Q_{M}(x) a(x) b(x)+Q_{C}(x)=0 \end{aligned}$$

然后是多项式累加器转换电路（提示：认为"== Z(x) \cdot H(x)"的意思是”对于我们关心的某个特定域内的所有坐标等于零,但是不一定在它之外”）：

$$\begin{aligned} \begin{array}{l}{P_{a}(\omega x)-P_{a}(x)\left(v_{1}+x+v_{2} a(x)\right) =Z(x) H_{1}(x)} \\ {P_{a^{\prime}}(\omega x)-P_{a^{\prime}}(x)\left(v_{1}+\sigma_{a}(x)+v_{2} a(x)\right)=Z(x) H_{2}(x)} \\ {P_{b}(\omega x)-P_{b}(x)\left(v_{1}+g x+v_{2} b(x)\right)=Z(x) H_{3}(x)} \\ {P_{b^{\prime}}(\omega x)-P_{b^{\prime}}(x)\left(v_{1}+\sigma_{b}(x)+v_{2} b(x)\right)=Z(x) H_{4}(x)} \\ {P_{c}(\omega x)-P_{c}(x)\left(v_{1}+g^{2} x+v_{2} c(x)\right)=Z(x) H_{5}(x)} \\ {P_{c^{\prime}}(\omega x)-P_{c^{\prime}}(x)\left(v_{1}+\sigma_{c}(x)+v_{2} c(x)\right)=Z(x) H_{6}(x)}\end{array} \end{aligned}$$

接下来时多项式累加器开始和结束约束：

$$\begin{aligned} \begin{array}{l}{P_{a}(1)=P_{b}(1)=P_{c}(1)=P_{a^{\prime}}(1)=P_{b^{\prime}}(1)=P_{c^{\prime}}(1)=1} \\ {P_{a}\left(\omega^{n}\right) P_{b}\left(\omega^{n}\right) P_{c}\left(\omega^{n}\right)=P_{a^{\prime}}\left(\omega^{n}\right) P_{b^{\prime}}\left(\omega^{n}\right) P_{c^{\prime}}\left(\omega^{n}\right)}\end{array} \end{aligned}$$

用户提供的多项式是：

• 线分配为$a(x),b(x),c(x)$
• 坐标对累加器$P_a(x), P_b(x), P_c(x), P_{a'}(x), P_{b'}(x), P_{c'}(x)$
• 商$H(x)$和$H_1(x)...H_6(x)$
  证明者和验证者首先需要计算的程序指定的多项式是：
• $Q_L(x), Q_R(x), Q_O(x), Q_M(x), Q_C(x)$,这些东西代表了电路中的所有门（$Q_C(x)$加密公共输入,因此它可能需要在运行时加密或修改）
• “排列多项式”$\sigma_a(x), \sigma_b(x)$和$\sigma_c(x)$,加密了a,b,c线中的复制约束

注意：验证者只需要存储这些承诺到多项式中。上面剩余的等式只有$Z(x) = (x - 1) \cdot (x - \omega) \cdot ... \cdot (x - \omega ^{n-1})$,这个等式被设计来计算这些点的零点.幸运的是,$\omega$可以被选择用来使多项式更容易计算：通常是选择$\omega$满足$Z(x) = x^n - 1$时,$\omega ^n=1$
有个细微差别就是：$P_a(\omega^{i+1})$和$P_a(\omega^i)$之间的约束无法阵阵的通过完整的w次方循环；它总是会在$\omega ^n-1$显示错误,因为下一个坐标是$\omega ^n=1$时,我们又回到了累加器的起点；为了解决这个问题,我们可以修改约束,“如果约束或$x=\omega ^n-1$为真”时,可以使用乘法将$x-\omega ^n-1$约束起来,因此它在那个点的值等于零
唯一的约束$v_1$和$v_2$选择之后,用户无法再选择$a(x),b(x)$和c(x),因此我们可以通过从承诺的哈希值来计算$v_1$和$v_2$给$a(x),b(x)$和$c(x)$
所以现在我们已经把程序满足问题变成了用多项式满足几个方程的简单问题,而这些就是对PLONK的优化,这可以让我们删除上述方程中的许多多项式,保持简单。但是多项式本身,包括程序特定的参数和用户的输入,都是很大的。因此,下一个问题是,我们如何绕过这个问题,使证明变得简短？

多项式承诺

多项式承诺已经单独讲过,如有补充将会在那里写。这里就不写了

回顾

最后,让我们再次回顾以下该计划。给定一个程序P,将其转换为电路,并生成一组如下所示的方程：

$$\begin{aligned} \left(Q_{L_{i}}\right) a_{i}+\left(Q_{R_{i}}\right) b_{i}+\left(Q_{O_{i}}\right) c_{i}+\left(Q_{M_{i}}\right) a_{i} b_{i}+Q_{C_{i}}=0 \end{aligned}$$

然后将这组方程转换为单个多项式方程：

$$\begin{aligned} Q_{L}(x) a(x)+Q_{R}(x) b(x)+Q_{O}(x) c(x)+Q_{M}(x) a(x) b(x)+Q_{C}(x)=0 \end{aligned}$$

你还可以从线路生成复制约束列表。根据这些复制约束,可以生成表示排列导线索引的三个多项式： $\sigma_a(x), \sigma_b(x), \sigma_c(x)$.要生成证明,你需要计算所有导线的值并将他们转换为三个多项式:$a(x), b(x), c(x)$.你还可以计算六个“坐标对累加器”多项式作为排列检查参数的一部分。最后计算辅因子$H_i(x)$
多项式之间有一组方程需要检查;您可以通过对多项式做出承诺来做到这一点,随机打开它们z（以及开口正确的证明）,并在这些评估上运行方程而不是原始多项式。证明本身只是一些承诺和开放,可以用几个方程式来检查。仅此而已！

$$\begin{aligned} Q_{L}(x) a(x)+Q_{R}(x) b(x)+Q_{O}(x) c(x)+Q_{M}(x) a(x) b(x)+Q_{C}(x)=0 \end{aligned}$$

热门协议

zk-SNARKs

也许过去十年中最强大的加密技术是通用简洁零知识证明,通常称为zk-SNARKs（“知识的零知识简洁论证”）。zk-SNARK 允许您生成证明某些计算具有某些特定输出的证明,这样即使底层计算需要很长时间才能运行,也可以非常快速地验证证明。“ZK”（“零知识”）部分增加了一个额外的功能：证明可以隐藏计算的一些输入。
例如,您可以为语句“我知道一个秘密数字”进行证明,这样,如果您采用单词’cow’,将数字添加到末尾,并且 SHA256 对其进行 100 亿次哈希处理,则输出以“开头。验证者可以比他们自己运行100亿个哈希更快地验证证明,而且证明也不会透露秘密数字是什么。0x57d00485aa
在区块链的背景下,有两个非常强大的应用程序：
1.可扩展性：如果一个区块链需要长时间来验证,一个人可以验证它并生成证明,而其他人可以快速验证证明
2.隐私：您可以证明您有权转移某些财产,而无需透漏您收到的资产的链接。这确保了安全性,而不会向公众过度泄漏有关谁与谁在进行交易的信息。

但是zk-SNARK非常复杂；事实上,直到2014-2017年,它们仍然被称为“月球数学”。好消息是,从那时起,协议变的简单,我们对它们的理解也变得更好。这篇文章将尝试解释zk-SNARKs是如何工作的。

zk-SNARKs应该很难

让我们以开始的例子为例：我们有一个数字（我们可以将“cow”编码为整数,后跟秘密输入）,我们采用该数字的SHA256哈希,然后我们再做99999999次,我们得到输出,然后我们验证它开头的数字是什么。这是一个非常大的计算。
一个“简洁的”证明就是从证明的大小和时间上,都要求验证它所需的时间比验证的计算慢得多。如果我们想要一个“简洁”的证明,我们不能要求验证者在每一轮哈希中做一些工作。相反,验证者必须以某种方式检查整个计算,而不是柜式计算的每个单独部分。
一种自然的技术是随机抽样：我们让验证其验证500个不同位置的计算,检查这些部分是否正确,如果所有的计算都是正确的,则假设剩下的所有计算以很高的概率正确。
这样的程序甚至可以使用Fiat-Shamir变换变成非交互式证明：证明这计算一个算式的默克尔根,使用默克尔根伪随机选择500个索引,并提供数据的500个相应的默克尔分支。关键思想是,证明者在他们已经“提交”数据之前不知道他们需要揭示哪些分支。如果恶意证明者知道要检查哪些索引后识图伪造数据,这将改变默克尔根,也将导致一组新的随机索引,而这又需要再次伪造数据…这样的话,恶意证明者就会被困在无休止的循环中。
不幸的是,简单的应用随机抽样的方式来进行抽查计算存在一个致命缺陷：计算本质上市脆弱的。如果恶意证明者在计算过程中的某个地方反转了一点。它们可以使其给出完全不同的结果,而随机抽样验证者几乎永远不会发现。

多项式

多项式是以下形式的一类特殊的代数表达式：

• $x+5$
• $x^4$
• $x^3 + 3x^2 + 3x + 1$
• $628x^{271} + 318x^{270} + 530x^{269} + ... + 69x + 381$

即他们是形式上任何（有限）项数的总和$cx^k$.多项式有很多令人着迷的地方.但在这里,我们将放大一个特定的对象：多项式是一个单一的数学对象,可以包含无限量的信息（将他们视为整数列表,这是显而易见的）。上面的第四个式子包含816位tau,并且人们可以很容易地想象一个多项式包含更多的信息。
此外,多项式之间的单个方程可以表示数字之间的无限放成熟。例如,考虑等式$A(x) + B(x) = C(x)$如果这个等式为真,那么下列狮子也是正确的：

• $A(0) + B(0) = C(0)$
• $A(1) + B(1) = C(1)$
• $A(2) + B(2) = C(2)$

以此类推,对于每个可能的最表,您甚至可以构造多项式来故意表示数学及,以便可以一次检查多个方程。例如,假设你要检查：

• $12+1=13$
• $10+8=18$
• $15+8=23$
• $15+13=28$

您可以使用拉格朗日插值的过程来构造多项式A(x)在某些特定的坐标集（例如,（10,10,15,15）（0,1,2,3）B(x)以此类推,事实上,这里是多项式：(1,8,8,13)

• $A(x) = -2x^3 + \frac{19}{2}x^2 - \frac{19}{2}x + 12$
• $B(x) = 2x^3 - \frac{19}{2}x^2 + \frac{29}{2}x + 1$
• $C(x) = 5x + 13$

检查等式$A(x) + B(x) = C(x)$使用这些多项式检查上卖弄的所有方程。

将多项式与自身进行比较

您甚至可以使用简单的多项式方程检查同意多项式的大量相邻等式之间的关系。这稍微先进一些,假设您要检查给定的多项式F,$F(x+2) = F(x) + F(x+1)$也在整数范围之内{0,1,…98}（所以如果你也检查F(0)=F(1)=1,并且F(100)将是第100个斐波那契数）

作为多项式,$F(x+2) - F(x+1) - F(x)$不会完全为零,因为它可以给出范围之外的任意答案x={0,1,…98}.但我们可以做一些聪明的事情。一般来说,有一个规则,如果多项式P在集合$S=\{x_1, x_2 ... x_n\}$中为零,那么它可以被解释为在$Z(x) =(x - x_1) * (x - x_2) * ... * (x - x_n)$且H(x)也是一个多项式时,$P(x) = Z(x) * H(x)$。另一方面,任何在某个集合中等于零多项式都是在同一集合中等于零的最简单（最低次）多项式的倍数

为什么会这样呢？这是多项式长除法的一个很好的推论：因子定理。我们知道,当$P(x)$被$Z(x)$整除时,我们可以得到一个满足$P(x) = Z(x) * Q(x) + R(x)$的商Q(x)和余数R(x).因为我们知道P在所有的S中都是0,也就是说R也在所有的S中都是0。因此我们可以简单地通过多项式插值计算R(x),因为它是最高次数为n-1且我们已知n的值的多项式.因此R(x)=0且H(x)=Q(x)。

回到我们的例子,如果我们有一个多项式F编码斐波那契数（所以F(x+2)=F(x)+F(x+1)且x={0,1,…98}）,那么我可以说服你F实际上通过证明多项式满足此条件,即P(x)=F(x+2)-F(x+1)-F(x)在该范围内为0,在$Z(x) = (x - 0) * (x - 1) * ... * (x - 98)$时,商$H(x) = \frac{F(x+2) - F(x+1) - F(x)}{Z(x)}$.你可以计算Z(x),检查方程,如果检查通过,那么F(x)满足条件！

现在,回顾一下,注意我们醉了什么。我们将一个100步长的计算（计算第100个斐波那契数）转换为具有多项式的单个方程。当然,证明第N个斐波那契数并不是一项特别有用的人物,特别是因为斐波那契数具有封闭形式。但是你可以使用完全相同的基本技术,只是使用一些额外的多项式和一些更复杂的方程,用任意大步数对任意计算进行编码。

现在,如果只有一种方法可以用多项式验证方程,这比检查每个系数要快得多…

多项式承诺

多项式承诺最好被当成是“散列”一个多项式的特殊方式,其中散列具有附加属性,你可以通过检查多项式之间的方程式来检查多项式之间的方程。不同的多项式承诺方案在可以检查的方程类型方面具有不同的属性。
以下是你可以使用各种多项式方案执行的一些常见示例（我们可以使用com(P)来指代“多项式P的承诺”）：

• 加法 给定一个com(P),com(Q)和com®,检查P+Q=R是否成立
• 乘法 给定一个com(P),com(Q)和com®,检查P*Q=R是否成立
• 计算点值 给定一个com(P),w,z和一个补充证明(或者“证人”)Q,验证P(w)=z

值得注意的是,这些基元可以互相构建。如果你可以使用加法和乘法,那么你可以计算点值：证明P(w)=z,你可以构建$Q(x) = \frac{P(x) - z}{x - w}$,并且验证器可以验证$Q(x) * (x - w) + z \stackrel{?}{=} P(x)$是否成立。因为如果这样的多项式Q(x)存在,那么$P(x) - z = Q(x) * (x - w)$,成立,这意味着P(x)-z在w上等于0,且P(x)在w上等于z。
如果你可以计算点值的话,你可以进行所有类型的检查。这是因为有个数学理论近似提到的,如果涉及某些多项式的某个方程在随机选择的坐标上成立,；那么它几乎肯定适用于整个多项式。因此,如果我们所拥有的只是计算点值的机制,我们可以检查我们的$P(x + 2) - P(x + 1) - P(x) = Z(x) * H(x)$,在使用如下交互式游戏的情况下：

正如之前提到的,我们可以使用Fiat-Shamir变换将这个方法变成非交互式的：证明者可以通过设置（该设置为任意哈希加密函数,不需要任何特殊设置）来计算它们本身。证明者无法通过选择“适合”的地方而不是另一个地方来进行“欺骗”,因为它们不知道那时候它们选择的是什么,并且$!rr = hash(com(P), com(H))hashPHrrPH$

快速回顾

• zk-SNARKs很难,因为验证者需要以某种方式检查计算中的数百万步,而不需要做一些工作来直接检查每个单独的步骤（因为这会花费太长时间）.
• 我们通过将计算编码为多项式来解决这个问题
• 单个多项式可以包含无限大量的信息,并且单个多项式（例如 P(x+2) - P(x+1) - P(x) = Z(x) * H(x)）可以"代替"数字之间无限数量的方程.
• 如果可以用多项式验证方程,则可以隐式验证所有数字方程（使用任意x坐标来代替x）
• 我们使用多项式的一种特殊类型的"哈希",称为多项式承诺,这可以使我们在很短的时间内实际验证多项式之间的方程,即使底层多项式非常大。

多项式哈希工作原理

目前广泛使用的三种主要方案是：bulletproofs, Kate and FRI.
下面是Dankrad Feist的Kate承诺的介绍：https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
下面是curve25519-dalek团队的bulletproofs的介绍：https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html
下面是关于FRI的介绍：https://vitalik.ca/general/2017/11/22/starks_part_2.html

FRI工作方式

最容易理解的是FRI,以下是FRI简化版本的工作方式（为了简单起见,真正的协议有许多技巧和优化,这里缺少这些技巧和优化）。假设你有一个degree<n的多项式P,承诺P是一组点值的集合在预先选择的坐标处的默克尔根。现在,我们需要添加一些额外的东西来证明这组点值实际上是一个degree<n的多项式。

使得Q是包含偶数系数的多项式,P和R是仅包含奇系数的多项式P。如果$P(x) = x^4 + 4x^3 + 6x^2 + 4x + 1$且$Q(x) = x^2 + 6x + 1$和$R(x) = 4x + 4$（注意,系数的范围被缩小到[0…n/2]）

注意$P(x) = Q(x^2) + x * R(x^2)$

我们伪随机抽样一大组索引,并要求证明者在这些指数提供默克尔分支P,Q,R和S。对于每一个提供的坐标,我们可以检查：

• P(x)实际上等于$Q(x^2) + x * R(x^2)$
• S(x)实际上等于$Q(x) + r * R(x)$

如果我们做了足够的验证,那么我们可以确信S(x)与"提供的"值不同,最多1%的情况.

注意Q和R两者的degree<n/2。因为S是拥有degree<n/2的Q和R,S的线性组合.反过来说：如果我们能证明S有degree<n/2,则它是随机选择的组合这一事实阻止了证明者选择恶意Q和R带有"抵消"的隐藏degree系数,因此Q和R必须都是degree<n/2,因为$P(x) = Q(x^2) + x * R(x^2)$,我们知道P必须有degree<n
从这里开始,我们只需重复游戏S,逐渐将我们关心的多项式“还原”到越来越低的次数,直到它处于足够低的次数,我们可以直接检查它。

和前面的示例一样,这里的“Bob”是一个抽象概念,对于密码学家在理论上推理协议很有用。实际上,Alice生成证明,为了防止她作弊,我们使用Fiat-Shamir：我们根据证明中生成的数据的哈希值选择每个随机样本坐标或值。
一个完整的“FRI”承诺P（在简单协议中）由以下组成：

1.默克尔树根点P
2.默克尔树根点Q,R,$S_1$
3.是随机选择的分支P,Q,R,$S_1$要检查$S_1$正确地减少自P
4.默克尔根和随机选择的分支,如步骤(2)和(3)中用于连续降低度数的还原$S_2$从$S_1,S_3$到$S_2$,所有的降低到低的读书$S_k$（总共可以重复$log_2 n$次）
5.全部的默克尔树的点$S_k$

该过程中的每个步骤都可能引入一些“错误”,但是如果你添加足够的验证,那么总错误将足够低,你至少可以证明P(x)和degree<n的多项式相等,或者说,80%相等。而这对于我们的用力来说已经够了。如果你想在zk-SNARKs中欺诈,你需要对分数表达式做出承诺（例如,"证明"错误的说法$x^2 + 2x + 3$在x=4时结果为5,你需要为$\frac{x^2 + 2x + 3 - 5}{x - 4} = x + 6 + \frac{22}{x - 4}$提供一个多项式承诺).这种分数表达式的结果集将与任何实际的degree<n的结果不同,任何试图对它们做出FRI承诺的尝试都会在某个步骤失败。
此外,您可以检查FRI承诺中对象的总和和大小是否在次数上是对数的,因此对于大多项式,承诺实际上比多项式本身小得多。
检查这种类型的不同多项式承诺之间的方程（例如 检查给定的FRI承诺$A(x) + B(x) = C(x)$中的A,B,C）,只需随机选择许多索引,向证明者询问每个多项式的每个索引处的默克尔分支,并验证方程在每个位置是否确实成立。
上面描述的是一个效率非常低的协议；如果你想要一个实际可行的协议,有一大堆代数技巧可以将其效率提升一百倍,比如说,在区块链交易中使用你需要这些技巧。特别是,例如,Q和R实际上不是必须的,因为如果你非常聪明地选择点集,你需要直接从点击中获取P,重建点击Q和R。但是上面的描述应该足以让你相信多项式承诺从根本上是有可能的。

有限域

从上面的描述中,有一个隐藏的假设：多项式每个单独“点集”都很小。但是当我们处理大的多项式时,这显然时不正确的。如果我们以上面的自立为例,$628x^{271} + 318x^{270} + 530x^{269} + ... + 69x + 381$对tau的816位数字进行编码,并在x=1000,你得到一个816位数字,包含所有这些tau数字.因此,我们还需要补充一件事。在实际实现中,我们在这里所做的所有算数都不会使用实数上的"常规"算数来完成。相反地,它将使用取模算术来完成。我们重新定义所有算术运算,如下所述。我们选择一些素数进行取模。%运算符表示“取剩余部分”：15%7=1,53%10=3等（注意结果总是非负的,例如-1%10=9）.我们重新定义

$$x + y \Rightarrow (x + y)$$

$$x * y \Rightarrow (x * y)$$

$$x^y \Rightarrow (x^y)$$

$$x - y \Rightarrow (x - y)$$

$$x / y \Rightarrow (x * y ^{p-2})$$

以上规则都是自洽的。例如,如果p=7,则

5 + 3 = 1($$作为$$8%7=1)

1 - 3 = 5($$作为$$-2%7=5)

$$2 \cdot 5 = 3$$

3 / 5 = 2$$（如$$(3 \cdot 5^5)%7=9375%7=2）

更复杂的身份,如分配法,也可以认为:$(2+4)\cdot 3$和$2 \cdot 3 + 4 \cdot 3$两者的结果为4.甚至像这样的公式($a^2-b^2=(a-b)(a+b)$)在这种新的算术中仍然适用。

除法是最难的部分,我们不能使用正则出发,因为我们希望值始终保持整数,而正则除法通常给出非整数结果。我们使用费马小定理来解决这个问题,该定理指出,对于任何非零x<p,费马小定理有$x^{p-1}$。这意味着给出一个数字$x^{p-2}$,如果x被乘以多次,给一个1,则我们可以说$x^{p-2}$等于$frac{1}{x}$.一个复杂但快速的计算模除操作的方法是扩展的欧几里得算法。

通过模运算数学,我们创建了一个全新的算术系统,它的自洽性与传统算术的自洽性相同。因此,我们可以讨论这个领域的所有相同类型的结果,包括多项式,我们在"常规数学"中谈论。密码学家喜欢在模数学中工作,因为任何模运算数学计算都可能存在数字大小限制-无论你做什么,这些值都不会"逃脱"集合{0,1,2…p-1}。即使在有限域中计算1万多次多项式也永远不会给出该集合之外的答案。

例子

将计算转换为一组多项式方程的稍微有用的例子是什么

假设我们想证明这一点,对于某些多项式P,$0 \le P(n) < 2^{64}$。而不透露具体的值P(n).这是区块链交易中的一个常见用力,你希望证明交易在不显示余额的情况下保持非负数。
我们可以用以下多项式方程来构造一个证明（为简单起见,假设n=64）

• P(0)=0
• P(x+1) = P(x)*2+R(x) 范围为{0…63}
• $R(x) \in \{0,1\}$ 范围为{0…63}

后两个陈述可以重述为“纯”多项式方程,如下所示（在这种情况下）$Z(x) = (x - 0) * (x - 1) * ... * (x - 63)$:

• $$P(x+1) - P(x) * 2 - R(x) = Z(x) * H_1(x)$$

• R(x) * (1 - R(x)) = Z(x) * H_2(x)$$（注意 当且仅当$y \in \{0, 1\}$时,$y * (1-y) = 0$）

这个想法是从P(i)连续点逐位建立数字：如果$P(4) = 13$,那么到那时为止的计算顺序将是：{0,1,3,6,13}。在二进制中,1是1,3是11,6是110,13是1101；注意 1 11 110 1101 $P(x+1) = P(x) * 2 + R(x)$只要在最后不断加一位,只要R(x)为0或1.$0 \le x < 2^{64}$范围内的任何数字可以通过这种方式建立超过64个步骤,超出该范围的任何数字都不能。

隐私

但是有一个问题：我们怎么知道承诺P(x)和R(x)不会泄露信息,使我们能够发现我们试图隐藏的P(64)的具体值
有一些好消息：这些证明是可以对大量数据和计算做出声明的小证明。因此通常来说,证明总是不足以泄露一点信息但是我们可以从“仅一比特”到“0”吗？幸运的是,我们可以。
一个相当普遍的技巧是在多项式中添加一个"软糖因子"。当我们选择P,添加Z(x)进入多项式（即对于任意的E(x)的集合$P'(x) = P(x) + Z(x) * E(x)$）.这并不影响陈述的正确性（事实上,P’计算值与P在"计算发生"的坐标上,所以它仍然是一个有效的副本）,但是它可以在承诺中添加足够的额外“噪音”,使任何剩余的信息无法恢复。此外,在FRI情况中,重要的是不要对计算发生域内的随机点进行采样（在本例中,域为{0…64}）

再回顾

• 三种最突出的承诺类型是FRI、Kate和bulletproof
• Kate在概念上是最简单的,但它取决于椭圆曲线配对的真正复杂度“黑匣子”
• FRI很酷,因为它只依赖于哈希；它的工作原理是连续将多项式简化为低次多项式,并使用默克尔分支进行随机样本检查以证明每一步的等价性。
• 为了防止单个数的大小爆炸,我们不是在整数域上进行算术和多项式,而是在有限域上做所有事情（通常是整数模一些素数p）
• 多项式承诺自然而然地有助于隐私保护,因为证明比多项式小得多,因此多项式承诺无论如何都不能透漏多项式中多一点点信息。但是我们可以为承诺的多项式添加一些随机性,以将泄露的信息从“一点点”减少到“零”

哪些问题仍在研究中？

• 优化FRI：已经有相当多的优化设计及精心选择的域计算、“DEEP-FRI”以及许多其他技巧,以使FRI更高校。Starkware和其他人正在研究这个问题
• 将计算编码为多项式的更好方法：找出将涉及哈希函数、内存访问和其他特征的复杂计算编码为多项式方程的最有效方法仍然使一个挑战。在这方面已经取得了很大进展（例如,PLLOKUP）,但我们仍然需要更多,特别是如果我们想将通用虚拟机执行编码为多项式
• 可增量验证的计算：能够在计算继续进行的同时有效地“扩展”证明,那就太好了。这在“单证明者”案例中很有价值,但在“多证明者”案例中也很有价值,特别是区块链,其中不同的参与者创建每个区块。

Pinoccnio

文章参考

• 零知识证明前传-什么是多项式承诺？
• 零知识证明入门指南： 发展历史、应用和基本原理
• Cryptography/KZG 多项式承诺
• 双线性映射
• PLONK电路理解
• 关于zk-SNARKs如何实现的近似介绍