浅谈零知识证明之四:zkSNARK证明体系的实现(下)

前段时间略忙,主要时间在研究全同态算法FHE和可信多方计算MPC方面的内容,所以迟迟没有写完zkSNARK具体实现的下篇。这次回来补上下篇!

回顾一下上一期,我们讲到了PCP定理,并且从PCP定理出发约束到了LPCP。随后我们讲到了如何用Fiat-Shamir把交互式的协议压缩成非交互式协议。最后我们学习了R1CS矩阵程序,以及如何从R1CS矩阵得到对应的多项式表达式

掌握R1CS之后,其实距离我们的结果zkSNARK已经不远了。今天这一期我们着重的了解一下,从R1CS电路到zkSNARK需要经过的三大步

  1. R1CS电路出发,建立我们的线性PCP(LPCP)交互式证明系统。
  2. LPCP交互系统转换成需要可信初始化的非交互式简短证明(SNARK w/ Trusted Setup)。
  3. 加入零知识(zk)。

话不多说,我们开始吧。

written equations on brown wooden board

从R1CS到LPCP

上一期结束的时候,我们大致的介绍过如何把区间证明的电路转换成R1CS矩阵程序,最后再转换成多项式。想必大家都大致了解了如何把R1CS的三个矩阵转换成多项式的过程——通过范德蒙矩阵\(V\)来把\(A, B, C\)矩阵转换成三个多项式\(P(x), Q(x), R(x)\)。

R1CS转换为多项式

上一期我们看到的\(A, B, C\)变成\(P(x), Q(x), R(x)\)只是一个方便大家理解而描述的例子,这一期我们先来系统性的概括总结一下从R1CS是如何转换到多项式的

  1. 首先,我们使用\(m, n\)来定义R1CS的三个矩阵\(A, B, C \in \mathbb{F}^{m \times (n+1)}\)的维度。对于R1CS程序对应的公有和私密输入,我们使用\(\vec{z} = \begin{bmatrix}1\\x\\w\end{bmatrix} \in \mathbb{F}^{n + 1}\)来表达。这里\(m\)代表的就是R1CS电路中有多少条约束(constraint),而\(n\)代表了一共有多少个输入变量(\(x + w\))。因为我们还需要用到常数1,所以矩阵的维度是\(m \times (n + 1)\)。
  2. 随后,我们将\(A\)还原为多项式\(f(x)\)。就像前一篇所述,我们找到多项式\(f(x)\)的多个取值点:\(f(i) = (A \cdot \vec{z})_i \text{ for } i = 1, ..., m\)。我们一共会得到\(m\)个取值点,然后就可以使用范德蒙反矩阵把这些取值点还原成一个\(m-1\)阶的多项式。
  3. 对于\(B\),我们也进行同样的操作,还原\(g(x)\)。
  4. 最后对于\(C\),我们首先设定\(h(i) = (C \cdot \vec{z})_i \text{ for } i = 1, ..., m\),然后由于\(h\)的阶度会是\(f, g\)的阶度之和(即\(2m - 2\)),我们需要额外定义\(m - 1\)个点的取值(这样我们就有\(2m - 1\)个取值点,可以还原\(2m - 2\)阶的多项式)。我们额外设定\(h(i) = f(i) \cdot g(i) \text{ for } i = m+1, ..., 2m-1\),随后就可以还原出多项式\(h(x)\)。

因为多项式保持了原先矩阵之间的关系,如果R1CS矩阵之间满足\((A \cdot \vec{z}) \circ (B \cdot \vec{z}) = C \cdot \vec{z}\),通过这个方法得到的\(f, g, h\)一定会满足\(f(i) \cdot g(i) = h(i)\)。反过来也是一样,如果我们可以找到三个多项式并且\(h = f \cdot g\),那么代表这三个多项式所对应的R1CS矩阵程序一定也满足\((A \cdot \vec{z}) \circ (B \cdot \vec{z}) = C \cdot \vec{z}\)的关系。

这一关系就是把R1CS转换成LPCP的核心思路了。只要我们可以验证三个多项式满足\(h = f \cdot g\)的关系,而且这三个多项式代表了我们想要证明的问题所对应的R1CS矩阵的话,那么就代表这个R1CS矩阵程序是正确的,进而代表证明方的私密输入\(w\)也是正确的

如果放在LPCP的语言里来说的话,我们想要随机抽查一个点\(r\),验证这三个多项式在这一点的关系\(f(r) \cdot g(r) \stackrel{?}{=} h(r)\)。如果这个验证通过的话,那LPCP可以保证原来的多项式绝大概率上满足\(f \cdot g = h\)。这样的好处是,因为\(f, g, h\)的取值是根据R1CS电路的约束来决定的,如果我们可以在一个或几个点上就验证这些多项式的关系,就等于一下子验证了所有的约束!而且这里不管有多少条约束,都是一样的。验证大小独立于约束的多少(即电路的大小)。这就是“简短性“的精髓了。

多项式转换为LPCP

在之前的文章中,我们了解过范德蒙矩阵\(V\)式如何通过多项式的取值来还原多项式的系数的。同理可得,我们也可以用一样的矩阵相乘来表达一个多项式\(f\)在\(r\)这个点上的取值:

\[\begin{align*} f(r) &= \begin{bmatrix} 1 & r^2 & ... & r^{m-1} \end{bmatrix} \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_{m-1} \end{bmatrix}\\ &= \begin{bmatrix} 1 & r^2 & ... & r^{m-1} \end{bmatrix} V^{-1} \begin{bmatrix} f(0) \\ f(1)\\ \vdots\\ f(m-1) \end{bmatrix} \\ &= \begin{bmatrix} 1 & r^2 & ... & r^{m-1} \end{bmatrix} V^{-1} (A \cdot \vec{z}) \end{align*}\]

一旦转换成最后形态的表达式之后,我们马上可以发现,由于\(V\)与R1CS矩阵\(A\)是证明方和验证方都公开的内容,\(r\)是验证方选择的随机抽验的取值点,所以我们可以把整个表达式分成两个部分

\[\begin{align*} f(r) &= (\begin{bmatrix} 1 & r^2 & ... & r^{m-1} \end{bmatrix} V^{-1} A) \cdot \vec{z} = \langle q_1, z \rangle\\ q_1 &= \begin{bmatrix} 1 & r^2 & ... & r^{m-1} \end{bmatrix} V^{-1} A \end{align*}\]

左边部分我们用一个向量\(q\)来表示,代表证明方想要验证的query。右边部分就是包含了证明电路中公有和私密输入的矩阵\(z\)。对于多项式\(g\),我们也如法炮制,得到另一对内积组合\(\langle q_2, z \rangle\)。

最后对于多项式\(h\),我们进行类似的操作。为了让整体的维度保持一致,我们需要额外加上一组单位矩阵

\[\begin{align*} h(r) &= \begin{bmatrix} 1 & r^2 & ... & r^{2m-1} \end{bmatrix} V^{-1} \begin{bmatrix} C\\ I_{m-1} \end{bmatrix} \cdot \begin{bmatrix} \vec{z}\\ h(m+1)\\ \vdots\\ h(2m-1) \end{bmatrix} = \langle q_3, [z, h(m+1), ..., h(2m-1)] \rangle\\ q_3 &= \begin{bmatrix} 1 & r^2 & ... & r^{2m-1} \end{bmatrix} V^{-1} \begin{bmatrix} C\\ I_{m-1} \end{bmatrix} \end{align*}\]

具体的数学公式看似比较复杂,但是其实理解起来很简单:我们只需要把三个多项式\(f, g, h\)在\(r\)上的取值转换为了两个向量的内积\(\langle q_i, z \rangle\)。

如果我们细心观察的话, 我们发现\(q_1, q_2, q_3\)这三个向量可以由验证方生成,而证明方只需要准备好电路的输入\(z\)就好了。这样一来,我们变相的把所有的计算难度放在了验证方的一侧,而证明方则不需要太多的运算。

LPCP验证协议

当我们成功的把多项式随机取值问题分解为三个query向量\(q_1, q_2, q_3\)之后,我们就可以正式地进入真正的LPCP验证协议了

  1. 首先,证明方Prover事先计算好证明\(\pi = [w, h(m+1), ..., h(2m-1)]\),并且把证明保存起来,不许修改它。
  2. 验证方Verifier随机的抽选一个验证点\(r \stackrel{R}{\leftarrow} \mathbb{F}\),并且根据\(r\)的取值计算得到三个query的向量\(q_1, q_2, q_3\)。
  3. 这三个Query需要和我们原本的输入向量\(z = \begin{bmatrix}1\\ x\\ w \end{bmatrix}\)相乘。我们观察这个向量之后发现,验证方事先已经可以得知向量的上半部分\(\begin{bmatrix}1\\ x\end{bmatrix}\)。所以验证方可以把Query向量\(q_i\)进行切割,变成\([q_i^L, q_i^R]\)两部分。这样的话,原本的计算也可以一分为二,然后把两部分的内积分别对叠起来:
\[\langle q_i, z \rangle = \begin{bmatrix} \langle q_i^L, \begin{bmatrix}1\\x\end{bmatrix} \rangle\\ \langle q_i^R, \begin{bmatrix}w\end{bmatrix} \rangle\end{bmatrix}\]
  1. 通过这一步切割,我们发现对于\(q_i^L\)部分的计算,验证方已经全部知道了,所以我们可以进一步的优化证明方需要做的计算,只把\(q_i^R\)发送给证明方,让证明方仅仅与私密输入\(w\)相乘。
  2. 综上所述,验证方现在可以发送\(q_1^R, q_2^R, q_3^R\)三个query向量给证明方。
  3. 证明方收到query向量之后,只需要把每个值和自己的证明向量\(\pi\)相乘
\[a = \langle [q_1^R 0^{m-1}], \pi \rangle\\ b = \langle [q_2^R 0^{m-1}], \pi \rangle\\ c = \langle q_3^R, \pi \rangle\\\]

由于证明向量\(\pi\)后面还带了多项式\(h\)的额外\(m-1\)个取值点,所以我们需要在\(q_1^R, q_2^R\)的背后补上一个空白矩阵,才可以适配矩阵相乘的维度。

随后,证明方把\(a, b, c\)三个值发回给验证方

  1. 最后,验证方只需要把左侧query的内积补上,最后检查等式是否相等:
\[(\langle q_1^L, [1, x] \rangle + a) \cdot (\langle q_2^L, [1, x] \rangle + b) \stackrel{?}{=} (\langle q_3^L, [1, x] \rangle + c)\]

组合起来之后,这也就是变相检查等式\(\langle q_1, z \rangle \cdot \langle q_2, z \rangle \stackrel{?}{=} \langle q_3, z \rangle\)是否相等

如果得到的\(a, b, c\)所组成的等式的确相等,那么就代表\(h(r) = f(r) \cdot g(r)\)。根据我们上文讨论的关系,这也就直接代表了\((A \cdot \vec{z}) \circ (B \cdot \vec{z}) = C \cdot \vec{z}\)!

这样一来,我们就得到了完全版的LPCP协议啦。通过抽查三个多项式在某个点上的随机取值,我们达到了简短证明的目的。只要证明方与验证方严格遵守上述描写的协议,那么就可以有效的通过简短交互来验证一个R1CS矩阵所对应的多项式是否满足我们想要的关系

number Zero wall signage

从LPCP到SNARK w/ Trusted Setup

我们距离最后的胜利,已经非常接近了!

当我们成功的推导出了可以证明R1CS电路正确性的LPCP协议之后,我们会发现LPCP是一个交互式协议。这也就是说,证明方首先需要生成一个证明字串\(\pi\),然后保证不会去改动这个字串(可以通过承诺来实现)。随后,验证方会随机抽选三个Query:\(q_1^R, q_2^R, q_3^R\)发送给证明方,随后证明方需要诚实的返回对应的乘积\(a, b, c\)三个值进行验证。

下一步,我们需要把LPCP协议进一步压缩成一个简短无交互式的协议

尝试去除LPCP中的交互部分

在LPCP中,我们现在依靠验证方生成随机验证Query,即\(q_1^R, q_2^R, q_3^R\),然后证明方需要根据Query的取值来“回答”,生成答案\(a, b, c\)。如果我们想要把整个证明变得无交互的话,我们就需要想办法把“证明方随机生成Query”这个步骤去除掉。

我们在上一篇文章学习了Fiat-Shamir Heuristic。这个算法可以有效的把一个生成随机值的交互方使用一个随机预言机(即哈希函数)来替代。我们可以把Fiat-Shamir运用在我们的LPCP协议里,构建如下的非交互式系统:

  1. 证明方事先准备好证明\(\pi\)。在后面的过程中,\(\pi\)始终不能被改变。
  2. 随后,证明方使用证明\(\pi\)为输入计算哈希函数\(H(\pi)\),并且根据结果得到Query \(q_1, q_2, q_3\)。
  3. 根据Query的值,证明方计算\(\langle q_1, \pi \rangle, \langle q_2, \pi \rangle, \langle q_3, \pi \rangle\),即\(a, b, c\)。
  4. 最后,证明方把\(\pi, H(\pi), a, b, c\)一并提交给验证方进行验证。
  5. 验证方收到证明之后,只需要重新自己进行一遍计算,就可以确认证明是否正确了。

这样一来,看似我们把LPCP做成了非交互式的样子,但是随之而来的,是更大的问题

首先,证明方需要把整个证明\(\pi\)全部发送给验证方,因为验证方随后要重复进行一模一样的计算。这一步就已经打破了我们之前的简短性要求,因为\(\pi\)的长度取决于\(w\)的大小以及多项式\(h\)的阶度,而这两个值恰好和电路的大小是成正比的。所以这样一来我们通讯的成本就和电路大小挂钩了,这和我们一开始想要达到的并不符合。

第二个问题在于零知识。虽然我们还没有说到零知识的部分,但是我们可以发现,如果证明方把\(\pi\)全部发送给验证方,那么证明方所有的私密输入\(w\)已经全部暴露无疑了。验证方其实并不想要看到这么多信息,只需要看到\(a, b, c\)三个乘积就够了。但是为了验证Fiat-Shamir变换是正确的,又不得不看到产生随机Query的哈希函数的输入,即证明\(\pi\)。

这么看来,在随机预言机模型(Random Oracle Model)下,使用Fiat-Shamir变换对于我们的LPCP协议并没有太大帮助,无法达到我们想要的目的。这个时候该怎么办呢?

其实,为了避免交互,zkSNARK使用了密码学中另有的一个假设:公共参考字串(CRS)

公共参考字串(Common Reference String,CRS)模型

公共参考字串(CRS)其实是一个相比起随机预言机更为简单的假设,具体是这样的:

我们假设在一个协议中,证明方与验证方都拥有一段相同的参考字串。这个字串可能是随机生成的,也可能是某个函数的输出。重要的是完成协议的两方并不知道这个字串具体是如何被生成的,就感觉像是天上掉下来的一样。

在CRS假设下,一个协议的双方可以共享一段事先生成的,但是谁也不知道是怎么生成的参考字串,并且基于这个参考字串完成原本的协议。

举个例子来说,假如为了完成一个协议,Alice与Bob都需要使用一个随机生成的一串数字\(\vec{r} \stackrel{R}{\leftarrow} \mathbb{Z}_q^n\)。我们都知道,在电脑系统里面,随机数生成基本都是通过伪随机数生成器与一个随机种子来完成的。这也就是说,知道了种子,也就可以预测到生成的伪随机数是什么。

假如说我们构想的这个协议中,双方都需要使用这个随机数来“抽查”他们的数据库内容是否正确,那么这个场景下,任何人都不可以知道生成这个随机数的种子,不然他们就可以事先做假,把会被检查到的那一部分数据改成对的。

这个时候,我们就可以使用CRS模型了。我们假设事先有别人已经选好了一个随机种子,并且根据这个种子验证生成了我们需要的随机数\(\vec{r}\),然后再把这串随机数字放入参考字串CRS当中,并且公开发布。这样一来,当Alice与Bob进行协议的时候,他们只能看到一个随机的字串,并且根据这个字串来”验证“数据库的一部分,但是他们并不知道这是怎么被生成的,所以没有办法事先做弊。

当然,有朋友看到这里会有些疑惑:既然CRS是公开给所有人的,那么Alice和Bob都可以事先根据CRS中看到的随机数来找到会被“抽查”的部分,然后进行做弊呢?

没错,如果直接把随机数放入CRS中是不行的。但是这个问题其实非常容易解决——我们只需要把生成的随机数加密起来就行了,这样就算被看到了也无法从密文中得知信息来做弊。

一旦涉及到加密,就还会派生出一系列的小问题。这里我们先留做一个悬念,稍后我们会回来重点描述这一部分

CRS模型下的无交互LPCP

回到我们之前的LPCP的问题上来。我们如果要去除LPCP的交互部分的话,我们就需要想办法不用交互,但是可以随机生成我们需要的Query \(q_1, q_2, q_3\)。之前我们发现,通过Fiat-Shamir并不能达到理想的效果。

学会了CRS模型之后,这个问题就变得简单了:我们只需要让别人事先生成好这些Query,然后通通丢进CRS里面,这样证明方就不需要与验证方交互就可以拿到这些随机生成的Query了。

我们接着这个想法,构想一下CRS模型下无交互LPCP的大概步骤:

  1. 首先,第三方根据LPCP用到的R1CS电路,选取随机数\(r\),并且根据随机数生成好Query部分,即\(q_1, q_2, q_3\),然后丢入CRS当中。
  2. 证明方准备好自己的证明向量\(\pi = [w, h(m+1), ..., h(2m-1)]\),然后从CRS中取出Query向量的右半部分,即\(q_1^R, q_2^R, q_3^R\)。随后分别和自己的证明向量相乘,得到我们要的\(a, b, c\)三个值。
\[a = \langle [q_1^R 0^{m-1}], \pi \rangle\\ b = \langle [q_2^R 0^{m-1}], \pi \rangle\\ c = \langle q_3^R, \pi \rangle\\\]
  1. 证明方把\(a, b, c\)发送给验证方。
  2. 验证方根据CRS得到\(q_1^L, q_2^L, q_3^L\),然后结合证明方提供的\(a, b, c\),检查等式是否相等:
\[(\langle q_1^L, [1, x] \rangle + a) \cdot (\langle q_2^L, [1, x] \rangle + b) \stackrel{?}{=} (\langle q_3^L, [1, x] \rangle + c)\]
  1. 如果相等,即代表LPCP验证通过。

如果我们观察一下我们得到的无交互LPCP的话,我们会发现这距离我们想要的非常接近了!证明方与验证方的沟通非常简短,只需要发送三个数字即可。验证方所需要做的事情相对来说也很简单,只需要做比较短的矩阵相乘,再把结果加上比较一下就ok了。

然而,这个体系现在还有一个很大的问题:随机生成的Query直接暴露在CRS当中

和上一段结尾提到的问题一样,如果证明方在生成证明向量\(\pi\)之前,就已经看到了Query的值,那么他完全就可以根据Query要取值的点来做弊,制造出虚假的证明来。

如何保证CRS中的Query不能被用来做弊,但是仍然还可以计算后面的内积呢?我们在上一段结尾也说到了,需要依靠一种比较特殊的加密系统:线性加密系统(Linear-only Encoding)

线性加密系统Linear-only Encoding

我们来回顾一下对于这一加密系统的需求。我们把加密原文\(x\)的密文用\([[x]]\)来表示。

首先,为了防止证明方实现看到Query的内容进行作弊,我们的加密系统一定要能够隐藏Query本身。也就是说看到密文的证明方并不可以得到任何和原文有关的信息。这一点所有的加密算法都可以做到。

其次,我们需要保证证明方仍然可以生成内积\([[\langle q_i, \pi \rangle]]\),并且最后验证方可以进行验证。这一点其实是一个非常独特的需求,我们可以把这两个要求拆开来看一下:

  1. 证明方可以生成内积\([[\langle q_i, \pi \rangle]]\)。因为\(\pi\)里面也就是一串数字,所以这就是说证明方可以输出Query \([[q_i]]\)中的数值与\(\pi\)向量的数值的线性组合。完成这一点我们可以使用拥有加法同态特性的加密算法。
  2. 验证方可以验证\([[a]] \cdot [[b]] = [[c]]\)。这也就是说,证明方通过加法同态性质得到的加密过后的\([[a]], [[b]], [[c]]\)需要通过类似于乘法同态一样的验证。这一点要求比较特殊,我们在选择加密算法的时候要额外注意。

除了上面两条必须要符合的特性之外,出于安全性考虑我们还需要考虑第三条:

  1. 证明方只能生成Query \([[q_i]]\)的线性组合,并不能生成任何其他的密文。这个要求的原因很简单,如果证明方可以任意生成合理的密文的话,那么他就可以不管看到的Query是什么,随便生成一组合理的\([[a]], [[b]], [[c]]\)使得他们满足验证,就可以欺骗过验证方了。

当我们归纳出这三条要求之后,接下来我们可以系统性地定义一下线性加密系统

  1. 生成算法\(Gen(1^\lambda) \rightarrow sk, pk, C\):我们首先需要随机生成一组密钥与公钥(\(sk, pk\)),方便后续的操作。与此同时我们还需要输出一个密文空间\(C\),为了后面验证证明方输出的内容是不是合理的线性组合。
  2. 加密算法\(Enc(sk, x \in \mathbb{F}) \rightarrow c \in C\):我们加密一个值\(x\),并且输出一个密文\(c\)。
  3. 验证算法\(Verify(pk, C, c) \rightarrow 1/0\):给定一个密文\(c\),判断这个密文是不是属于我们的加密空间\(C\)当中。
  4. 加法同态运算\(Add(pk, c_1, c_2 \in C) \rightarrow c^* \in C\):我们把两个密文相加,得到组合起来的密文,正好对应原本的原文相加的值。当我们拥有\(Add\)算法之后,我们就可以得到一个数字\(x\)的任意线性组合了:
\[Enc(x + y) = Enc(x) + Enc(y)\\ Enc(ax) = \underbrace{Enc(x) + Enc(x) + \cdots + Enc(x)}_\text{$a$ times}\]
  1. 乘积验证\(QuadTest(pk, (c_1, c_2, c_3 \in C), \alpha) \rightarrow 1/0\):验证\(c_1, c_2, c_3\)这三个密文是否是正确的密文(即对应了某些\(x_1, x_2, x_3\)的值),并且判断\(x_1 \cdot x_2 \stackrel{?}{=} \alpha \cdot x_3\)。

一个线性加密系统还需要满足两条额外的属性(properties)

单向性(One-way):这条属性是说,如果看到了\([[x]]\),我们不能推导出\(x\)的值。这一点确保了密文是安全的。

仅限线性组合(Linear-only):这一点要求了,如果给定了一组密文\([[x]], [[y]]\),我们只能生成这组密文的线性组合,即\([[ax + by]]\),但是不能生成任何其他的值来。这一点确保了我们不能在没有密钥的情况下任意生成合理的密文。

一般来说,满足这些要求的线性加密系统很少。一个最常见的例子,就是有Pairing配对属性的循环群\(\mathbb{G}\)了,比如说某些椭圆曲线。

在循环群中,我们拥有生成元\(g \in \mathbb{G}\)。加密一个数字\(x\)就是\(g^x\),然后任何人都可以获得\(g^x\)的线性组合(即\((g^x)^a g^y = g^{ax + y}\)),但是很难通过\(g^x\)推导出\(x\),因为离散对数的困难性。

同时,因为我们选择的循环群拥有配对操作,所以我们可以非常轻松的验证密文的乘积是否相等。

\[x_1 \cdot x_2 \stackrel{?}{=} \alpha \cdot x_3\\ e(g^{x_1}, g^{x_2}) = g^{x_1 x_2}_T \stackrel{?}{=} g^{\alpha x_3}_T = e(g, (g^c)^\alpha)\]

有了线性加密系统之后,我们之前在尝试无交互LPCP的时候遇到的作弊问题就引刃而解了。

基于线性加密的无交互LPCP(SNARK)

当我们把线性加密系统应用于无交互LPCP的系统中,我们就得到SNARK了!

因为距离上一期又过去了一段时间,我们再来回顾一下这个系列第二篇文章提到的简短证明体系(SNARK)的三个核心算法: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\):验证证明。

接下来,我们结合刚刚学到的知识点,把SNARK的三个基本算法具体实现一下:

  1. \(Setup(C) \rightarrow (S_p, S_v)\):首先,我们根据R1CS的电路的大小,随机选取我们要用到的Query \(q_1, q_2, q_3\),并且使用\(Gen\)算法初始化一个线性加密系统。最后,我们输出:
\[S_v \leftarrow [[q_1^L]], [[q_2^L]], [[q_3^L]]\\ S_p \leftarrow [[q_1^R]], [[q_2^R]], [[q_3^R]]\]
  1. \(Prove(S_p, x, w) \rightarrow \pi\):证明的过程也很简单,证明方先准备好LPCP的证明字串\(\pi'\),然后只需要输出\(\pi = [[a]], [[b]], [[c]]\)(表达式中省略了单位矩阵的部分):
\[[[a]] = \langle [[q_1^R]], \pi' \rangle\\ [[b]] = \langle [[q_2^R]], \pi' \rangle\\ [[c]] = \langle [[q_3^R]], \pi' \rangle\]
  1. \(Verify(S_v, x, \pi) \rightarrow Yes/No\):验证就和我们之前说的一样,首先验证方需要自己计算\(q_i^L\)的部分,并且和证明方的结果合并起来,最后组成LPCP最后的验证等式\([[\langle q_1, z \rangle]], [[\langle q_2, z \rangle]], [[\langle q_3, z \rangle]]\)。这个时候,验证方可以通过乘积验证\(QuadTest\)算法,来验证LPCP的三个数字是否满足\(\langle q_1, z \rangle \cdot \langle q_2, z \rangle \stackrel{?}{=} \langle q_3, z \rangle\)。

这就是基于LPCP的SNARK的全貌了。我们发现这个系统满足了我们之前的所有要求,即简短、无交互、知识证明。在我们收尾之前,还有一些小细节需要关注一下。

随机线性检查(Random Linearity Check)

当我们加上了线性加密系统之后,现在得到的SNARK还有一个巨大的漏洞

我们观察发现,因为Query的部分都是加密隐藏起来的,所以证明方还可以做一个骚操作:在计算\([[a]], [[b]], [[c]]\)的时候,在中途偷偷的变换用到的证明\(\pi'\)。因为证明方也可以自己跑\(QuadTest\)算法,他可以使用三个不同的\(\pi'\)值来得到最后的密文,并且使得密文的乘积相等,可以通过\(QuadTest\)测试,并且欺骗验证方。

这一问题解决的方法也不难,我们需要修改一下LPCP协议,在中间多加上一个随机线性检查(Random Linearity Check)

在我们生成LPCP的Query \(q_1^R, q_2^R, q_3^R\)的时候,我们随机的选取\(\alpha, \beta, \gamma\),然后额外的生成一个线性检查Query \(q^* = \alpha q_1^R + \beta q_2^R + \gamma q_3^R\)。我们把\(q^*\)也发送给证明方,并且要求证明方提供\(\langle q^*, \pi \rangle\)的内积\(d\)。

这样一来,最后验证方可以收到四个数字,即\(a, b, c, d\)。这个时候验证方就可以验证:

\[d \stackrel{?}{=} \alpha a + \beta b + \gamma c\]

如果符合检查的话,那就表示证明方在生成\(a, b, c, d\)的时候,用到的是同样的\(\pi\)啦。

同理可得,在SNARK中,我们需要在\(Setup\)阶段额外的生成一组\(q^*\)。随后我们在在\(S_v\)中额外添加\([[q^{*L}]], [[\alpha]], [[\beta]], [[\gamma]]\),并且在\(S_p\)中添加\([[q^{*R}]]\)。随后,证明方提交的证明中额外需要提交一个\([[d]] = \langle q^{*R}, \pi' \rangle\)。

这样一来,验证方可以首先通过\(QuadTest\),验证\([[a]], [[b]], [[c]]\)与\([[d]]\)之间的关系,确保证明方没有做弊。验证通过之后,再验证\([[a]], [[b]]\)与\([[c]]\)的关系。如果两次检查都通过了,那就基本上等于LPCP通过了

加上随机线性检查之后,我们就得到了zkSNARK中的SNARK的完全体啦。

如果你看到这儿,我们已经完成了99%!最后一步也是最简单的一步,就是加上零知识

加入零知识(zk)

我们在当前的SNARK中,只需要做一个非常细微的变动,就可以转换成zkSNARK了。

我们观察发现,证明方唯一暴露给验证方的数据,就是\([[a]], [[b]], [[c]], [[d]]\)这四个值,其中\(d\)是\(a, b, c\)组合得到的。这也就是说,只要我们确保\(a, b, c\)不会暴露任何信息,那这个协议就符合零知识的定义了。

我们再仔细观察就会发现,\(a, b, c\)这三个数字,无疑就是多项式\(f, g, h\)的取值。因为零知识的定义是,我们不能泄漏任何一丁点信息,所以我们也不能暴露多项式\(f, g, h\)的取值。如果取值看到的过多了,甚至还可以通过插值的方法还原出系数。

解决的方法也非常简单,我们只需要在一开始还原多项式\(f, g, h\)的时候,额外选择两个随机数\(\delta_1, \delta_2\),并且多加一组取值点,使得\(f(0) = \delta_1, g(0) = \delta_2, h(0) = f(0) \cdot g(0)\)。这样一来我们还原出来的多项式,因为多了一阶(之前是\(m-1\)阶,现在是\(m\)阶),所以整体的样子看上去和原来的多项式完全不同。

具体的证明我在这里就不多说了,不过大概的构造是:如果我们在给定的一组取值点中再额外增加一个随机取值点的话,那么最后新得到的多项式就会拥有和这个随机数类似的一个随机分布,这样我们就没法从新得到的多项式中看到和原来的多项式相关的任何信息,也就是我们所说的零知识了。

以上就是zkSNARK的整体构造啦!完结撒花。

在结束之前,我还想再和大家聊一聊对于SNARK中\(Setup\)这一步的细节。

可信初始化(Trusted Setup)

我们观察会发现,在我们构造的zkSNARK体系当中,Setup这一步需要由第三方来完成。在整个协议的过程中,只要证明方得知任何一点Setup中用到的数值(比如说随机数、随机种子等等),那么证明方就可以马上用这些知识来做弊,使得自己可以生成虚假证明,欺骗任何人。

如果应用在ZCash场景中(第一期有所提到),如果掌握了这些随机参数的人,就可以随机的给自己发钱,任意铸币,破坏整个生态系统。

这也就是说,单纯的委托第三方来生成这些参数的话,我们还必须要确保第三方必须要在生成完之后,彻底摧毁所用生成所用的参数。这一过程我们称之为可信初始化(Trusted Setup)。ZCash在可信初始化这步做出了各种惊人的举动:比如去切尔诺贝利核电站去读取辐射数据,用辐射的指数作为随机数值来生成Query等等……

我们通过LPCP生成的SNARK中,所有的Query \(q_1, q_2, q_3\)的维度都是挂钩于我们最初R1CS的电路大小的。这也就是说,我们对于每个电路的验证,都需要经过一次可信初始化的过程。这其实是一个比较麻烦的事情,如果我们想要验证别的东西,或者修改电路逻辑,我们就需要额外的再初始化一次,这会浪费很多资源,并且效率也不是很高。虽然对于ZCash来说,验证的电路都是相同的(验证交易的数额与Nullifier),但是这仍然是zkSNARK面临的一个巨大挑战。

相比起来,同一阶段还有一些别的零知识证明体系,可以解决可信初始化的问题。

一方面的体系,类似于Sonic,Plonk,Marlin,选择的路线是通用可信初始化(Universal Trusted Setup)。意思是说,我们只需要初始化一次,然后生成的随机Query可以适用于任意的电路。这样一来,我们可以节约很多成本。

另一类不同的体系,是彻底抛弃了可信初始化的概念,比如说STARK,SuperSonic等等。这一类的体系用的方法和我们一开始提出的Fiat-Shamir的去交互方法非常相似。我们遇到的问题在于Fiat-Shamir生成的无交互系统没法达到我们简短性的要求,这是因为LPCP基于PCP,本身证明\(\pi\)的体积就非常大。在STARK中,我们就需要使用除了LPCP外的另一条路线:多项式承诺多项式取值验证(Polynomial IOP)。具体的就不多说啦,感兴趣的朋友可以去读一读STARK的文章研究一下构造。

grayscale photography of clock

篇尾回顾

从19年圣诞节左右开始酝酿零知识方面的文章,一直到20年夏天,经过了疫情,终于把zkSNARK的整体构造写完了。开始写之前本来觉得是一个比较简单的概念,但是真正开始研究之后,发现每一步里面都蕴涵了很多知识和对应的背景材料。

在最后,我们再来回顾一下我们一共学习了哪些内容:

  1. 区块链系统(如比特币)并没有很强的匿名性,没有办法隐藏住交易的数额或者用户。这也是零知识问题的由来。
  2. 如果要构造私密区块链,我们需要实现哪些部分(ZCash中的私密交易,Pedersen承诺,区间证明,所有权证明)。
  3. 我们系统性的介绍了SNARK的定义,并且把要解决的问题(如区间证明,Merkle证明)转换成数学运算电路
  4. 把数学运算电路转换成了R1CS的形式来表达,并且把R1CS程序验证转换成了多项式取值验证的形式
  5. 学习了解了PCP是什么,然后把PCP问题约束到LPCP问题
  6. 把多项式取值验证的问题简化成几个Query,然后使用LPCP的形式来表述。
  7. 尝试把LPCP中的交互部分移除(使用Fiat-Shamir)。
  8. 采用CRS模型再次尝试移除交互部分。
  9. 移除了交互部分之后,为了防止证明方做弊,引入了线性加密系统
  10. 结合线性加密系统与LPCP,构造出了CRS模型下的SNARK。
  11. 额外加入了一个随机线性检查,避免证明方再次做弊。
  12. 通过增加随机多项式取值点的方法,加入零知识部分。
  13. 分析讨论了zkSNARK和其他零知识体系的区别(可信初始化方面)。

希望大家看完这一期文章,对于zkSNARK和零知识证明整体有了一个更深的了解。我们下期再见啦。