零知识证明从入门到入土

　　文章共8000字，预计阅读时间3035分钟。
　　这篇博客的灵感来源于我的好朋友Kokii（Joey），感谢他通俗、详尽且充满趣味的介绍！
　　在谈论零知识证明之前，首先需要明确其定义：证明（Prover）向验证者（Verifier）证明一个命题成立，同时不泄露其他任何知识，这种就被称为零知识证明。鉴于零知识证明这个词太长，简称zk。文章是个人对于zk的理解，欢迎讨论。为什么要zk隐私
　　一个用户如果用过加密货币，就会发现，它并不像传说中的那么保密。不保密的原因显然，加密货币的信息都在区块链上，任何人都查询的到。虽然比特币等一部分加密货币出于隐私考虑，会给用户分配一个随机的地址，但这更像是假名，而不是号称的匿名，一旦用户到交易所将加密货币换成了法币，假名就和现实中的人对应上了。假名就像风清扬，初看无意义，但如果某次偶然，你发现风清扬对应着马云，之后再看到署名风清扬的邮件你就能想到那张大脸。匿名像大专院校的校园墙，墙上所有消息都是不署名的，对隐私的保护也更强。如果我们需要证明自己在校园墙上发过消息，但不想透露发的是什么消息，这时候该怎么办？如果还记得上面zk的定义，会发现zk完美地契合这种需求。
　　这就揭露了zk在区块链领域的第一个主要用途隐私，如果需要证明自己拥有某类账户的私钥但不想透露具体的账户地址，如果需要证明自己持有某种NFT一定时间但不想透露持有哪个NFT，这时就需要用到zk。扩容
　　以太坊的开发者和用户常常抱怨主链过慢的交易速度和过高的gasfee，为了解决这些问题，以太坊发展出了Layer2，当前主流的Layer2有两种：Optimismrollup和ZKrollup。
　　Optimismrollup目前最为常用，它默认对交易不执行任何计算，但为了防止欺诈，如果有人能够发现交易中的欺诈，可以进行证明并提出异议，如果异议被核实，欺诈者会受到惩罚，证明者会收获奖励。因为可能需要等待异议，Optimismrollup中交易的等待时间会比较长。
　　ZKrollup顾名思义，是使用到zk的扩容方式。ZKrollup会打包数百个交易生成SNARK（简洁的非交互式知识论证）或STARK（可扩展的透明知识论证）形式的有效性证明。ZKrollupLayer2的状态转移只需要提供有效性证明，不像Optimismrollup需要交易的全部信息，需要的空间更小；同时Layer2的数据转移到主链时不需要等待异议（因为都已经被证明有效了），完成的速度也更快。值得一提的是，有效性证明需要的计算量很大，同时因为改变了世界状态转移的方式，一些ZKrollup没有EVM的支持，但总的来说Optimismrollup是现在，ZKrollup是未来已成为一种区块链扩容的共识。童话世界
　　在深入历史、数学和计算机世界之前，不妨先看一眼童话世界。zk和它的表兄弟多方安全计算从诞生伊始就被各种童话故事所包围，这些故事极大地降低了zk的理解门槛，我选取了其中流传最广的一些故事，希望能有助于后续的理解。两个百万富翁
　　两个百万富翁的故事由姚期智院士在1982年发表的论文Protocolsforsecurecomputations中提出。
　　有两个百万富翁，他们的资产有1百万9百万，共9种可能。某一天，这两个百万富翁想比一比谁更有钱，但他们不希望透露自己的资产，既不想向对方，也不想向围观的群众透露。有没有一种既不透露他们的资产，又能比较谁更有钱的方法呢？
　　姚期智老师给出了以下的方法：
　　先造9个一模一样的箱子，放在房子里，箱子的钥匙只有富翁A拥有。先让富翁A进入房子，假设富翁A的资产是7百万，那么他在前7个箱子里放上1，在后2个箱子里放上0，将箱子锁好；之后让富翁B进入房子，假设富翁B的资产是5百万，那么富翁B就将第5个箱子拿出来，将其他箱子全烧了；最后富翁A使用钥匙打开富翁B拿出来的箱子，如果箱子中是1，代表A比B有钱，如果箱子中是0，代表B比A有钱。
　　在这个故事中，富翁A和B只知道自己的资产，但是他们成功比较出了谁更加有钱。当然，在这个故事中，我们默认两个富翁符合多方安全计算中的半诚实模型，即参与方会诚实的运行协议，但是他们会根据其它方的输入或者计算的中间结果来推导额外的信息，换句话说，这两个富翁都是乐于窥探他人隐私但诚实的人。安全模型
　　在安全多方计算中，根据参与方的可信程度可以建立三种安全模型：RealIdealParadigm（理想模型）：在理想模型中，每一个参与方都是可信的，一方将其信息发送给另一方，另一方不会去查看这份信息，只会根据规定计算出结果，并发送给下一方或者所有参与方。SemiHonestSecurity（半诚实模型）：半诚实模型就是参与方会诚实的运行协议，但是他会根据其它方的输入或者计算的中间结果来推导额外的信息。MaliciousSecurity（恶意模型）：恶意模型则可能不会诚实的运行协议，甚至会搞破坏。
　　在现实世界中，理性模型是不存在的，但相比于恶意模型，参与方如果真的想获取到同时对自己有用的信息（例如：真的想知道哪个富翁更加有钱），多数情况下符合半诚实模型。
　　接下来的这个故事也默认符合半诚实模型。员工平均工资
　　你是某公司的员工，觉得自己工资太少，但你每次向老板提出加薪要求的时候，老板总是用你已经超过公司的平均工资啦的理由来搪塞你。某天，你想弄清公司员工平均工资到底是多少，但由于公司合同，员工不能向他人透露工资的具体数目，有没有一种既不透露员工的工资，又能算出平均工资的方法呢？你开始思考。
　　不久，你发现了一种解决办法：
　　所有的员工围成一圈，每个员工都打造一对公钥E和私钥D，私钥D自己保存，公钥E发给右手边的员工。从员工1开始，员工1想一个大数M，将M与自己的工资X1相加后，使用公钥E2加密后发给员工2；员工2使用私钥D2解密之后，加上自己的工资X2，再使用公钥E3加密后发给员工3，以此类推，最终员工1会收到员工N发来的信息，使用私钥D1解密后，将数据减去大数M，再处以员工总数N，则算出了员工平均工资。
　　示意图中，黑括号内是员工能看到的信息，可以发现，所有员工除了知道自己的工资，并不知道其他任何人的工资。
　　上面两个故事是关于多方安全计算的，本文的重点zk与此有所不同，但他们共享着一些理念，下面是关于zk的故事。阿里巴巴和数独
　　阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个数独游戏才能获得宝藏，阿里巴巴知道数独的答案，而四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道数独的答案呢？（为了让四十大盗不要伤害自己）
　　聪明的阿里巴巴很快发现了证明方法：
　　假设黑色是数独的题面，红色是数独的解。阿里巴巴先制作81张数字1～9的卡片，黑色位置数字朝上，红色位置数字朝下，这样四十大盗并不能看到具体的解。阿里巴巴可以让四十大盗选择，是按行、按列还是按格子检验（Verify），假设四十大盗选择按行检验，阿里巴巴将每行的卡片放到一个袋子里，把卡片打乱，然后打开让四十大盗查看数字是否为1～9，这样按行、按列和按格子的检验可以重复进行多次。最后，阿里巴巴可以向四十大盗证明，如果他不知道数独的答案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗数独答案的情况下，向四十大盗证明了自己知道数独的答案。
　　这个故事就是一个典型的交互式zk，也称作IZK，阿里巴巴和四十大盗经过多轮的交互，最后阿里巴巴除了向四十大盗证明自己确实知道数独的答案，没有透露一点关于答案的知识，四十大盗到最后依然对数独的答案一无所知。阿里巴巴和三染色
　　阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个地图三染色游戏才能获得宝藏，阿里巴巴知道地图如何三染色，四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道地图三染色的方法呢？
　　聪明的阿里巴巴很快发现了证明方法：
　　阿里巴巴先将红绿蓝随机分配三个数字，之后将数字写在纸片上，面朝下盖在地图上。阿里巴巴可以让四十大盗随机选择两个临近的区域进行检验（Verify），翻开盖着的纸片，查看纸片上的数字是否不同。然后阿里巴巴重新给红绿蓝分配三个数字，重复上述的步骤。最后，阿里巴巴可以向四十大盗证明，如果他不知道染色方案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗地图如何染色的情况下，向四十大盗证明了自己知道染色方案。
　　有的地图是可以三染色的，例如左图；而有的地图无法进行三染色，例如右图。三染色是NPC（NPComplete）问题，NPC问题在多项式时间内可以检验，但不能在多项式时间内求解，并且所有的NP问题都能在多项式时间内规约到NPC问题，NPC问题在zk中起到了重要作用。阿里巴巴和哈密尔顿回路
　　这个是瞎编的但下文确实会出现哈密尔顿回路的故事，寻找哈密尔顿回路也是一个NPC问题（跟三染色一样）。什么是知识
　　Goldwasser等人在1985年zk的开创性论文Theknowledgecomplexityofinteractiveproofsystems中对知识的定义是theoutputofanunfeasiblecomputation，从中可以提取到两个关键词output和unfeasiblecomputation。首先，知识必须是一个输出，不能将我们藏在心里的信息称作知识；其次，知识必须是关于unfeasiblecomputation的，否则验证者（Verifier）根本不需要阅读证明者（Prover）的输出，如112这种常识，不能说验证者看到证明者输出112，验证者就获得了知识，因为即使验证者不看到输出，也能够自行算出112。
　　什么问题算是unfeasible呢？在zk中，一般说NP问题是unfeasible。图灵机
　　在解释P和NP前，需要先说明图灵机。计算机的先驱图灵构想了一种单带图灵机，这种机器只执行两种操作：在一条纸带上写上或擦除某个符号；将读取位置，从纸带的一处移动到另一处。
　　基于这个思想发展出来的机器，被称作图灵机，也称确定性图灵机，例如我们日常生活使用的个人电脑；而不确定性图灵机在现实并不存在，这是一种理想的产物，为了帮助我们理解NP问题，不确定性图灵机在遇到ifelse等分支语句时，能够同时计算所有的分支。
　　PNP
　　如上图所示，NP问题，是确定性图灵机在多项式时间内可以验证的问题，也是不确定性图灵机在多项式时间内可以求解的问题（但这种机器并不存在），例如在上文提到的阿里巴巴和三染色中，给定一种涂色方案，确定性图灵机（四十大盗）能够较快地完成验证；而P问题是在多项式时间内可以求解的问题。显然P属于NP，因为能在多项式时间内求解，一定能在多项式时间内验证，但P是否等于NP，依然是一个谜，不过目前大多数科学家选择信仰P不等于NP。
　　观察上图，能帮助理解知识的含义，当验证者面对NP问题时，如果没有看到蓝色计算路径，那么它无法在多项式时间内求解这个问题（因为现实的图灵机是确定性图灵机）；而一旦验证者看到了蓝色计算路径，那么它能很快地进行验证，这个蓝色计算路径就是知识。zk在证明过程中，不能透露关于蓝色计算路径的信息，因为一旦验证者看到了蓝色计算路径，它就同样能展示给别人看，以此冒充原本的证明者。ZK证明
　　两方面判断协议是否是zk，第一是零知识，第二是证明可靠，即不能随便一个没知识的证明者也能完成证明过程。换句话说，判断是否zk，需要对证明者安全、对验证者可靠。对证明者安全
　　先证明zk对证明者安全，以上文阿里巴巴和三染色为例，下图中变换了称呼，阿里巴巴变成了Alice，四十大盗变成了Bob，但他们交互的过程不变，希望不会引起误解。
　　零知识是为了保护证明者Alice利益的，因为Alice不希望透露任何信息给Bob。零知识的证明方法是通过模拟器，如果使用模拟器能够模拟出一个Zlice，Zlice没有任何信息，但是依然能够说服Bob，则说明Zlice所在的模拟世界是零知识的，又因为如果我们把Bob放入世界里，Bob没有办法区分自己是在现实世界还是在模拟世界，所以在现实世界里，协议也是零知识的，即对证明者安全。
　　以上图为例，模拟器模拟了一个Zlice，Zlice没有掌握任何知识，那么它是如何骗过Bob的呢？
　　Zlice在进行到step3时，它并没有揭露涂色方案，而是通过虚拟机的快照机制，记录了Bob的选择，并重新返回了step1，由于Bob目前是在虚拟机内运行的程序，所以它并没有感知到快照机制的启动（在现实世界的程序才能感知到快照的启动），在模拟的世界中，零知识的Zlice成功骗过了Bob，让Bob以为Zlice掌握了知识，而正如之前所说：Bob没有办法区分现实世界和模拟世界，所以在现实世界，协议也是零知识。
　　这里还有个疑惑，如果模拟器真的存在，对Bob来说岂不是一个灾难？有没有可能在现实世界里，Alice没有知识也能用这个模拟的方法骗到Bob？这是不可能的，因为虽然模拟世界和现实世界对Bob来说是不可区分的，但是模拟世界的Zlice需要使用超能力，例如虚拟机快照机制的时间倒流才能够骗到Bob选择相同的边，而这种超能力是现实世界的Alice所不具备的（毕竟没有人可以倒流现实中的时间）。
　　模拟器的超能力是有限的，例如它不能够改变Bob的内部状态，不能说Bob输出的False，模拟器强行改成了True，因为如果这样Bob就很容易确定自己处在模拟世界中！就像各类缸中之脑的科幻电影，如果人类发现了世界是模拟的，那模拟世界就崩塌了。模拟器的超能力被严格限制在现实中的虚拟机的能力范围。对验证者可靠
　　虽然在现实世界中，Alice没有时间倒流超能力，但是这并不能说明Alice就有知识，谁来保证验证者Bob的利益呢？
　　证明可靠是为了保护验证者Bob利益的，因为Bob不希望被没有知识的Alice欺骗。证明可靠的证明方法同样是通过模拟器，如果使用模拟器能够模拟出一个Zlice，Zlice能够提取出Alice的知识，则说明Zlice所在的模拟世界是证明可靠的，又因为如果我们把Alice放入世界里，Alice没有办法区分自己是在现实世界还是在模拟世界，所以在现实世界里，协议也是证明可靠的，即对验证者可靠。
　　下图使用的是Schnorr协议，该协议使用了椭圆曲线加密算法，由于篇幅原因这里不展开。简单理解下，a是密钥，aG是公钥，根据密钥a和椭圆曲线基点G可以轻松算出公钥aG，反之则不能（因为离散对数问题，这里用大数分解问题来帮助理解，给两个质数很容易算出他们乘积，但给一个大数，很难分解成两个质数）。
　　Schnorr协议共分以下四步：Alice生成随机数r，根据椭圆曲线基点G，计算RrG，将R发送给Bob；Bob生成随机数c（称作挑战challenge），将c发送给Alice；Alice计算zrca，将z发送给Bob；Bob验证zG，即（rca）G是否等于Rc（aG）。
　　接下来证明Schnorr协议对验证者可靠。
　　以上图为例，模拟器模拟了一个Zlice，Zlice是怎么提取出Alice的知识的呢？
　　Zlice在进行到step4时，它并没有验证zG是否等于Rc（aG），而是通过虚拟机的快照机制，记录了Alice发送的z，并重新返回了step2发送给了Alice另一个随机数c’，由于Alice目前是在虚拟机内运行的程序，所以它并没有感知到快照机制的启动（在现实世界的程序才能感知到快照的启动），在模拟的世界中，Zlice成功骗取Alice以相同的随机数r发送了两个z，算出了Alice的私钥a，而正如之前所说：Alice没有办法区分现实世界和模拟世界，所以在现实世界，协议也是证明可靠。
　　如果模拟器真的存在，对Alice来说岂不是一个灾难？有没有可能在现实世界里，Bob也能用这个模拟的方法骗到Alice的密钥？这是不可能的，因为虽然模拟世界和现实世界对Alice来说是不可区分的，但是模拟世界的Zlice需要使用超能力，例如虚拟机快照机制的时间倒流才能够骗到Alice不更改随机数r，而这种超能力是现实世界的Bob所不具备的（毕竟没有人可以倒流现实中的时间）。
　　以上用两个例子（三染色、Schnorr）展示了zk证明的全过程，分别证明了zk协议对证明者安全、对验证者可靠。禁忌
　　观察虚拟机所代表的模拟世界中发生的事，我们可以发现，有些事是在IZK协议中绝对不能做的：验证者不随机（三染色验证同一条边，使证明者可以欺骗验证者）证明者不随机（Schnorr中r保持不变，使验证者可以提取证明者的知识）
　　如果在IZK中犯了上面的错误，就相当于在现实世界给予了对手超能力，这会造成恶劣的影响，例如2011年SonyPlaystation3的root私钥的泄漏，就是因为索尼工程师没有更改Alice的随机数r。NIZK
　　除了IZK，区块链更常使用的是非交互式zk，简称NIZK。区块链上的一个交易会分发给多个矿工进行验证，如果每个矿工都进行交互式的验证，那耗时将是难以想象的。而NIZK在证明者进行一次证明之后，能够取信多个验证者，所以更加适合区块链上的场景。随机预言机
　　上文所说的Schnorr协议也有NIZK的版本：
　　从图中可以看到，NIZK版本取消了Bob人工的随机challenge，而是使用Hash（PK，R）来表示随机challenge，相当于引入了一个虚拟的第三方（数学之神）来产生随机数c，并且证明者和验证者都认可这个第三方生成的随机数（Hash值）。
　　NIZK形式的Schnorr协议，也是需要证明对证明者安全、对验证者可靠的，同样是使用模拟的方法进行证明，这里不展开。
　　值得一提的是，在禁忌中明确写有验证者不随机。换句话说，在NIZK中，我们需要challengec是由一个完全随机的预言机生成的，而这个理想中的随机预言机和上图中的Hash（PK，R）还是有很大区别：随机预言机每次对于新字符串返回的是一个具有一致性分布的真随机数Hash函数计算的结果并不是一个真正具有一致性分布的随机数
　　既然Hash函数并不是我们理想中的随机预言机，那我们为什么还信任使用Hash函数的SchnorrNIZK协议呢？这是因为我们假设一个具有密码学安全强度的Hash函数能够近似地模拟随机预言机，默认这个假设的模型被称为标准模型，不默认这个假设的模型称为非标准模型。这种使用Hash函数将IZK变成NIZK的方法，被称为FiatShamir变换。
　　使用FiatShamir变换将IZK变换成NIZK的时候，需要注意Hash函数需要包含所有逻辑上早于Hash函数的随机数，例如SchnorrNIZK中的Hash函数中就一定要包含r，否则就相当于在现实世界给予了证明者时间回溯的能力，证明者可以通过选择随机数，使得最终验证结果无误。公共参考串
　　除了随机预言机，NIZK还能采用公共参考串（CommonReferenceString），简称CRS来生成随机challengec。如果说随机预言机是隐式地引入了第三方，那么公共参考串就是直接显式引入第三方。
　　还记得阿里巴巴和哈密尔顿回路吗？哈密尔顿回路是图中经过所有节点仅一次的回路，寻找哈密尔顿回路是一个NPC问题。
　　上图是一个IZK，Alice向Bob证明自己知道图G的哈密尔顿回路，证明的交互过程是：Alice随机拖动图G，生成图G’（拖动操作对图来说是同构的，不会改变图的哈密尔顿性质），Alice将变换后的图G’加密发送给Bob；Bob发出挑战b；如果b为0，Alice发送变换函数Perm并解密G’，Bob验证G’是否由原图G通过变换函数Perm得到；如果b为1，Alice计算原本的哈密尔顿回路C在变换之后的位置C’，解密G‘中C’所在的位置，Bob验证解密的是否为一个哈密尔顿回路。
　　当b为1时，Alice解密的C’属于G’，根据集合的性质！G’应该属于！C’（原图的补集应该属于哈密尔顿回路的补集），所以上图的交互过程也可以更改成：
　　观察上图，变换之后证明的交互过程是：Alice随机拖动哈密尔顿回路C，生成C’，Alice将变换后的哈密尔顿回路C’加密发送给Bob；Bob发出挑战b；如果b为0，Alice解密C’，Bob验证C’是否是一个哈密尔顿回路；如果b为1，Alice计算原图G在变换之后的位置G’，发送变换函数Perm并解密C’中的！G’，Bob验证解密的位置是否全部为0（即！G‘是否属于！C’），同时验证G’是否由原图G通过Perm变换得到。
　　这跟公共参考串CRS有什么关系呢？
　　我们仔细观察能够发现，交互式证明的第一步Alice随机拖动哈密尔顿回路C，生成C’是跟图G无关的。所以完全可以通过第三方生成一个随机的哈密尔顿回路C’，而使用随机的C’和C反向算出变换函数Perm。
　　由于C’是第三方提供的，所以b为0没有了意义，Bob只需要检验b为1的情况。但第三方生成的C’是不能被Bob看到的，因为一旦Bob看到了C’，又知晓变换函数Perm，是很容易逆向算出原图G的哈密尔顿回路C的，所以C’必须是对Bob的隐藏比特。Bob收到Alice发送的！G’后，需要做两个验证，一是验证G’是否由原图G通过变换函数Perm生成，二是验证隐藏比特C’中，！G’位置是否都为0（即验证！G’是否属于！C’）。
　　该协议同样可以通过模拟证明是ZK的，这里不展开。
　　但到这一步还没有结束，因为第三方生成的C’是只有Alice能够看到的，而Bob无法看到，因此还不能说C’是公共的参考串CRS。解决问题的办法是使用限门置换：
　　限门置换函数是一个正向很容易计算但反向很难的函数，可以把它理解为一种加密。同时限门置换也可以匹配一个HardcorePredicate，HardcorePredicate能生成我们需要的隐藏比特，隐藏比特中含有哈密尔顿回路C’。当在哈密尔顿回路NIZK中，Alice需要揭露！G’所对应的某个隐藏比特时，它提供对应位置的x，Bob在收到x后，会通过HardcorePredicate验证对应的隐藏比特是否为0，同时通过限门置换函数F严重对应的CRS是否正确。
　　这样就实现了CRS，而哈密尔顿回路又是NPC问题，任何NP问题都能在多项式时间内规约到哈密尔顿回路问题，所以基于NP问题的IZK都能通过使用CRS变成NIZK形式了。zkSNARKs
　　Vitalik在21年写过多篇文章介绍zkSNARKs，这里认为有必要简述以下。zkSNARKs，全称零知识简洁的非交互式知识论证，zkSNARKs常常使用随机预言机来实现NIZK（IZK的FiatShamir变换），但他们的IZK形式通常不是Schnorr协议，而是哈希串的多项式比较验证等形式。尾记
　　zk是一个涉及多方面的领域，从软件到硬件，从zk协议到加密算法，几乎都能够和zk扯上关系，文中只介绍了从入门到入土的内容，没有详细介绍限门置换、硬件实现、新的NIZK协议等等内容，如果感兴趣可以查看该网站。
　　今天就到这里，再见。
　　参考文章
　　Gradwohl，Ronen，etal。CryptographicandphysicalzeroknowledgeproofsystemsforsolutionsofSudokupuzzles。TheoryofComputingSystems44。2（2009）：245268。
　　QuisquaterJJ，QuisquaterM，QuisquaterM，etal。Howtoexplainzeroknowledgeprotocolstoyourchildren〔C〕ConferenceontheTheoryandApplicationofCryptology。Springer，NewYork，NY，1989：628631。
　　FiatA，ShamirA。Howtoproveyourself：Practicalsolutionstoidentificationandsignatureproblems〔C〕Conferenceonthetheoryandapplicationofcryptographictechniques。Springer，Berlin，Heidelberg，1986：186194。
　　Goldwasser，S。，S。Micali，andC。Rackoff。Theknowledgecomplexityofinteractiveproofsystems。ProceedingsoftheseventeenthannualACMsymposiumonTheoryofcomputing。1985。
　　Yao，AndrewC。Protocolsforsecurecomputations。23rdannualsymposiumonfoundationsofcomputerscience（sfcs1982）。IEEE，1982。
　　https：zhuanlan。zhihu。comp98077048
　　https：github。comsecbitlearningzkp