一个略显严肃的科普：从交互到非交互式零知识证明

Challenges are at times an indication of Lord’s trust in you.

挑战，有时是上天信任你的一种表现。 

——  D. Todd Christofferson

本文继续长篇大论零知识证明背后的机制原理，希望帮助大家理解这一类「现代密码学工具」的大致轮廓。本文约8000字，少量数学公式。

交互与挑战

我们之前介绍的零知识证明系统都是「交互式」的，需要验证者 Bob 在交互中提供一个或若干个「随机数」来挑战，比如「地图三染色问题」（参看『系列二』）中，验证者 Bob 需要「不断地」随机挑选一条边来挑战 Alice 的答案，直到 Bob 满意为止，而 Alice 的作弊概率会「指数级」地衰减。而让 Bob 相信证明的「基础」取决于 Bob 所挑选的随机数是不是足够随机。如果 Alice 能够提前预测到 Bob 的随机数，灾难就会发生，现实世界就会退化成「理想世界」，而 Alice 就可以立即升级成「模拟器」，通过超能力来愚弄 Bob。而『系列三』中，我们分析了 Schnorr 协议，协议中虽然验证者 Bob 只需要挑选一个随机数 c 来挑战 Alice ，让她计算一个值 z，但 Bob 绝对不能让 Alice 有能力来预测到 c 的任何知识，否则，Alice 也会变身成模拟器。随机数的重要性不言而喻：

通过随机数挑战是交互式零知识证明的「信任根基」。

但，「交互过程」会限制应用场景。如果能将交互式零知识证明变成「非交互」？这会非常非常激动人心。所谓的非交互可以看成是只有「一轮」的证明过程，即Alice 直接发一个证明给 Bob 进行验证。

非交互式零知识证明，英文是 Non-Interactive Zero Knowledge，简称 NIZK。它意味整个证明被编码为一个「字符串」，它可以写到一张纸上，通过邮件、聊天工具等各种方式随意发送给任何验证者，字符串甚至可以放在 Github 上随时供大家下载验证。

在区块链世界，「NIZK」可以作为共识协议的一部分。因为一个交易需要多个矿工进行校验。设想下，如果交易的发送者和每个矿工都要交互一下，让矿工进行挑战，那么共识过程将奇慢无比。而非交互式零知识证明则可以直接广播给所有的矿工节点，让他们自行验证。

可能有朋友会问：只让一个矿工挑战不就够了吗？把矿工和交易发送者的交互脚本编码成证明，然后广播给其他矿工，然后其他矿工就直接相信这个挑战过程是可信的，不也可以吗？但是，很显然，这里需要相信第一个交互矿工作为可信第三方，第三方？似乎不是一个好主意……

而非交互式零知识证明，以下我们直接说「NIZK」，似乎就很理想了，没有第三方赚差价。

「非交互」带来的困惑

非交互式零知识证明，NIZK，如果存在，那么它要比交互式证明强大得多。

NIZK 不仅可以跨越空间，还能跨越时间

听上去很美，不是吗？But, ……重复下上节的一个结论：

通过随机数挑战是交互式零知识证明的「信任根基」。

可是如果 NIZK 失去了挑战过程，有什么后果？我们已经回忆过「零知识」性质的证明（参考『系列二』），证明过程需要构造一个模拟器（算法），它也和验证者（Bob）在理想世界中进行交互，而验证者 Bob 没有能力区分出来对方是否是真的 Alice 还是一个模拟器。如果现在考虑下 NIZK 中的 非交互式，假如「我」向「你」出示一张纸，上面写着一个「真」证明 X ，又假如「你」在看过这张纸之后确实相信我了；又因为协议是「零知识」，那么如果把「我」换成一个模拟器，模拟器也能「伪造」一个假证明 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 协议

我们再看一下老朋友——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 角度看数字签名
不严格地说，数字签名方案相当于在证明（1）我拥有私钥，并且（2）私钥和消息进行了关联计算。
我首先要证明我的身份，那么这个简单，这正是 Schnorr 协议的功能，能够向对方证明「我拥有私钥」这个陈述。并且这个证明过程是零知识的：不泄露关于「私钥」的任何知识。那么如何和这句唐诗关联呢？我们修改下计算 c 的过程：
m = "白日依山尽，黄河入海流"
c = Hash(m, R)
                                                        
转载声明：本文 由CoinON抓取收录，观点仅代表作者本人，不代表CoinON资讯立场，CoinON不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。若以此作为投资依据，请自行承担全部责任。
声明：图文来源于网络，如有侵权请联系删除
风险提示：投资有风险，入市需谨慎。本资讯不作为投资理财建议。
                        

                        
交互式证明随机数挑战零知识证明
                        

                            
 赞 (0)

                                                            

                                     打赏                                    
                                                                                                            
                                                        
                                                            微信扫一扫                                                    
                                                                                                                                            
                                
                                                    

                        

                            

                                                                    

                                                                                
                                            Bob鲍师傅                                        
                                    
                                                                

                                    

                                                                                     0                                                                                                                    
                                    

                                        
                                          分享生成图片