零知识证明(零)前置知识

一、零知识证明(零)前置知识

0.1 默认已掌握的基础

0.1.1 P与NP问题

问题 计算时间 验证时间 例子
P 多项式 多项式 排序,最短路径
NP 无要求 多项式 数独,三着色
PSPACE 无要求 无要求 下棋,正则表达式是否等价

P和NP问题可以通过验证其对应的布尔可满足问题的解来验证。所有P和NP问题的验证都可以转化成布尔表达式。例如:

  • 排序:两个数比大小可以封装成布尔表达式,相邻的数之间比大小可以写成布尔表达式。
  • 三着色:每个块只能着色为一种颜色可以表示成布尔表达式,相邻的块颜色不同也可以表示成布尔表达式。

如果给出了答案(witness),P和NP问题可以快速验证,ZKP就是要在不暴露witness的前提下完成验证。

ZKP只适用于P和NP问题,因为只有P和NP能快速验证。

0.1.2 布尔电路,算术电路

算术电路:只使用加、乘、等号。算术电路被满足即存在一组变量赋值使得每个方程都成立。如:

6 = x1 + x2
9 = x1x2

算术电路中的变量称为signals,等号用===表示。注意等号不是表示赋值,而是断言左右的值相等,如a === b + c表示assertEq(a, b + c)

算术电路的例子:

  • 0 === (1 - WA) * (2 - WA) * (3 - WA)表示WA只能取1或2或3。

  • >=如何表示?假设a和b是n-1位的变量,>=可以表示为\(2^{n-1}+(a-b)=c\),然后看c的最高位是1(a>=b)还是0(a<b),写成约束如下(以n=4为例):

    // u and v are represented with at most 3 bits:
    2²a₂ + 2¹a₁ + a₀ === u
    2²b₂ + 2¹b₁ + b₀ === v
    
    // 0 1 constraints for aᵢ, bᵢ
    a₀(a₀ - 1) === 0
    a₁(a₁ - 1) === 0
    a₂(a₂ - 1) === 0
    b₀(b₀ - 1) === 0
    b₁(b₁ - 1) === 0
    b₂(b₂ - 1) === 0
    
    // 2ⁿ⁻¹ + (u - v) binary representation
    2³ + (u - v) === 8c₃ + 4c₂ + 2c₁ + c₀
    
    // 0 1 constraints for cᵢ
    c₀(c₀ - 1) === 0
    c₁(c₁ - 1) === 0
    c₂(c₂ − 1) === 0
    c₃(c₃ − 1) === 0
    
    // Check that the MSB is 1
    c₃ === 1

布尔电路转换成算术电路:

  • 变量都为0或1:x(x - 1) === 0
  • 与:t === uv
  • 非:t === 1 - u
  • 或:t === u + v - uv

NP问题的解可以表示成布尔电路,每个布尔电路完全等价为一个算术电路。通常都用算术电路,因为表示更简单。

0.1.3 群,群同态,有限域

略。

0.1.4 椭圆曲线

略。

0.2 双线性配对(Bilinear Pairing)

\(\mathbb G_1,\mathbb G_2\)是两个椭圆曲线群,\(\mathbb G_T\)是一个乘法群,双线性映射定义为: \[ e:\mathbb G_1\times\mathbb G_2\to\mathbb G_T \] 满足以下性质:

  • 双线性\(e(aP,bQ)=e(P,Q)^{ab}\),其中\(P\in\mathbb G_1\)\(Q\in\mathbb G_2\)
  • 非退化性\(\exists P\in\mathbb G_1,Q\in\mathbb G_2\),使得\(e(P,Q)\ne1\)。否则都映射到\(1\)就没意义了。

如果\(\mathbb G_1=\mathbb G_2\)则称双线性配对是对称的(symmetric pairing),反之称为非对称的(asymmetric pairing),后者更常用。

双线性配对中\(\mathbb G_1,\mathbb G_2,\mathbb G_T\)的阶都为\(r\)(注意\(r\ne p\)\(p\)是有限域的特征)。下面以BN128为例感受一下这三个群:

from py_ecc.bn128 import curve_order, G1, G2, pairing

print(curve_order)
# 21888242871839275222246405745257275088548364400416034343698204186575808495617
  • \(\mathbb G_1\):是\(\mathbb F_p\)上的椭圆曲线群,生成元\(G_1\)如下。

    print(G1)
    # (1, 2)

  • \(\mathbb G_2\):是\(F_{p^2}\)上的椭圆曲线群,生成元\(G_2\)如下。

    print(G2)
    # ((10857046999023057135944570762232829481370756359578518086990519993285655852781,
    #   11559732032986387107991004021392285783925812861821192530917403151452391805634),
    #  (8495653923123431417604973247489272438418190587263600148770280649306958101930,
    #   4082367875863433681332203403145435568316851327593401208105741076214120093531))

  • \(\mathbb G_T\)(有时也写作\(\mathbb G_{12}\)):是\(\mathbb F_{p^{12}}\)中的一个乘法子群,运算为乘法,单位元为\(1\),生成元\(g=e(G_1,G_2)\)。因此双线性可以写成\(e(aP,bQ)=e(P,Q)^{ab}=g^{ab}\)

    print(pairing(G2, G1))	# 需要把G2写在前面
    # (18443897754565973717256850119554731228214108935025491924036055734000366132575,
    #  10734401203193558706037776473742910696504851986739882094082017010340198538454,
    #  5985796159921227033560968606339653189163760772067273492369082490994528765680,
    #  4093294155816392700623820137842432921872230622290337094591654151434545306688,
    #  642121370160833232766181493494955044074321385528883791668868426879070103434,
    #  4527449849947601357037044178952942489926487071653896435602814872334098625391,
    #  3758435817766288188804561253838670030762970764366672594784247447067868088068,
    #  18059168546148152671857026372711724379319778306792011146784665080987064164612,
    #  14656606573936501743457633041048024656612227301473084805627390748872617280984,
    #  17918828665069491344039743589118342552553375221610735811112289083834142789347,
    #  19455424343576886430889849773367397946457449073528455097210946839000147698372,
    #  7484542354754424633621663080190936924481536615300815203692506276894207018007)

举个计算的例子: \[ e(2G_1,3G_2)\times e(4G_1,5G_2)=e(G_1,G_2)^{26}=e(13G_1,2G_2) \] 另外双线性配对还有如下性质: \[ \begin{align} e(aG_1+bG_1,cG_2)&=e((a+b)G_1,cG_2)\\ &=e(G_1,G_2)^{(a+b)c}\\ &=e(G_1,G_2)^{ac}\cdot e(G_1,G_2)^{bc}\\ &=e(aG_1,cG_2)\cdot e(bG_1,cG_2) \end{align} \] 为了简化表示,我们有时会用\(P\cdot Q\)表示\(e(P,Q)\),用\(+\)表示\(G_T\)中的乘法;用\([a]_1\)表示\(aG_1\),用\([b]_2\)表示\(bG_2\),其中下标表示所属的群是\(\mathbb G_1\)还是\(\mathbb G_2\)。因此上面的性质可以写成: \[ ([a]_1+[b]_1)\cdot[c]_2=[a]_1\cdot[c]_2+[b]_1\cdot[c]_2 \] 就像分配律一样。上述表示会在Groth16的推导中用到。

0.3 Schwartz-Zippel引理

Schwartz-Zippel引理:两个多项式\(p(x)\)\(q(x)\)的度(次数)分别是\(d_p\)\(d_q\),如果\(p(x)\ne q(x)\),那么\(p(x)\)\(q(x)\)至多交于\(\max(d_p,d_q)\)个点。

例如:\(p(x)=x,q(x)=x^3\)有3个交点。

利用这个引理可以快速验证两个向量是否相等。设向量\(\mathbf a\)\(\mathbf b\)的长度都是\(n\),常规方法验证两个向量是否相等需要依次比较每一个元素,复杂度为\(O(n)\)。这里我们把\(\mathbf a\)看成\(n\)个点组成的向量,\(\mathbf b\)同理,x坐标从\(1\)\(n\),即: \[ \begin{align} \mathbf a&=[(1,a_1),(2,a_2),\cdots,(n,a_n)]\\ \mathbf b&=[(1,b_1),(2,b_2),\cdots,(n,b_n)] \end{align} \] 然后对\(\mathbf a\)\(\mathbf b\)分别进行拉格朗日插值(Lagrange Interpolation)得到多项式\(p(x)\)\(q(x)\)。这两个多项式的次数最高为\(n-1\),根据Schwartz-Zippel引理,如果\(p(x)\ne q(x)\),则它们在定义域上至多交于\(n-1\)个点。以ZKP中的实际参数为例,设\(n=2^{20}\),定义域取有限域\(\mathbb F_p\)\(p\approx2^{254}\),则在\(\mathbb F_p\)中随机取一点\(x_0\)使得\(p(x_0)=q(x_0)\)的概率是: \[ \frac{2^{20}}{2^{254}}=\frac{1}{2^{234}}\approx\frac{1}{10^{70}} \] 这相当于从整个宇宙找一颗原子的难度,因此我们有把握认为这两个多项式是相等的,即原来的两个向量是相等的。这种用随机点检验多项式的方法只需要一次求值验证,(不考虑插值)复杂度仅为\(O(1)\)

向量和多项式对于加法是同态的。这里向量\(\mathbf a=[a_1,a_2,\cdots,a_n]\)理解成给定了\(x=1,2,\cdots,n\)的点,即\([(1,a_1),(2,a_2),\cdots,(n,a_n)]\)。对这些点使用拉格朗日插值法可以得到唯一的次数为\(n-1\)的多项式\(f(x)\)\(\mathbf a\)\(f(x)\)是一一对应的。对向量进行加法/数乘等价于对应的多项式相加/数乘。如\([1,4,9]\)对应的多项式是\(f_1(x)=x^2\)\([1,8,27]\)对应的多项式是\(f_2(x)=x^3\)\([1,4,9]+[1,8,27]=[2,12,36]\),其对应多项式为\(x^3+x^2\)

0.4 R1CS

R1CS(Rank 1 Constraint System,秩1约束系统)是表示算术电路的一种通用形式,简单来说就是每个约束只能包含一个乘法,而不限制加法的数量。

\(z=3x^2y+5xy-x-2y+3\),写成R1CS的形式如下(结果不唯一),我们统一把乘法放在右边,加法放在左边。 \[ \begin{align} v_1&=3xx\\ v_2&=v_1y\\ -v_2+x+2y-3+z&=5xy \end{align} \] 证明者所持有的解,即witness,表示为一个(列)向量。第一个元素为\(1\),之后为输出、输入、中间变量,比如上面例子对应的witness为: \[ \text{witness}=[1,z,x,y,v_1,v_2]^T \]

可以先尝试一些简单的例子:\(z=xy\)\(z=xyuv\)\(z=xy+2\)\(z=2x^2+y\)

我们把上述约束表示成矩阵形式便于后续处理: \[ O\cdot\text{witness}=(L\cdot\text{witness})\circ(R\cdot\text{witness}) \]

  • \(L,R,O\)\(n\times m\)的系数矩阵。
  • \(n\)表示约束的个数
  • \(m\)表示witness中元素个数
  • \(\ \cdot\ \)表示矩阵乘法,\(\circ\)表示向量逐元素相乘(element-wise/Hadamard product)。

以前面的约束为例,矩阵形式如下,可以代入每一行自行验证。 \[ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ -3 & 1 & 1 & 2 & 0 & -1 \end{bmatrix} \begin{bmatrix} 1\\z\\x\\y\\v_1\\v_2 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 5 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1\\z\\x\\y\\v_1\\v_2 \end{bmatrix} \circ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1\\z\\x\\y\\v_1\\v_2 \end{bmatrix} \]

0.5 从R1CS构建ZKP

这章介绍很naive的方法,效率很低,但有助于理解ZKP的实现。

证明者只需对witness用椭圆曲线进行加密。设: \[ \text{witness}=[a_1,a_2,\cdots,a_m]^T \] 在矩阵形式\(O\cdot\text{witness}=(L\cdot\text{witness})\circ(R\cdot\text{witness})\)中,对\(L\cdot\text{witness}\)中witness的每个元素\(a_i\)都乘\(G_1\),对\(R\cdot\text{witness}\)中witness的每个元素\(a_i\)都乘\(G_2\)

至于\(O\cdot\text{witness}\),容易想到的方法是对其witness的每个元素都乘\(\mathbb G_T\)的生成元g,然后验证每个元素是否和pairing的结果相同,以一个元素为例: \[ e(\sum^m_{i=1}l_{1i}\cdot a_iG_1,\sum^m_{i=1}r_{1i}\cdot a_iG_2)=g^{\sum^m_{i=1}o_{1i}\cdot a_i} \]\(\mathbb G_T\)中的运算复杂度太大,更简单的做法是对\(O\cdot\text{witness}\)中witness的每个元素也乘以\(G_1\),与\(G_2\)做pairing,然后比较两边pairing是否相等,即: \[ e(\sum^m_{i=1}l_{1i}\cdot a_iG_1,\sum^m_{i=1}r_{1i}\cdot a_iG_2)=e(\sum^m_{i=1}o_{1i}\cdot a_iG_1,G_2) \] 存在的问题:一是需要大量的pairing计算,二是加密后的witness可能会被尝试出来(因为\(a_i\)的取值一般不大)。

0.6 QAP

QAP即二次算术程序(Quadratic Arithmetic Programs),是在R1CS的基础上对算术电路更高级的表示。

为什么要将R1CS转换成QAP?判断R1CS是否正确需要将witness代入矩阵,检验每一行是否相等,复杂度为\(O(n)\)。而如果将其转换成多项式形式,那么根据Schwartz-Zippel引理在\(O(1)\)时间内就能完成验证。

对于R1CS的矩阵形式:\(O\cdot\text{witness}=(L\cdot\text{witness})\circ(R\cdot\text{witness})\),分别将\(L,R,O\)矩阵的每一列视为一个向量,按前面的方法插值得到其对应的多项式。对于\(L\),插值出的多项式记为\(u_1(x),u_2(x),\cdots,u_m(x)\),它们的次数为\(n-1\),示意如下: \[ L= \begin{bmatrix} l_{11} & l_{12} & l_{13} & l_{14}\\ l_{21} & l_{22} & l_{23} & l_{24}\\ l_{31} & l_{32} & l_{33} & l_{34} \end{bmatrix} = \underbrace{\begin{bmatrix}l_{11}\\l_{21}\\l_{31}\end{bmatrix}}_{u_1(x)} \underbrace{\begin{bmatrix}l_{12}\\l_{22}\\l_{32}\end{bmatrix}}_{u_2(x)} \underbrace{\begin{bmatrix}l_{13}\\l_{23}\\l_{33}\end{bmatrix}}_{u_3(x)} \underbrace{\begin{bmatrix}l_{14}\\l_{24}\\l_{34}\end{bmatrix}}_{u_4(x)} \] 同理\(R\)对应的多项式记为\(v_1(x),v_2(x),\cdots,v_m(x)\)\(O\)对应的多项式记为\(w_1(x),w_2(x),\cdots,w_m(x)\)。记: \[ u(x)=L\cdot\text{witness} =[u_1(x),u_2(x),\cdots,u_m(x)] \begin{bmatrix}a_1\\a_2\\\vdots\\a_m\end{bmatrix} =\sum_{i=1}^ma_iu_i(x) \]

同理\(v(x)=R\cdot\text{witness}\)\(w(x)=O\cdot\text{witness}\),它们的次数都是\(n-1\)。这里统一列出便于查看: \[ \begin{align} u(x)&=\sum_{i=1}^ma_iu_i(x)\\ v(x)&=\sum_{i=1}^ma_iv_i(x)\\ w(x)&=\sum_{i=1}^ma_iw_i(x) \end{align} \] 对应R1CS的\(O\cdot\text{witness}=(L\cdot\text{witness})\circ(R\cdot\text{witness})\),现在我们需要验证\(u(x)v(x)\overset{?}{=}w(x)\)

对于多项式加法的验证,如\(u(x)+v(x)\overset{?}{=}w(x)\),我们可以通过前面讲过的方法,随机取\(x_0\)判断\(u(x_0)+v(x_0)\)是否等于\(w(x_0)\),来判断。

但是乘法不一样,因为相乘之后次数变了,并不能保证在除\(x=1,2,\cdots,n\)的点之外相等。如\(u(x)=x\)\(v(x)=x+1\)\(w(x)=4x-2\)\(x=1,2\)\(u(x)v(x)=w(x)\),但当取\(x=3\)\(u(3)v(3)=12\ne10=w(3)\)。本质上就是因为\(u(x)v(x)\)已经是二次多项式的了,不可能处处与一次多项式\(w(x)\)相同。

解决的办法是让\(u(x)v(x)\)减去一个多项式\(s(x)\),使得

  • \(u(x)v(x)-s(x)\)\(w(x)\)次数相同;
  • \(1,2,\cdots,n\)上取值相等。

满足了这两条实际上\(u(x)v(x)-s(x)\)就等于\(w(x)\)了。这样的\(s(x)\)是容易构造的,可以将\(s(x)\)写成\(s(x)=h(x)t(x)\),其中\(t(x)=(x-1)(x-2)\cdots(x-n)\),这样\(s(x)\)\(1,2,\cdots,n\)的取值都为\(0\)\(u(x)v(x)\)减去\(s(x)\)就不会影响在\(1,2,\cdots,n\)的值了。

另一种理解是: \[ u(x)v(x)\equiv w(x)\pmod{t(x)} \]

最终QAP要验证的公式为\(u(x)v(x)-s(x)=w(x)\),移项展开得: \[ u(x)v(x)=w(x)+h(x)t(x) \] 其中\(h(x)\)通过\(\frac{u(x)v(x)-w(x)}{t(x)}\)来计算,如果witness不满足约束则无法计算出\(h(x)\)

为什么是对\(L,R,O\)的列进行插值而不是对\(L\cdot\text{witness},R\cdot\text{witness},O\cdot\text{witness}\)的列?因为\(L,R,O\)是公开的,对其插值的结果是可以被验证的。而witness是证明者私有的,对\(L\cdot\text{witness},R\cdot\text{witness},O\cdot\text{witness}\)进行插值的结果无法验证。

如何验证?验证有什么问题?验证者选择一个随机数\(\tau\)发送给证明者,证明者返回\(u(\tau),v(\tau),w(\tau),h(\tau),t(\tau)\)的值,验证者检验是否满足上述等式。问题在于如何保证证明者是根据QAP进行的正确的多项式求值(evaluation)。


零知识证明(零)前置知识
https://shuusui.site/blog/2025/07/23/zkp-pre/
作者
Shuusui
发布于
2025年7月23日
更新于
2025年7月25日
许可协议