本文作者：郭宇
Onceexposed,asecretlosesallitspower.一旦泄露，秘密就失去了全部威力―
AnnAguirre
这已经是本系列的第五篇文章了，这一篇继续深入非交互式零知识证明。本文约12,000字。
系列一：初识「零知识」与「证明」
系列二：理解「模拟」
系列三：寻找「知识」
系列四：随机「挑战」
提纲
CRS的前世今生
哈密尔顿环路问题
云中的秘密：HiddenBits
升级随机性
FLS变换：从HiddenBits到NIZK
寻找理想的TrapdoorPermutation
NIZKProofvs.NIZKArgument
没有秘密的世界
追到这里的读者想必已对零知识证明有了一个大概的认识。你是否想过这个问题：零知识证明为何可行？这里请大家思考一下（比如
系列一中的地图三染色问题的流程）……下面两个要素
似乎必不可少：
「交互」：验证者通过多次反复挑战，把证明者作弊概率降低到一个极小的值
「隐藏随机性」：验证者产生让证明者无法预测的随机数进行挑战
然而对于非交互式零知识证明——NIZK来说，如何实现上面两点？在
系列四我们介绍了如何采用「随机预言机」来扮演一个虚拟的「第三方」角色，实现虚拟的「交互」与「随机挑战」。本文将深入讲述另一种方法，如何通过一段共享的字符串去除「交互」与「隐藏随机性」。这个字符串必须事先由「第三方」来随机产生，这就是传说中的「公共参考串」。
CRS的前世今生
假如我们不借助任何其它手段，限定证明者Prover和验证者Verifier只能进行「一次交互」来实现「零知识证明」，那么他们只能证明「平凡」问题，也就是计算复杂类BPP，而这个复杂度类大家一般猜想可能等价于P。
注：如果Prover与Verifier只做一次交互，在这样的NIZK系统中，我们很容易能构造一个DecisionProcedure——Verify(x,Sim(x))，来证明和证伪定理，因此只能证明平凡问题BPP。
平凡问题虽然也可以零知识证明，但没有意义！怎么理解呢？因为验证者直接可以在多项式时间内根据「输出」求解出「秘密输入」，虽然验证者能够求解，但是「证明」本身并没有额外为验证者提供更多的「知识」。换句话说，不需要证明者出示证明，验证者就知道命题为真，于是证明过程也是零知识的。
因此，当我们讨论「零知识证明」时，要考虑带「知识」的NP类问题。大家都知道，P问题是「确定性图灵机」多项式时间内可以求解的复杂类，它的执行路径对于输入x是一个线性的状态转移。而NP问题是「不确定性图灵机」多项式时间可以求解的问题类。所谓的不确定性图灵机，就是它每次往前走一步是不确定的，有很多个选择，只要任何一个执行路径能到达终止状态，就表示它解决了该问题x。换句话说，它的执行轨迹是一棵树。那么如果我们把不确定性图灵机每一步的路径选择记录下来，那么把(x,witness)交给一个确定性图灵机，那么它也能在多项式时间内解决掉x问题。
再强调一下，「知识」能提高图灵机的解决问题的能力。
NP问题中存在着不想「泄露」给验证者的知识witness，这时，在一个交互式证明系统中，证明者和验证者在「知识」的掌握程度上是不对等的。
为了保证证明过程的「零知识」，我们需要保证：模拟器与验证者的不对等。可是，模拟器没有witness啊，怎么能让他们不对等呢？上一篇我们介绍了「随机预言机」，我们通过允许让模拟器可以绑架「随机预言精灵」的方式制造不平等。本篇将讲述如何利用CRS来制造不平等。
CRS是一个在证明之前就已经公开的，并且在证明者与验证者之间共享的，随机字符串。我们怎么来使用CRS呢？直觉上，一串双方都「知道」的信息，并不会增加「知识」不对等的情况。
首先大家会想，能不能直接用CRS作为随机挑战数呢？可不可以让CRS来代替「随机预言精灵」的角色？答案是不行！
为什么？这是因为CRS是在证明之前就已经产生了，如果证明者Prover提前知道了所有的随机挑战数，那么很显然这个随机挑战也就失去了意义。
注：请大家回想下「随机预言机」是如何保证证明者无法提前预测「随机挑战数」的？没想明白的你，请重读系列。
CRS的使命就是让「模拟器」与「验证者」不平等。怎么做呢？隐藏一些「秘密」进去。
如果进一步追问，隐藏了「秘密」有什么用呢？当然有用啦，在「理想世界」中，模拟器与抽取器才能很开心地玩耍起来……
1988年，ManuelBlum，PaulFeldman和SilvioMicali三位先驱发表的论文「Non-InteractiveZero-KnowledgeandItsApplications」展示了「交互」与「隐藏随机性」的不必要性。他们给出了一个地图三染色问题的NIZK证明系统，在一段共享的随机产生的字符串的帮助下。
不过，……，我不会告诉你这个方案需要共享大概n^4超长的CRS，其中n是要证明的「命题」的长度。
1990年，UrielFeige，DrorLapidot与AdiShamir三人提出了另一种构造NP语言的NIZK方案。与不一样的是，这个NIZK方案不再基于特定的数论假设，而是基于一个密码学工具TrapdoorPermutation。在这个方案中，FLS提出了「隐藏比特」的概念，然后把HiddenBits藏入了CRS。对于模拟器而言，就可以通过修改CRS中的HiddenBits来达到模拟的效果，从而体现出对验证者Verifier的优越性。不过，这个方案需要共享更长的CRS，超过k*n^5，这里k是安全参数。
此后，HiddenBits的思路被很多人采用，值得一提的是，Kilian与Petrank采用了一种更巧妙的方法来使用HiddenBits，成功地把CRS的长度缩减到了k*n^2。后来J.Groth继续优化，把CRS的长度缩小到了大约k*n。
除了HiddenBits，J.Groth，R.Ostrovsky与A.Sahai使用了同态加密方案Boneh-Goh-Nissim或Boneh-Boyen-Shacham来实现NIZK，他们把加密方案的「公钥」当做是CRS，同时Prover加密作为证明，然后利用同态性质来证明另一个NP-Complete问题——布尔电路的可满足性问题。这个方案的最大优点，就是CRS长度是固定的，因为只是一个密钥而已，长度只有k。对于模拟器而言，它可以通过超能力，拿到这个公钥所对应的陷门，从而能够实现密封任何信息，但得到相同的密文；对于抽取器而言，它可以用超能力拿到公钥对应的私钥，从而能够解密证明得到「知识」。
JensGroth在2010年基于KEA假设与Pairing提出了一种新的NIZKArguments方案，这也是后续许许多多zkSNARKs方案的起点。这里的CRS由一对对的构成，被用来实现「知识承诺」。其中x与?是两个随机数，在产生完CRS之后，必须被「遗忘」。有些人把这部分需要遗忘的随机数叫做「ToxicWastes」，这容易误导读者。他们不仅无无害，而且非常有用。他们是被藏入CRS的「秘密」，是模拟器的武器。如果模拟器得到了x与?，就能伪造证明，从而保证证明的零知识。而对于抽取器，他能直接通过KEA假设内建的抽取函数来抽取知识。
最新的Sonic方案又在的基础上实现了UpdateableCRS。如果任何人担心CRS中的秘密已经被泄露了，他就可以在原有CRS基础上打一个补丁，继续往里藏一个秘密，这样就能保证CRS的安全性。这里的CRS还是「Universal全局」的，即CRS只需要生成一次，就可以应付所有的命题证明。这个方案后续被最新的Plonk，Marlin等方案采用。
接下来，我们就从一个简单的例子开始，理解如何基于CRS来构造NIZK。在这之前，我们需要介绍一个NP-Complete问题——哈密尔顿环路问题。
哈密尔顿环路问题
想象出一个地图中有若干个城市，城市与城市间可以有公路。
假如给你一副地图，让你找出一条路径，不重复地走遍所有的公路。相信你会马上兴奋起来，这不就是小时候学过的「一笔画」么？判断一个地图能否一笔画，这是小学生做的数学题，我们可以计算每个城市连接的公路个数，根据奇偶性分成「奇点」与「偶点」。如果一个地图中存在两个奇点城市，那么你只能从一个奇点城市出发，遍历所有的公路，并且最终到达另一个奇点城市。这条路径就被称为「欧拉路径」。
如果一个地图中所有的城市都是偶点，那么你可以从任意一个城市出发，轻松地找出一条路径，不重复地遍历所有的公路，并且回到起点。这个环路被称为「欧拉环路」。
而如果地图存在超过2个以上的奇点，那么就不存在欧拉回路，比如著名的哥德斯堡七桥问题。
著名的哥德斯堡七桥问题就是这么描述，如果不重复地穿过下面七座桥。
哥德斯堡七桥地图显然存在多个奇点，不存在欧拉路径。如果给定任何一个地图，是否存在一个欧拉环路，这是一个P问题，也就是一个计算机可以在poly(n)多项式时间内寻找。
注：欧拉环路的寻找算法被称为Fleury算法。
对于这样一个P问题，如果一个证明者Prover证明他知道一个欧拉回路，那么他可以直接发送回路的明文，然后验证者Verifier验证回路正确与否。请注意，这个过程仍然是零知识的。因为，Verifier并没有通过Prover发送的信息获得任何额外的知识。换句话说，Verifier并没有因为看到回路，而增强了自身计算能力，因为Verifier本来就可以自行计算欧拉回路。
而我们要讲的是「哈密尔顿环路问题」则是一个NP问题，描述如下：
是否一个地图存在一个环路，能不重复地穿过每一个城市。
比如下面这张地图：
我们用一个矩阵V*V的矩阵来表示这个地图，凡是两个城市有公路相连接，那么就在(A,B)和(B,A)里面填上1，否则填0。这个矩阵被称为「邻接矩阵」，我们可以把这个邻接矩阵拍扁，就变成了一个0/1比特串。
寻找「哈密尔顿环路」是一个NP-Complete问题，换句话说，不存在一个算法使得计算机在poly(n)多项式时间内找到环路。但是，计算机可以在多项式时间内检验一个路径是否是「哈密尔顿环路」。比如这个地图中就有一个带方向的哈密尔顿环路，我们一眼就能验证这个环路确实穿过了每一个城市。如果一个地图有哈密尔顿环路，那么它的矩阵一定是满足下面的特征：每一行一定有一个1，每一列一定也有一个1。
ZK-HAM协议
我们下面给出一个三步交互的Sigma协议，Alice向Bob证明她「知道」上面这个地图G的哈密尔顿环路。
公共输入：G为一个有6个顶点的地图，表示为一个6*6的邻接矩阵
秘密输入：G的哈密尔顿环路C
第一步：Alice随机选择一个「置换」，Perm(.)，然后通过这个置换，产生一个新的图G'；然后Alice把G'矩阵的每一个单元加密，产生一个新的矩阵发送给Bob。
：所谓置换，大家可以想象成用
鼠标随意拖动图中的点，但是点和点之间的连线会跟着点一起被拖动，拖动结束之后形成的图，进行重新编号就得到G'，比如上图左侧的两个图。经过置换变换的图前后是
同构的。其中下图中，每一个顶点上角括号中的标号为拖动之前该顶点在上图中的编号。形式化一点可以这么定义：Perm()是一个{1,V}到{1,V}的双射函数新图G'的邻接矩阵，=1当且仅当=1，其中i是顶点编号，V是顶点个数。
第二步：Bob随机选择bin{0,1}}进行挑战。
第三步情况：Alice根据Bob第二步发送的值：如果b=0，那么Alice发送置换函数Perm()，并且揭示完整的图G'。而Bob则确认G'是否是原图G经过置换无误。
第三步情况：如果Bob第二步发送的b=1，那么Alice只揭示G'中的哈密尔顿环路C'即可。而Bob需要验证C'是否是一个哈密尔顿环路
回忆一下三步Sigma协议，我们再理解下上面看似复杂的动作：
第一步：被称为Commit，证明者Alice需要把手里的答案进行同态变换，产生一个新答案，然后把每一条边都锁起来，交给Bob；
第二步：Bob进行随机挑战；
第三步：Alice根据Bob的随机挑战，做出两种不同的回应。如果Bob挑战0，那么Alice打开第一步的承诺，表示自己在第一步没有作弊；如果Bob挑战1，那么Alice只解密暴露出哈密尔顿环路的边，其它边则不需解密。Bob可以轻易地检查地图上露出来的那些边是否构成了一个不重复地经过所有城市的环路。
如果这个Sigma协议只走一遍的话，Alice作弊的概率是50%，如果重复n遍，Alice作弊概率会指数级减小。大家可以试着用「模拟器」和「抽取器」的方法来证明这个协议的「零知识」与「可靠性」。
ZK-HAM的变形：ZK-HAM-2
接下来把上面的这个三步协议改动一下。大家先考虑下这样一个简单事实：如果一个仅包含环路的子图C是图G的子图，C<=G那么说明G包含哈密尔顿环路。
这个事实等价于另一个事实：一个哈密尔顿图G的补集!G是环路子图C的补集!C的子图。
图的补集：所谓补集就是这样一个新地图，顶点保持不变，旧地图上的边在新地图中不存在，而新地图中的公路在旧地图中不存在，但是两个图重合在一起，就变成了一个完全图。
用邻接矩阵来理解，就是如果一个图G包含一个环路子图C，那么G矩阵中所有值为0的单元集合必然被C矩阵中所有值为0的单元集合包含。可以表示为!G<=!C。
根据第二个事实，我们可以定义如下的Sigma协议：
公共输入：图G，表示为6*6的邻接矩阵
秘密输入：G的哈密尔顿环路C
第一步：
Alice随机选择一个「置换」，Perm(.)，并且通过C构造一个哈密尔顿环路子图C'=Perm(C)；
然后Alice加密C'的每一个单元，把解密后的结果发送给Bob。
第二步：Bob随机选择bin{0,1}进行挑战
第三步情况：如果b=0，Alice揭示完整的C'，而Bob验证这个C'是否确实是一个哈密尔顿环路子图。
第三步情况：如果b=1，Alice发送Perm()，同时按照G'=Perm(G)中的所有含0单元所在的位置，揭示C'中所对应的单元；Bob验证C'所有被揭示单元是否全部为0。
再理解下这三步Sigma协议：
第一步：证明者Alice需要把哈密尔顿子图C进行置换变换，产生一个新的哈密尔顿子图C'，加密后交给Bob；
第二步：Bob进行随机挑战，0或者1；
第三步：如果Bob挑战0，那么Alice打开第一步的承诺，展示一个带有唯一环路的图；如果Bob挑战1，Alice则按照G'中的0单元的位置打开承诺，展示承诺中被打开的位置全部为0。
重点来了，大家仔细看看这个新版的Sigma协议的第一步。有没有发现什么情况？
第一步Alice发送的内容是与地图G无关的！
同样，第二步Bob发送的挑战也是与地图无关的。这样我们可以把第一步发的承诺改成事先准备好的比特串，而且我们假设这个比特串由一个可信第三方来产生，这样一来Bob就没有必要发送b=0这个分支，因为可信的第三方是诚实的，他一定是事先准备好一个正确的环路子图。这样，由于Bob只需要发送1挑战分支，那么这一步也可以去除。
于是，三步协议变成了一步，我们成功去除了交互，有望实现NIZK。
我们接下来把ZK-HAM-2协议的第一步和第二步推到一个事先准备的字符串中，然后只让Alice发送第三步的内容给Bob。如下图所示：
请注意，这里还不算是一个NIZK系统，因为这个共享字符串并不能对Bob公开，否则Bob就能算出环路C。接下来，我们要解释一个新概念：「隐藏比特」。HiddenBits是这样一串随机比特，它们对于验证者Bob隐藏，但是对于证明者Alice公开。然后在证明过程中，Alice可以选择性地揭示一部分比特展示给Bob看。这是构造NIZK证明系统的一个利器，下面我们需要再继续深入……
云中的秘密：HiddenBits
让我们再次开下脑洞，想象天上有朵云，云后面藏着一串随机产生的比特值，不是0就是1，然后Alice带着一个「超级眼镜」，于是能够看到云后面所有的随机比特串，但是Bob却看不到。同时Alice手里还有一个「超级手电筒」，她可以打开手电筒用激光穿透云层，让Bob也能看见其中某个或某些比特。当然，Bob能看到的比特的选择权完全在Alice手中。
云朵中隐藏的比特串就是所谓的HiddenBits。
接下来我们要通过HiddenBits来完成一个单步交互，完成ZK-HAM-2协议的功能。在ZK-HAM-2中的第一步，Alice产生一个随机的置换Perm()，然后通过G中的哈密尔顿环路子图C产生一个变换后的环路子图C'=Perm(C)。这等价于，事先由任何人产生一个随机的哈密尔顿环路子图C'，然后Alice根据C和C'计算得出一个相应的Perm()。
假设由某个「第三方」产生了一个随机的环路子图C'，编码成「邻接矩阵」比特串，放到云朵后面。假设V为顶点的个数，E为边的条数。这个邻接矩阵的编码需要一个V*V长度的比特串，可以解释成一个V*V的矩阵，其中每一行只包含一个1，每一列也只包含一个1，矩阵的其它单元都为0。
接下来Alice如何构造证明呢？这其实很简单：
Alice通过「超级眼镜」得到了一个随机的哈密尔顿环路子图C'，然后计算得到一个置换Perm()，使得Perm(C)=C'。
Alice根据Perm()来计算出一个换后的图G'=Perm(G)
Alice产生证明，由两部分组成：置换Perm()G'的邻接矩阵中所有值为0的单元坐标所对应的C'矩阵的值，相当于Alice需要用「超级手电筒」给Bob揭示的隐藏比特。
那么Bob怎么验证这个证明呢？Bob拿到证明之后，只需要检验两个东西：
Perm()是否是一个合法的置换V->V，比如不能出现两个顶点映射到同一个顶点的情况。
对于G中的每一条「非边」，经过置换之后，Bob抬头看天上对应的「隐藏比特」，比特值必须为0
我们再仔细地深入理解下这个非交互协议。先从「完备性」入手：如果Alice没有作弊，那么很显然能够通过Bob的验证，这里请大家自行检查。
接下来我们分两步简要证明下「可靠性」：首先，因为Bob经过验证得知，所有G置换后的非边集合都已被揭示，且全为0，那么可以得出结论，!G<=!C，即G的非边集合是环路子图C的非边集合的子集。这等价于，C<=G，也就是说G包含一个哈密尔顿环路。这里请注意，这个可靠性概率是100%。
然后，设想在一个「理想世界」中，Bob获得了某种超能力，不需要Alice的超级手电筒，就能看穿云层，得到所有的隐藏比特C'。然后当Bob得到Perm()之后，就能通过Perm()反算出C，于是Bob就相当于变身成了一个「抽取器」，在理想世界中，它能把Alice要证明的知识给成功抽取出来。
那么怎么证明「零知识」呢？Alice要具备一个超能力，就是在「理想世界」中，可以偷偷修改云朵中的隐藏比特。接下来就简单了，模拟器Zlice可以这么Bob：
Zlice把云朵中的隐藏比特全部置为0
Zlice随机产生一个合法的Perm()
大家发现了，关键是，天上隐藏的比特必须是一个可信的字符串，所谓「可信」，就是指它确实应该是一个哈密尔顿环路子图。那么第三方需要可信。
可是，这样一个第三方是不是难以令人满意？Alice和Bob要绝对信任他，不会和对手串谋。如果他和Alice串谋，可以把隐藏比特串直接设置为全0；或者他和Bob串谋，直接把这个比特串给Bob看。这个协议看起来不错，但是很难实用。我们接下来要对这个简单协议进行升级。
升级随机性
第一个升级是让隐藏比特串变成一个「一致性均匀分布」的随机的隐藏比特串，是一个看起来相当随机的比特串，而不是一个刻意摆放好的哈密尔顿子图。
完全随机意味着比特串中的0的个数和1出现的概率大概接近。那么接下来一个难题是如何让随机比特串中能出现一个随机的哈密尔顿环路子图矩阵。方法非常简单粗暴：产生一个足够长的随机串，然后从头扫描，直到找到一个随机的哈密尔顿环路为止。
可是……这个成功概率是不是非常非常小？我们下面给出一个概率没那么小的一种寻找方法。
我们先把比特串按照5log(V)的长度进行切分，然后如果每一个分片中的所有比特全为1，那么我们把这个片段被视为邻接矩阵中的一个值为1的单元，否则视为一个值为0的单元。这样每一个矩阵单元出现1的概率为1/(V^5)。
我们取连续的V^6个片段，构成一个V^3*V^3的大矩阵。如果大矩阵中包含一个V*V的哈密尔顿环路矩阵，并且其他单元都为0。那么我们称这个大矩阵为「有用」。
根据概率计算，出现一个「有用」矩阵的概率为1/。
注：「有用」矩阵的概率计算过程请参考Fact4.10.8,「FoundationsofCryptography,VolI」byOdedGoldreich，P304。
好了，我们需要升级下上一节的协议。因为现在「隐藏比特串」被拆分成了若干个大矩阵，这些大矩阵有些是「有用」的，有些是没用的。
接下来Alice要来构造证明了，她先戴上超级眼镜，扫描云朵中的HiddenBits，这要分两种情况，
Case1：如果Alice遇到了一个没用的大矩阵M，Alice公开M的所有单元。
Case2：如果Alice遇到了一个「有用」的大矩阵M，这意味着Alice得到了一个随机的哈密尔顿环路C'，然后Alice参照上一节的步骤进行证明即可。
那么Bob怎么验证这个证明呢？我们还要分情况进行讨论，
Case1：如果Alice公开了全部的M，那么Bob就检查这个M是否「无用」。如果M无用，就认为证明有效；否则拒绝。
Case2：如果Alice发送的是形如这样的证明，那么Bob按照上一节的验证方法进行验证。
对于这个协议，Bob已经不再担心第三方是否作弊，故意产生一个全零的比特串，但是Alice仍然担心一旦第三方和Bob串谋，那么知识就彻底泄露了。
不仅如此，现在的协议还有个很强的限制，Alice不能在看到隐藏比特之后再选择需要证明的G，否则Alice就可以作弊。如果一个证明者选择证明的「命题」与CRS无关，那么这个证明者被称为Non-adaptiveAdversary。
FLS变换：从HiddenBits到NIZK
接下来，我们再次升级协议，把「隐藏比特串」中的隐藏特性去除，变成「公共参考串」CRS。这里我们要借助一个密码学工具——TrapdoorPermutation，陷门置换。
所谓的陷门置换是指一个置换函数F(x)，x是一个集合S中的元素，然后函数F(x)把x映射到S中的另一个元素y。同时F(x)满足单向性，即通过y很难反算出x；但是如果谁拥有陷门t，就能实现反向计算F^(-1)(t,y)=x。陷门置换还可以匹配一个HardcorePredicate，h(x)=0/1，它能根据S集合中的元素产生一个一致性分布的0/1比特。介绍完毕，大家是不是有点晕，没关系，晕一晕就习惯了。总之一句话，陷门置换可以对公共参考串和HiddenBits进行相互转换。
先假设有这样的密码学工具，然后我们升级协议。
我们把公共参考串看成是一个列表，y1,y2,y3,...,yn，列表中的每一项都是集合S中的元素。然后通过HardcorePredicate产生HiddenBits中的每一个比特位。但是请注意，这里不能直接通过h(y)=b来产生HiddenBits，因为这样一来Bob就能自己算出所有的HiddenBits，这违反了上一节的协议。为了保证对Bob隐藏，我们需要用公共参考串的原象，也就是x1,x2,x3,...,xn来产生HiddenBits，h(x)=b。Bob虽然不能自己计算b1,b2,b3,...,bn，但是一旦得到一个x，他就能检验F(x)?=y来判断是否x是和公共参考串对应，同时再计算h(x)=b得到被揭示的HiddenBits，b。
我们可以换一种不太准确，但是更直观的方式来理解，Alice相当于自己产生一对公私钥。然后Alice把公共参考串看成是一段「密文」，由于Alice有私钥，于是可以对密文进行解密，得到明文，这些明文，对于Bob而言就相当于是HiddenBits。当Alice要「揭示」HiddenBits时，就出示相应的明文片段，并且带上公钥，那么Bob就能通过公钥再次「加密」明文，与公共参考串的密文进行比对，确保Alice没有在揭示过程作弊。
下面是升级后的协议：
对于证明者Alice：
Alice随机选择一个TrapdoorPermutation，(F,h,t)
根据公共参考串中的每一个yi，利用陷门反向计算出xi=F^(-1)(t,yi)
计算HiddenBits，bi=h(xi)
根据上一节的协议产生证明。假设Alice要揭示的Hiddenbits的位置集合为r1,r2,...,rl，那么Alice向Bob发送对应位置的x，分别为x_r1,x_r2,x_r3,...x_rl，连同(F,h)，和证明一起并发给Bob。
对于验证者Bob：
检查(F,h)是否为一个合法的TrapdoorPermutation。
对L中的每一个元素x_r，计算出被揭示的HiddenBitsbi=h(F(x_r))，然后按照上一节的协议检查证明。
这个新协议的「完备性」，请大家自行检查。
对于「零知识」，我们需要构造一个「模拟器」Zlice2，它的超能力是修改公共参考串。
模拟器直接调用上一节协议的模拟器Zlice。得到一个三元组，(proof,{r},{b})
对于每一个公共参考串位置，如果它对应某一个r，模拟器从集合S中随机选择一个x_r，使得h(x_r)=b_r，这里b_r就是{b}中对应r；然后把y_r=F(x_r)作为假参考串的一部分。
对于每一个公共参考串位置，如果与{r}无关，那么模拟器随机选一个y即可
模拟器把所有的y拼在一起，得到一个假CRS。
对于「可靠性」，事情变得不那么简单了。因为现在Alice有能力挑选(F,h,t)，Alice可以挑选一个对自己有利，甚至作弊的(F,h,t)，使得她可以控制一次协议运行的HiddenBits{b}的结果。对于本节升级后的新协议而言，需要重复很多遍，以致于虽然Alice可以控制一次协议运行的HiddenBits，但是她对其它若干次协议运行的HiddenBits无能为力。换句话说，Alice无论如何挑选(F,h,t)都无法完全掌控多次的协议运行。
这个升级变换理论上可以支持任意的HiddenBits模型下的非交互式零知识证明，被称为FLSProtocol。FLS变换有很多的好处：首先，这个随机产生的CRS可以多次使用，实现所谓的「Multi-TheoremNIZK」；其次，可以实现「AdaptiveSoundness」，即Alice可以先看到CRS，然后再选择要证明的内容。最后，这个协议还是「AdaptiveZero-Knowledge」，即Bob也可以先看到CRS，然后再选择要证明的内容给Alice。
注：AdaptiveAdversary是比较符合现实世界的安全情况，比如第二类CCA安全。因为CRS是公开的，攻击者可以先分析CRS，再决定如何发起攻击。
寻找理想的TrapdoorPermutation
陷门置换TrapdoorPermutation最早出现在姚期智老师的论文「TheoryandApplicationofTrapdoorFunctions」中，是公钥密码学的重要基础。在上一节给出的FLS变换中，需要一个理想化的TrapdoorPermutation，所谓的理想化是指，每一个n-bit字符串都能唯一变成另一个n-bit字符串，并且不会出现「多对一」的映射关系。Alice需要随机抽样一个Index，发给Bob，然后Bob要能检查出这个Index所对应的F()是否是一个「完美」的置换。问题来了，怎么Bob怎么能在多项式时间内检查出来呢？如果Bob不能检查，那么Alice就可以抽样一个不完美的Permutation，从而可能作弊，破坏「Soundness」这个性质，Bellare和Yung发表在1996年的论文最早注意到了这一点，但是并没有完全解决这个问题。
如何找到一个桥梁，能够将TrapdoorPermutation合适地抽象出来，同时能够对接到密码学工具的实现上，是一个及其有挑战性的工作。随后各路密码学家在这方面研究了很长时间，发表了许许多多的论文，各种不同类型的TrapdoorPermutation被定义、被研究，但是仍然不能让人满意。直到最近一个工作是RanCanetti与AmitLichtenberg提出了CertifiableInjectiveTrapdoorFunction这样一个新类型，并证明了这种TrapdoorPermutation终于能满足FLS变换要求。但这是不是故事的结束呢？理论密码学家们估计不会停下探索的脚步。
除了基于TrapdoorPermutation的FLS变换，还有各式各样的解决方案来升级HiddenBitsModel，比如采用InvariantSignature，或VerifiableRandomGenerator来实现HiddenBits的变换，或者弱可验证随机函数，还有一种叫做publicly-verifiabletrapdoorpredicates的方案。
三十年来，密码学家们发明的NIZK方案有很多，但HiddenBits方法是目前已知唯一的办法，(1)基于「一致性分布」的共享CRS，(2)实现任意NP语言的NIZKProofs。
NIZKProofs与NIZKArguments
在本文中，我们构造的NIZK「证明」系统的可靠性属于「StatisticalSoundness」，而零知识则属于「ComputationalZero-Knowledge」。这意味着什么呢？这意味着，不管证明者Alice的算力有多强大，Alice仍然无法作弊。但是，如果验证者Bob拥有超强的计算能力，那么是存在这种可能性：Bob从证明中抽取到有价值的「知识」。
这又意味着什么？
这意味着，对于NIZKProofs来说，它的长度肯定要比「知识」长，知识即NP问题中的witness。只要Bob算力够强，他就可以把证明解密。对于「抽取器」而言，它也需要在没有交互的情况下抽取witness。证明最短的NIZKProofs当属GregGentry等人采用「全同态加密」技术构造的NIZK方案了，证明长度只是稍稍大于witness的长度。
那能不能构造证明尺寸小于witness的NIZK呢？答案是YES！
还有一类的NIZK系统被称为NIZKArguments：它们的可靠性是「ComputationalSoundness」，零知识属于「PerfectZero-Knowledge」或者「StatisticalZero-Knowledge」。这说明，Alice如果算力超强，那么她是有作弊空间的，但是因为现实世界中，我们可以通过加大安全参数来极大地降低Alice作弊的可能性，但是能实现非常极致的零知识特性。由于弱化了可靠性，那么我们就可以继续压缩证明的尺寸。
注：在本系列中，我们并不刻意区分「证明」与「论证」这两个词。如果需要指明Arguments而非Proofs，会专门强调。
假如说我们要公开一个NIZK证明到Github上，假如过了一百年以后，Github网站还在，而未来计算机的计算能力已经有了质的飞跃，这时候，一个NIZKProof可能会被算力攻破，泄露知识，而NIZKArgument则很大可能性上还保持安全性。
现在流行的热词——zkSNARK中的AR正是指代Argument。
NIZKArgument可以实现O(1)常数级长度的证明，即与witness的长度无关。然而这需要隐藏更多的秘密到CRS中。
没有秘密的世界
1956年，哥德尔在一封寄给冯诺依曼的信中提到了一个著名的问题，「P是否等于NP」。后来，这个问题被Clay研究所列为七个千禧年难题之一，悬赏百万美金。
零知识证明系统正是为了保护witness不泄露的前提下，实现NP问题的验证。那如果一旦证明了「P==NP」，这会意味着什么？这意味着witness不再有多大意义了，反正一个图灵机也可以在多项式时间内找到witness。零知识证明试图保护的witness也变得徒劳无益。
事实上，如果「P==NP」，现有的公钥密码学、对称加密AES与SM4、哈希算法所依赖的难解问题都可能坍塌，我们可能很难保存秘密。不仅如此，
如果P==NP，我们所处的世界将会变得非常不一样。「CreativeLeaps」将不再有价值，求解问题与验证问题之间的鸿沟不复存在。每个能欣赏交响乐的人都会成为莫扎特，每个会推理的人都会变成高斯，每个能判断投资好坏的人都会变成巴菲特。从达尔文进化论的观点出发：如果这就是我们存在的宇宙，为什么我们还没有进化得可以充分利用这个好处？——ScottAaronson(2006)
对于数学也一样，数学证明的验证过程也是多项式复杂度的，如果「P==NP」，那么也就存在着多项式时间寻找证明的算法。这意味着哥德巴赫猜想、黎曼猜想将有可能得到证明，难怪LanceFortnow在博客里这么说：
ApersonwhoprovesP==NPwouldwalkhomefromtheClayInstitutenotwithonemillion-dollarcheckbutwithseven.如果谁能证明P=NP，那么他不会只拿着一张百万美元支票回家，而是七张。——LanceFortnow(2004)
2002年的调查显示，61%的计算机科学家相信「P!=NP」，而十年后，这个比例上升到了83%。而我是被ScottAaronson的如下论断说服的：
自指论证：如果P=NP是事实，那么这个证明会比较容易被发现；但是如果P!=NP，那么这个证明会比较难发现。所以相信P!=NP看起来会让数学现实更一致一些。——ScottAaronson(2006)
尽管是如此不情愿，如果我们真的生活在一个没有秘密的世界，那会是什么样子？「环形监狱Panopticon」是18世纪英国哲学家JeremyBentham提出的一个惊悚概念。囚徒们被中心全天候监控，没有任何隐私可言，而且他们对自己是否处于被监控状态也无从得知。这个无比悲观的论调让人浑身不适，但很多人认为，这可能是两百多年前对未来网络数字时代的一则精准寓言。
从『BillyBudd』，卡夫卡的『TheTrial』，到奥威尔的『1984』，到著名黑客KevinMitnick写的超级大卖书『隐形的艺术』，似乎，危机四伏，风险不断累积，对末日世界的想象给了作家们很好的素材……
偶尔无意中看到了一本有趣的漫画『ThePrivateEye』，它描述了一个劫后余生的后现代场景：在未来，我们的所有信息数据都存放在云上，然后突然有一天，这个数据云「爆炸」了，不知道是什么原因，反正所有的信息，包括每个人最阴暗的过去，都不再成为秘密；所有的数字化的资产都被抹掉，所有的在线知识库永久丢失；每个人的言行、账单、邮件、聊天消息、银行卡密码、中学考卷、GPS位置信息，写了一半的日记、删除的照片、上网记录，这些信息都将暴露给同事、邻居、朋友、亲人、甚至任何一个好奇的人。
每个人都无地自容，惶惶不可终日，然后逐渐地，大家都选择隐藏自己，人们出门都要戴上面具，以小心翼翼地保护自己的身份，甚至一个人可以选择使用多个身份，国家法律规定任何偷窥行为都将被严惩，获取信息成为了一种至少无上的权力，照相机需要被严格管控，互联网不再存在，人们通讯又回到了电话亭时代……
这会是人类的终极命运么？
未完待续
本文开头提到了「隐藏随机性」并不是必要的，我们来回想下HiddenBits模型。这些HiddenBits并没有对Prover隐藏，而是敞开了让Prover知道，但是由于HiddenBits是「一致性随机分布」的字符串，所以即使让Prover知道了，他仍然逃不过随机挑战的火力。然而在流行的zkSNARK方案中，并没有采用「一致性随机分布」的CRS，而是一组结构化的随机数。不管怎样，用CRS来构建「信任根基」的秘密，就是藏在其中的「秘密」。
这符合直觉，保守「秘密」也是一种信任。因为Alice不知道CRS中隐藏的秘密后门，所以无法作弊。同样，Bob不知道CRS中的秘密，也就没办法获得「知识」。同样，人与人之间的协作既要建立在公开透明的基础上，也要保守秘密。
Allhumanbeingshavethreelives:public,private,andsecret.每个人都有三种生活，公开的，私人的，以及秘密的。——GabrielGarcíaMárqueel
致谢：感谢陈宇，丁晟超，张宇鹏，胡红钢，刘巍然，何德彪，万志国等老师的专业建议和指正，感谢安比实验室小伙伴的修改建议。本文内容不代表他们观点。
最后附上漫画书的链接：http://panelsyndicate.com/comics/tpeye作者甚至把创作过程的邮件和草图都放了出来，大家可以体验一下窥视制作过程的快感。
参考文献
Aaronson,Scott.Reasonstobelieve,2006.https://www.scottaaronson.com/blog/?p=122
Blum,Manuel,PaulFeldman,andSilvioMicali."Non-interactivezero-knowledgeanditsapplications."STOC'88.1988.
Bellare,Mihir,andShafiGoldwasser."Newparadigmsfordigitalsignaturesandmessageauthenticationbasedonnon-interactivezeroknowledgeproofs."ConferenceontheTheoryandApplicationofCryptology.Springer,NewYork,NY,1989.
Boneh,Dan,Eu-JinGoh,andKobbiNissim."Evaluating2-DNFformulasonciphertexts."TheoryofCryptographyConference.Springer,Berlin,Heidelberg,2005.
Brakerski,Zvika,ShafiGoldwasser,GuyN.Rothblum,andVinodVaikuntanathan."Weakverifiablerandomfunctions."InTheoryofCryptographyConference,pp.558-576.Springer,Berlin,Heidelberg,2009.
Bellare,Mihir,andMotiYung."Certifyingpermutations:Noninteractivezero-knowledgebasedonanytrapdoorpermutation."JournalofCryptology9.3(1996):149-166.
Canetti,Ran,ShaiHalevi,andJonathanKatz."Aforward-securepublic-keyencryptionscheme."InternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.Springer,Berlin,Heidelberg,2003.
Chiesa,Alessandro,etal.Marlin:Preprocessingzksnarkswithuniversalandupdatablesrs.CryptologyePrintArchive,Report2019/1047,2019,https://eprint.iacr.org/2019/1047,2019.
Dwork,Cynthia,andMoniNaor."Zapsandtheirapplications."Proceedings41stAnnualSymposiumonFoundationsofComputerScience.IEEE,2000.
Feige,Uriel,DrorLapidot,andAdiShamir."Multiplenon-interactivezeroknowledgeproofsbasedonasinglerandomstring."Proceedings31stAnnualSymposiumonFoundationsofComputerScience.IEEE,1990.
Fortnow,Lance."WhatifP=NP?".2004.https://blog.computationalcomplexity.org/2004/05/what-if-p-np.html
Fortnow,Lance."ThestatusofthePversusNPproblem."CommunicationsoftheACM52.9(2009):78-86.
Groth,Jens."Shortnon-interactivezero-knowledgeproofs."InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,Berlin,Heidelberg,2010.
Groth,Jens."Shortpairing-basednon-interactivezero-knowledgearguments."InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,Berlin,Heidelberg,2010.
Groth,Jens,RafailOstrovsky,andAmitSahai."Perfectnon-interactivezeroknowledgeforNP."AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.Springer,Berlin,Heidelberg,2006.
Gabizon,Ariel,ZacharyJ.Williamson,andOanaCiobotaru.PLONK:PermutationsoverLagrange-basesforOecumenicalNoninteractiveargumentsofKnowledge.CryptologyePrintArchive,Report2019/953,2019.
Kilian,Joe,andErezPetrank."Anefficientnoninteractivezero-knowledgeproofsystemforNPwithgeneralassumptions."JournalofCryptology11.1(1998):1-27.
Maller,Mary,etal."Sonic:Zero-KnowledgeSNARKsfromLinear-SizeUniversalandUpdateableStructuredReferenceStrings."IACRCryptologyePrintArchive2019(2019):99.
RanCanettiandAmitLichtenberg."Certifyingtrapdoorpermutations,revisited."TheoryofCryptographyConference.Springer,Cham,2018.
Gasarch,WilliamI."GuestColumn:TheThirdP=?NPPoll."ACMSIGACTNews50.1(2019):38-59.
Yao,AndrewC."Theoryandapplicationoftrapdoorfunctions."23rdAnnualSymposiumonFoundationsofComputerScience(sfcs1982).IEEE,1982.
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。