作者:benlaw.eth
你之前是否阅读过一些零知识证明的文章,但仍一头雾水?这些文章可能:
本文提供了对ZKP简明扼要的概述,并从数学、密码学和编程角度进一步阐述ZKP的核心要素。
向色盲提供颜色证明
如何向色盲患者证明两个球的颜色确实是不同的?这其实并不复杂:
让他在手里握住两个球,背到背后,然后随机选择交换或不交换两个球的位置,再展示给你看,你告诉他这两个球的位置是否有变化。
在他看来,你可以通过瞎蒙来完成一次证明。不过,如果成千上万次地重复这个过程:如果你总是能说出正确答案,那么靠纯蒙的方式来保持一直正确的概率,是小到可以忽略的。因此可以通过这种方式来向色盲患者证明:两个球的颜色确实不一样,并且我们也有感知和区分的能力。
颜色证明
上述证明过程是典型的零知识证明:
掌握知识的证明
我们已经分享了一种现实世界中的零知识证明的例子,接下来再来看一下在二进制世界中如何实现零知识证明。
Arthur是Elon的朋友,并且知道对方的手机号。Betty不知道Elon的号码。如果Arthur想要向Betty证明他知道,但又不想泄露号码,应该怎么实现呢?
知识证明
一种不成熟的方案是,Elon发布自己电话号码的哈希,Arthur通过一个程序输入哈希的原像,程序进行运算并检查结果。这个方法有一些致命的缺陷:
常规的方法在这里碰壁了,是时候让零知识证明出场了!
基于密码学的零知识证明的实现方案
在此我会用零知识证明中的Sigma Protocol来解决问题,因为它比较简单。并且,为了简洁和易于理解,这里不会使用严格的密码学和数学中的定义、术语及推导过程等。
核心流程
使用零知识证明证明一个人有特定的知识,我们采取如下办法:
Sigma协议
好啦,该证明协议到此就结束了!非常简短,但你仍可能对上面的一些数学运算感到困惑,但这不要紧,我们先有个大概印象再深入理解。
数学原理
这套流程背后的核心数学原理是离散对数难题:当P是一个很大的质数时,对于给定的h,很难找到满足h = g^w(mod P)的w。该原理适用于上面所有类似的式子。
我们来一步一步解析下:
经过加密的知识h = g^w (mod P),是难以被暴力破解的。由于求余运算的特点,即使被破解了也不具备单一确定解。这意味着对证明者而言,通过暴力破解来作弊,欺骗验证者,是不可行的。
然后我们将3,4,5步作为一个整体来看一下他们为什么要交换这些随机数:
I. 证明者并不想暴露其秘密,所以他必须用随机数包裹一下将其隐藏起来。而验证者也需要通过添加一些随机数,让该知识可被自己验证的同时防止证明者作弊,而且不会窥探到证明者的秘密。
II. 如果验证者先发送了随机数e(即将3和4步交换一下),很明显,证明者可以通过编造a = g^z·h^-e来在最终检查中欺骗验证者,即使没有知识也可以通过。所以证明者必须先手发送一个承诺(a=g^r),但非r本身,来避免可作弊场景,同时不让验证者通过w = (z - r)/e提取到秘密。
III. 在收到承诺后,验证者向证明者发送随机数e。由于其本身或者其衍生物无法泄露任何一方的信息,这个数不需要加密。之后证明者计算z = r + ew并将z发送给验证者。验证者最终通过检查g^z= g^(r+ew)= g^r·(gw)^e= a·h^e来确定证明者是否掌握知识。
通过这种往返交错的结构,我们收获了三个性质:
完备性:当且仅当证明者输入正确知识,验证才能通过。
可靠性:当且仅当证明者输入错误知识,验证才会失败。
零知识性:验证者无法在验证过程中获取任何知识。
上述三点即零知识证明的核心特性。通过数学和密码学,我们构建出了一套光怪陆离的证明体系。恭喜你一路走了这么远,现在应该已经可以说正式迈入了富丽堂皇又奥妙无穷的ZKP圣殿。
Have fun!
进一步了解
模拟器和零知识性
我们现在来考虑一些魔幻场景。如果一个证明者具有预言或篡改验证者生成的随机数的超能力,我们称其为模拟器。
模拟器 vs 验证者
设想,模拟器在验证者的随机数e生成前就对其进行了篡改,确保其生成后是自己预设的值。根据上面II所说,这种能力使模拟器能编造承诺a来欺骗验证者。不论模拟器的输入是什么,验证者总会得出结论模拟器具有知识,然而实际上他并没有。
显然,经过这种思想实验我们可以得出结论,验证者无法在该零知识证明协议中获取任何知识,也即其零知识性是成立的:
零知识性 <== ∀模拟器S,使得S(x)与真实的协议执行不可区分,其中S(x):选择随机的z和e,令a = g^z·h^-e,其中(a,e,z)的分布与真实的随机数环境一致并满足g^z=a·h^e。
抽取器和可靠性
再来想象一下另一种超能力者——抽取器,具有时光倒流的能力。不过这次是抽取器作为验证者,面对一个正常的证明者。
当协议结束时,抽取器发起时间倒流,回到协议的起点,并持有上一轮得到的(z, e, a) 。现在,协议重新执行一遍。由于证明者没有超能力无法进行时间旅行只能在固定的时间线上做确定的事,他又生成了一个一模一样的随机数r以及承诺a = g^r,而抽取器则可以生成新的随机数e'给证明者。
证明者 vs 抽取器
现在,抽取器获得了:g^z= a·h^e, g^z'=a·h^e => g^(z-z') = h(e-e') => 加密后的知识 h = g^((z-z')/(e-e')) => 知识 w = (z-z')/(e-e').
显然,只要证明者真的掌握了知识,抽取器总是可以将其抽取出来,也即完备性成立:完备性 <== ∀抽取器E,对给定的任何h,在掌握(a,e,z),(a,e',z')且e≠e'的情况下,都能输出w s.t. (h,w) ∈ R.
完备性
完备性不需要任何特殊角色来证明,因为:g^z = g^r+ew = g^r·(g^w)^e = a·h^e.