ALI:亚瑟王的「随机」挑战：从交互到非交互式零知识证明——探索零知识证明系列（四）

本文来自安比实验室，作者郭宇，Odaily星球日报经授权转载。

本文已更新至Githubhttps://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md“ChallengesareattimesanindicationofLord'strustinyou.”挑战，有时是上天信任你的一种表现。―D.ToddChristofferson本文继续长篇大论零知识证明背后的机制原理，希望帮助大家理解这一类「现代密码学工具」的大致轮廓。本文约8000字，少量数学公式。系列一：初识「零知识」与「证明」系列二：理解「模拟」系列三：寻找「知识」交互与挑战

我们之前介绍的零知识证明系统都是「交互式」的，需要验证者Bob在交互中提供一个或若干个「随机数」来挑战，比如「地图三染色问题」中，验证者Bob需要「不断地」随机挑选一条边来挑战Alice的答案，直到Bob满意为止，而Alice的作弊概率会「指数级」地衰减。而让Bob相信证明的「基础」取决于Bob所挑选的随机数是不是足够随机。如果Alice能够提前预测到Bob的随机数，灾难就会发生，现实世界就会退化成「理想世界」，而Alice就可以立即升级成「模拟器」，通过超能力来愚弄Bob。而『系列三』中，我们分析了Schnorr协议，协议中虽然验证者Bob只需要挑选一个随机数c来挑战Alice，让她计算一个值z，但Bob绝对不能让Alice有能力来预测到c的任何知识，否则，Alice也会变身成模拟器。随机数的重要性不言而喻：通过随机数挑战是交互式零知识证明的「信任根基」。但，「交互过程」会限制应用场景。如果能将交互式零知识证明变成「非交互」？这会非常非常激动人心。所谓的非交互可以看成是只有「一轮」的证明过程，即Alice直接发一个证明给Bob进行验证。非交互式零知识证明，英文是Non-InteractiveZeroKnowledge，简称NIZK。它意味整个证明被编码为一个「字符串」，它可以写到一张纸上，通过邮件、聊天工具等各种方式随意发送给任何验证者，字符串甚至可以放在Github上随时供大家下载验证。在区块链世界，「NIZK」可以作为共识协议的一部分。因为一个交易需要多个矿工进行校验。设想下，如果交易的发送者和每个矿工都要交互一下，让矿工进行挑战，那么共识过程将奇慢无比。而非交互式零知识证明则可以直接广播给所有的矿工节点，让他们自行验证。可能有朋友会问：只让一个矿工挑战不就够了吗？把矿工和交易发送者的交互脚本编码成证明，然后广播给其他矿工，然后其他矿工就直接相信这个挑战过程是可信的，不也可以吗？但是，很显然，这里需要相信第一个交互矿工作为可信第三方，第三方？似乎不是一个好主意……而非交互式零知识证明，以下我们直接说「NIZK」，似乎就很理想了，没有第三方赚差价。「非交互」带来的困惑

非交互式零知识证明，NIZK，如果存在，那么它要比交互式证明强大得多。交互式证明，只能取信于一个验证者；而NIZK可以取信于多个验证者，以至所有人。交互式证明，只能在交互的那个时刻有效；而NIZK将始终有效。NIZK不仅可以跨越空间，还能跨越时间听上去很美，不是吗？But,……重复下上节的一个结论：通过随机数挑战是交互式零知识证明的「信任根基」。可是如果NIZK失去了挑战过程，有什么后果？我们已经回忆过「零知识」性质的证明，证明过程需要构造一个模拟器，它也和验证者在理想世界中进行交互，而验证者Bob没有能力区分出来对方是否是真的Alice还是一个模拟器。如果现在考虑下NIZK中的非交互式，假如「我」向「你」出示一张纸，上面写着一个「真」证明X，又假如「你」在看过这张纸之后确实相信我了；又因为协议是「零知识」，那么如果把「我」换成一个模拟器，模拟器也能「伪造」一个假证明Y，能够也让「你」相信。好了，问题来了：你如何区分X和Y，孰真孰假？当然你无法区分，因为协议是零知识的，你必须不能区分我可以同样可以把Y出示给你看，那岂不是「我」就可以你了吗？是不是不和谐了？请大家在此处思考两分钟。(两分钟后……)因为NIZK没有了交互，也就没了挑战过程，所有的证明过程都有Alice来计算书写，理论上Alice确实是想写什么就写什么，没人拦得住，比如Alice就写「理想世界」的假证明Y。想必深刻理解模拟器的朋友，在这里会发现一个关键点：模拟器必须只能在「理想世界」中构造Y，也就是说，Y这么邪恶的东西只能存在于「理想世界」，不能到「现实世界」祸害人间。继续思考……还有一个更深层次的问题，请大家回忆下「地图三染色问题」，之所以模拟器不能在「现实世界」中为非作歹，核心原因是，他在理想世界中有「时间倒流」的超能力，而在「现实世界」中不存在这种黑魔法。现实世界的「不存在性」是关键。而且，NIZK中没有交互，于是导致了一个严重的后果，模拟器没有办法使用「时间倒流」这个超能力，当然似乎也就不能区分证明者在两个世界中的行为。换句话说，如果我们面对任何一个NIZK系统，似乎「模拟器」就很难高高在上了，它好像只能飘落人间，成为一个普普通通的凡人。如果，我说如果，按此推论，假设模拟器不再具备超能力，那就意味着Alice和模拟器没有区别，Alice也可以成为一个模拟器，再继续推论，Alice就可以在「现实世界」中任意Bob，那么这个证明系统就不再有价值，因为它失去了「可靠性」。结论：任何的NIZK都不可靠。这一定是哪里出了问题……上面我们在分析的过程中，提到了交互挑战的缺失。确实，如果Bob不参与Alice产生证明的过程，证明所包含的每一个bit都由Alice提供，似乎「证明」本身不存在任何让Bob信任的「根基」。这个从「直觉」上似乎说不通。那是不是说，没有Bob的参与就「彻底」没办法建立「信任根基」了呢？信任的根基还可以从哪里来呢？答案是「第三方」！Wait……，协议交互不是只有两方吗？Alice和Bob，哪来第三方？需要用特殊的方式引入第三方，而且方法不止一种，我们先研究第一种。回顾Schnorr协议

数据：Uniswap NFT聚合服务总交易额突破500万美元，月增长超400%:1月16日消息，据Dune Analytics数据显示，Uniswap NFT聚合服务总交易额已突破500万美元，截至目前达到5,137,547美元，总交易量为7711笔。当前Uniswap NFT聚合服务中交易额最高的平台来自OpenSea，交易额排名前三的NFT系列分别为：Mutant Ape Yacht Club（477,510美元）、“无聊猿”Bored Ape Kennel Club（387,752美元）和CLONE X - X TAKASHI MURAKAMI（252,562美元）。

Uniswap NFT于12月初交易额达到100万美元，Uniswap在过去约1个月时间的交易额增长超过400%。[2023/1/16 11:14:35]

我们再看一下老朋友——Schnorr协议，它是一个三步协议：第一步，Alice发送一个承诺，然后第二步Bob发送随机数挑战，第三步，Alice回应挑战。

我们来看，如何把一个三步的Schnorr协议变成一步。看一下Schnorr协议的第二步，Bob需要给出一个随机的挑战数c，这里我们可以让Alice用下面这个式子来计算这个挑战数，从而达到去除协议第二步的目的。c=Hash(PK,R)其中R是Alice发给Bob的椭圆曲线点，PK是公钥。大家可以好好看看这个利用Hash算法计算c的式子。这个式子达到了两个目的：Alice在产生承诺R之前，没有办法预测c，即使c最终变相是Alice挑选的c通过Hash函数计算，会均匀分布在一个整数域内，而且可以作为一个随机数请注意：Alice绝不能在产生R之前预测到c，不然，Alice就等于变相具有了「时间倒流」的超能力，从而能任意愚弄Bob。而一个密码学安全Hash函数是「单向」的，比如SHA256，SHA3，blake2等等。这样一来，虽然c是Alice计算的，但是Alice并没有能力实现通过挑选c来作弊。因为只要Alice一产生R，c就相当于固定下来了。我们假设Alice这个凡人在「现实世界」中是没有反向计算Hash的能力的。

看上图，我们利用Hash函数，把三步Schnorr协议合并为了一步。Alice可以直接发送：(R,c,z)。又因为Bob拥有PK，于是Bob可以自行计算出c，于是Alice可以只发送(R,z)即可。我们把上面这个方案稍微变下形，就得到了「数字签名」方案。所谓的数字签名，就是「我」向「你」出示一个字符串，比如「白日依山尽，黄河入海流」，然后为了证明这句诗是我出示的，我需要签署某样东西。这个东西能证明我的身份和这句诗进行了关联。从NIZK角度看数字签名

不严格地说，数字签名方案相当于在证明我拥有私钥，并且私钥和消息进行了关联计算。我首先要证明我的身份，那么这个简单，这正是Schnorr协议的功能，能够向对方证明「我拥有私钥」这个陈述。并且这个证明过程是零知识的：不泄露关于「私钥」的任何知识。那么如何和这句唐诗关联呢？我们修改下计算c的过程：m="白日依山尽，黄河入海流"c=Hash(m,R)这里为了保证攻击者不能随意伪造签名，正是利用了离散对数难题与Hash函数满足抗第二原象这个假设。注：这里严格点讲，为了保证数字签名的不可伪造性，需要证明Schnorr协议满足「SimulationSoundness」这个更强的性质。这点请参考文献

上图就是大家所熟知的数字签名方案——Schnorr签名方案。在这里还有一个优化，Alice发给Bob的内容不是(R,z)而是(c,z)，这是因为R可以通过c,z计算出来。注：为什么说这是一个「优化」呢？目前针对椭圆曲线的攻击方法有Shanks算法、Lambda算法还有Pollard'srho算法，请大家记住他们的算法复杂度大约都是，n是有限域大小的位数。假设我们采用了非常接近2^256的有限域，也就是说z是256bit，那么椭圆曲线群的大小也差不多要接近256bit，这样一来，把2^256开平方根后就是2^128，所以说256bit椭圆曲线群的安全性只有128bit。那么，挑战数c也只需要128bit就足够了。这样Alice发送c要比发送R要更节省空间，而后者至少需要256bit。c和z两个数值加起来总共384bit。相比现在流行的ECDSA签名方案来说，可以节省1/4的宝贵空间。现在比特币开发团队已经准备将ECDSA签名方案改为一种类Schnorr协议的签名方案——muSig，可以实现更灵活地支持多签和聚合。而采用Hash函数的方法来把一个交互式的证明系统变成非交互式的方法被称为Fiat-Shamir变换，它由密码学老前辈AmosFiat和AdiShamir两人在1986年提出。重建信任——随机预言精灵

链游《我的邻居爱丽丝》2.0版本已面向主流用户发行:金色财经报道，链游《我的邻居爱丽丝》现在已经向主流用户推出2.0版本。

据悉，该在线游戏于2021年9月成功进行了9个月的预alpha阶段，于2022年6月发布。[2022/12/21 21:58:43]

前文提到，失去了挑战，似乎失去了证明的「信任根基」。而在Schnorr签名方案中，Hash函数担负起了「挑战者」的角色，这个角色有一个非常学术的名字：「随机预言机」。可是这里为何用Hash？实际上当Alice要产生公共随机数时，需要一个叫做「随机预言机」的玩意儿，这是什么？开脑洞时间到！我们设想在「现实世界」中，天上有一位「精灵」，他手持一个双栏表格，左边一栏为字符串，右边一栏为数字。任何人，包括你我，包括Alice和Bob，都可以发字符串给「精灵」。

精灵在拿到字符串之后，会查表的左边栏，看看表格里有没有这个字符串，下面分两种情况：情况一：如果左边栏找不到字符串，那么精灵会产生一个「真随机数」，然后把字符串与随机数写入到表格中，然后把随机数返回地面上的凡人。情况二：如果左边栏有这个字符串记录，那么精灵会将右边栏里面的数字直接返回给地面。大家会发现这个精灵的行为其实很像一个随机数发生器，但是又很不一样，不一样的地方在于当我们发送相同的字符串时，他会返回相同的数。这个精灵就是传说中的「随机预言机」。而在合并Schnorr协议过程中，其实我们需要的是一个这样的随机预言精灵，而不是一个Hash函数。两者有什么不同的地方？区别就是：随机预言机每次对于新字符串返回的是一个具有一致性分布的「真」随机数Hash函数计算的结果并不是一个真正具有一致性分布的随机数那么为什么前面用的是Hash函数呢？这是因为在现实世界中，真正的随机预言机不存在！为什么呢？事实上，一个Hash函数不可能产生真的随机数，因为Hash函数是一个「确定性」算法，除了参数以外，再没有其它随机量被引入。而一个具有密码学安全强度的Hash函数「似乎」可以充当一个「伪」随机预言机。那么合并后的安全协议需要额外增加一个很强的安全假设，这就是：假设：一个密码学安全的Hash函数可以近似地模拟传说中的「随机预言机」因为这个假设无法被证明，所以我们只能信任这个假设，或者说当做一个公理来用。插一句，Hash函数的广义抗碰撞性质决定了它的输出可以模拟随机数，同时在很多情况下，对Hash函数实施攻击难度很高，于是许多的密码学家都在大胆使用。不使用这个假设的安全模型叫做「标准模型」，而使用这个假设的安全模型当然不能叫「非标准模型」，它有个好听的专有名词，叫做「随机预言模型」。世界上有两种不同类型的人，喜欢甜豆花的，不喜欢甜豆花的。同样，世界上的密码学家分为两种，喜欢随机预言模型的，和不喜欢随机预言模型的。构造根基——被绑架的精灵

Schnorr协议经过Fiat-Shamir变换之后，就具有NIZK性质。这不同于我们证明过的SHVZK，SHVZK要求验证者诚实，而NIZK则不再对验证者有任何不现实的要求，因为验证者不参与交互，所谓要求诚实的验证者这个问题就不复存在。注：如果验证者Bob不诚实会怎样？那么Bob有可能抽取出Alice的知识。但是对于三步Schnorr协议而言，它是否满足「零知识」，目前还处于未知状态。我们在系列三中只证明了它满足一个比较弱的性质：SHVZK。但是，当Schnorr协议摇身一变，变成非交互零知识证明系统之后，就真正的「零知识」了。然而，可能你的问题也来了，这个论断听起来似乎有道理，请问能证明吗？时间到了，“翠花，上模拟器”怎么用模拟器大法来构造一个「理想世界」呢？大家可以想一下，我们之前使用过「时间倒流」，还有修改「随机数传送带」超能力来让「模拟器」来作弊。可是没有交互了，这就意味着：「时间倒流」超能力不能用；Bob的随机数传送带也不存在了，「篡改传送带」这个超能力也不能用！但模拟器总要具备某种「超能力」，从而能够构建信任的「根基」。可能大家现在已经猜出来了，模拟器要在「随机预言机」上动手脚。先考虑下构造一个「理想世界」来证明「零知识」。在理想世界中，模拟器「绑架」了负责提供预言的「精灵」，当Bob向精灵索要一个随机数的时候，精灵并没有给一个真随机数，而是给Zlice提前准备好的一个数，「精灵」无可奈何地返回Bob一个看起来随机，但实际上有后门的数字。所谓后门，就是这个数字是Zlice自己提前选择好的。

Kyle Roche已从涉嫌与Ava Labs合作发起恶性竞争的事务所离职:10月20日消息，律师事务所Roche Freedman宣布，其创始合伙人Kyle Roche已从该事务所离职，未来该事务所将更名为Freedman Normand Friedland。

此前Cryptoleaks曾释出大量爆料视频，内容为Kyle Roche在谈论Ava Labs（Avalanche开发公司）和Roche Freedman的一项秘密合作协议。通过该项合作，Ava Labs向Roche Freedman支付了大量Ava Labs股权和AVAX（现价值数亿美元），Roche Freedman则向Binance、Solana Labs和DFINITY Foundation等Avalanche的竞争对手发起恶意诉讼。（路透社）[2022/10/20 16:31:16]

第一步：Zlice随机选择z，随机选择c，计算R'=z*G-c*PK。

第二步：Zlice将c与(m,R')写入精灵的表格。

第三步：Zlice将签名(c,z)发送给Bob。

第四步：Bob计算R=z*G-c*PK，并向精灵发送(m,R)，精灵返回c’。请注意，这里Bob计算出来的R和Zlice计算出来的R'是相等。

第五步：Bob验证c?=c'，看看精灵传回来的随机数和对方发过来的随机数是否相等。如果相等，则验证签名通过；否则，则验证失败。通过绑架「精灵」，Zlice同样可以提前预知随机数，这和时间倒流能达到同样的效果。我们已经证明了模拟器Zlice的「存在性」，于是我们上面已经证明了NIZK。接下来我们证明这个这个协议的「可靠性」。设想在另一个「理想世界」中，一个叫做「抽取器」的玩意儿，也同样绑架了精灵。当无辜Alice的向「精灵」索要一个随机数时，「精灵」返回了一个c1，「抽取器」从精灵的表格中偷窥到了c1，当Alice计算出来z1之后，然后这时候「抽取器」仍然可以发动「时间倒流」超能力，让Alice倒退到第二步，再次向「精灵」要一个随机数，Alice发送的字符串显然和第一次发送的字符串是相同的，(R,m)。按道理，因为(R,m)已经写在精灵表格的「左栏」里，所以一个诚实的「精灵」应该返回c1。但是，「抽取器」绑架了精灵，他把表格中对应(R,m)这一行的「右栏」改成了一个不同的数c2。当Alice计算出另一个z2之后，抽取器就完成了任务，通过下面的方程计算出Alice的私钥sk：sk=(z1-z2)/(c1-c2)Fiat-Shamir变换——从Public-Coin到NIZK

不仅仅对于Schnorr协议，对于任意的「Public-Coin协议」，都可以用Fiat-Shamir变换来把整个协议「压缩」成一步交互，也就是一个非交互式的证明系统，这个变换技巧最早来自于AmosFiat与AdiShamir两人的论文『HowtoProveYourself:PracticalSolutionstoIdentificationandSignatureProblems.』，发表在1986年的Crypto会议上。也有一说，这个技巧来源于ManuelBlum.重复一遍，在Public-coin协议中，验证者Bob只做一类事情，就是产生一个随机数，然后挑战Alice。通过Fiat-Shamir变换，可以把Bob每一次的「挑战行为」用一次「随机预言」来代替。而在具体实现中，随机预言需要用一个具有密码学安全强度的Hash函数，而Hash函数的参数应该是之前所有的上下文输入。下面是一个示例图，大家可以迅速理解这个Fiat-Shamir变换的做法。

前面提到，在非交互式证明系统中，需要引入一个第三方来构建信任的「根基」，使得Bob可以完全相信由Alice所构造的证明。在这里，第三方就是那个「精灵」，用学术黑话就是「随机预言」。这个精灵并不是一个真实存在的第三方，而是一个虚拟的第三方，它同时存在于「现实世界」与「理想世界」。在「现实世界」中，精灵是一个负责任的安静美男子，而在「理想世界」中，它会被「模拟器」绑架。Public-Coin协议还有一个好听的名字，「Arthur-Merlin游戏」……

美联储乔治：我支持继续加息:10月14日消息，美联储乔治：我支持继续加息。加息路径需要是稳健和可预测的。[2022/10/14 14:27:57]

看上图，左边的“白袍”就是Merlin，中间拿剑的帅哥就是KingArthur，两个角色来源于中世纪欧洲传说——亚瑟王的圆桌骑士。Arthur是一个不耐烦的国王，他随身携带一个硬币，而Merlin是一个有着无限制计算能力的神奇魔法师，然后魔法师想说服国王相信某个「论断」为真，于是魔法师会和国王进行到对话，但是由于国王比较懒，他每次只会抛一个硬币，然后「挑战」魔法师，而魔法师需要及时应对，而且需要让国王在k轮之后能够相信自己的论断。由于Merlin有魔法，所以亚瑟王抛的硬币都能被Merlin看到。这与我们在『系列一』中提到的交互式证明系统有些神似，但又不同。IP由Goldwasser，Micali与Rackoff在1985年正式提出，它的证明能力覆盖很大一类的计算复杂性问题。而不同的地方在于：在IP的定义中，证明者Prover和验证者Verifier都是可以抛硬币的图灵机，Verifier可以偷偷抛硬币，并对Prover隐藏；而在Arthur-Merlin游戏中，国王只能抛硬币，不仅如此，而且抛硬币的结果总会被Merlin知道。但是，Fiat-Shamir变换只能在「随机预言模型」下证明安全，而用Hash函数实现随机预言的过程是否安全是缺少安全性证明的。不仅如此，「随机预言模型」下安全的协议可能是有不安全的，已经有人找到了一些反例；更不幸的是，S.Goldwasser与Y.Tauman在2003年证明了Fiat-Shamir变换本身也是存在安全反例的。但是这并不意味着Fiat-Shamir变换不能用，只是在使用过程中要非常小心，不能盲目套用。尽管如此，人们无法抵挡Fiat-Shamir变换的诱惑，其使用极其广泛。值得一提的是，最热的通用非交互零知识证明zkSNARK的各种方案中，Fiat-Shamir变换比比皆是。比如大家可能耳熟能详的Bulletproofs，此外还有一些暂时还不那么有名的通用零知识证明方案，比如Hyrax，Ligero，Supersonic，Libra等。小心：Fiat-Shamir变换中的安全隐患

在Fiat-Shamir变换中，要尤其注意喂给Hash函数的参数，在实际的代码实现中，就有这样的案例，漏掉了Hash函数的部分参数：比如在A,Hash(A),B,Hash(B)中，第二个Hash函数就漏掉了参数A，正确的做法应该是A,Hash(A),B,Hash(A,B)。这一类的做法会引入严重的安全漏洞，比如在瑞士的电子投票系统SwissPost-Scytl中，就在Fiat-Shamir变换的实现代码中多次漏掉了本来应该存在的参数，导致了攻击者不仅可以随意作废选票，还可以任意伪造选票，达到舞弊的目的。因此在工程实现中，请务必注意。细心读者也许会回看一下Schnorr签名，大家会发现Schnorr签名中的Hash算法似乎也漏掉了一个参数PK，并不是严格的Fiat-Shamir变换，这被称为WeakFiat-Shamir变换，不过这个特例并没有安全问题，请未成年人不要随意模仿。最近一些学者开始在标准模型下研究如何严格证明Fiat-Shamir变换的安全性，目前要么引入额外的强安全假设，要么针对某个特定协议进行证明，但似乎进展并不大。交互的威力

话说在1985年，当GMR三人的论文历经多次被拒之后终于被STOC’85接受，另一篇类似的工作也同时被STOC'85接受，这就是来自于匈牙利罗兰大学的LászlóBabai，与来自以色列理工的ShlomoMoran两人撰写的论文『Arthur-MerlinGames:ARandomizedProofSystem,andaHierarchyofComplexityClasses』，引入了Public-coin交互式协议。国王Arthur的方法很简单，通过反复地「随机」挑战来检验Merlin的论断，这符合我们前面讲述过的直觉：采用随机挑战来构建信任的「根基」。Babai在论文中证明了一个有趣的结论：AM=AM，其中k表示交互的次数，交互多次产生的效果居然和交互两次等价。所谓交互两次是指：Arthur发一个挑战数，然后Merlin回应。注：还有一类的问题属于MA，这一类问题的交互顺序与AM不同，MA中是Merlin先给出证明，然后Arthur抛硬币检验。已证明：MA能处理的问题是AM的子集。不仅如此，Babai还大胆猜测：AM与IP是等价的。这是一个神奇的论断：国王很懒，他只需要通过抛多项式次硬币，就能成功挑战魔法师，而这种方式的表达能力居然完全等价于GMR描述的交互式证明系统IP。果不其然，在STOC'86会议上，来自S.Goldwasser与M.Sipser的论文证明了这一点，AM==IP。

Rocket Pool拟推出Staking-as-a-Service产品，并计划将minipool运营者抵押要求降至4ETH:7月19日消息，据以太坊质押协议Rocket Pool的DAO活跃成员Marceau.eth表示，Rocket Pool将进行一列升级，计划为基础设施公司和机构托管人推出Staking-as-a-Service产品，使得大型质押运营商以信任最小化的方式来参与质押；还计划将小型矿池运营商（minipool）的抵押要求从16ETH减少到4ETH，这将使运行节点所需的抵押品减少2至4倍，提升节点运营商的收益。此外，在之后的Capella硬分叉后，Solo质押者也将能够直接迁移到RocketPool。（The Defiant）[2022/7/19 2:22:55]

这意味着：反复公开的「随机挑战」威力无穷，它等价于任意的交互式证明系统。但是AM和别的计算复杂性类的关系如何，是接下来的研究热点。三年后，1989年11月底，距今恰好三十年，年轻的密码学家NoamNisan发出了一封邮件，把自己的临时学术结论发给了几个密码学家，然后他就跑去南美洲度假了。可是他不曾想到，这一个邮件会引爆历史上一场激烈的学术竞赛，M.Blum,S.Kannan,D.Lipton,D.Beaver,J.Feigenbaum,H.Karloff,C.Lund等等一大群精英开始加入战斗，他们没日没夜地互相讨论，并且竞相发布自己的研究成果，终于在12月26号，刚好一个月，AdiShamir证明了下面的结论：AM==IP==PSPACE

它解释了「有效证明」这个概念的计算理论特征，并且解释了「交互式证明系统」这个概念所能涵盖的计算能力。注：NP类是PSPACE类的子集，前者大家比较熟悉，后者关联游戏或者下棋中的制胜策略。而L.Babai于是写了一篇文章，名为「Emailandtheunexpectedpowerofinteraction」，详细阐述了这一整个月在「邮件交互」中精彩纷呈的学术竞赛，以及关于「交互证明」的来龙去脉。公共参考串——另一种「信任根基」

除了采用「随机预言机」之外，非交互零知识证明系统采用「公共参考串」，简称「CRS」，完成随机挑战。它是在证明者Alice在构造NIZK证明之前由一个受信任的第三方产生的随机字符串，CRS必须由一个受信任的第三方来完成，同时共享给Alice和验证者Bob。是的，你没看错，这里又出现了「第三方」！虽然第三方不直接参与证明，但是他要保证随机字符串产生过程的可信。而产生CRS的过程也被称为「TrustedSetup」，这是大家又爱又恨的玩意儿。显然，在现实场景中引入第三方会让人头疼。CRS到底用来做什么？TrustedSetup的信任何去何从？这部分内容将留给本系列的下一篇。未完待续

非交互式零知识证明NIZK的「信任根基」也需要某种形式的随机「挑战」，一种「挑战」形式是交给「随机预言精灵」；另一种「挑战」是通过Alice与Bob双方共享的随机字符串来实现。两种挑战形式本质上都引入了第三方，并且两者都必须提供可以让「模拟器」利用的「后门」，以使得让模拟器在「理想世界」中具有某种「优势」，而这种优势在「现实世界」中必须失效。NIZK散发着无穷魅力，让我不时惊叹，在过去三十多年里，先驱们所探寻到的精妙结论，同时还有如此之多的未知角落，在等待灵感之光的照射。本系列文章在Github上的项目仓库收到了第一个PullRequest，来自JingyuHu(colortigerhu)，只改了个把字，但那一瞬间，我感受到了生命力。知识交流，思想碰撞，很迷人，不是吗？“Everyoneweinteractwithbecomesapartofus.”与我们交往互动的每一个人都是我们自身的一部分。―JodiAman*致谢：特别感谢丁晟超，刘巍然，陈宇的专业建议和指正，感谢安比实验室小伙伴们(p0n1,even,aphasiayc,Vawheter,yghu,mr)的修改建议。致谢：自Nisan发起的密码学研究轶事参考自邓老师的文章。参考文献Schnorr,Claus-Peter."Efficientsignaturegenerationbysmartcards."Journalofcryptology4.3(1991):161-174.Paillier,Pascal,andDamienVergnaud."Discrete-log-basedsignaturesmaynotbeequivalenttodiscretelog."InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,Berlin,Heidelberg,2005.Pointcheval,David,andJacquesStern."Securityargumentsfordigitalsignaturesandblindsignatures."Journalofcryptology13.3(2000):361-396.Maxwell,Gregory,AndrewPoelstra,YannickSeurin,andPieterWuille."Simpleschnorrmulti-signatureswithapplicationstobitcoin."Designs,CodesandCryptography87,no.9(2019):2139-2164.Fiat,Amos,andAdiShamir."Howtoproveyourself:Practicalsolutionstoidentificationandsignatureproblems."ConferenceontheTheoryandApplicationofCryptographicTechniques.Springer,Berlin,Heidelberg,1986.Bellare,Mihir,andPhillipRogaway."RandomOraclesArePractical:aParadigmforDesigningEfficientProtocols."Proc.ofthe1stCCS(1995):62-73.LászlóBabai,andShlomoMoran."Arthur-Merlingames:arandomizedproofsystem,andahierarchyofcomplexityclasses."JournalofComputerandSystemSciences36.2(1988):254-276.mCanetti,Ran,OdedGoldreich,andShaiHalevi."Therandomoraclemethodology,revisited."JournaloftheACM(JACM)51.4(2004):557-594.ShafiGoldwasser,andYaelTauman."Onthe(in)securityoftheFiat-Shamirparadigm."44thAnnualIEEESymposiumonFoundationsofComputerScience,2003.Proceedings..IEEE,2003.Lewis,SarahJamie,OlivierPereira,andVanessaTeague."Addendumtohownottoproveyourelectionoutcome:TheuseofnonadaptivezeroknowledgeproofsintheScytlSwissPostInternetvotingsystem,anditsimplicationsforcastasintendedverification."Univ.Melbourne,Parkville,Australia(2019).Bernhard,David,OlivierPereira,andBogdanWarinschi."Hownottoproveyourself:Pitfallsofthefiat-shamirheuristicandapplicationstohelios."InternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity.Springer,Berlin,Heidelberg,2012.Goldwasser,Shafi,andMichaelSipser."Privatecoinsversuspubliccoinsininteractiveproofsystems."ProceedingsoftheeighteenthannualACMsymposiumonTheoryofcomputing.ACM,1986.Papadimitriou,ChristosH."Gamesagainstnature."JournalofComputerandSystemSciences31.2(1985):288-301.Babai,László."E-mailandtheunexpectedpowerofinteraction."ProceedingsFifthAnnualStructureinComplexityTheoryConference.IEEE,1990.YiDeng."零知识证明：一个略显严肃的科普."https://zhuanlan.zhihu.com/p/29491567

标签：LICICEALIALICEethicalsiliconpoliceNot Financial AdviceKalima Blockchainalice币创始人

Polygon热门资讯