首页 > 社交 > 科普中国

零知识证明:从入门到入土

常驻编辑 科普中国 2022-11-16 图灵机   哈密尔顿   多项式   随机数   知识   阿里巴巴   回路   入门   现实   协议   世界
Alice
  • Alice计算z=r+c*a,将z发送给Bob
  • Bob验证z*G,即(r+c*a)*G是否等于R+c*(a*G)。
  • 接下来证明Schnorr协议对「验证者可靠」。6HZ拜客生活常识网

    6HZ拜客生活常识网

    以上图为例,模拟器模拟了一个ZliceZlice是怎么提取出Alice的知识的呢?6HZ拜客生活常识网

    Zlice在进行到step 4时,它并没有验证z*G是否等于R+c*(a*G),而是通过虚拟机的「快照机制」,记录了Alice发送的z,并重新返回了step 2发送给了Alice另一个随机数c’,由于Alice目前是在虚拟机内运行的程序,所以它并没有感知到「快照机制」的启动(在现实世界的程序才能感知到快照的启动),在模拟的世界中,Zlice成功骗取Alice以相同的随机数r发送了两个z,算出了Alice的私钥a,而正如之前所说:Alice没有办法区分现实世界和模拟世界,所以在现实世界,协议也是「证明可靠」。6HZ拜客生活常识网

    如果模拟器真的存在,对Alice来说岂不是一个灾难?有没有可能在现实世界里,Bob也能用这个模拟的方法骗到Alice的密钥?这是不可能的,因为虽然模拟世界和现实世界对Alice来说是不可区分的,但是模拟世界的Zlice需要使用「超能力」,例如虚拟机快照机制的「时间倒流」才能够骗到Alice不更改随机数r,而这种「超能力」是现实世界的Bob所不具备的(毕竟没有人可以倒流现实中的时间)。6HZ拜客生活常识网

    以上用两个例子(三染色、Schnorr)展示了zk证明的全过程,分别证明了zk协议「对证明者安全」、「对验证者可靠」。6HZ拜客生活常识网

    禁忌

    观察「虚拟机」所代表的模拟世界中发生的事,我们可以发现,有些事是在IZK协议中绝对不能做的:6HZ拜客生活常识网

    • 验证者不随机(三染色验证同一条边,使证明者可以欺骗验证者)
    • 证明者不随机(Schnorr中r保持不变,使验证者可以提取证明者的知识)

    如果在IZK中犯了上面的错误,就相当于在现实世界给予了对手「超能力」,这会造成恶劣的影响,例如2011年Sony Playstation 3的root私钥的泄漏,就是因为索尼工程师没有更改Alice的随机数r。6HZ拜客生活常识网

    NIZK

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

    随机预言机

    上文所说的Schnorr协议也有NIZK的版本:6HZ拜客生活常识网

    6HZ拜客生活常识网

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

    NIZK形式的Schnorr协议,也是需要证明「对证明者安全」、「对验证者可靠」的,同样是使用模拟的方法进行证明,这里不展开。6HZ拜客生活常识网

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

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

    既然Hash 函数并不是我们理想中的随机预言机,那我们为什么还信任使用Hash 函数的Schnorr NIZK协议呢?这是因为我们假设「一个具有密码学安全强度的Hash 函数能够近似地模拟随机预言机」,默认这个假设的模型被称为「标准模型」,不默认这个假设的模型称为「非标准模型」。这种使用Hash 函数将IZK变成NIZK的方法,被称为「Fiat-Shamir 变换」。6HZ拜客生活常识网

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

    相关阅读:

  • 百度无人车驾驶参考线处理专利获授权,可提高避障能力
  • “许可IPFS存储网络”
  • “非酋”不配玩游戏?游戏中万恶的随机数
  • 溺水安全知识是什么?防溺水安全知识有哪些?[图]
  • 关晓彤密室恋爱教学,不仅推理智商在线,传授恋爱知识表白
  • 机器人比赛有哪些(机器人大赛需要哪些知识)
  • 门有哪些种类(门的知识以及分类)
  • 环保知识有哪些(环保基本常识及基础知识)
  • 在哪里学美(医美专业学哪些知识)
  • 如何选手机(买手机需要懂哪些知识)
    • 网站地图 |
    • 声明:登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不做权威认证,如若验证其真实性,请咨询相关权威专业人士。