浅谈零知识证明之三：zkSNARK证明体系的实现

15 Mar 2020

距离上期更新已经过去了几个月了。前段时间回到美国之后，忙了好一阵子，这学期跟着Dan继续学习了密码学（CS255 Introduction to Cryptography）。这两天美国新冠疫情严重，封城在家里，正好有空把我的零知识证明笔记拿出来整理一下，继续写第三篇。

这一期，我们接着上一次讲过的数学运算电路，讲一讲简短零知识证明（zkSNARK）体系的具体实现和背后的原理。由于内容实在太多，我打算把这期的内容一分为二。

证明体系回顾

因为距离上一期已经过去了一段时间，我们可以先来回顾一下上次提到的简短证明体系的三个核心算法：Setup，Prove和Verify。

1. $Setup(C) \rightarrow (S_p, S_v)$：通过实现约定好的电路，生成后续需要使用的随机参数$S_p$和$S_v$。
2. $Prove(S_p, x, w) \rightarrow \pi$：通过公有输入$x$和私密输入$w$，生成零知识证明。
3. $Verify(S_v, x, \pi) \rightarrow Yes/No$：验证证明。

一个健全的零知识证明体系需要满足一定的要求。

第一条要求是完整性，也就是说如果秘密输入$w$满足了电路的要求，那么通过$w$生成的证明$\pi$一定可以被验证通过。用公式来表达就是： \(Verify(S_v, x, Prove(S_p, x, w)) = Yes \iff C(x, w) = 0\) 第二条要求是知识证明（Proof of Knowledge）， 换句话来说其实就是证明方一定得拥有一些我们没有的信息，我们需要知道这个$w$是真真切切存在的，是可以被提取出来的。具体的知识证明比较复杂，需要涉及到一个提取器（Extractor）的概念，详细可以参照郭宇老师的文章。

第三条要求就是简短证明（SNARK）。这个证明体系一定得简短高效才能满足我们的要求，不然抛开零知识的要求的话，还不如直接把原有的$w$直接告诉对方来的简单。用Big O来表示需要的时间和空间的话，具体是这样的：

1. 证明所需时间：$time(P) = O( \mid C \mid )$， 和电路大小成正比。
2. 证明大小：$ \mid \pi \mid = O(log \mid C \mid )$，和log电路大小成正比。
3. 验证所需时间：$time(V) = O( \mid x \mid + log \mid c \mid )$，和公有输入$x$的大小再加上log电路大小成正比。

第四条要求就是零知识，也是相对来说最简单描述的要求。总的来说就是公有输入$x$和证明$\pi$不能暴露任何与私密输入$w$有关的信息。

我们把这四条要求牢记在心，接下来我们可以开始探索，传说中的零知识证明体系到底是如何实现的了。

PCP定理与Kilian SNARK

如果要完整的讲起简短证明的历史，我们需要回到1992年，一位叫Kilian的密码学家第一次正式的提出了SNARK的概念——简短、无交互性知识证明。

SNARK的概念之所以能够被提出，是因为在1990年一个著名的复杂性理论定理被证明了。这个定理叫做PCP，全称Probabilistically Checkable Proof，意思就是，所有的NP问题，都可以在多项式时间内通过概率验证的方法被证明。

什么叫概率验证呢？其实我们可以把它理解为随机抽查：如果A有一个很复杂的问题的解，但是这个解很长很长，那么B就可以通过随机抽查这个解的某几位来大概确定A的解是否准确。因为A不知道B会抽查哪一位，所以A没有任何有利的方法作弊，B每抽查验证成功一次，A的解是错误的解的可能性就下降一次。

因为所有的NP问题都可以有效地转换为数学运算电路，PCP定理指出，对于所有的电路$C$，我们都可以构造一套概率验证体系$(S, P, V)$，其工作方式如下：

\[\forall C: \exists \text{ Proof System } (S, P, V): \\ S(C) \rightarrow (C, S_v)\]

生成算法Setup还是和以前一样，把电路$C$转换成后续会用到的随机参数。

我们可以画个图来看一看证明和验证算法是如何运作的。

简单来说，这个图其实和我们之前看到的证明方与验证方都差不多：证明方通过公有和私密输入生成一个证明$\pi$，并且把证明$\pi$存入只读区域后共享给验证方查看（只读区域可以防止双方篡改证明内容）。唯一不同的是验证方并不能看到所有的$\pi$，只能通过一个query机制来检查这个证明$\pi$随机的$k$位数。通过看完这$k$位数之后，验证方就需要输出验证结果。

举一个简单的例子：假如A需要向B证明她拥有一个从0到100依次升序排列的数组，那么B可以通过随机抽查的方式来验证A的数组是否正确排列。B可以抽查第49位是不是48，第3位是不是2等等来确定A是否真的拥有这么一个数组。当然，A也有可能是运气好，除了第49位和第3位其他都是乱序的。不过当抽查的次数越来越多，A作假的可能性也会越来越低。抽查的总次数$k$代表了整个证明体系的安全性。

这套随机抽查的系统也需要满足两个要求：

1. 完整性（Completeness）：就像之前提到的一样，如果证明方是诚实的，那么$C(x, w) = 0$，所以验证方一定会验证通过。
2. 健全性（Soundness）：如果证明方不诚实，作假自己的答案，那么也就是说$\nexists w:C(x, w) = 0$， 验证方验证通过的可能性会小于一个由安全指数$k$决定的概率区间：$Pr[V=Yes] \le (\frac{1}{2})^{k}$。

满足这两个要求之后，这一套PCP证明系统就可以用于生成验证证明了。

从经典PCP到Kilian SNARK

但是我们会发现，简单的PCP系统很难满足简短证明的要求。

就像上文所描述的B验证A的数组的问题一样，A的证明$\pi$就是她的整个数组，而且还需要导出到只读区域放置篡改。这样一来，虽然B验证的次数很简短（$k$次），但是从中还是难以避免这个庞大的证明$\pi$可以储存在哪里的问题。如果A要向B证明自己拥有一个长度为100万的数组，那么我们就需要额外规划100万长度的空间来存储证明。

这个时候，Kilian提出了第一个真正具有简短性的证明体系：Kilian SNARK。

Kilian SNARK其实就是对PCP证明系统做出了一个小小的改进。与其我们把证明全部导出来让A后续的时候无法篡改，我们可以使用Merkle承诺和Merkle证明的方式来确保A不会篡改她自己的数据。这样一来，我们就不需要一个中间方来存储A的大量证明数据了。（关于Merkle树和证明在前面写的几篇文章中有所提到过。）

改进过的Kilian SNARK的具体证明步骤如下：

1. 首先，证明方生成一系列需要的证明$\pi$，并且向验证方提供$\pi$的Merkle承诺$C_\pi$。
2. 随后，验证方随机的抽查证明$\pi$其中的某几项。
3. 证明方向验证方展示抽查的那几项的值，并且附加一个Merkle证明来证明这几个值真的是在原有的证明$\pi$当中。验证方通过对比Merkle证明得到的Merkle承诺是否与最早的时候得到的承诺相等来确保证明方没有作假。
4. 同样的协议进行$k$轮之后，验证方输出验证结果，结束证明。

Kilian SNARK通过使用Merkle树的结构，巧妙的把证明的大小从原有的$O( \mid C \mid )$降低到了$O(log \mid C \mid )$。

从交互式到非交互式

到了这一步，我们距离真正的Kilian SNARK已经非常接近了。现在唯一不一样的地方在于，我们的证明系统仍然是交互式的，在证明的过程中，一直需要验证方在线，用于提供随机抽查的随机参数。然而Kilian SNARK是非交互式的，也就是说证明方在提交证明的时候不需要验证方在线，验证方也可以在后面任意一个时间点来验证这个证明的正确性。这个时候，我们就需要Fiat-Shamir Heuristic的帮助。

Fiat-Shamir Heuristic是一个1988年被提出的算法，可以把任何交互式的随机验证协议(Public-coin Protocol)转换为非交互式的协议。我们来看看它是如何实现的。

首先，我们需要随便定义一个交互式的随机验证协议$I$：

图上表示的是非常笼统的交互式证明$I$，这个流程图同样也适配于我们之前讨论的交互式Kilian SNARK。总的来说就是证明方会根据验证方提供的随机字串$rand_i$来返回对应的消息$m_i$。

接下来，我们用Fiat-Shamir Heuristic把$I$转换成非交互协议。

首先，我们需要一个安全的哈希函数$H$（cryptographic hash function）。我们同时也需要假设这一类哈希函数是一个随机预言机，也就是说，无论输入的是什么，输出的值我们都可以看作是一个和输入没有关联的随机数。

当我们有了这个假设之后，我们就可以把交互式协议$I$压缩成非交互式协议$I’$了：

1. 首先，证明方需要生成消息$m_1$。然后根据$m_1$的值来生成原本由验证方来生成的$rand_1 \leftarrow H(x, m_1$。
2. 随后，证明方根据$rand_1$的值来生成消息$m_2$，然后同理得到$rand_2 \leftarrow H(x, m_1, m_2)$。
3. 最后，证明方生成$m_3$，并且把$\pi = (m_1, m_2, m_3)$一并发给验证方。

当验证方收到证明$\pi$之后，他只需要根据这几个数字和哈希函数$H$重新生成$rand_1, rand_2$就可以验证证明是否准确了。

通过巧妙运用哈希函数，我们把整个协议变成了非交互式的：证明方可以一口气生成所有的内容，发给验证方之后就可以走人了。验证方则可以在任何时候打开证明$\pi$，计算出随机数$rand_1, rand_2$并且验证证明。这样一来，证明方甚至可以把证明直接发到网上，然后验证方可以定期下载这些证明并且验证它们。

到这里， 我们基本上就看到Kilian SNARK的全貌了：

首先，证明方向验证方展示自己证明$\pi$的Merkle承诺，然后根据这一系列输出的哈希值来得到一个随机数$rand_1$。随后证明方揭露$\pi$在$rand_1$位置上的值，并且提供对应的Merkle证明。然后再根据前一步得到的值来计算出新的哈希值$rand_2$，然后以此类推，揭露在$rand_2$上的值。如此往复这个过程，直到揭露$k$个位置结束。

当整个过程结束之后，证明方只需要把每个对应位置的值和Merkle证明发给验证方，验证方就可以通过$H$来重新构造出随机数，并且验证证明了！

PS：“哈希函数是随机预言机”是一个非常强的假设，到现在也没有被彻底的证实（虽然也找不到反例来破解它）。虽然学术界并不敢轻下定论，业界已经在广泛的使用SHA256作为随机预言机来使用了。这也就是为什么这个算法一直被称作一个启发法（Heuristic）而不是一个算法（Algorithm）。

从PCP到LPCP

通过Kilian SNARK（PCP定理），我们已经可以构造出证明体系了。然而需要注意的是，PCP其实是一个非常笼统的定理，只是证明了NP范围内的问题可以通过随机抽验的方法来验证，但是并没有详细说明这个证明$\pi$到底是什么，也没有讲明白具体抽验的过程。

纯粹依赖于PCP猜数字抽查的Kilian SNARK其实效率非常低，生成一个问题的证明，可能就要花费半天时间。这对于我们在网络上的应用场景来说非常不现实。为了更加高效率的生成简短证明，我们要对PCP问题进行进一步的约束。

我们这次说的zkSNARK算法，其实也是基于PCP定理，但是对于PCP所描述的问题又加了一个约束：线性PCP（Linear PCP/LPCP）。

如果说PCP形容的是所有NP范围内的问题都可以通过简短的随机抽验来验证，LPCP则是说任意一个$d$阶的多项式$P$，都可以通过随机验证多项式在几个点上取值来确定这个多项式的每一项系数是否满足特定的要求。 \(P(x) = c_0 + c_1 \cdot x + c_2 \cdot x^2 + ... + c_k \cdot x^d\) 假如取值在$\mathbb{F}$域内的多项式$P(x)$拥有$(c_0, c_1, … c_d)$的系数，那么这个$d$阶多项式在每个点上的取值一定是特殊的。换句话说，如果我们还有一个$d$阶的多项式$Q(x)$，哪怕$Q$的系数稍微变了一点点，整个多项式的取值马上会发生巨大的改变。如果两个多项式$P, Q$的系数不一样，那么如果我们随机验证一个点$r$的取值$P(r), Q(r)$，这两个值相等的几率会非常非常小： \(P \ne Q, r \stackrel{R}{\leftarrow} \mathbb{F} : Pr[P(r) = Q(r)] \le \frac{d}{ \mid \mathbb{F} \mid }\) 精确的来说的话，两个$d$阶的不同系数的多项式，在所有整数范围$\mathbb{F}$内，最多也只会有$d$个点重合，其他的点因为系数不同，是不会重合的。

回到上文讨论的例子：A想要向B证明她拥有一个0到100升序排列的数组。如果B只是每次选其中的一个数字检查，就算检查通过了，那么还是有很大的可能性A在其他位置上的数字不符w合要求，但是B只能通过多次抽查来降低A作弊的几率。这样不仅需要抽查很多次，而且总是难以保证没有抽查到的数字符合要求。

但是如果我们把这101个数不是放在一个数组里让B抽查，而是作为一个100阶多项式$P$的系数$(c_0, … c_{101})$，那么B只需要检查这个多项式在任意随机数$r$上的取值$P(r)$，就可以马上知道A是不是真的拥有这101个数字。 \(P(x) = c_0 + c_1 \cdot x + ... + c_d \cdot x^d \\ Q(x) = 0 + 1 \cdot x + ... + 100 \cdot x^d \\ P(r) = Q(r) : Pr[P = Q] \ge 1 - \frac{d}{ \mid \mathbb{F} \mid }\) 我们可以看一下上面的公式，A把她的101个数字组成了多项式$P$，B在自己心中根据自己期待的检查结果（0到100升序）组成了多项式$Q$。此时如果B随机抽查了一个点$r$并且发现$P(r) = Q(r)$，那么B基本上已经可以完全相信P和Q是相等的，也就代表了A的101个数字和B想要的数字是相同的了。

这种通过多项式系数来检查数字关系的方法效率很高，就仿佛像我们不是一个一个数字抽查，而是一次性的抽查了所有数字之间的关系一样。通过简短的几次随机取值验证，验证方就可以立刻验证证明方是否真的拥有私密的$w$，证明方作假的几率也几乎为零。

高效率简短证明体系（Efficient SNARK）

当我们知道LPCP可以使用多项式来大大提高随机抽查验证的效率之后，我们就可以开始搭建简短证明体系了。整个证明体系将会由以下几步来完成：

1. 将数学运算电路$C$转化为到R1CS程序矩阵。
2. 从R1CS程序矩阵还原成多项式。
3. 用多项式表达式定义LPCP。
4. 从多项式LPCP到可信初始化（trusted setup）的简短零知识证明（zkSNARK）。

从电路到R1CS

我们首先来看一看，如何把真正想要解决的问题（数学运算电路）转化为上文描述过的多项式。

我们在前一篇文章里详细谈论了怎么把一个问题，比如验证一个值$w$是否在可限的取值范围内，转换为一个数学运算电路$C$。但是一般来说，电路所代表的逻辑关系非常复杂，是很难直接推导出多项式来的。所以我们往往需要借助一个中间媒介，把电路先转换为一组矩阵关系。这种矩阵关系，我们称之为R1CS程序矩阵。

R1CS，全名为Rank-1 Constraint System，其实讲白了就是三个矩阵$A, B, C \in \mathbb{F}^{m \times (n+1)}$，这三个矩阵之间可以找到一组解$\vec{z}$，从而满足$A \cdot \vec{z}$和$B \cdot \vec{z}$的逐项积等于$C \cdot \vec{z}$。 \(\exists \vec{z} : (A \cdot \vec{z}) \circ (B \cdot \vec{z}) = C \cdot \vec{z}\) 逐项积的意思就是把两个一样大小的矩阵$A, B$的每个元素乘起来，最后得到一个同样大小的矩阵$C$。 \(A = \begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32}\end{bmatrix}, \ B = \begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22} \\ b_{31} & b_{32}\end{bmatrix}, \ C = A \circ B = \begin{bmatrix}a_{11} \cdot b_{11} & a_{12} \cdot b_{12} \\ a_{21} \cdot b_{21} & a_{22} \cdot b_{22} \\ a_{31} \cdot b_{31} & a_{32} \cdot b_{32}\end{bmatrix}\) 在我们想要证明的电路问题$C$里，我们可以把电路每个逻辑门之间的关系用矩阵$A, B, C$来表达，然后把电路的公有与私密输入$x, w$用$\vec{z} = \begin{bmatrix}1\x\w\end{bmatrix}$来表达。这样一来，只要R1CS矩阵$A,B,C$之间的逐项积关系成立，那么也就代表了这个电路的输入合法，即$C(x, w) = 0$。

区间证明的R1CS程序矩阵

讲完了R1CS的定义，我们来看看一个实际的例子。

既然讲到了区间证明，我们现在来尝试把一个简单的区间证明电路$C$转换为R1CS矩阵$A, B, C$。为了方便在文章中表述，我们假设要证明一下某个电路的私密输入$w$的值在0到15之间。这样的话，我们的数学运算电路如下： \(2^0 \cdot w_0 + 2^1 \cdot w_1 + 2^2 \cdot w_2 + 2^3 \cdot w_3 - w = 0 \\ w_0 \cdot (w_0 - 1) = 0 \\ w_1 \cdot (w_1 - 1) = 0 \\ w_2 \cdot (w_2 - 1) = 0 \\ w_3 \cdot (w_3 - 1) = 0\) 具体电路的构造原理我们在上一篇文章中有详细的介绍。大概来说就是我们先把私密输入$w$拆分为$w_0, …, w_3$的四个二进制位，然后分别约束这四位的取值只能是0或1。这里我们就来尝试把这一组逻辑表达式转化为R1CS程序矩阵。首先我们先根据电路的要求，找到公有输入$x$和私密输入$w$分别是哪些。因为这个问题不涉及到任何公有输入，所以我们的解$\vec{z}$就是： \(\vec{z} = \begin{bmatrix} 1 \\ w \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix}\) 然后，我们根据之前得到的5个表达式，可以依次转换为5行R1CS矩阵： \(A = \begin{bmatrix} 0 & -1 & 1 & 2 & 4 & 8 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}, \ B = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}, \ C = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}\) 我们把$\vec{z}$代入之后，发现$A, B, C$三个矩阵之间的逐项积正好还原了我们之前所推导出来的5条逻辑电路关系。也就是说，如果$\vec{z}$满足了R1CS程序，那也代表了$\vec{z}$当中的私密输入$w$满足了数学运算电路$C$。 \((A \cdot \begin{bmatrix} 1 \\ w \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix}) \circ (B \cdot \begin{bmatrix} 1 \\ w \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix}) = C \cdot \begin{bmatrix} 1 \\ w \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix} \iff \mathbb{C}(x, w) = 0\) 这样一来，我们就得到了可以构成R1CS程序矩阵的$A, B, C$了。得到R1CS的三个矩阵之后，我们不妨先观察一下矩阵的大小。

我们会发现，矩阵的长和辅助变量的数量$\vec{z}$中的辅助变量数量有关。因为最开始的输入通过数学运算门之后我们需要用辅助变量把这些中间值存起来，所以说辅助变量越多，电路里的数学运算门也越多。然而，比较有趣的是，矩阵的高其实只和电路中的乘法门的数量有关。乘法做的越多，矩阵就有越多行。原因其实很简单，我们如果把$A, B, C$的关系每一行拆开来看，我们可以发现其实每一行都表达了$\vec{z}$中的两组元素的线性组合相乘等于另一个$\vec{z}$中的元素的线性组合。这也就是说加法门表达的相加的关系可以压缩起来，然而乘法门代表的相乘的关系则每一个都要占据一行。我们把矩阵的每一行称之为约束（Constraint）。越复杂的电路，所需要的约束也越多。

熟悉布尔可满足性问题的朋友可能会对约束这个概念比较熟悉。只是在布尔问题当中，每一条约束都是逻辑表达式，而这里的约束则是数学表达式。如果我们找到了一组值$\vec{z}$使得R1CS的关系被满足了，那也就代表$\vec{z}$真的就是R1CS矩阵里描述的问题的解。

从R1CS到多项式

当我们将一个问题成功的从数学运算电路转换为R1CS程序矩阵之后，接下来需要做的就是把R1CS这个等式$(A \cdot \vec{z}) \circ (B \cdot \vec{z}) = (C \cdot \vec{z})$ 转化为用多项式的方法来表达，以便后续我们通过LPCP来生成简短证明。

在讲这个问题之前，我们先来看一看矩阵和多项式之间有什么样的关系。

了解过线性代数的朋友们也许可能会知道多项式插值问题（Polynomial Interpolation）。这个问题是这样的：给定任意一个$d$阶的多项式： \(f(x) = f_0 + f_1 \cdot x + f_2 \cdot x^2 + ... + f_d \cdot x^d\) 假如我们不知道这个多项式的系数$f_0, f_1, …, f_d$是什么，但是我们可以获得这个多项式$f$在随机选择的几个点上的取值$f(a_0), f(a_1), … , f(a_d)$，多项式插值定理证明了如果我们获得了$d+1$个不重复的取值，那么可以直接还原出整个多项式$f$的所有系数。

多项式插值的原理

听到这个概念，可能感觉还是有点云里雾里的。为了更方便理解，我们可以来看一个简单的例子。

假如我们像上文一样，有一个$d$阶的多项式$f$，然后想知道$f$在$a_0$这个点上的取值是什么。最简单的方法那就是把$a_0$代入成多项式里的$x$，然后计算出： \(f(a_0) = f_0 + f_1 \cdot a_0 + f_2 \cdot a_0^2 ... + f_d \cdot a_0^d\) 这一步非常好理解，不过就是把$x$替换成了$a_0$罢了。除了用这种逐项加起来的方法来表达$f(a_0)$，其实我们还可以用矩阵关系来表达： \(\begin{bmatrix} 1 & a_0 & a_0^2 & \dots & a_0^d \end{bmatrix} \times \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_d \end{bmatrix} = \begin{bmatrix} f(a_0) \end{bmatrix}\) 从上面的矩阵表达式中，我们可以看到，两边矩阵相乘的结果就是我们想要得到的多项式$f$在$a_0$点上的取值。不同的是通过拆分成两个相乘的矩阵的方法，我们把需要验证取值的点$a_0$和多项式的系数$f_0 \dots f_d$分离了出来。这样一来，我们可以在左侧的矩阵下面添加更多行，用同一个矩阵表达式来表示多项式$f$在$a_0 \dots a_d$点上的所有取值： \(\begin{bmatrix} 1 & a_0 & a_0^2 & \dots & a_0^d \\ 1 & a_1 & a_1^2 & \dots & a_1^d \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_d & a_d^2 & \dots & a_d^d \end{bmatrix} \times \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_d \end{bmatrix} = \begin{bmatrix} f(a_0) \\ f(a_1) \\ \vdots \\ f(a_d) \end{bmatrix}\) 当我们得到这个矩阵表达式之后，其实就可以很简单的理解多项式还原问题了。最左侧的大型矩阵，其实就是多项式$f$的$d+1$个独立取值点，构成的方式也非常简单，直接把取值的数字和他们的幂依次计算好放进去就得到了。这个大型矩阵在线性代数中被称为范德蒙矩阵，写作$V$。这个矩阵的特殊之处在于，只要$a_0 \dots a_d$都是不重复的数字，那么构成的范德蒙矩阵被证实一定是可逆的。也就是说，一定存在一个逆矩阵$V^{-1}$，使得$V \times V^{-1} = 1$。

那么范德蒙矩阵可逆代表了什么呢？这恰恰证明了多项式还原的定理，我们把上面的矩阵表达式稍微变动一下： \(\begin{bmatrix} 1 & a_0 & a_0^2 & \dots & a_0^d \\ 1 & a_1 & a_1^2 & \dots & a_1^d \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_d & a_d^2 & \dots & a_d^d \end{bmatrix}^{-1} \times \begin{bmatrix} f(a_0) \\ f(a_1) \\ \vdots \\ f(a_d) \end{bmatrix} = \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_d \end{bmatrix}\) 当我们把左侧的范德蒙矩阵替换成它的逆矩阵之后，我们就可以直接用逆矩阵乘以原表达式右侧多项式$f$在各个点上的取值结果，还原出多项式每一项的系数。

用区间证明的R1CS矩阵还原多项式

既然数学上已经被证明了，接下来我们就能用同样的方法，把R1CS程序矩阵的$A, B, C$三个矩阵变成多项式$P, Q, R$。为了方便描述，我们就用上面提到的区间证明的例子中得到的R1CS程序矩阵。

首先，我们观察发现，R1CS矩阵表达式中，$(A \cdot \vec{z})$得到的矩阵的大小正好是5x1： \(A \cdot \vec{z} = \begin{bmatrix} 0 & -1 & 1 & 2 & 4 & 8 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ w \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix} = \begin{bmatrix} -w + w_0 + 2w_1 + 4w_2 + 8w_3 \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix}\) 既然如此，那么我们可以把这个5x1的矩阵作为一个多项式$P$在5个点上的取值结果。我们假设有一个4阶的多项式$P$，然后这个多项式在从1到5的5个点上取值的时候，恰巧满足： \(\exists P(x) = f_0 + f_1 \cdot x + f_2 \cdot x^2 + f_3 \cdot x^3 + f_4 \cdot x^4 : \\ P(1) = -w + w_0 + 2w_1 + 4w_2 + 8w_3 \\ P(2) = w_0 \\ P(3) = w_1 \\ P(4) = w_2 \\ P(5) = w_3\) 如果我们计算出对应的范德蒙逆矩阵的话，我们就可以反推出这个多项式$P$的每一项系数：

\[\begin{bmatrix} 1 & 1 & 1^2 & 1^3 & 1^4 & 1^5 \\ 1 & 2 & 2^2 & 2^3 & 2^4 & 2^5 \\ 1 & 3 & 3^2 & 3^3 & 3^4 & 3^5 \\ 1 & 4 & 4^2 & 4^3 & 4^4 & 4^5 \\ 1 & 5 & 5^2 & 5^3 & 5^4 & 5^5 \end{bmatrix}^{-1} \times \begin{bmatrix} -w + w_0 + 2w_1 + 4w_2 + 8w_3 \\ w_0 \\ w_1 \\ w_2 \\ w_3 \end{bmatrix} = \begin{bmatrix} f_0 \\ f_1 \\ f_2 \\ f_3 \\ f_4 \end{bmatrix}\]

得到系数之后，我们也就还原了多项式$P$。同理可得，我们也可以用$B$矩阵来还原出多项式$Q$：

\[\begin{align*} \exists Q(x) &= g_0 + g_1 \cdot x + g_2 \cdot x^2 + g_3 \cdot x^3 + g_4 \cdot x^4 : \\ Q(1) &= 1 \\ Q(2) &= w_0 - 1 \\ Q(3) &= w_1 - 1 \\ Q(4) &= w_2 - 1 \\ Q(5) &= w_3 - 1 \\ \end{align*}\] \[\begin{bmatrix} 1 & 1 & 1^2 & 1^3 & 1^4 & 1^5 \\ 1 & 2 & 2^2 & 2^3 & 2^4 & 2^5 \\ 1 & 3 & 3^2 & 3^3 & 3^4 & 3^5 \\ 1 & 4 & 4^2 & 4^3 & 4^4 & 4^5 \\ 1 & 5 & 5^2 & 5^3 & 5^4 & 5^5 \end{bmatrix}^{-1} \times \begin{bmatrix} 1 \\ w_0 - 1 \\ w_1 - 1 \\ w_2 - 1 \\ w_3 - 1 \end{bmatrix} = \begin{bmatrix} g_0 \\ g_1 \\ g_2 \\ g_3 \\ g_4 \end{bmatrix}\]

还原出$P, Q$之后，我们再接再厉，用$C$矩阵还原出多项式$R$。

$R$和前两个不同的地方在于，因为$C \cdot \vec{z}$的结果是$A, B$两个矩阵的结果相乘得到的，所以如果$A$和$B$还原出了一个4阶的多项式的话，那么$C$由于是多项式相乘，所以应当可以还原出一个8阶的多项式。

如果需要成功还原8阶的多项式那么需要9个取值点，但是我们只能从$C$矩阵中得到5个取值。解决的方法其实很简单，我们只需要先得到$P$和$Q$之后，再在$R$的范德蒙矩阵后面不够的地方手动多填上几个用$P$和$Q$算出来的数字就行了。

\[\begin{align*} \exists R(x) &= h_0 + h_1 \cdot x + h_2 \cdot x^2 + \dots + h_8 \cdot x^8 : \\ Q(1) &= 0 \\ Q(2) &= 0 \\ Q(3) &= 0 \\ Q(4) &= 0 \\ Q(5) &= 0 \\ Q(6) &= P(6) \cdot Q(6) \\ Q(7) &= P(7) \cdot Q(7) \\ Q(8) &= P(8) \cdot Q(8) \\ Q(9) &= P(9) \cdot Q(9) \\ \end{align*}\] \[\begin{bmatrix} 1 & 1 & 1^2 & 1^3 & 1^4 & 1^5 \\ 1 & 2 & 2^2 & 2^3 & 2^4 & 2^5 \\ 1 & 3 & 3^2 & 3^3 & 3^4 & 3^5 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 9 & 9^2 & 9^3 & 9^4 & 9^5 \end{bmatrix}^{-1} \times \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ P(6) \cdot Q(6) \\ P(7) \cdot Q(7) \\ P(8) \cdot Q(8) \\ P(9) \cdot Q(9) \end{bmatrix} = \begin{bmatrix} h_0 \\ h_1 \\ h_2 \\ \vdots \\ h_8 \end{bmatrix}\]

当我们得到$P, Q, R$三个多项式之后，只要R1CS给我们的约束正确，并且私密输入矢量$\vec{z}$也是正确的解，那么我们就可以保证$P \times Q = R$。如果我们想单独验证R1CS中的第一条约束（$w$由$w_0, w_1, w_2, w_3$组成），我们只需要看$P(1) \cdot Q(1)$是否等于$R(1)$，如果他们想等，那就代表这一组多项式满足了R1CS的第一条约束。同理，我们也可以代入2看第二条约束，以此类推。

到这一步的时候，相信很多朋友已经能隐约感觉到距离之前说过的LPCP非常接近了。如果证明方已经拥有了一个合法的私密输入$\vec{z}$，并且根据这个私密输入和事先约定好的电路$C$（即R1CS矩阵）成功还原出了多项式$P, Q, R$，这个时候，验证方需要做的事情，无疑就是随机的让证明方验证$P, Q, R$上的一个取值$r$，然后判断$P(r) \cdot Q(r) \stackrel{?}{=} R(r)$。如果判断成立，那就代表证明方拥有的私密输入是合法的了。

当然，完整的LPCP协议并没有那么简单，我们还需要定义很多证明方和验证方要做的步骤，然后通过query的形式让验证方逐步看到多项式$P, Q, R$在某些点$r$上的取值。

快速多项式还原

在实际应用当中，因为大型电路（比如SHA256）的约束非常之多，我们往往不会使用范德蒙逆矩阵来还原多项式，因为计算一个几万行的逆矩阵会非常缓慢。一般来说，我们会用快速傅立叶变换（FFT）之类的动态算法来快速的找到一个可以代表约束关系的多项式。我在文末链接了V神的一篇文章，专门讲FFT和多项式之间的关系。

未完待续

由于篇幅的限制，我们这一期就先讲到这里。

想必看到这里，大家应该都了解了构成简短证明最关键的几个部分：

1. PCP定理是通过随机抽查的方法来快速验证任何NP问题的解。
2. LPCP是约束版的PCP，讲了通过随机抽查多项式取值的方法来快速验证多项式的系数。
3. Fiat-Shamir Heuristic可以把一个交互式协议变成一个非交互式协议。
4. 从一个数学运算电路出发，变换成R1CS程序矩阵之后，可以最后还原成多项式。

当我们学会这些基础的工具之后，下一期我们就可以来看看，怎么把这些积木全部拼在一起，构成高效率的LPCP证明体系，然后再用Fiat-Shamir，同态加密，加上随机值等等的步骤，逐步搭建出zkSNARK协议。

更多阅读

1. Fiat-Shamir Heuristic：https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
2. PCP定理：https://en.wikipedia.org/wiki/PCP_theorem
3. 范德蒙矩阵：https://en.wikipedia.org/wiki/Vandermonde_matrix
4. FFT与多项式：https://vitalik.ca/general/2019/05/12/fft.html