zk-SNARKs简洁的非交互式零知识证明学习(一)

密码学区块链技术密码学

字数统计: 4.6k阅读时长: 19 min

 2021/08/25 

zk-SNARKs即"zero knowledge Succinct Non-interactive Argument of Knowledge"，第一次见到是在ZCash的介绍里 Zcash is the first widespread application of zk-SNARKs, a novel form of zero-knowledge cryptography. ...，他给出了简洁的非交互式零知识证明的办法，属于零知识证明的一种。

zk-SNARKs的第一个应用就是Zcash，可以做到毫秒级的验证效果，但是产生这个证明的过程较为复杂。这篇开始学习一下流程。大致上流程如下：

Computation计算问题 -> Arithmetic Circuit代数电路 -> R1CS -> QAP -> zk-SNARK

基本概念

什么是零知识证明

一句话就可以说明了：

“Zero-knowledge” proofs allow one party (the prover) to prove to another (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself. For example, given the hash of a random number, the prover could convince the verifier that there indeed exists a number with this hash value, without revealing what it is.

即实现在不泄露真实信息的情况下证明这个我确实拥有这个信息，比如上面提到的，我可以提供给你哈希值供校验，而无需提供秘密信息本身。

什么是zk-SNARKs？

zk-SNARKs全称是Zero-knowledge Succinct Non-interactive Argument of Knowledge，名字挺长的，我们分开来看一下都包含了哪些主体：

Zero-knowledge：即零知识证明，zk-SNARKs属于零知识证明的一种
Succinct：意为简洁的，zk-SNARKs的证明耗时为毫秒级，且证明的大小也仅为几百个字节
Non-interactive：即非交互式的，而传统的零知识证明，证明者prover和验证者vervifier需要来回的交互，效率较低。zk-SNARKs属于非交互式的零知识证明，你只需要给验证者提供证明，正确与否之后的操作验证者会自行执行，不会有交互反馈。
Argument of Knowledge：这个很多人都没有提到，官网也说没必要深入探讨，但是这里还是说一下。零知识证明是proof of knowledge，保证了一个假的prover不能成功证明一个错的结论，而Argument of knowledge在这个保证上加了一个条件--只针对计算有界的provers(computationally bounded provers)。

为什么用zk-SNARKs以及Future Application？

所以这个东西它用起来效率比较高，不过目前来看证明的实现比较复杂，产生证明效率较低，离实际应用还有一段距离[1]。因为属于计算密集型，所以对很多应用不够友好，官方也叙述了这一缺点以及表示正在改进：

Theoretically, you can use a zk-SNARK to verify any relation without disclosing inputs or leaking information. —Generating proofs for complex functions is still too computationally intensive to be practical for many applications. but the Zcash team is pushing the boundaries for optimizing zk-SNARKs, and is already breaking new ground with more efficient implementations.

官方指出zk-SNARKs可以作为一个组件添加到现存的区块链技术中，称为ZSL(Zero-knowledge Security Layer)。

此外，zk-SNARKs在整个代数电路的运算过程中都是在椭圆曲线上的，且依赖于配对密码学(pairing-based cryptography)，关于配对密码学的概念、可使用的编程依赖库(比如jpbc)可以参考我兄弟的文章：B1ank (blank-vax.github.io) - 基于配对的密码学-基础知识及JPBC库。

[1]李佩丽, 徐海霞. 区块链用户匿名与可追踪技术[J]. 电子与信息学报, 2020, 42.

计算步骤概述

这里直接用一张图来总结，这张图包含了本篇文章的全部内容，具体的计算细节你可以对照我的文章来看。图片来源:zk-snark之R1CS->QAP_江小白希的博客-CSDN博客

20191029203605385

下面具体叙述一下重要概念以及计算步骤。

计算步骤

这里以V神的教程为基础，更为详尽的在计算方面复现一下整体思路流程。

大体上来说我们的步骤如下：

官方给出的例子是这样的一个函数，类似python代码：

1
2
3

def qeval(x)：
    y = x ** 3
    return x + y + 5

接下来我们像上面那个图一样，将这个函数变为zk-SNARKs。

计算问题转化为代数电路(The Arithmetic Circuits)

代数电路简介以及重点说明

电路(Circuits)可以有效的来表示计算模型。一个电路的主体是线路(wires)和门(gate)，其中线路携带值，而门则代表对这些值所进行的操作。

最简单好理解的就是逻辑电路：

值只能为0或1
门包含与(AND)、或(OR)、非(NOT)

而在zk-SNARKs的计算过程中，我们使用代数电路(Arithmetic circuits)，一个例子如上图，实际上就是一个代数电路的图，它是一种有向无环图，流动方向始终从输入到输出，其中的门实际上包括的就是模运算中的加减乘除(modular addtion and multiplication)。使用模运算是因为整个运算都是在椭圆曲线上完成的。

对于上图中的等式：\(a^2+ab-b=n\)，实际上，可以将这个式子化为两个门，我们用var等变量名来代替： \[ \begin{align} var_3 = var_1 * var_2 \tag{1}\\ var_6 = var_4 + var_5 \tag{2} \end{align} \]

观察一下就可以发现\(a^2\)和\(ab\)实际上就是1式的类型，加减则是2式的类型，我们可以用伪代码来表示：

tmp_1 = a * a
tmp_2 = a * b
tmp_3 = tmp_1 + tmp_2
tmp_4 = tmp_3 - b

最后我们的\(n\)值就保存在了\(tmp_4\)中。

在零知识中，该电路实际上就相当于Verifier，对于一个正确的proof，prover输入有效的witness，电路应该返回1。

计算问题展开 (Flatttening)

这是第一步，我们要将原始的功能代码转变为基本算术单元，就像上一节那样。

这里再看一下源代码：

1
2
3

def qeval(x)：
    y = x ** 3
    return x + y + 5	// 即返回c

这里有两种类型：加法和乘法，或者更为抽象一点，只有两种类型，也就是两种门

x = y，单纯的赋值
x = y (opt) z，其中opt代表任意的一次计算，可能为加减乘除

所以我们进行展开：

sym_1 = x * x
y = sym_1 * x	// y = x**3
sym_2 = y + x   // x^3 + x
~out = sym_2 + 5 // x^3 + x + 5，完成计算

最后我们的输出就是~out变量了。其实思路很简单吧？到这里我们就生成了两种门。

展开后的式子其实计算结果是一样的，好比我们x取3，那么最终return就是35，对于上面的式子：

x = 3
sym_1 = 9
y = 27
sym_2 = 30
~out = 35 -- 最终结果

R1CS(a rank-1 constraint system)

R1CS简介以及重点说明

上面也说到了，我们首先要将待计算的式子简化为一系列的基本计算，构成代数电路，其中每一条线都代表这一个数值的传递，门则代表一次基本计算。那么下一步就是生成一系列的约束(Constraints)，这些约束可以断言(assert)一个门计算已经正确执行，且内部的赋值是一致的。这样的约束保证了门计算的准确性，所以我们需要给每一个门都生成一个rank-1的约束，rank-1我也不知道怎么理解，姑且认为是一条约束吧。所有这些约束条件集合起来就是R1CS(A Rank-1 Constraint System)。

具体有什么作用呢？如果一个假的prover向verifier进行证明的时候，由于他不知道正确的witness，并拿了个假的输出来糊弄verifier，因为他的输入就是错的，所以在代数电路中运算的时候，某一个门的输出就会导致该门的约束无效。

那么问题来了，实际中一个代数过于复杂怎么办？一个个去验证岂不是很花时间？所以zk-SNARKs将所有这些约束都封装到了三维向量中，以此来同时验证整个约束集。这三个多项式向量下一小节会看到，它们就是A、B、C。

门运算变换为R1CS

上面说了zk-SNARKs将R1CS整理为了一个三维向量，其中每一个门我们也一样用一个三维向量来描述：(a, b, c)，最终所有门三维向量的组合我们用(A, B, C)表示，其中的A由所有的a组成，另外两个也类似。

那为啥要用三元组呢？因为从上面我们简化后的计算来看，我们右边都最多只有两个数，并进行赋值，所以用三元组就可以表示这个等式了。

那么这个三维向量的a、b、c有什么关系呢？我们首先定义这个R1CS的解是s，则有如下关系： \[ \begin{align} (s·a) * (s·b) - s·c = 0 \\ or \\ (s·a) * (s·b) = s·c \end{align} \]

根据我们简化后的运算，我们可以看到需要如下几个变量，其中~one是常量1，用来得到我们需要的常量，比如等式中的5。

1	[~one、x、~out、sym_1、y、sym_2] // 下标从0开始，可以看做一个数组

那么对于第一个门:

1	sym_1 = x * x

它的三元组如下

1
2
3

a = [0, 1 ,0, 0, 0, 0] // 我们可以看到第二个元素也就是下标1的位置为1，代表输入x
b = [0, 1, 0, 0, 0, 0] // 输入x
c = [0, 0, 0, 1, 0, 0] // 代表得到sym_1，而sym_1的下标是3

是不是发现有点像往内存单元里面填数据的感觉？对号入座，那么剩下三个门及其三元组如下：

// y = sym_1 * x
a = [0, 0, 0, 1, 0, 0] // 输入sym_1
b = [0, 1, 0, 0, 0, 0] // 输入x
c = [0, 0, 0, 0, 1, 0] // y = sym_1 * x

// sym_2 = y + x
a = [0, 1, 0, 0, 1, 0] // 输入y + x
b = [1, 0, 0, 0, 0, 0] // 相当于1*y + 1*x，即x + y
c = [0, 0, 0, 0, 0, 1] // sym_2 = y + x

// ~out = sym_2 + 5
a = [5, 0, 0, 0, 0, 1] // 输入sym_2 + 5
b = [1, 0, 0, 0, 0, 0] // 相当于1*sym_2 + 1*5，即sym_2 + 5
c = [0, 0, 1, 0, 0, 0] // ~out = sym_2 + 5

然后我们把4个门的a放到一起就是A，剩下的一样。比如对于有k个门的R1CS，它的A： \[ A = \begin{bmatrix} A_1[1]&A_1[2]&... &A_1[n]\\ &...\\ A_k[1]&A_k[2]&... &A_k[n]\\ \end{bmatrix} \] 所以我们就得到了最终的R1CS： \[ A = \begin{bmatrix} 0, &1, &0, &0, &0, &0\\ 0, &0, &0, &1, &0, &0\\ 0, &1, &0, &0, &1, &0\\ 5, &0, &0, &0, &0, &1 \end{bmatrix} B = \begin{bmatrix} 0, &1, &0, &0, &0, &0\\ 0, &1, &0, &0, &0, &0\\ 1, &0, &0, &0, &0, &0\\ 1, &0, &0, &0, &0, &0 \end{bmatrix}\\ C = \begin{bmatrix} 0, &0, &0, &1, &0, &0\\ 0, &0, &0, &0, &1, &0\\ 0, &0, &0, &0, &0, &1\\ 0, &0, &1, &0, &0, &0 \end{bmatrix} \]

QAP(quadratic arithmetic program)

概念

Quadratic Arithmetic Program简称QAP，我也不知道叫啥，应该是二次代数规划吧emmmm。他的作用如下：

a way of representing any computational problem with a polynomial equation that is much more amenable to various forms of mathematical trickery.

即他可以用多项式等式来表示一个可计算的问题，更便于数学计算。那为啥我们要把R1CS转变为QAP呢？这俩啥区别？

实际上QAP和R1CS的逻辑是一样的，区别在于将向量的点积运算转变为了多项式。下面阐述一下过程。

R1CS计算QAP

在上一章中我们得到了多项式x^3 + x + 5的R1CS，这个R1CS的内容Prover和Verifier双方都知道。接下来我们来构造QAP。

我们都有什么？我们有四个门的对应的(a, b, c)三个向量，其中a，b，c长度均为6
我们要做什么？我们要把这一共四个门的、每个门三组、每组包含长度为6的三个向量的数据，依旧转变为(A，B，C)，但是区别是A，B，C每个组包含了长度为4的6个向量，即6*4，而不是R1CS那样的4x6

那我们怎么转换呢？这里要用到一个定理：拉格朗日插值法，这里很快过一下：

拉格朗日插值法(Lagrange Interpolation Polynomial)指可以找到一个多项式，该多项式恰好在各个观测的点取到观测值，说人话就是找到一条过指定的一些点的一条曲线。

公式内容如下：

现有点\((x_0,y_0),(x_1, y_1),...,(x_{n-1}, y_{n-1})\)，设\(D_n=\{0,...,n-1\}\)，\(B_k=\{k|k \ne i,i \in D_n\}\)。对于每一个\(x\)存在一个符合观测值的多项式\(p_k(x)\)，使\(p_k(x) = \prod_{i \in B_k}\\limit\frac{x-x_i}{x_k-x_i}\)。则满足上述所有观测点的\(f(x)=\sum_{j=0}^{n-1}y_ip_j(x)\)

看着比较复杂，实际上比较好记，即对于每一个点的多项式，它是这么来的：用未知数x减去其他点的x的乘积除以该点x减其他点的x的乘积，最后乘一个该点y，最后的最后把所有点多项式一加就可以了。给一个例子吧，过点(1, 3)，(2, 2)，(3, 4)的函数：

\[ f(x) = \frac{(x-2)(x-3)}{(1-2)(1-3)}\cdot3 + \frac{(x-1)(x-3)}{(2-1)(2-3)}\cdot2 + \frac{(x-1)(x-2)}{(3-1)(3-2)}\cdot4=\frac{3}{2}x^2-\frac{11}{2}x+7 \]

该算法的时间复杂度为O(n^3)其中n代表点的个数，而每个点计算多项式需要O(n^2)的时间复杂度，我们可以利用快速傅里叶变化来降低时间复杂度，因为实际中会有成千个门。然后我们再来看怎么转换我们的R1CS，我们以A矩阵为例，B，C都要进行相同的操作。

这里重点来了，很多网上的文章都没有说这一部分是怎么来的，包括最开始那张总结全部流程的图，A是啥？可以看成矩阵，那我们要使用拉格朗日插值法得有点啊，纳闷了点哪来的啊？官网描述的我反正来来回回看了三四遍没看懂啥意思：

What we are going to do is take the first value out of every a vector, use Lagrange interpolation to make a polynomial out of that(where evaluating the polynomial at i gets you the first value of the ith a vector)

然后从最后这句话自己试出来结论了，首先我们取A矩阵的第一列作为纵坐标，而横坐标则是行数，上面我们得到的A： \[ A = \begin{bmatrix} 0, &1, &0, &0, &0, &0\\ 0, &0, &0, &1, &0, &0\\ 0, &1, &0, &0, &1, &0\\ 5, &0, &0, &0, &0, &1 \end{bmatrix} \]

则四个点分别为：(1, 0)，(2, 0)，(3, 0)，(4, 5)，然后对这四个点进行拉格朗日插值法得到多项式：

\[ f(x)=\frac{(x-1)(x-2)(x-3)}{(4-1)(4-2)(4-3)}\cdot5=\frac{5}{6}x^3-5x^2+\frac{55}{6}x-5 \] 然后我们把这个多项式转成行向量，即从左到右依次是低次项到高次项的系数，实际上就是多项式的矩阵化。

得(也就是V神的结果)，B，C同理：

上述的数据就是QAP了，当然上述的过程只需要执行一次，一旦QAP参数生成后，就可以复用了。

假如x取1，那么就可以得到如下结果(就是多项式赋值):

这恰好和我们R1CS的A、B、C的第一行行向量对应，这也就是作者说的那句： > where evaluating the polynomial at i gets you the first value of the ith a vector)

你x取多少，A算出来的就是R1CS中第x个a，你比如x取1上面算出来是[0, 1, 0, 0, 0, 0]，这不就是我们R1CS的第1行吗？不就是第一个门的a吗？

QAP正确性检查

好了到这里其实本文主体就结束了，下来我们验证一下QAP，这样我们就不需要去验证我们的R1CS了。在验证过程中，如果每一个门(x=1,2,3,4)他的多项式计算出来是0，那就对了，否则就不对，比如y = x * sym_1结果x=2和sym_1=2，y=5，那显然输入输出是不匹配的。

具体计算方法呢？

\[ h=\frac{(A \cdot s)*(B \cdot s) - C \cdot s}{Z}, Z=(x - 1)*(x - 2)*(x - 3)..., t=(A \cdot s)*(B \cdot s) - C \cdot s \]

其中Z是一个在任意门x都为零的多项式，即有k个门，则Z就乘到(x-k)。

所以有：

1
2
3

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

这里我们就需要多项式矩阵化的乘法规则了，这个属于单另的知识，包括怎么矩阵化后进行多项式的乘法和除法，这部分请参考学习：多项式的矩阵表示及乘法运算 - 知乎 (zhihu.com)。

所以(A·s)*(B·s)-C·s：

1	t=[-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

又因为Z=(x - 1)*(x - 2)*(x - 3)(x - 4)，所以

1	Z = [24, -50, 35, -10, 1]

我们得到最终的h，且该结果无余数

1	h = t / Z = [-3.666, 17.055, -3.444]

还记得前面说过R1CS的解(solution)是s吗，对于x取3，记不记得我们的s是[1, 3, 35, 9, 27, 30]？如果说我们的solution是假的，比如把最后的30换成31，这就会导致当x=3的时候t算出来不是0(是-1)，且t/Z的结果也会有余数(结果是[-5.0, 8.833, -4.5, 0.666])