当前位置:首页 区块链 正文

零知识证明协议交互式和非交互式的转换

2023-03-20

随着零知识证明算法的应用越来越广泛,近几年出现了各种各样的算法,比如 FOAKS, Orion,zk-stark等等。这些算法和密码学界早期的 sigma协议等的核心证明逻辑都是:证明者(Prover)先将某个值发送给验证者(Verifier),验证者通过本地随机数产生一个挑战(Challenge),将这个随机产生的挑战值发给证明者,证明者需要真的有知识才能以大概率做出通过验证者的响应。打个比方来说,在没有知识的山洞里面,记者抛出一枚铜板,让阿里巴巴选择左边还是右边,“左和右”两个字就是在挑战阿里巴巴,如果他懂得咒语的话,那么就一定能够走到指定的方向,否则的话,失败的几率就会高达50%。


Challenge的产生是非常重要的一步,需要满足两个条件:随机性和不可证据性。第一个方面,它的随机性使其具有概率性质。第二点,如果你能预测到挑战值,那么你的计划就会失效,就算你什么都不懂,也可以继续下去,如果阿里巴巴能预测到你想要走的路,那么你不需要任何咒语,就可以走到你想走的那条路,你的计划也会成功。


所以,我们需要一种方法,让证明者自己产生一个随机数,然后由验明者来验证。


非互动式浮点定位系统


在这一部分中,我们具体说明了Fiat-Shamir启发式在 FOAKS协议中的应用,主要用于为实现非交互式 FOAKS的 Brakedown部分带来的挑战。


首先,我们可以看出, Brakedown生成证明过程中,最有挑战性的一步,就是“近似检验”和“Merkle树的证明”。


现在我们用哈希函数,来让证明者自己,去生成随机矢量。


令γ0= H (C1, R,r0,r1),相应地,在验证者的验证计算中,需要增加这一步来计算γ0。按照这个结构,证明者无法预知挑战的大小,所以他无法根据挑战的大小进行相应的“作弊”,从而产生一个虚假的承诺,而哈希函数的输出是随机的,所以这个挑战的大小也是随机的。


菲亚特-沙米尔启发式(赫里斯蒂克)


实际上,Fiat-Shamir启发式算法正是通过使用哈希函数,对先前生成的脚本执行哈希操作,从而获得一个数值,并将其作为一个挑战数值。


由于哈希函数 H被看作是一种随机函数,所以这个挑战被均匀地、随机地选择,与公开的信息无关,也与证明者的诺言无关。安全性分析表明,爱丽丝无法预测出 H的输出结果,只能把它看成是一条线。在此情形中,爱丽丝(尤其是在不知道必要机密的情况下)作出正确回答的可能性与 H的值域大小成反比。


哈希函数


对于我们来说,哈希函数这个名字应该很熟悉,它可以用来解决比特币共识协议中的数学问题,也可以用来压缩数据,构建消息验证码等等,也可以用到哈希函数。在这些不同的协议中,哈希函数被应用到了不同的地方。


具体地说,安全哈希函数具有如下特征:


可压缩性:一个确定哈希函数能把任何长度的消息压缩成一个固定的长度.


效率:给定一个输入,很容易计算出输出 h (x).


抗冲突性:给定输入为x1,要找出另一个输入为x2, h (x1)= h (x2),难度很大。


请注意,如果哈希函数满足抗碰撞性,则必然满足单向性,即给定输出 y,则很难找到 x满足 h (x)= y的条件。在密码学中,理论上没有一种函数能够完全满足单向性,但实际上,哈希函数可以看作是一种单向函数。


因此,以上几类应用都与哈希函数相对应,同时,哈希函数的另一项重要功能是提供随机性,尽管目前还不能构建完美的随机数生成器,但实际中却可以提供这种功能,这也是我们后面所讨论的Fiat-Shamir启发式方法的基础。


很多零知识证明算法在设计之初依赖于验证者与验证者之间的交互,但不适用于链上数据隐私保护、 zkRollup等需要高通信开销、高效率的应用场景。利用Fiat-Shamir启发式,证明者可以在不损害协议安全的前提下,本地产生随机数进行“挑战”,并由证明者进行验证。按照这一思路, FOAKS也实现了非交互证明,并将其应用到系统中去。