# 零知识证明：从入门到入土

By [choovybi](https://paragraph.com/@choovybi) · 2022-09-26

---

> 文章共8000字，预计阅读时间30-35分钟。

这篇博客的灵感来源于我的好朋友[Kokii(Joey)](https://linktr.ee/0xkokii)，感谢他通俗、详尽且充满趣味的介绍！

在谈论「零知识证明」之前，首先需要明确其定义：证明者（Prover）向验证者（Verifier）证明一个命题成立，同时「不泄露其他任何知识」，这种就被称为「零知识证明」。鉴于「零知识证明」这个词太长，简称「zk」。文章是个人对于zk的理解，[欢迎讨论](https://linktr.ee/choovybi)。

为什么要zk
------

### 隐私

一个用户如果用过加密货币，就会发现，它并不像传说中的那么「保密」。「不保密」的原因显然，加密货币的信息都在区块链上，任何人都查询的到。虽然比特币等一部分加密货币出于隐私考虑，会给用户分配一个随机的地址，但这更像是「假名」，而不是号称的「匿名」，一旦用户到交易所将加密货币换成了法币，「假名」就和现实中的人对应上了。「假名」就像「风清扬」，初看无意义，但如果某次偶然，你发现「风清扬」对应着马云，之后再看到署名「风清扬」的邮件你就能想到那张大脸。「匿名」像大专院校的「校园墙」，墙上所有消息都是不署名的，对隐私的保护也更强。如果我们需要证明自己在「校园墙」上发过消息，但不想透露发的是什么消息，这时候该怎么办？如果还记得上面zk的定义，会发现zk完美地契合这种需求。

这就揭露了zk在区块链领域的第一个主要用途——隐私，如果需要证明自己拥有某类账户的私钥但不想透露具体的账户地址，如果需要证明自己持有某种NFT一定时间但不想透露持有哪个NFT，这时就需要用到zk。

### 扩容

以太坊的开发者和用户常常抱怨主链过慢的交易速度和过高的gas fee，为了解决这些问题，以太坊发展出了Layer 2，当前主流的Layer 2有两种：Optimism roll-up和ZK roll-up。

Optimism roll-up目前最为常用，它默认对交易不执行任何计算，但为了防止欺诈，如果有人能够发现交易中的欺诈，可以进行证明并提出异议，如果异议被核实，欺诈者会受到惩罚，证明者会收获奖励。因为可能需要等待异议，Optimism roll-up中交易的等待时间会比较长。

![Optimism roll-up](https://storage.googleapis.com/papyrus_images/1ac9a2a5dab09c283e0ba15237c5b968da69b7fea1dc105c0627e07678af99ff.png)

Optimism roll-up

ZK roll-up顾名思义，是使用到zk的扩容方式。ZK roll-up会打包数百个交易生成SNARK（简洁的非交互式知识论证）或 STARK（可扩展的透明知识论证）形式的有效性证明。ZK roll-up Layer 2的状态转移只需要提供有效性证明，不像Optimism roll-up需要交易的全部信息，需要的空间更小；同时Layer 2的数据转移到主链时不需要等待异议（因为都已经被证明有效了），完成的速度也更快。值得一提的是，有效性证明需要的计算量很大，同时因为改变了世界状态转移的方式，一些ZK roll-up没有EVM的支持，但总的来说「Optimism roll-up 是现在，ZK roll-up是未来」已成为一种区块链扩容的共识。

童话世界
----

在深入历史、数学和计算机世界之前，不妨先看一眼童话世界。「zk」和它的表兄弟「多方安全计算」从诞生伊始就被各种童话故事所包围，这些故事极大地降低了「zk」的理解门槛，我选取了其中流传最广的一些故事，希望能有助于后续的理解。

### 两个百万富翁

「两个百万富翁」的故事由姚期智院士在1982年发表的论文「_Protocols for secure computations_」中提出。

> 有两个百万富翁，他们的资产有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只知道自己的资产，但是他们成功比较出了谁更加有钱。当然，在这个故事中，我们默认两个富翁符合多方安全计算中的「半诚实模型」，即「参与方会诚实的运行协议，但是他们会根据其它方的输入或者计算的中间结果来推导额外的信息」，换句话说，这两个富翁都是「乐于窥探他人隐私但诚实」的人。

### 安全模型

在安全多方计算中，根据参与方的可信程度可以建立三种安全模型：

*   Real-Ideal Paradigm（理想模型） ：在理想模型中，每一个参与方都是可信的，一方将其信息发送给另一方，另一方不会去查看这份信息，只会根据规定计算出结果，并发送给下一方或者所有参与方。
    
*   Semi-Honest Security（半诚实模型） ：半诚实模型就是参与方会诚实的运行协议，但是他会根据其它方的输入或者计算的中间结果来推导额外的信息。
    
*   Malicious Security（恶意模型） ：恶意模型则可能不会诚实的运行协议，甚至会搞破坏。
    

在现实世界中，「理性模型」是不存在的，但相比于「恶意模型」，参与方如果真的想获取到同时对自己有用的信息（例如：真的想知道哪个富翁更加有钱），多数情况下符合「半诚实模型」。

接下来的这个故事也默认符合「半诚实模型」。

### 员工平均工资

> 你是某公司的员工，觉得自己工资太少，但你每次向老板提出加薪要求的时候，老板总是用「你已经超过公司的平均工资啦」的理由来搪塞你。某天，你想弄清公司员工平均工资到底是多少，但由于公司合同，员工不能向他人透露工资的具体数目，有没有一种既不透露员工的工资，又能算出平均工资的方法呢？你开始思考。

不久，你发现了一种解决办法：

![员工平均工资](https://storage.googleapis.com/papyrus_images/d4c788bc749ac65003bbde1803eb0ac00fdbc2da9ce1471475c654af26da3244.jpg)

员工平均工资

所有的员工围成一圈，每个员工都打造一对公钥E和私钥D，私钥D自己保存，公钥E发给右手边的员工。从员工1开始，员工1想一个大数M，将M与自己的工资X1相加后，使用公钥E2加密后发给员工2；员工2使用私钥D2解密之后，加上自己的工资X2，再使用公钥E3加密后发给员工3，以此类推，最终员工1会收到员工N发来的信息，使用私钥D1解密后，将数据减去大数M，再处以员工总数N，则算出了员工平均工资。

示意图中，黑括号内是员工能看到的信息，可以发现，所有员工除了知道自己的工资，并不知道其他任何人的工资。

上面两个故事是关于「多方安全计算」的，本文的重点「zk」与此有所不同，但他们共享着一些理念，下面是关于「zk」的故事。

### 阿里巴巴和数独

> 阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个数独游戏才能获得宝藏，阿里巴巴知道数独的答案，而四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道数独的答案呢？（为了让四十大盗不要伤害自己）

聪明的阿里巴巴很快发现了证明方法：

![数独游戏](https://storage.googleapis.com/papyrus_images/601c6728ff8ff7114c3dd56d4faed9af46cfa2e90f10e38ab03b7e6508f80d48.jpg)

数独游戏

假设黑色是数独的题面，红色是数独的解。阿里巴巴先制作81张数字1～9的卡片，黑色位置数字朝上，红色位置数字朝下，这样四十大盗并不能看到具体的解。阿里巴巴可以让四十大盗选择，是按行、按列还是按格子检验（Verify），假设四十大盗选择按行检验，阿里巴巴将每行的卡片放到一个袋子里，把卡片打乱，然后打开让四十大盗查看数字是否为1～9，这样按行、按列和按格子的检验可以重复进行多次。最后，阿里巴巴可以向四十大盗证明，如果他不知道数独的答案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗数独答案的情况下，向四十大盗证明了自己知道数独的答案。

这个故事就是一个典型的「交互式zk」，也称作「IZK」，阿里巴巴和四十大盗经过多轮的交互，最后阿里巴巴除了向四十大盗证明自己确实知道数独的答案，没有透露一点关于答案的知识，四十大盗到最后依然对数独的答案一无所知。

### 阿里巴巴和三染色

> 阿里巴巴和四十大盗在寻宝途中遇到了难题，他们需要完成一个地图三染色游戏才能获得宝藏，阿里巴巴知道地图如何三染色，四十大盗不知道，阿里巴巴该如何在不告诉四十大盗答案的情况下，向四十大盗证明自己知道地图三染色的方法呢？

聪明的阿里巴巴很快发现了证明方法：

![三染色](https://storage.googleapis.com/papyrus_images/311611ae19e952265ed7492a40885ea2d53ce6c3af2a36cf220a86547d82782c.jpg)

三染色

阿里巴巴先将红绿蓝随机分配三个数字，之后将数字写在纸片上，面朝下盖在地图上。阿里巴巴可以让四十大盗随机选择两个临近的区域进行检验（Verify），翻开盖着的纸片，查看纸片上的数字是否不同。然后阿里巴巴重新给红绿蓝分配三个数字，重复上述的步骤。最后，阿里巴巴可以向四十大盗证明，如果他不知道染色方案，那么每次都能满足四十大盗检验的概率无限趋向于0，这样阿里巴巴就在不告诉四十大盗地图如何染色的情况下，向四十大盗证明了自己知道染色方案。

![三色问题](https://storage.googleapis.com/papyrus_images/85c631080e6a53b7e32463b25eccca7276498881e279b3b9b6b7cc9fc4462f68.jpg)

三色问题

有的地图是可以三染色的，例如左图；而有的地图无法进行三染色，例如右图。三染色是NPC（NP Complete）问题，NPC问题在多项式时间内可以检验，但不能在多项式时间内求解，并且所有的NP问题都能在多项式时间内规约到NPC问题，NPC问题在zk中起到了重要作用。

### 阿里巴巴和哈密尔顿回路

这个是瞎编的……但下文确实会出现哈密尔顿回路的故事，寻找哈密尔顿回路也是一个NPC问题（跟三染色一样）。

什么是知识
-----

_Goldwasser_等人在1985年zk的开创性论文「_The knowledge complexity of interactive proof-systems_」中对「知识」的定义是「the output of an unfeasible computation」，从中可以提取到两个关键词「output」和「unfeasible computation」。

*   首先，「知识」必须是一个「输出」，不能将我们藏在心里的「信息」称作「知识」；
    
*   其次，「知识」必须是关于「unfeasible computation」的，否则验证者（Verifier）根本不需要阅读证明者（Prover）的「输出」，如「1+1=2」这种常识，不能说验证者看到证明者输出「1+1=2」，验证者就获得了「知识」，因为即使验证者不看到输出，也能够自行算出「1+1=2」。
    

什么问题算是「unfeasible」呢？在zk中，一般说NP问题是「unfeasible」。

### 图灵机

在解释P和NP前，需要先说明「图灵机」。计算机的先驱图灵构想了一种「单带图灵机」，这种机器只执行两种操作：

*   在一条纸带上写上或擦除某个符号；
    
*   将读取位置，从纸带的一处移动到另一处。
    

基于这个思想发展出来的机器，被称作图灵机，也称「确定性图灵机」，例如我们日常生活使用的个人电脑；而「不确定性图灵机」在现实并不存在，这是一种理想的产物，为了帮助我们理解NP问题，「不确定性图灵机」在遇到「if - else」等分支语句时，能够同时计算所有的分支。

![P&NP的计算路径](https://storage.googleapis.com/papyrus_images/125396bb8735b0f7ddec37957f988ece0424c8cf33df999e3e1221d1e6b46f9a.jpg)

P&NP的计算路径

### P&NP

如上图所示，「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_没有办法区分自己是在现实世界还是在模拟世界，所以在现实世界里，协议也是「零知识」的，即对「证明者安全」。

![模拟证明者](https://storage.googleapis.com/papyrus_images/5717132dd0ab23cfa6ed880e5f82a1859b532feb906dfd42e88a6eb78c0fa5c9.jpg)

模拟证明者

以上图为例，模拟器模拟了一个_Zlice_，_Zlice_没有掌握任何知识，那么它是如何骗过_Bob_的呢？

_Zlice_在进行到step 3时，它并没有揭露涂色方案，而是通过虚拟机的「快照机制」，记录了_Bob_的选择，并重新返回了step 1，由于_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协议，该协议使用了[椭圆曲线加密算法](https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/)，由于篇幅原因这里不展开。简单理解下，a是密钥，a\*G是公钥，根据密钥a和椭圆曲线基点G可以轻松算出公钥a\*G，反之则不能（因为离散对数问题，这里用大数分解问题来帮助理解，给两个质数很容易算出他们乘积，但给一个大数，很难分解成两个质数）。

Schnorr协议共分以下四步：

*   _Alice_生成随机数r，根据椭圆曲线基点G，计算R=r\*G，将R发送给_Bob_；
    
*   _Bob_生成随机数c（称作挑战challenge），将c发送给_Alice_；
    
*   _Alice_计算z=r+c\*a，将z发送给_Bob_；
    
*   Bob验证z\*G，即(r+c\*a)\*G是否等于R+c\*(a\*G)。
    

接下来证明Schnorr协议对「验证者可靠」。

![模拟验证者](https://storage.googleapis.com/papyrus_images/9a75ee4bc34e1b780aaf91a9820192c131861acfe731347fccbf173d672bce06.jpg)

模拟验证者

以上图为例，模拟器模拟了一个_Zlice_，_Zlice_是怎么提取出_Alice_的知识的呢？

_Zlice_在进行到step 4时，它并没有验证z\*G是否等于R+c\*(a\*G)，而是通过虚拟机的「快照机制」，记录了_Alice_发送的z，并重新返回了step 2发送给了_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年Sony Playstation 3的root私钥的泄漏，就是因为索尼工程师没有更改_Alice_的随机数r。

NIZK
----

除了IZK，区块链更常使用的是「非交互式zk」，简称「NIZK」。区块链上的一个交易会分发给多个矿工进行验证，如果每个矿工都进行交互式的验证，那耗时将是难以想象的。而NIZK在证明者进行一次证明之后，能够取信多个验证者，所以更加适合区块链上的场景。

### 随机预言机

上文所说的Schnorr协议也有NIZK的版本：

![Schnorr NIZK](https://storage.googleapis.com/papyrus_images/965af2baa95556eebd11b0962e699ae92615e8dee3b917c2cbe0af4a0b960372.png)

Schnorr NIZK

从图中可以看到，NIZK版本取消了_Bob_人工的随机challenge，而是使用Hash(PK, R)来表示随机challenge，相当于引入了一个虚拟的第三方（数学之神）来产生随机数 c，并且证明者和验证者都认可这个第三方生成的随机数（Hash 值）。

NIZK形式的Schnorr协议，也是需要证明「对证明者安全」、「对验证者可靠」的，同样是使用模拟的方法进行证明，这里不展开。

值得一提的是，在「禁忌」中明确写有「验证者不随机」。换句话说，在NIZK中，我们需要challenge c是由一个完全随机的预言机生成的，而这个理想中的「随机预言机」「Random Oracle」和上图中的Hash(PK, R)还是有很大区别：

*   随机预言机每次对于新字符串返回的是一个具有一致性分布的「真」随机数
    
*   Hash 函数计算的结果并不是一个真正具有一致性分布的随机数
    

既然Hash 函数并不是我们理想中的随机预言机，那我们为什么还信任使用Hash 函数的Schnorr NIZK协议呢？这是因为我们假设「一个具有密码学安全强度的Hash 函数能够近似地模拟随机预言机」，默认这个假设的模型被称为「标准模型」，不默认这个假设的模型称为「非标准模型」。这种使用Hash 函数将IZK变成NIZK的方法，被称为「[Fiat-Shamir 变换](https://link.springer.com/content/pdf/10.1007/3-540-47721-7_12.pdf)」。

使用Fiat-Shamir变换将IZK变换成NIZK的时候，需要注意Hash 函数需要包含所有逻辑上早于Hash 函数的随机数，例如Schnorr NIZK中的Hash 函数中就一定要包含r，否则就相当于在现实世界给予了证明者「时间回溯」的能力，证明者可以通过选择随机数，使得最终验证结果无误。

### 公共参考串

除了随机预言机，NIZK还能采用「公共参考串」（Common Reference String），简称「CRS」来生成随机challenge c。如果说「随机预言机」是隐式地引入了第三方，那么「公共参考串」就是直接显式引入第三方。

还记得「阿里巴巴和哈密尔顿回路」吗？哈密尔顿回路是图中经过所有节点仅一次的回路，寻找哈密尔顿回路是一个NPC问题。

![哈密尔顿回路1](https://storage.googleapis.com/papyrus_images/1274c4ac4c067d10746ca43942cee79b666624eaa1f49f9d930de003b4f35a52.jpg)

哈密尔顿回路1

上图是一个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’（原图的补集应该属于哈密尔顿回路的补集），所以上图的交互过程也可以更改成：

![哈密尔顿回路2](https://storage.googleapis.com/papyrus_images/18237135c81ab9511132d8e525ff57b0c09a4f6a1e2aafbd4d217bd79b7f2073.jpg)

哈密尔顿回路2

观察上图，变换之后证明的交互过程是：

*   _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。

![哈密尔顿回路NIZK](https://storage.googleapis.com/papyrus_images/3d9f3c33d9bc723b01ba7837003dee64cf1c4d7e2aa022db027316421e2f6e89.png)

哈密尔顿回路NIZK

由于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」。解决问题的办法是使用「限门置换」：

![限门置换](https://storage.googleapis.com/papyrus_images/c1723d9394425ffcf65e2ca94450e83f20ffdaca69d1be211b5c4a4e6be0e4f7.png)

限门置换

「限门置换函数」是一个正向很容易计算但反向很难的函数，可以把它理解为一种加密。同时限门置换也可以匹配一个「Hardcore Predicate」，Hardcore Predicate能生成我们需要的隐藏比特，隐藏比特中含有哈密尔顿回路C’。当在哈密尔顿回路NIZK中，_Alice_需要揭露!G’所对应的某个隐藏比特时，它提供对应位置的x，_Bob_在收到x后，会通过Hardcore Predicate验证对应的隐藏比特是否为0，同时通过限门置换函数F验证x对应的CRS是否正确。

这样就实现了CRS，而哈密尔顿回路又是NPC问题，任何NP问题都能在多项式时间内规约到哈密尔顿回路问题，所以基于NP问题的IZK都能通过使用CRS变成NIZK形式了。

### zk-SNARKs

Vitalik在21年写过[多篇文章](https://vitalik.ca/general/2021/01/26/snarks.html)介绍zk-SNARKs，这里认为有必要简述以下。zk-SNARKs，全称「零知识简洁的非交互式知识论证」，zk-SNARKs常常使用随机预言机来实现NIZK（IZK的Fiat-Shamir变换），但他们的IZK形式通常不是Schnorr协议，而是哈希串的多项式比较验证等形式。

尾记
--

zk是一个涉及多方面的领域，从软件到硬件，从zk协议到加密算法，几乎都能够和zk扯上关系，文中只介绍了「从入门到入土」的内容，没有详细介绍限门置换、硬件实现、新的NIZK协议等等内容，如果感兴趣可以查看[该网站](https://kurtpan666.github.io/ktpzkp22.html)。

今天就到这里，再见。

[Subscribe](null)

参考文章

[_Gradwohl, Ronen, et al. "Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles." Theory of Computing Systems 44.2 (2009): 245-268._](https://link.springer.com/content/pdf/10.1007/s00224-008-9119-9.pdf)

[_Quisquater J J, Quisquater M, Quisquater M, et al. How to explain zero-knowledge protocols to your children\[C\]//Conference on the Theory and Application of Cryptology. Springer, New York, NY, 1989: 628-631._](https://link.springer.com/content/pdf/10.1007/0-387-34805-0_60.pdf)

[_Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems\[C\]//Conference on the theory and application of cryptographic techniques. Springer, Berlin, Heidelberg, 1986: 186-194._](https://link.springer.com/content/pdf/10.1007/3-540-47721-7_12.pdf)

[_Goldwasser, S., S. Micali, and C. Rackoff. "The knowledge complexity of interactive proof-systems." Proceedings of the seventeenth annual ACM symposium on Theory of computing. 1985._](https://dl.acm.org/doi/pdf/10.1145/22145.22178)

[_Yao, Andrew C. "Protocols for secure computations." 23rd annual symposium on foundations of computer science (sfcs 1982). IEEE, 1982._](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4568388)

[https://vitalik.ca/general/2021/01/26/snarks.html](https://vitalik.ca/general/2021/01/26/snarks.html)

[https://vitalik.ca/general/2019/09/22/plonk.html](https://vitalik.ca/general/2019/09/22/plonk.html)

[https://zhuanlan.zhihu.com/p/98077048](https://zhuanlan.zhihu.com/p/98077048)

[https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/](https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/)

[https://kurtpan666.github.io/ktpzkp22.html](https://kurtpan666.github.io/ktpzkp22.html)

[https://github.com/sec-bit/learning-zkp](https://github.com/sec-bit/learning-zkp)

---

*Originally published on [choovybi](https://paragraph.com/@choovybi/qCMNNaqLJZd6wv5YNsxK)*