浅谈零知识证明：背景与起源 本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学，本系列文章来源于作者在斯坦福著名的课程《CS 251: Cryptocurrencies and blockchain technologies》上的学习笔记，该课程授课老师是密码学大拿 Dan Boneh。前段时间略忙，主要时间在研究全同态算法FHE和可信多方计算MPC方面的内容，所以迟迟没有写完zkSNARK具体实现的下篇。这次回来补上下篇！ 回顾一下上一期，我们讲到了PCP定理 ， 并且从PCP定理出发约束到了 LPCP 。随后我们讲到了如何用Fiat-Shamir把交互式的协议压缩成非交互式协议。最后我们学习了 R1CS矩阵程序 ，以及如何从R1CS矩阵得到对应的 多项式表达式 。
掌握R1CS之后，其实距离我们的结果zkSNARK已经不远了。今天这一期我们着重的了解一下，从R1CS电路到zkSNARK需要经过的三大步 ：
从R1CS电路 出发，建立我们的线性PCP （LPCP）交互式证明系统。
把LPCP 交互系统转换成需要可信初始化的非交互式简短证明 （SNARK w/ Trusted Setup）。
加入零知识 （zk）。
话不多说，我们开始吧。
上一期结束的时候，我们大致的介绍过如何把区间证明的电路转换成R1CS矩阵程序，最后再转换成多项式。想必大家都大致了解了如何把R1CS的三个矩阵转换成多项式的过程——通过范德蒙矩阵 上一期我们看到的从R1CS是如何转换到多项式的 。 首先，我们使用 随后，我们将还原为多项式 范德蒙反矩阵 把这些取值点还原成一个 最后对于额外定义 个点的取值 （这样我们就有 因为多项式保持了原先矩阵之间的关系 ，如果R1CS矩阵之间满足反过来也是一样 ，如果我们可以找到三个多项式并且 这一关系就是把R1CS转换成LPCP的核心思路了 。只要我们可以验证三个多项式满足正确的 ，进而代表证明方的私密输入 也是正确的 ！ 如果放在LPCP的语言里来说的话，我们想要随机抽查一个点 ，验证这三个多项式在这一点的关系一下子验证了所有的约束 ！而且这里不管有多少条约束，都是一样的。验证大小独立于约束的多少（即电路的大小）。这就是“简短性“的精髓了。 在之前的文章中，我们了解过范德蒙矩阵 式如何通过多项式的取值来还原多项式的系数 的。同理可得，我们也可以用一样的矩阵相乘 来表达一个多项式 在 这个点上的取值： 一旦转换成最后形态的表达式之后，我们马上可以发现，由于 与R1CS矩阵 证明方和验证方都公开的内容， 是验证方选择的随机抽验的取值点，所以我们可以把整个表达式分成两个部分 ： 左边部分我们用一个向量 来表示，代表证明方想要验证的query 。右边部分就是包含了证明电路中公有和私密输入的矩阵 。对于多项式 ，我们也如法炮制，得到另一对内积组合 。 最后对于多项式 ，我们进行类似的操作。为了让整体的维度保持一致，我们需要额外加上一组单位矩阵 ： 具体的数学公式看似比较复杂，但是其实理解起来很简单：我们只需要把三个多项式 在 上的取值转换为了两个向量的内积 。 如果我们细心观察的话， 我们发现 这三个向量可以由验证方生成，而证明方只需要准备好电路的输入 就好了。这样一来，我们变相的把所有的计算难度放在了验证方的一侧 ，而证明方则不需要太多的运算。 当我们成功的把多项式随机取值问题分解为三个query向量 之后，我们就可以正式地进入真正的LPCP验证协议了 。
首先，证明方Prover 事先计算好证明 ，并且把证明保存起来，不许修改它。 验证方Verifier 随机的抽选一个验证点 ，并且根据 的取值计算得到三个query的向量 这三个 Query需要和我们原本的输入向量 相乘。我们观察这个向量之后发现，验证方事先已经可以得知向量的上半部分 。所以验证方可以把Query向量 进行切割，变成 两部分。这样的话，原本的计算也可以一分为二，然后把两部分的内积分别对叠起来： 通过这一步切割，我们发现对于 部分的计算，验证方已经全部知道了 ，所以我们可以进一步的优化证明方需要做的计算 ，只把 发送给证明方，让证明方仅仅与私密输入 相乘。 综上所述，验证方现在可以发送 三个query向量给证明方。 证明方收到query向量之后，只需要把每个值和自己的证明向量 相乘 。由于证明向量 后面还带了多项式 的额外 个取值点，所以我们需要在 的背后补上一个空白矩阵 ，才可以适配矩阵相乘的维度。 最后，验证方只需要把左侧query的内积补上 ，最后检查等式是否相 等： 如果得到的 所组成的等式的确相等，那么就代表 。根据我们上文讨论的关系，这也就直接代表了 这样一来，我们就得到了完全版的LPCP协议 啦。通过抽查三个多项式在某个点上的随机取值，我们达到了简短证明的目的。只要证明方与验证方严格遵守上述描写的协议 ，那么就可以有效的通过简短交互 来验证一个R1CS矩阵所对应的多项式是否满足我们想要的关系 。 从LPCP到SNARK w/ Trusted Setup
我们距离最后的胜利，已经非常接近了！
当我们成功的推导出了可以证明R1CS电路正确性的LPCP协议之后，我们会发现LPCP是一个交互式协议。这也就是说，证明方首先需要生成一个证明字串 ，然后保证不会去改动这个字串（可以通过承诺来实现）。随后，验证方会随机抽选三个Query： 发送给证明方，随后证明方需要诚实的返回对应的乘积 三个值进行验证。
下一步，我们需要把LPCP协议进一步压缩成一个 简短无交互式的协议 。 在LPCP中，我们现在依靠验证方生成随机验证Query，即 ，然后证明方需要根据Query的取值来“回答”，生成答案 。如果我们想要把整个证明变得无交互的话，我们就需要想办法把“证明方随机生成Query” 这个步骤去除掉。 我们在上一篇文章学习了 Fiat-Shamir Heuristic 。这个算法可以有效的把一个生成随机值的交互方使用一个 随机预言机 （即哈希函数）来替代。我们可以把Fiat-Shamir运用在我们的LPCP协议里，构建如下的非交互式系统： 证明方事先准备好证明 随后，证明方使用证明 验证方收到证明之后，只需要重新自己进行一遍计算，就可以确认证明是否正确了。 这样一来，看似我们把LPCP做成了非交互式的样子，但是随之而来的，是 更大的问题 。 首先，证明方需要把整个证明 全部发送给验证方，因为验证方随后要重复进行一模一样的计算。这一步就已经打破了我们之前的简短性要求，因为 的长度取决于 的大小以及多项式 的阶度，而这两个值恰好和电路的大小是成正比的。所以这样一来我们 通讯的成本就和电路大小挂钩 了，这和我们一开始想要达到的并不符合。 第二个问题在于 零知识 。虽然我们还没有说到零知识的部分，但是我们可以发现，如果证明方把 全部发送给验证方，那么证明方所有的私密输入 已经全部暴露无疑了。验证方其实并不想要看到这么多信息，只需要看到 三个乘积就够了。但是为了验证Fiat-Shamir变换是正确的，又不得不看到产生随机Query的哈希函数的输入，即证明 。 这么看来，在随机预言机模型（Random Oracle Model） 下，使用Fiat-Shamir变换对于我们的LPCP协议并没有太大帮助，无法达到我们想要的目的。这个时候该怎么办呢？ 其实，为了避免交互，zkSNARK使用了密码学中另有的一个假设： 公共参考字串（CRS） 。 公共参考字串（Common Reference String，CRS）模型
公共参考字串（CRS）其实是一个相比起随机预言机更为简单的假设，具体是这样的： 我们假设在一个协议中，证明方与验证方都拥有一段相同的参考字串。这个字串可能是随机生成的，也可能是某个函数的输出。重要的是完成协议的两方并不知道这个字串具体是如何被生成的，就感觉像是天上掉下来的一样。
在CRS假设下，一个协议的双方可以共享一段事先生成的，但是谁也不知道是怎么生成的参考字串 ，并且基于这个参考字串完成原本的协议。 举个例子来说，假如为了完成一个协议，Alice与Bob都需要使用一个随机生成的一串数字 假如说我们构想的这个协议中，双方都需要使用这个随机数来“抽查”他们的数据库内容是否正确，那么这个场景下，任何人都不可以知道生成这个随机数的种子，不然他们就可以事先做假，把会被检查到的那一部分数据改成对的。 这个时候，我们就可以使用CRS模型了。我们假设事先有别人已经选好了一个随机种子，并且根据这个种子验证生成了我们需要的随机数 当然，有朋友看到这里会有些疑惑：既然CRS是公开给所有人的，那么Alice和Bob都可以事先根据CRS中看到的随机数来找到会被“抽查”的部分 ，然后进行做弊呢？ 没错，如果直接把随机数放入CRS中是不行的。但是这个问题其实非常容易解决——我们只需要把生成的随机数加密起来 就行了，这样就算被看到了也无法从密文中得知信息来做弊。 一旦涉及到加密，就还会派生出一系列的小问题。这里我们先留做一个悬念，稍后我们会回来重点描述这一部分 。 回到我们之前的LPCP的问题上来。我们如果要去除LPCP的交互部分的话，我们就需要想办法不用交互，但是可以随机生成我们需要的Query 学会了CRS模型之后，这个问题就变得简单了：我们只需要让别人事先生成好这些Query ，然后通通丢进CRS里 面，这样证明方就不需要与验证方交互就可以拿到这些随机生成的Query了。 我们接着这个想法，构想一下CRS模型下无交互LPCP 的大概步骤：
首先，第三方根据LPCP用到的R1CS电路，选取随机数 证明方准备好自己的证明向量 验证方根据CRS得到 如果我们观察一下我们得到的无交互LPCP的话，我们会发现这距离我们想要的非常接近了 ！证明方与验证方的沟通非常简短 ，只需要发送三个数字即可。验证方所需要做的事情相对来说也很简单，只需要做比较短的矩阵相乘，再把结果加上比较一下就ok了。 然而，这个体系现在还有一个很大的问题：随机生成的Query直接暴露在CRS当中 。 和上一段结尾提到的问题一样，如果证明方在生成证明向量根据Query要取值的点来做弊 ，制造出虚假的证明来。 如何保证CRS中的Query不能被用来做弊，但是仍然还可以计算后面的内积呢？我们在上一段结尾也说到了，需要依靠一种比较特殊的加密系统：线性加密系统（Linear-only Encoding） 。 线性加密系统Linear-only Encoding
我们来回顾一下对于这一加密系统的需求。我们把加密原文 首先，为了防止证明方实现看到Query的内容进行作弊，我们的加密系统一定要能够隐藏Query本身 。也就是说看到密文的证明方并不可以得到任何和原文有关的信息。这一点所有的加密算法都可以做到。 其次，我们需要保证证明方仍然可以生成内积 验证方可以进行验证 。这一点其实是一个非常独特的需求，我们可以把这两个要求拆开来看一下： 证明方可以生成内积线性组合 。完成这一点我们可以使用拥有加法同态 特性的加密算法。 验证方可以验证类似于乘法同态 一样的验证。这一点要求比较特殊，我们在选择加密算法的时候要额外注意。 除了上面两条必须要符合的特性之外，出于安全性考虑我们还需要考虑第三条： 证明方只能生成Query 的线性组合，并不能生成任何其他的密文 。这个要求的原因很简单，如果证明方可以任意生成合理的密文的话，那么他就可以不管看到的Query是什么，随便生成一组合理的 当我们归纳出这三条要求之后，接下来我们可以系统性地定义一下线性加密系统 。 生成算法 验证算法 加法同态运算 乘积验证 一个线性加密系统还需要满足两条额外的属性（properties） ： 单向性（One-way） ：这条属性是说，如果看到了仅限线性组合（Linear-only） ：这一点要求了，如果给定了一组密文一般来说，满足这些要求的线性加密系统很少。一个最常见的例子，就是有Pairing配对属性的循环群 在循环群中，我们拥有生成元 同时，因为我们选择的循环群拥有配对操作 ，所以我们可以非常轻松的验证密文的乘积是否相等。 有了线性加密系统之后，我们之前在尝试无交互LPCP的时候遇到的作弊问题就引刃而解了。 当我们把线性加密系统应用于无交互LPCP的系统中，我们就得到SNARK了！
因为距离上一期又过去了一段时间，我们再来回顾一下这个系列第二篇文章提到的简短证明体系(SNARK)的三个核心算法：Setup，Prove和Verify 。
：通过实现约定好的电路，生成后续需要使用的随机参数 接下来，我们结合刚刚学到的知识点，把SNARK的三个基本算法具体实现一下： ：首先，我们根据R1CS的电路的大小，随机选取我们要用到的Query ：证明的过程也很简单，证明方先准备好LPCP的证明字串 ：验证就和我们之前说的一样，首先验证方需要自己计算 这就是基于LPCP的SNARK 的全貌了。我们发现这个系统满足了我们之前的所有要求，即简短、无交互、知识证明 。在我们收尾之前，还有一些小细节需要关注一下。 随机线性检查（Random Linearity Check）
当我们加上了线性加密系统之后，现在得到的SNARK还有一个巨大的漏洞 。 我们观察发现，因为Query的部分都是加密隐藏起来的，所以证明方还可以做一个骚操作：在计算在中途偷偷的变换用到的证明 这一问题解决的方法也不难，我们需要修改一下LPCP协议，在中间多加上一个随机线性检查（Random Linearity Check） 。 在我们生成LPCP的Query 这样一来，最后验证方可以收到四个数字，即 如果符合检查的话，那就表示证明方在生成 同理可得，在SNARK中，我们需要在 这样一来，验证方可以首先通过如果两次检查都通过了，那就基本上等于LPCP通过了 。 加上随机线性检查之后，我们就得到了zkSNARK中的SNARK的完全体啦。 如果你看到这儿，我们已经完成了99% ！最后一步也是最简单的一步，就是加上零知识 。
我们在当前的SNARK中，只需要做一个非常细微的变动，就可以转换成zkSNARK 了。 我们观察发现，证明方唯一暴露给验证方的数据，就是确保 不会暴露任何信息 ，那这个协议就符合零知识的定义了。 我们再仔细观察就会发现，任何一丁点 信息，所以我们也不能暴露多项式插值 的方法还原出系数。 解决的方法也非常简单，我们只需要在一开始还原多项式额外选择两个随机数 具体的证明我在这里就不多说了，不过大概的构造是：如果我们在给定的一组取值点中再额外增加一个随机取值点 的话，那么最后新得到的多项式就会拥有和这个随机数类似的一个随机分布 ，这样我们就没法从新得到的多项式中看到和原来的多项式相关的任何信息，也就是我们所说的零知识了。 在结束之前，我还想再和大家聊一聊对于SNARK中
我们观察会发现，在我们构造的zkSNARK体系当中，Setup这一步需要由第三方来完成。在整个协议的过程中，只要证明方得知任何一点Setup中用到的数值（比如说随机数、随机种子等等），那么证明方就可以马上用这些知识来做弊，使得自己可以生成虚假证明，欺骗任何人。
如果应用在ZCash场景中（第一期有所提到），如果掌握了这些随机参数的人，就可以随机的给自己发钱，任意铸币，破坏整个生态系统。
这也就是说，单纯的委托第三方来生成这些参数的话，我们还必须要确保第三方必须要在生成完之后，彻底摧毁 所用生成所用的参数。这一过程我们称之为可信初始化（Trusted Setup） 。ZCash在可信初始化这步做出了各种惊人的举动：比如去切尔诺贝利核电站去读取辐射数据，用辐射的指数作为随机数值来生成Query等等…… 我们通过LPCP生成的SNARK中，所有的Query 对于每个电路的验证，都需要经过一次可信初始化的过程 。这其实是一个比较麻烦的事情，如果我们想要验证别的东西，或者修改电路逻辑，我们就需要额外的再初始化一次，这会浪费很多资源，并且效率也不是很高。虽然对于ZCash来说，验证的电路都是相同的（验证交易的数额与Nullifier），但是这仍然是zkSNARK面临的一个巨大挑战。 相比起来，同一阶段还有一些别的零知识证明体系 ，可以解决可信初始化的问题。 一方面的体系，类似于Sonic，Plonk，Marlin ，选择的路线是通用可信初始化（Universal Trusted Setup）。意思是说，我们只需要初始化一次，然后生成的随机Query可以适用于任意的电路 。这样一来，我们可以节约很多成本。 另一类不同的体系，是彻底抛弃了可信初始化的概念，比如说STARK，SuperSonic 等等。这一类的体系用的方法和我们一开始提出的Fiat-Shamir的去交互方法非常相似。我们遇到的问题在于Fiat-Shamir生成的无交互系统没法达到我们简短性的要求，这是因为LPCP基于PCP，本身证明多项式承诺 与多项式取值验证（Polynomial IOP） 。具体的就不多说啦，感兴趣的朋友可以去读一读STARK的文章研究一下构造。
从19年圣诞节左右开始酝酿零知识方面的文章，一直到20年夏天，经过了疫情，终于把zkSNARK的整体构造写完了 。开始写之前本来觉得是一个比较简单的概念，但是真正开始研究之后，发现每一步里面都蕴涵了很多知识和对应的背景材料。
在最后，我们再来回顾一下我们一共学习了哪些内容：
区块链系统（如比特币）并没有很强的匿名性，没有办法隐藏住交易的数额或者用户。这也是零知识问题的由来。
如果要构造私密区块链，我们需要实现哪些部分（ZCash中的私密交易，Pedersen承诺，区间证明，所有权证明）。
我们系统性的介绍了SNARK的定义，并且把要解决的问题（如区间证明，Merkle证明）转换成数学运算电路 。
把数学运算电路转换成了R1CS的形式来表达，并且把R1CS程序验证转换成了多项式取值验证的形式 。
学习了解了PCP是什么，然后把PCP问题约束到LPCP问题 。
把多项式取值验证的问题简化成几个Query ，然后使用LPCP的形式来表述。
尝试把LPCP中的交互部分移除（使用Fiat-Shamir ）。
采用CRS模型再次尝试移除交互部分。
移除了交互部分之后，为了防止证明方做弊，引入了线性加密系统 。
结合线性加密系统与LPCP，构造出了CRS模型下的SNARK。
额外加入了一个随机线性检查 ，避免证明方再次做弊。
通过增加随机多项式取值点的方法，加入零知识 部分。
分析讨论了zkSNARK和其他零知识体系的区别（可信初始化方面）。
希望大家看完这一期文章，对于zkSNARK和零知识证明整体有了一个更深的了解。我们下期再见啦。
