Jan's website

零知识证明系统的实现

Contents

本文内容仅供学习交流使用，不可用于生产环境。未经授权，禁止以任何形式转载、复制或用于商业用途。

介绍 #

零知识证明（Zero-Knowledge Proof, ZKP）是一种密码学方法，起源于1980年代中期。随着区块链技术的迅速发展，零知识证明逐渐被广泛应用。例如：Zcash使用它实现交易信息的完全隐私；以太坊通过它实现Layer2层的扩容；在Web3与DeFi领域中，用于验证用户资产、资金证明、DAO治理等场景，提升系统透明度与安全性。

什么是零知识证明？在数字世界里，我可以向你证明我知道一个秘密，使得某个计算是正确的，而不用向你透露这个秘密本身。这个概念可能有些抽象，让我们用以太坊Layer2的方案来举例：链下的一台计算机打包并执行了100,000笔交易，计算出结果，并生成一个简短的证明。这样主链就无需再重新计算一遍，只需要验证这个证明是否成立，如果验证通过就直接使用前面的计算结果。

发展历程 #

在开始之前先来回顾一下关于零知识证明的发展历程，其中关键点已加粗显示，下面在运算演示的时候都会涉及到：

  • 1980s：零知识的概念被提出，并研究出许多NP问题都可以通过零知识证明来证明。（*NP：求解问题可能很难，但验证解很快）
  • 1990s：非交互式零知识证明被提出（ Fiat-Shamir 启发式），将交互式证明转化为非交互式形式，实现了密码学上的身份验证与签名应用。
  • 2000：zk-SNARK 被提出，将计算转换成多项式验证问题。
  • 2007：Groth16 被提出，使零知识证明能真正被应用。
  • 2014：Zcash使用 zk-SNARK 实现交易隐私。
  • 2018至今：以太坊使用zk-Rollup方案扩容，大大降低交易手续费。zk-STARK协议被提出，无需可信设置、基于哈希的抗量子零知识证明。

zk-SNARK #

zero-knowledge Succint Non-interactive ARguments of Knowledge（零知识简洁非交互式知识论证）是零知识证明系统的其中一种方案，也是本篇主要介绍的方案，名称由几个特性组成：

  • zero-knowledge（zk）：零知识，隐藏所需要的秘密
  • Succint（S）：简洁性，证明很短且验证速度快
  • Non-interactive ARguments(NAR)：非交互式的论证

一个容易混淆的概念：怎么定义一个系统是否 零知识？如果verifier（验证者）在不需要prover（证明者）参与的情况下，verifier 能在没有解向量的情况下，用模拟器生成一个与真实证明无法区分的证明，那就说明该系统是零知识的。也就是，verifier可以自己构造数据来跑通，而且构造的数据看起来和prover提供的没什么区别。既然和随意构造的数据都无法区分，那说明prover提供的数据都算不上知识。

SNARK协议其实相当复杂，直到2014年一直被戏称为“月球数学”。实际上整个零知识的证明过程包含了大量的数学知识。以下尝试以一个实际的陈述为示例，一步步了解整个证明和验证过程。

思考的问题 #

现在，让我们先忘掉零知识证明，来思考一个更基础的问题：假如我们要计算斐波那契数列$ F(10000)$，即序列$ [0,1,1,2,3,5…]$，其中每个数等于前两个数的和。有人声称已经把所有值都算好了，我们该如何验证？

最直接的方法是一个一个去检查，但这样需要验证 9999 次（从 $F(2)$ 到 $F(10000)$），效率太低。那么，能否随机抽取 100 个位置来验证呢？由于他无法事先知道我要抽取哪些点，如果抽取的结果都是对的，那其余的值是否就没问题了呢？

答案是否定的。有问题的概率非常大，因为计算者可能只在某些特定位置出错。要保证没问题，抽查的样本需要足够多，抽查 9999 次达到100%。但如果抽查 9999 次，那和一个一个去检查没有区别，又回到了原点。

让我们重新思考：计算者之所以能轻易作弊，是因为每个值都是独立存在的，即使他在第三个位置把 1 改成 0，也不会影响第四个位置 2 的正确性。简单说，就是每个值之间没有强依赖关系，这种没有关联的抽查方式可以称为"样本抽查"。

我们需要找到一种方式，将这些值组成一个强依赖的结构，即使计算者修改了其中一个值，所有值都会随之改变。在这种情况下，即使只抽查一次，也能大概率知道是否有问题。到这里，问题就变成了：怎样将这些一个个的值组合成一个结构，使得验证一次就等于验证了所有的值？

听起来是否有点熟悉？跟数学中某个东西有点像——是的，就是 多项式。

多项式 #

在数学里，多项式（Polynomial）是指由变量和常数，通过加、减、乘、非负整数次幂组合而成的表达式。例如：

f(x)=3x3+2x2−5x+7f(x) = 3x^3 + 2x^2 - 5x + 7

其中 $x$ 是变量，$3$、$2$、$-5$、$7$ 是常数（系数），$x^3$、$x^2$、$x^1$称为多项式的项。

一个关于$x$的多项式方程，实际上封装了无穷多个数值等式。如 $A(x)+B(x)=C(x)$， 假设我们想要验证以下四个等式是否成立：

1+1=22+3=53+5=84+7=11\begin{aligned} 1+1 &= 2 \\ 2+3 &= 5 \\ 3+5 &=8 \\ 4+7 &=11 \end{aligned}

把$A(x)$表示左边输入，$B(x)$表示右边输入，$C(x)$表示输出得到：

A(x)=[1,2,3,4]B(x)=[1,3,5,7]C(x)=[2,5,8,11]\begin{aligned} A(x)&=[1,2,3,4]\\ B(x)&=[1,3,5,7]\\ C(x)&=[2,5,8,11] \end{aligned}

接着，我们选择插值点$0,1,2,3$，并计算分别经过这四个点的三个多项式，因为四个点比较简单，所以直接计算得到：

  • $A(x)$过点$(0,1)，(1,2)，(2,3)，(3,4)$的多项式，$A(x)=x+1$
  • $B(x)$过点$(0,1)，(1,3)，(2,5)，(3,7)$的多项式，$B(x)=2x+1$
  • $C(x)$过点$(0,2)，(1,5)，(2,8)，(3,11)$的多项式，$C(x)=3x+2$

代入$A(x)+B(x)=C(x)$得到：

(x+1)+(2x+1)=3x+2\begin{aligned} (x+1)+(2x+1)=3x+2 \\ \end{aligned}

到此，上面的问题转化为验证这个多项式方程是否成立，就等于验证了上面四个等式。这里的关键在于 Schwartz–Zippel 引理：如果多项式在随机选择的点上评估正确，那么它在所有点上正确的概率极高；反之，如果多项式有错误，随机评估发现错误的概率也极高。因此，我们只需要随机检查一个点，就能以极高的概率判断所有等式是否正确。

多项式的确是零知识证明系统重要组成部分，但我发现上面演示的好像都是数学的公式，假如我需要证明的是一些更偏应用的问题比如"我拥有某个账户的密码，并且我有足够的余额转出去"，又该怎么才能变成多项式的问题呢？这就好比从计算机的世界突然跳到数学的世界，我们需要找到一种类似桥梁的方法把它们连接起来。

阶段1：从电路到多项式 #

算术电路 #

什么是算术电路（Arithmetic Circuit）？ 算术电路就是把一个算术计算（比如多项式、函数、程序中的算术部分）用加法门（+）、乘法门（×）和连线搭成的电路图，它的结构与布尔电路类似。实际上，任何程序都可以经过编译，转化成相应的电路结构（无论是布尔电路还是算术电路），这样我们就能用数学方法对整个计算过程进行分析和验证，所以这一部分的所有事情都是围绕这个点介绍。

下面用一个简单的算术电路图，用于表达加法与乘法的组合，假设我们要计算：$x^2 + x + 5 =11$，可以拆解为：

S1=x×xS2=S1+x11=S2+5\begin{aligned} S1 &= x \times x \\ S2 &= S1 + x \\ 11 &= S2 + 5 \end{aligned}

约束系统 #

下一步，我们通过R1CS（Rank-1 Constraint System，秩一约束系统）来规范表达的形式，它是一种表达计算约束的方法，能够把我们想验证的计算（比如密码正确且余额充足）编译成一组关于未知数的等式约束，每个约束都具有 Rank-1（秩1）的特殊形式，便于后续多项式表示和高效验证。

  • 秩一：表示每个约束只能表达一个乘法门，不能表达更复杂的结构，因为一个最小的乘法门，就可以组合出所有电路，所以上面算术电路图中的加完全可以使用乘法来替换掉。
  • 约束系统：表示描述计算过程的表达方式。如转账计算过程描述为：操作人必须拥有账户的密钥（签名验证通过），而且必须有足够的余额（转账后余额非负数）。

R1CS约束的固定形式为：

(A⋅s)×(B⋅s)=(C⋅s)\begin{aligned} (A⋅s) \times (B⋅s) = (C⋅s) \end{aligned}

其中：

  • $s$表示所有变量的组成的向量，又称为解向量，或者见证（Witness），由名字可知，这里面将会包含我们的解
  • $A$，$B$，$C$为系数向量，用来表示约束

我们以一个示例来演示如何将问题转化为R1CS，再转化为多项式的，假如想要证明：

a×b+6=20\begin{aligned} a \times b + 6 = 20 \end{aligned}

根据上面算术电路的思路，我们可以把问题拆分为以下三个约束：

  1. $a \times b = c$
  2. $(c+6) \times 1 = d$
  3. $d \times 1 = 20$

提取解向量$s=[1,a,b,c,d]$，构造矩阵$A$，$B$，$C$：

约束1：$a \times b = c$

  • $A_1 = [0,1,0,0,0]$ (表示选择$a$)
  • $B_1 = [0,0,1,0,0]$ (表示选择$b$)
  • $C_1 = [0,0,0,1,0]$ (表示选择$c$)

约束2：$(c+6) \times 1 = d$

  • $A_2 = [6,0,0,1,0]$ (表示选择$6$个$1$和$c$)
  • $B_2 = [1,0,0,0,0]$ (表示选择$1$)
  • $C_2 = [0,0,0,0,1]$ (表示选择$d$)

约束3： $d \times 1 = 20$

  • $A_3 = [0,0,0,0,1]$ (表示选择$d$)
  • $B_3 = [1,0,0,0,0]$ (表示选择$1$)
  • $C_3 = [20,0,0,0,0]$ (表示选择$20$)

得到矩阵：

A=[010006001000001],B=[001001000010000],C=[0001000001200000]A = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 6 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} , B = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix} , C = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 20 & 0 & 0 & 0 & 0 \end{bmatrix}

补充说明：

1、拆分后，约束2和约束3可能有些费解：为什么需要$\times 1$？

因为R1CS的形式为$(A⋅s) \times (B⋅s) = (C⋅s)$，即左边输入 $\times$ 右边输入 $=$ 输出，所以电路只能是乘法，加法可以通过$\times 1$来转化，这也是为什么解向量$s$里面需要有一个常数$1$的原因。

QAP #

Quadratic Arithmetic Program（二次算术程序）解决如何将任意计算（或证明语句）转换成一种统一的数学形式，使得可以高效地进行零知识验证，也就是上面所说的需要将问题转为多项式来计算。完成这一步，我们将得到一个多项式方程，验证这个方程是否成立，就等于验证了我们的问题。

让我们继续上面的示例，上一部分我们已经把需要证明的问题 $a \times b + 6 = 20$ 转化为三个矩阵和一个解向量$s$,下面我将这些离散的点变成三组多项式：

观察上面三个矩阵，发现每个矩阵的每一列是每个变量在各个约束中的系数，例如矩阵A的第一列$[0,6,0]$是常数 $1$ 在三个约束中的系数的表现，而$[1,0,0]$就是$a$的系数表现，我们可以把它们看成是某个多项式在一组点上的取值，也就是需要把这些分散的点给连接起来，使它们变得有关联。

所以我们可以使用拉格朗日插值法，该插值方法可以给出一个恰好穿过若干个已知点的多项式函数。

求$A(x)，B(x)，C(x)：$

首先，我们先定好三个插值点$x=1,2,3$（因为有三个约束），所以多项式$A_0(x)$过点$(1,0)$，$(2,6)$，$(3,0)$，根据拉格朗日插值法公式，构造这个多项式的公式为：

P(x)=y0L0(x)+y1L1(x)+y2L2(x)\begin{aligned} P(x) = y_0 L_0(x) + y_1 L_1(x) + y_2 L_2(x) \end{aligned}

其中，

L0=(x−x1)(x−x2)(x0−x1)(x0−x2),  L1=(x−x0)(x−x2)(x1−x0)(x1−x2),  L2=(x−x0)(x−x1)(x2−x0)(x2−x1)\begin{aligned} L_0 = \cfrac{(x - x_1)(x - x_2)}{(x_0 - x_1)(x_0 - x_2)} \end{aligned} ,\,\, \begin{aligned} L_1 = \cfrac{(x - x_0)(x - x_2)}{(x_1 - x_0)(x_1 - x_2)} \end{aligned} ,\,\, \begin{aligned} L_2 = \cfrac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)} \end{aligned}

将$(1,0)$，$(2,6)$，$(3,0)$中$x = 1,2,3$分别代入：

L0=(x−2)(x−3)(1−2)(1−3),  L1=(x−1)(x−3)(2−1)(2−3),  L2=(x−1)(x−2)(3−1)(3−2)L_0 = \cfrac{(x - 2)(x - 3)}{(1 - 2)(1 - 3)} ,\,\, L_1 = \cfrac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)} ,\,\, L_2 = \cfrac{(x - 1)(x - 2)}{(3 - 1)(3 - 2)}

最后把$y=0,6,0$和$L_0$，$L_1$，$L_2$代入以上公式：

P(x)=0×(x−2)(x−3)(1−2)(1−3)+6×(x−1)(x−3)(2−1)(2−3)+0×(x−1)(x−2)(3−1)(3−2)P(x)=6×(x−1)(x−3)(2−1)(2−3)P(x)=−6x2+24x−18\begin{aligned} P(x) &= 0 \times \cfrac{(x - 2)(x - 3)}{(1 - 2)(1 - 3)} + 6 \times \cfrac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)} + 0 \times \cfrac{(x - 1)(x - 2)}{(3 - 1)(3 - 2)} \\ P(x) &= 6 \times \cfrac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)} \\ P(x) &= -6x^2 + 24x -18 \end{aligned}

所以求得 $A_0(x) = -6x^2 + 24x -18$，按照以上步骤分别求得：

过点$(1,1)$，$(2,0)$，$(3,0)$求得 $A_1(x) = \dfrac{1}{2} x^2 - \dfrac{5}{2} x + 3$

过点$(1,0)$，$(2,0)$，$(3,0)$求得 $A_2(x) = 0$

过点$(1,0)$，$(2,1)$，$(3,0)$求得 $A_3(x) = -x^2 + 4x -3$

过点$(1,0)$，$(2,0)$，$(3,1)$求得 $A_4(x) = \dfrac{1}{2} x^2 - \dfrac{3}{2} x + 1$

即 $A(x)$ 的一组多项式：

A(x)=[−6x2+24x−18,  12x2−52x+3,  0,  −x2+4x−3,  12x2−32x+1]\begin{aligned} A(x) = \begin{bmatrix}-6x^2 + 24x -18,\,\,\frac{1}{2} x^2 - \frac{5}{2} x + 3,\,\, 0 ,\,\, -x^2 + 4x -3,\,\, \frac{1}{2} x^2 - \frac{3}{2} x + 1\end{bmatrix} \end{aligned}

同理求得 $B(x)$：

B(x)=[−12x2+52x−2,  0,  12x2+52x+3,  0,  0]\begin{aligned} B(x) = \begin{bmatrix} -\frac{1}{2} x^2 + \frac{5}{2} x - 2,\,\, 0,\,\, \frac{1}{2} x^2 + \frac{5}{2} x + 3 ,\,\, 0,\,\, 0\end{bmatrix} \end{aligned}

同理求得 $C(x)$：

C(x)=[10x2−30x+20,  0,  0,  12x2−52x+3,  −x2+4x−3]\begin{aligned} C(x) = \begin{bmatrix} 10x^2 - 30x + 20,\,\, 0,\,\, 0 ,\,\, \frac{1}{2} x^2 - \frac{5}{2} x + 3,\,\, - x^2 + 4x - 3 \end{bmatrix} \end{aligned}

到此，我们得到几组多项式，它们是通过约束转换而来，如果把整个ZKP流程比作考试过程，现在可以说我们的"试卷"已经生成好了。

核心验证等式 #

接下来需要考虑如何验证你往"试卷"填写的答案是否正确，我们不能直接把答案公布出去让其他人验证，这样做就是普通的证明系统而非零知识。假设你是该证明系统设计者，你会如何做？

我会想到是否可以通过一个多项式等式来证明，如果其他人验证了该等式成立，证明解合法。此时，脑海中出现了这样一个等式：$? = ?$。左右两边的多项式应该填什么？首先应该想办法把我们的解$a=2, b=7$放进去，很明显我们已经有解向量$s$了，很自然会想到需要把解向量$s$结合所有约束组成新的多项式，放到等式的一边，并用$P(x)$来表示，这时候等式变成$P(x)=?$，$P(x)$具体是什么？”结合$s$和所有约束“这个操作其实是$A(x)$、$B(x)$和$C(x)$多项式在解向量$s$下的线性组合，就像在一张已经出好题的试卷填上答案。可以定义如下：

P(x)=(A(x)⋅s)⋅(B(x)⋅s)−(C(x)⋅s)\begin{aligned} P(x) = (A(x)⋅s)⋅ (B(x)⋅s) − (C(x)⋅s) \end{aligned}

其中，在前面我们已求得$A(x)$、$B(x)$、$C(x)$，而解向量$s=[1,2,7,14,20]$，因此代入如下：

A(x)⋅s=[−6x2+24x−18,  12x2−52x+3,  0,  −x2+4x−3,  12x2−32x+1]⋅[1,a,b,c,d]B(x)⋅s=[−12x2+52x−2,  0,  12x2+52x+3,  0,0]⋅[1,a,b,c,d]C(x)⋅s=[10x2−30x+20,  0,  0,  12x2−52x+3,  −x2+4x−3]⋅[1,a,b,c,d]\begin{aligned} A(x)·s &= \begin{bmatrix}-6x^2 + 24x -18,\,\,\frac{1}{2} x^2 - \frac{5}{2} x + 3,\,\, 0 ,\,\, -x^2 + 4x -3,\,\, \frac{1}{2} x^2 - \frac{3}{2} x + 1\end{bmatrix} · [1,a,b,c,d] \\ B(x)·s &= \begin{bmatrix} -\frac{1}{2} x^2 + \frac{5}{2} x - 2,\,\, 0,\,\, \frac{1}{2} x^2 + \frac{5}{2} x + 3 ,\,\, 0, 0\end{bmatrix} · [1,a,b,c,d]\\ C(x)·s &= \begin{bmatrix} 10x^2 - 30x + 20,\,\, 0,\,\, 0 ,\,\, \frac{1}{2} x^2 - \frac{5}{2} x + 3,\,\, - x^2 + 4x - 3\end{bmatrix}· [1,a,b,c,d] \end{aligned}

到此得到了$P(x)$，我们可以把它叫做”约束检查多项式“，但上面的等式$P(x)=?$还没有完成，右边是什么？我能令$P(x)$在某种条件下等于 $0$ 吗？根据观察我发现其实$P(x)$就是从最开始的R1CS约束等式$(A·s)·(B·s)=(C·s)$变过来的，将它变换一下就等价于$(A·s)·(B·s) - (C·s) = 0$，是不是跟$P(x)$结构很像？所以想要让$P(x)=0$，其实满足约束就可以了，而因为在第1阶段选择插值点是$x=1,2,3$（因为示例有3个约束），所以$P(x)$在集合$[1,2,3]$上都为零，用来表示满足了3个约束。如果$P(x)$在$[1,2,3]$上都为零，那么可以构造一个目标多项式$Z(x)=(x-1)(x-2)(x-3)$，它在$x=1,2,3$都为零。根据因式定理$(x-1)$是$P(1)$的因式，如果一个多项式$P(x)$能被另一个多项式$Z(x)$整除，那么存在一个商多项式$h(x)$，商多项式的存在就是是计算正确的数学证明。最终的核心验证等式如下：

P(x)=Z(x)h(x)\begin{aligned} P(x)=Z(x)h(x) \end{aligned}

在后续构造证明和验证的过程都是围绕这个核心验证等式来进行，但并不代表把等式的数值直接提交给verifier验证，这样做一是泄露了太多信息，二是验证速度太慢。为了达到“零知识性”和“简洁性”，我们还需要做大量的工作。

阶段2：可信设置（Trusted Setup） #

这个阶段也叫生成公共参考字符串（Common Reference String, CRS），根据名字可知就是生成一些公共的参数，提供给ZKP做证明和验证使用。哪需要生成什么样的参数呢？在一开始提到zk-SNARK的几个相关特性，这里的参数就是为了满足 非交互性、零知识性 以及 简洁性。

我们再回顾 “思考的问题” 中的例子，知道如果将需要校验的值建立某种关联，就能实现随机抽取一个点校验所有值是否正确的目的。如果是交互协议的证明过程可能是这样的：prover（证明者）将问题转为多项式问题发送给verifier（验证者），verifier随机挑选一个点$r$返回给prover，prover根据得到的$r$生成证明发送给verifier，最后verifier验证。

非交互式的证明过程：提前生成$r$，prover在第一步就已经利用$r$直接生成证明发送给verifier，verifier做验证。但是$r$提前生成prover就事先知道要检查是哪个点了，他完全可以作弊。确实是的，$r$的值一定不能被任何人知道，不然整个证明系统就无效了。但是如果我们有方法在不知道$r$的情况下，也能对其进行运算呢：生成$r$并计算另一个值$r’$，重点是无法通过$r’$推算出真实的$r$， 然后销毁$r$，后续的操作都是对$r’$进行。

椭圆曲线密码（ECC） #

在开始生成公共参数前，必须先引入另一个工具：椭圆曲线密码。ECC属于公钥密码，在如今的密码学中起到非常重要的作用，另一种更久远和更常见的公钥密码是RSA，但同等长度密钥下它比RSA验证速度更快且更安全，有研究表明RSA如果要达到ECC 228 位密钥的安全性，至少需要长度 2380 的密钥。我们熟知的比特币、以太坊就是通过椭圆曲线数字签名算法（ECDSA）来验证签名，不过这一部分的目的并非探讨签名和验签的细节，而是要了解生成点$G$的概念以及是如何在椭圆曲线上做标量乘法。

椭圆曲线密码是一类算法的统称，其实现是通过选择不同的椭圆曲线方程来体现，不同的方程有不同的性质、安全特性和应用场景。我们以曲线secp256k1为例，该曲线对应的方程是：

y2≡x3+7  ( mod  p)\begin{aligned} y^2 \equiv x^3 + 7 \,\, (\bmod \,p) \end{aligned}

其中$p$是一个很大的质数，$\equiv$是同余符号，表示$y^2$与 $x^3+7$对于模$p$同余。下图演示如何在该椭圆曲线上做加法：过曲线两点A，B画一条直线，找到直线与椭圆曲线的交点，我们把该点关于x轴对称位置的点定义为A+B。

但是，上述定义无法解释A+A，即两点重合时的情况，因为当两点重合时，无法画出“过两点的直线”。这种情况下，我们画出“曲线在点A的切线”，然后找到该切线与椭圆曲线的交点，将该交点关于x轴的对称位置定义为A+A，也就是2A。这样的运算，称为“点倍运算”。

现在，我们假设有一个点$G$，将它定义为初始点，给定点$G$我们可以求出$2G$，$3G$，···等点的坐标。$2G$相当于$G$的二倍，而$3G$则相当于$G+2G$，以此类推，一直求出$8G$的坐标。

现在，我们脑海中想象一下，如果把图中的所有的蓝绿线和中途的坐标点隐藏掉（如下图），已知信息只有$G$和$8G$的坐标点，你知道$8G$是经过什么样的路径得来的吗？不能，因为有太多的可能性了。因此我们可以说：当给定点$G$时，已知数$x$求点$xG$的问题并不难。但反过来，已知点$xG$求数$x$的问题非常困难。这就是椭圆曲线密码中所利用的“椭圆曲线上的离散对数问题”。

而在比特币和以太坊应用中，会先得到一个随机点$k$，经过计算$kG$的得到$P$，即 $K = k·G$，其中$k$为私钥，$K$为公钥。但有些区别的是这里运算并非通过一步步做切线映射，因为这样效率实在太低了，而是通过一种叫标量乘法的运算交替使用“加法”和“乘法”，可以理解为优化过的算法。

双线性配对 #

到这里我们对椭圆曲线有一些了解，知道$G$是椭圆曲线上的一个坐标点，知道有标量乘法。说了这么多，这和ZKP有什么关系呢？为了达到零知识和简洁性需要依赖椭圆曲线密码，但这里使用的曲线方程和上面介绍的不同，这里需要用到一种称为“配对友好型”的曲线（如BLS12-381、BN254），在证明生成和验证的时候需要使用双线性配对来进行运算，配对的定义如下：

e:G1×G2→GT\begin{aligned} e:G_1 \times G_2 \rarr G_T \end{aligned}

其中，$G_1$可以理解为一个特定生成点$G$通过重复标量乘法生成的点的集合，称为群。符号$\times$是笛卡尔乘积，符号$\rarr$表示映射，而$G_T$是另一个群。以上定义的意思是：存在一个名为$e$的配对函数，它接受两个输入，第一个输入是群$G_1$中的一个点，第二个输入是群$G_2$中的一个点，然后输出一个在群$G_T$中的元素。

这样的作用是什么？为什么需要通过映射到$G_T$的方式来运算？因为传统的椭圆曲线只允许在线性运算，即上面介绍的加法（$A+B$）和标量乘法（$kG$），不允许进行非线性运算，而双线性配对的出现正好弥补了这个缺失。配对操作引入了一种非线性关系，允许我们在目标群 $G_T$ 的指数上进行乘法：

e(aG,bG)=e(G,G)ab\begin{aligned} e(aG, bG) = e(G, G)^{ab} \end{aligned}

不仅如此，$G_1$和$G_2$群也是有讲究的，它是一个非对称结构，即$G_1 ≠ G_2$。它们的大小不一样，如果$G_1$是48字节，$G_2$就是96字节。一般来说$G_1$计算速度快，承载大部分证明计算，$G_2$计算慢但安全性高，承载证明的关键部分。所以，我们接下来需要生成的公共参数会根据特点输入到不同的群。

通过MPC生成公共参数 #

这种公共参数有个别称叫做“有毒废物”，意思是这些参数很重要需要严格保密，一旦渗漏会导致整个系统失效，所以使用一次后参数真实的值会被销毁，只留下对应的秘密值。需要生成的参数如下：

  • $\tau$：核心秘密的"秘密位置"，又称为评估点，也就是"随机抽查"验证的点。
  • $\alpha$、$\beta$：$\alpha$约束$A$多项式；$\beta$约束$B$多项式。它们共同保证prover不会随意更改证明的结构。
  • $\delta$：零知识因子，用于确保证明者在生成证明时可以随机化他们的见证，以实现零知识性。
  • $\gamma$：公共输入验证因子，用于验证公共输入部分与 CRS 中的预计算值是否一致，确保证明者不能伪造公共输入。

为了确保保密，不能只靠一个人来生成，这些参数需要使用MPC(Multi-Party Computation，多方计算)，每个参与者贡献一些随机性，只要有一个诚实，就不会泄露整个秘密。这些原始元素永远不公开，会被参与者销毁。

以下我们以$\tau$为例，看下它是如何通过多方合作生成，首先是第一个参与者Alice：

  1. 她生成自己的秘密值$s_1$，这相当于她自己的“私钥”。
  2. 计算 $[g^{s_1},g^{s_1^2},g^{s_1^3},…,g^{s_1^n}]$ ，其中$n$与QAP多项式的阶数相关，通常是最高阶加一些数。$G$是一个公开的生成点，注意这里为了隐藏掉$s_1$的值做标量乘法。
  3. Alice销毁自己的$s_1$，把结果公开并传给下一位参与者Bob

注意： $g^{s_1} = G \cdot s_1$

Bob拿到Alice传过来的一组数值，并进行自己的计算：

  1. 他也生成自己的秘密值$s_2$。
  2. 他将自己的秘密值混入到Alice的结果 $[g^{(s_1\times s_2)}, g^{(s_1\times s_2)^2} , g^{(s_1\times s_2)^3} ,…, g^{(s_1\times s_2)^n} ]$
  3. Bob销毁自己的$s_2$，把结果公开并传给下一位参与者

以此类推，通常参与者可以达到数百位。通过MPC来生成$\tau$，可以保证就算只有一位参与者是诚实的（销毁了自己的秘密值），$\tau$就是安全的。这里你可能会问：如果Bob根本就没有使用Alice传给他的结果来计算呢？有办法可以验证他确实是使用了吗？有的。

  • 我们暂且将Alice的点$G·s_1^i$记为$P_i$
  • Bob计算新的点$s_2$·$P_i$，此外，他还需要发布一个承诺$C=H·s_2$，其中$H$是另一个公开的生成点。
  • 验证者根据双线性配对特性进行验证：
    • 左边： $e$$($Bob的点,$H$$)$ = $e(s_2·P_i,H)$
    • 右边：$e$$($Alice的点,$C$$)$ = $e(P_i,H·s_2)$
  • 根据双线性：
    • 左边：$e(s_2·P_i,H)$ = $e(P_i,H)^{s_2}$
    • 右边：$e(P_i,H·s_2)$ = $e(P_i,H)^{s_2}$
  • 左边等于右边，证明Bob确实是包含了Alice的结果。

前面提到，我们需要将不同的公共参数输入到不同的群，即$G1$和$G2$，具体如下：

  • $G_1$：$[\tau]_1$、$[\alpha]_1$、$[\beta]_1$、$[\delta]_1$
  • $G_2$：$[\tau]_2$、$[\beta]_2$、$[\delta]_2$、$[\gamma]_2$

所以其实我们是需要两个$\tau$分别在$G_1$和$G_2$，生成的过程都一样，只需要把生成点$G$换一下就可以了。后续的计算都会以$[\tau]_1$的形式来表示元素群$G_1·\tau$，

最终，我们所生成的$\tau$在$G_1$群的整个CRS列表类似这样：

[τ]1=[g1(s1×s2×...sn),g1(s1×s2×...sn)2,g1(s1×s2×...sn)3,...,g1(s1×s2×...sn)n][τ]1=[g1τ,g1τ2,g1τ3,...,g1τn]\begin{aligned} [\tau]_1 &= [g_1^{(s_1 \times s_2 \times {...} s_n)},g_1^{(s_1 \times s_2 \times {...} s_n)^2},g_1^{(s_1 \times s_2 \times {...} s_n)^3},..., g_1^{(s_1 \times s_2 \times {...} s_n)^n} ] \\ [\tau]_1 &= [g_1^\tau , g_1^{\tau^2} , g_1^{\tau^3},...,g_1^{\tau^n}] \end{aligned}

以此类推，其他的公共参数也可以用同样的方法生成。

阶段3：构造证明 #

在开始构造零知识证明之前，我们先了解一个基础概念：有限域（$\mathbb{F}_p$）。在数学里，数字可以无限大，但在计算机内部，数值必须限制在特定范围内。有限域的概念类似于12小时制时钟：即使实际时间可能很大，但每12小时就会归零重新计数。有限域$\mathbb{F}_p$就是元素为$0$到$p-1$的循环体系，比如：

x=a×b, (a=5,b=3, 在 F12)x=(5×3) mod 12x=3\begin{aligned} x &= a \times b, \, (a=5, b=3,\, \text{在}\,\mathbb{F}_{12}) \\ x &= (5 \times 3) \bmod 12\\ x &= 3 \end{aligned}

无论怎么运算，$x$的结果都不会超过有限域$12$，只会在$0$到$11$之间。

在零知识证明系统中，实际使用的有限域通常是非常大的素数$p$，甚至是素数的幂（$p^k$）。但为了模拟和便于演示，下面我们选用较小的素数101，有限域表示为$\mathbb{F}_{101}$，以避免数字过大导致计算复杂。

在$\tau$点评估多项式 #

在一开始有提到验证多项式就是选取一个随机的点$\tau$，检查多项式的等式是否成立。而现在我们有约束多项式、验证等式（第1阶段得到），也有了$\tau$等多个公共参数（第2阶段生成）。回顾最初需要证明的问题是：我们知道$a \times b + 6 = 20$的一个解。

在开始前，我们先初始化一些数值，因为公共参数在现实中都是非常大的数，这里为了演示，我们简单假设：

τ=5, α=7, β=11, γ=13, δ=17\begin{aligned} \tau = 5,\, \alpha = 7, \, \beta = 11, \, \gamma = 13, \, \delta = 17 \end{aligned}

回顾约束系统的内容，假如我们知道$a=2, b=7$是问题的解，那么在约束中$c=14$，$d=20$，则解向量$s$就是：

s=[1, a, b, c, d]s=[1, 2, 7, 14, 20]\begin{aligned} s &= [1,\,a,\,b,\,c,\,d] \\ s &= [1,\,2,\,7,\,14,\,20] \end{aligned}

在第1阶段求得的多项式组$A$、$B$和$C$分别是：

A(x)=[−6x2+24x−18,  12x2−52x+3,  0,  −x2+4x−3,  12x2−32x+1]B(x)=[−12x2+52x−2,  0,  12x2+52x+3,  0,  0]C(x)=[10x2−30x+20,  0,  0,  12x2−52x+3,  −x2+4x−3]\begin{aligned} A(x) &= \begin{bmatrix}-6x^2 + 24x -18,\,\,\frac{1}{2} x^2 - \frac{5}{2} x + 3,\,\, 0 ,\,\, -x^2 + 4x -3,\,\, \frac{1}{2} x^2 - \frac{3}{2} x + 1\end{bmatrix} \\ B(x) &= \begin{bmatrix} -\frac{1}{2} x^2 + \frac{5}{2} x - 2,\,\, 0,\,\, \frac{1}{2} x^2 + \frac{5}{2} x + 3 ,\,\, 0,\,\, 0\end{bmatrix} \\ C(x) &= \begin{bmatrix} 10x^2 - 30x + 20,\,\, 0,\,\, 0 ,\,\, \frac{1}{2} x^2 - \frac{5}{2} x + 3,\,\, - x^2 + 4x - 3 \end{bmatrix} \end{aligned}

因为我们需要在$\tau=5$处评估，所以它在群$G1$和$G2$的CRS列表分别是：

[τ]1=[g15, g152, g153, ..., g15n][τ]2=[g25, g252, g253, ..., g25n]\begin{aligned} [\tau]_1 &= [g_1^5,\,g_1^{5^2},\,g_1^{5^3},\,...,\,g_1^{5^n}] \\ [\tau]_2 &= [g_2^5,\,g_2^{5^2},\,g_2^{5^3},\,...,\,g_2^{5^n}] \end{aligned}

既然我们想要评估$\tau=5$处的多项式，那就把$x=5$代入$A(x)$：

A0(5)=(−6×52)+(24×5)−18  ( mod  101)A0(5)=−150+120−18  ( mod  101)A0(5)=−48  ( mod  101)A0(5)=53⋮A1(5)=3A2(5)=0A3(5)=93A4(5)=6\begin{aligned} A_0(5) &= (-6 \times 5^2) + (24 \times 5) - 18 \,\,(\bmod\,101) \\ A_0(5) &= -150 + 120 - 18 \,\,(\bmod\,101) \\ A_0(5) &= -48 \,\,(\bmod\,101) \\ A_0(5) &= 53 \\ \vdots \\ A_1(5) &= 3 \\ A_2(5) &= 0 \\ A_3(5) &= 93 \\ A_4(5) &= 6 \\ \end{aligned}

注意结果只能在$[0,101)$范围内，在$A_0(5)$处结果$-48$是负数，所以必须加上$101$的倍数，直到结果落在这个范围内，即 $-48 + 101 = 53$。

同理可求得$B(x)$和$C(x)$，最终：

A(5)=[53, 3, 0, 93, 6]B(5)=[99, 0, 3, 0, 0]C(5)=[19, 0, 0, 3, 93]\begin{aligned} A(5) &= \begin{bmatrix} 53,\,3,\,0,\,93,\,6 \end{bmatrix} \\ B(5) &= \begin{bmatrix} 99,\,0,\,3,\,0,\,0 \end{bmatrix} \\ C(5) &= \begin{bmatrix} 19,\,0,\,0,\,3,\,93 \end{bmatrix} \\ \end{aligned}

接着计算$A(5)$、$B(5)$和$C(5)$与解向量$s$的线性组合：

A(5)⋅s=[53, 3, 0, 93, 6]⋅[1, 2, 7, 14, 20]A(5)⋅s=(53×1+3×2+0×7+93×14+6×20) mod  101A(5)⋅s=(53×1+3×2+0×7+93×14+6×20) mod  101A(5)⋅s=67⋮B(5)⋅s=19C(5)⋅s=2\begin{aligned} A(5)·s &= \begin{bmatrix} 53,\,3,\,0,\,93,\,6 \end{bmatrix} · [1,\,2,\,7,\,14,\,20] \\ A(5)·s &= (53\times1+3\times2+0\times7+93\times14+6\times20) \bmod\,101\\ A(5)·s &= (53\times1+3\times2+0\times7+93\times14+6\times20) \bmod\,101\\ A(5)·s &=67 \\ \vdots \\ B(5)·s &=19 \\ C(5)·s &=2 \end{aligned}

在第一阶段中，我们知道核心验证等式为$P(x) = Z(x)h(x)$，其中：

P(x)=(A(x)⋅s)⋅(B(x)⋅s)−(C(x)⋅s)Z(x)=(x−1)(x−2)(x−3)\begin{aligned} P(x) &= (A(x)·s) · (B(x)·s) - (C(x)·s) \\ Z(x) &= (x-1)(x-2)(x-3) \end{aligned}

将$x=\tau=5$代入并展开：

P(5)=Z(5)h(5)\begin{aligned} P(5) &= Z(5)h(5) \end{aligned}

先求约束检查多项式$P(x)$：

P(5)=(A(5)⋅s)⋅(B(5)⋅s)−(C(5)⋅s)((5−1)(5−2)(5−3))⋅h(5)≡67×19−2≡1271≡59( mod  101)\begin{aligned} P(5) &= (A(5)·s) · (B(5)·s) - (C(5)·s)\\ ((5-1)(5-2)(5-3))· h(5) &\equiv 67\times 19-2\equiv1271\equiv59 \quad(\bmod\, 101)\\ \end{aligned}

再求目标多项式$Z(x)$：

Z(5)=(5−1)(5−2)(5−3)≡24( mod  101)\begin{aligned} Z(5) &=(5-1)(5-2)(5-3)&\equiv24 \quad(\bmod\, 101)\\ \end{aligned}

最后求商多项式$h(5)$：

h(5)=P(5)⋅Z(5)−1≡59×24−1≡59×80≡74( mod  101)\begin{aligned} h(5) &=P(5)·Z(5)^{-1} \equiv 59\times 24^{-1} \equiv 59\times 80 \equiv 74 \quad(\bmod\, 101) \end{aligned}

最后，我们得到：

a(τ)=A(τ)⋅s=67b(τ)=B(τ)⋅s=19c(τ)=C(τ)⋅s=2h(τ)=74Z(τ)=24\begin{aligned} a(\tau)&=A(\tau)·s=67 \\ b(\tau)&=B(\tau)·s=19 \\ c(\tau)&=C(\tau)·s=2 \\ h(\tau)&=74 \\ Z(\tau)&=24 \end{aligned}

证明的三要素$\pi_1$、$\pi_2$和$\pi_3$ #

$\pi = ([\pi_1]_1,[\pi_2]_2,[\pi_3]_1)$就是最终prover发送给verifier的数据，其中$[\pi_1]_1$表示$\pi_1$在$G_1$群，所以这里有$\pi_1\in G_1 , \pi_2\in G_2 ,\pi_3 \in G_1$。

为了保证证明是零知识，prover在构造的时候会选择两个随机值$r$、$s$加入到运算，这里我们假设$r=3$、$n=4$。

$\pi_1,\pi_2,\pi_3$公式[1]如下：

[π1]1=[α]1+∑jsj[Aj(τ)]1+r[δ]1[π2]2=[β]2+∑jsj[Bj(τ)]2+n[δ]2[π3]1=∑jsj[Kjp(τ)]1+[h(τ)Z(τ)]1+s[π1]1+r[π2]1−rn[δ]1\begin{aligned} [\pi_1]_1 &=[\alpha]_1 + \displaystyle\sum_j s_j [A_j(\tau)]_1 + r[\delta]_1 \\ [\pi_2]_2 &=[\beta]_2 + \displaystyle\sum_j s_j [B_j(\tau)]_2 + n[\delta]_2 \\ [\pi_3]_1 &=\displaystyle\sum_j s_j [K_j^p(\tau)]_1 + [h(\tau)Z(\tau)]_1 +s[\pi_1]_1 + r[\pi_2]_1 - rn[\delta]_1 \end{aligned}

其中在$[\pi_3]_1$：

Kjp(τ)=δ−1(βAj(τ)+αBj(τ)+Cj(τ))[π2]1=[β]1+∑jsj[Bj(τ)]1+n[δ]1\begin{aligned} K_j^p(\tau) &= \delta^{-1} \biggl( \beta A_j(\tau) + \alpha B_j(\tau) + C_j(\tau) \biggr) \\ [\pi_2]_1 &= [\beta]_1 + \displaystyle\sum_j s_j [B_j(\tau)]_1 + n[\delta]_1 \end{aligned}

其中我们已经求得：

∑jsj[Aj(τ)]1=a(τ)=67∑jsj[Bj(τ)]2=b(τ)=19并知道 τ=5, α=7, β=11, γ=13, δ=17\begin{aligned} \displaystyle\sum_j s_j [A_j(\tau)]_1 &=a(\tau)=67 \\ \displaystyle\sum_j s_j [B_j(\tau)]_2 &=b(\tau)=19\\ \text{并知道}\, \tau = 5,\, \alpha = 7, \, \beta &= 11, \, \gamma = 13, \, \delta = 17 \end{aligned}

计算$[\pi_1]_1$ #

根据公式:

π1=α+a(τ)+r⋅δ( mod  101)\begin{aligned} \pi_1 = \alpha + a(\tau) + r·\delta \quad (\bmod \,101) \end{aligned}

代入数值：

π1=7+67+3×17=7+67+51=125≡24( mod  101)\begin{aligned} \pi_1 = 7 +67 +3\times 17 = 7 +67+51 =125 \equiv 24 \quad(\bmod \,101) \end{aligned}

因此：

[π1]1=g124\begin{aligned} [\pi_1]_1 = g_1^{24} \end{aligned}

计算$[\pi_2]_2$ #

根据公式:

π2=β+b(τ)+n⋅δ( mod  101)\begin{aligned} \pi_2 = \beta + b(\tau) + n·\delta \quad (\bmod \,101) \end{aligned}

代入数值：

π2=11+19+4×17=11+19+68=98( mod  101)\begin{aligned} \pi_2 = 11 +19 +4\times 17 = 11 +19+68 =98 \quad(\bmod \,101) \end{aligned}

因此：

[π2]2=g298\begin{aligned} [\pi_2]_2 = g_2^{98} \end{aligned}

计算$[\pi_3]_1$ #

公式比较复杂，这里再抄一次：

[π3]1=∑jsj[Kjp(τ)]1+[h(τ)Z(τ)]1+s[π1]1+n[π2]1−rn[δ]1\begin{aligned} [\pi_3]_1 &=\displaystyle\sum_j s_j [K_j^p(\tau)]_1 + [h(\tau)Z(\tau)]_1 +s[\pi_1]_1 + n[\pi_2]_1 - rn[\delta]_1 \end{aligned}

(1) 按照公式，先计算第一项：

∑jsjKjp(τ)其中Kjp(τ)=δ−1(β⋅a(τ)+α⋅b(τ)+c(τ))\begin{aligned} \displaystyle\sum_j s_j K_j^p(\tau) \quad \text{其中} \quad K_j^p(\tau) &= \delta^{-1} \biggl( \beta·a(\tau) + \alpha·b(\tau) + c(\tau) \biggr) \\ \end{aligned}

将数值代入：

δ=17,代入δ−1=17−1 mod  101 ,即17⋅x≡1 mod  101 ,x=6求得δ−1=6β⋅a(τ)=11×67≡30( mod  101)α⋅b(τ)=7×19≡32( mod  101)c(τ)=2∑jsjKjp(τ)=6×(30+32+2)≡81( mod  101)\begin{aligned} \delta &= 17,\text{代入} \quad \delta^{-1} = 17^{-1} \bmod\,101 \,,\quad \text{即} 17 · x \equiv 1 \bmod\,101 \,,x=6 \\ \text{求得} \quad \delta^{-1} &= 6 \\ \beta·a(\tau) &= 11 \times 67 \equiv 30 \quad (\bmod\,101) \\ \alpha·b(\tau) &= 7 \times 19 \equiv 32 \quad (\bmod\,101) \\ c(\tau) &= 2 \\ \displaystyle\sum_j s_j K_j^p(\tau) &= 6 \times (30 + 32 + 2) \equiv 81 \quad (\bmod\,101) \end{aligned}

(2) 计算公式第二项，在实际计算中等于$h(\tau)Z(\tau)\delta^{-1}$，为了防止prover伪造证明，所以$CRS$不会直接给出$Z(\tau)$的值，而是给出$Z(\tau)\delta^{-1}$：

h(τ)Z(τ)δ−1=74×24×6≡51( mod  101)\begin{aligned} h(\tau)Z(\tau)\delta^{-1} = 74 \times 24 \times 6 \equiv 51 \quad (\bmod\,101) \end{aligned}

(3) 公式第三项$s\pi_1 = n \times 24 \equiv 4 \times 24 \equiv 96 \quad (\bmod,101) $

(4) 公式第四项$r\pi_2 = r \times 98 \equiv 3 \times 98 \equiv 92 \quad (\bmod,101) $

(5) 公式最后一项$rn\delta = 3 \times 4 \times 17 \equiv 2 \quad (\bmod,101)$

所以：

π3=81+51+96+92−2≡15( mod  101)[π3]1=g115\begin{aligned} \pi_3 &= 81 + 51 + 96 + 92 -2 \equiv 15 \quad (\bmod\,101) \\ [\pi_3]_1 &= g_1^{15} \end{aligned}

最后得到以下三要素，也就是prover需要发送给verifier的数值。

π=([π1]1,[π2]2,[π3]1)=(g124,g298,g115)\begin{aligned} \pi = ([\pi_1]_1,[\pi_2]_2,[\pi_3]_1) = (g_1^{24},g_2^{98},g_1^{15}) \end{aligned}

阶段4：验证证明 #

verifier验证的根据其实是：

e([π1]1,[π2]2)=e([α]1,[β]2)⋅e([π3]1,[δ]2)\begin{aligned} e([\pi_1]_1,[\pi_2]_2) = e([\alpha]_1,[\beta]_2)·e([\pi_3]_1,[\delta]_2) \end{aligned}

这个验证等式就是从核心验证等式$P(x) = h(x)Z(x)$演变而来，我们可以左边和右边各自展开，最终可以看到：

exp(π3)=δ−1(αB+Aβ+C+hZ)+T 其中T=αs+rβ+rsδ+rB+As\begin{aligned} exp(\pi_3) = \delta^{-1}(\alpha B + A\beta +C +hZ) +T \quad \,\text{其中}T = \alpha s + r\beta + rs\delta + rB + As \end{aligned}

如果去掉随机项和$CRS$参数就会回退到：

AB−C=hZP=hZ\begin{aligned} AB - C &= hZ \\ P&=hZ \end{aligned}

现在开始验证，从上一阶段我们可知$\pi_1$、$\pi_2$和$\pi_3$由prover提供，而$[\alpha]_1$、$[\beta]_2$和$[\delta]_2$从$CRS$获取。

prover提供：

[π1]1=24[π2]2=98[π3]1=15\begin{aligned} [\pi_1]_1 &= 24 \\ [\pi_2]_2 &= 98 \\ [\pi_3]_1 &= 15 \end{aligned}

从$CRS$公共参数可知：

[α]1=7[β]2=11[δ]2=17\begin{aligned} [\alpha]_1 &= 7 \\ [\beta]_2 &= 11 \\ [\delta]_2 &= 17 \end{aligned}

将以上数值代入，根据双线性配对进行运算：

e([π1]1,[π2]2)=e([α]1,[β]2)⋅e([π3]1,[δ]2)e(g124,g298)=e(g17,g211)⋅e(g115,g217)e(g1,g2)24⋅98 mod 101=e(g1,g2)(7⋅11)+(15⋅17) mod 101e(g1,g2)29=e(g1,g2)29\begin{aligned} e([\pi_1]_1,[\pi_2]_2) &= e([\alpha]_1,[\beta]_2)·e([\pi_3]_1,[\delta]_2) \\ e(g_1^{24},g_2^{98}) &=e(g_1^{7},g_2^{11}) · e(g_1^{15},g_2^{17}) \\ e(g_1,g_2)^{24·98 \bmod 101} &=e(g_1,g_2)^{(7·11)+(15·17) \bmod 101} \\ e(g_1,g_2)^{29} &= e(g_1,g_2)^{29} \end{aligned}

验证通过，可以看到验证的过程是非常简洁，即使有成千上万的约束，过程也不会变得复杂。

总结 #

通过以上四个阶段的介绍，我们从零开始完整地走过了zk-SNARK协议的核心流程：从将实际问题转化为多项式问题（阶段1），到生成可信的公共参数（阶段2），再到构造零知识证明（阶段3），最后验证证明的有效性（阶段4）。这个过程虽然涉及大量的数学知识，但每一步都有其明确的动机和目的。

在实际应用中，我们通常不需要从零开始实现这些底层协议。目前已经有许多成熟的零知识证明框架和工具链可以帮助我们更高效地构建应用：

  • Circom & Snarkjs：Circom是一个用于编写算术电路的领域特定语言（DSL），而Snarkjs则提供了完整的证明生成和验证工具链。开发者只需要用Circom描述计算逻辑，框架会自动处理电路编译、R1CS转换、QAP生成等复杂步骤。

  • Arkworks：这是一个用Rust编写的零知识证明生态系统，提供了丰富的密码学原语和工具库。它支持多种证明系统（包括Groth16、PLONK等），并提供了高性能的实现。

  • PLONK：作为Groth16的改进协议，PLONK支持通用可信设置（Universal Setup），意味着一次设置可以用于所有相同大小的电路，大大降低了部署成本。

  • zk-STARKs：与zk-SNARKs不同，zk-STARKs不需要可信设置，且具有抗量子特性。虽然证明体积更大，但在某些场景下提供了更好的安全保证。

  • 应用层框架：如zkSync、Polygon zkEVM、StarkNet等，这些框架在底层协议之上构建了完整的应用生态，开发者可以直接使用它们提供的API和工具来构建去中心化应用。

这些框架和工具的出现，极大地降低了零知识证明技术的使用门槛。它们封装了复杂的数学运算和协议细节，让开发者能够专注于业务逻辑的实现。然而，理解底层协议的工作原理仍然至关重要。虽然Groth16协议看起来复杂和繁琐，但它实际上是许多现代零知识证明系统的基础。深入了解它的设计思想、数学原理和实现细节，不仅能够帮助我们更好地使用现有框架，还能让我们在遇到问题时快速定位和解决，甚至为改进和创新现有协议打下坚实的基础。

References

[1] lambdaclass, An overview of the Groth16 proof system

[2] Jens Groth, On the Size of Pairing-based Non-interactive Arguments