Cointime

扫码下载App
iOS & Android

如何将交互式的零知识证明协议改造为非交互式?

撰文:康水跃,Fox Tech CEO;孟铉济,Fox Tech 首席科学家

前言

密码学当中的零知识证明技术在web3世界有着广泛的应用,包括进行隐私计算、zkRollup等等。其中Layer2项目FOX所使用的FOAKS就是一个零知识证明算法。在上述的一系列应用当中,对于零知识证明算法而言,有两方面属性极为重要,那就是算法的效率以及交互性。

算法效率的重要性不言而喻,高效的算法可以明显的降低系统运行时间,从而降低客户端延迟,显著的提高用户体验和效率,这也是FOAKS致力于实现线性证明时间的一个重要原因。

另一方面,从密码学的角度来讲,零知识证明系统的设计往往依赖证明者和验证者的多轮交互。例如在许多介绍零知识证明的科普文章当中都会使用的“零知识洞穴”的故事当中,证明的实现就依赖于阿里巴巴(证明者)和记者(验证者)多轮的信息传递交互才能实现。但是事实上,在许多应用场景当中,依赖交互会使得系统不再可用,或者极高的增加延迟。就像在zkRollup系统当中,我们期望证明者(也就是FOX当中的folder)能够在本地,不依赖于和验证者交互的情况下就计算出正确的证明值。

从这个角度说,如何将交互式的零知识证明协议改造为非交互式,就是一个很有意义的问题。在这篇文章当中,我们将介绍FOX使用经典的Fiat-Shamir启发式(heuristic)来生成Brakedown中的挑战从而实现非交互式协议的过程。

零知识证明中的Challenge

零知识证明算法随着应用的铺开而变得异常火爆,近些年也诞生了包括FOAKS、Orion、zk-stark等在内的各种算法。这些算法,以及密码学界早期的sigma协议等的核心证明逻辑都是证明者(Prover)先将某个值发送给验证者(Verifier),验证者通过本地随机数产生一个挑战(Challenge),将这个随机产生的挑战值发给证明者,证明者需要真的有知识才能以大概率做出通过验证者的响应。例如在零知识洞穴当中,记者抛一个硬币,告诉阿里巴巴从左侧出来还是从右侧出来,这里的“左和右”就是对阿里巴巴的挑战,他如果真的知道咒语,就一定可以从要求的方向走出来,否则就有一半的概率失败。

这里我们注意到,Challenge的生成是一个很关键的步骤,它有两个要求,随机和不可被证明者预测。第一点,随机性保证了它的概率属性。第二点,如果证明者可以预测挑战值那就意味着协议的安全性被破坏了,证明者没有知识也可以通过验证,可以继续类比,阿里巴巴如果能预测记者要求他从哪边出来,他即使没有咒语也可以提前进入那一边,结果表现出来一样可以通过协议。

所以我们需要一种办法,能够让证明者自己本地生成这样一个不可预测的随机数,同时还能够被验证者验证,这样就可以实现非交互式的协议。

哈希函数(Hash Function)

哈希函数的名字对我们来说或许并不陌生,无论是在比特币的共识协议POW当中担任挖矿的数学难题,还是压缩数据量,构造消息验证码等等,都有哈希函数的身影。而在上述不同的协议当中,其实是运用了哈希函数的各种不同性质。

具体来讲,安全的哈希函数的性质包括以下几点:

  1. 压缩性:确定的哈希函数可以将任意长度的消息压缩成为固定长度。
  1. 有效性:给定输入x,计算输出h(x)是容易的。
  1. 抗碰撞性:给定一个输入x1,希望找到另一个输入x2,x1x2,h(x1)= h(x2),是困难的。

注意,如果哈希函数满足抗碰撞性,那么必然满足单向性,也就是说给定一个输出y,要找出x满足h(x)= y是困难的。在密码学当中,还不能构造出理论上绝对满足单向性的函数,但是哈希函数在实际应用当中可以基本视作单向函数。

这样一来,可以发现上述的几种应用分别对应于哈希函数的几点不同的性质,同时我们说,哈希函数还有一个很重要的作用是提供随机性,虽然密码学理论当中要求的完美的随机数生成器目前也无法构造,但是哈希函数在实际当中同样可以充当这个角色,这就为我们后文介绍的Fiat-Shamir 启发式(Heuristic)的技巧提供了基础。

Fiat-Shamir启发式(Heuristic)

事实上,Fiat-Shamir 启发式(Heuristic)就是利用哈希函数来对前面生成的脚本进行哈希运算,从而得到一个值,用这个值来充当挑战值。

因为将哈希函数H视作一个随机函数,挑战是均匀随机的被选择,独立于证明者的公开信息和承诺的。安全分析认为Alice不能预测H的输出,只能将其当作一个oracle。在这种情况下,Alice在不遵循协议的情况下做出正确响应的概率(特别是当她不知道必要的秘密时)与H的值域的大小成反比。

图1: 利用Fiat-Shamir Heuristic实现非交互式证明

非交互式FOAKS

在本节,我们具体展示Fiat-Shamir启发式在FOAKS协议当中的应用,主要是用来产生Brakedown部分的挑战,从而实现非交互式的FOAKS。

首先我们看到,在Brakedown生成证明的步骤当中,需要挑战的步骤是“近似性检验”以及Merkle Tree的证明部分(读者可以参考之前的文章《一文了解FOAKS当中的多项式承诺协议Brakedown》)。对于第一点原本的过程是证明者在这里需要验证者产生的一个随机向量,计算过程如下图所示:

图2: 非交互证明FOAKS中的Brakedown Checks

现在我们使用哈希函数,让证明者自己产生这个随机向量。

令0=H(C1,R, r0,r1),对应的,在验证者的验证计算当中,也需要增加这个计算出0的步骤。根据这样的构造,可以发现,在生成承诺之前,证明者并不能提前预测挑战值,于是不能提前根据挑战值来对应的“作弊”,也就是对应的生成假的承诺值,同时,根据哈希函数输出的随机性,这个挑战值也满足随机性。

对于第二点,令I=H(C1,R, r0,r1,c1,y1,c0,y0)。

我们使用伪代码给出改造后非交互式的Brakedown多项式承诺当中的证明和验证函数,这也是FOAKS系统当中使用的函数。

  1. function PC. Commit():
  2. Parse w as a kk matrix. The prover locally computes the tensor code encoding C1,C2 ,C1 is a kn matrix,C2 is a nn matrix.
  3. for i [n] do
  4. Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i])
  5. Compute a Merkle tree root R=Merkle.Commit([Root0,......Rootn-1]),and output R as the commitment.
  6. function PC. Prover(, X, R)
  7. The prover generates a random vector 0Fk by computing: 0=H(C1,R, r0,r1)
  8. Proximity: c0=i=0k-10[i]C1[:,i],y0=i=0k-10[i]w[i]
  9. Consistency: c1=i=0k-1r0[i]C1[:,i],y1=i=0k-1r0[i]w[i]
  10. Prover sends c1,y1,c0,y0 to the verifier.
  11. Prover computes a vector I as challenge, in which I=H(C1,R, r0,r1,c1,y1,c0,y0)
  12. for idxI do
  13. Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier
  14. function PC. VERIFY_EVAL(X,X,y=(X),R)
  15. Proximity: idxI,C0[idx]==<0,C1[:,idx]>and EC(y0)==C0
  16. Consistency: idxI,C1[idx]==<r0,C1[:,idx]>and EC(y1)==C1
  17. y==<r1, y1>
  18. idxI, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.
  19. Output accept if all conditions above holds. Otherwise output reject.

结语

许多的零知识证明算法在设计之初都依赖证明者和验证者双方的交互,但是这种交互式证明协议不适合用在追求高效,网络通讯开销大的应用场景下,比如链上数据隐私保护和zkRollup等等。通过Fiat-Shamir启发式(Heuristic),可以在不破坏协议安全性的条件下让证明者本地生成随机数“挑战”,并且可以被证明者验证。根据这种方法,FOAKS同样实现了非交互式的证明,并应用在系统当中。

评论

所有评论

推荐阅读

  • IPO在即,灰度创始人Barry Silbert回归出任董事会主席

    Grayscale Investments 在提交保密 IPO 申请后,宣布四项高管任命并迎回创始人 Barry Silbert 担任董事会主席。新任命的高管包括:首席运营官 Diana Zhang、首席营销官拉蒙娜·波士顿 Ramona Boston、首席传讯官 Andrea Williams、首席人力资源官 Maxwell Rosenthal。四位高管都将向灰度首席执行官 Peter Mintzberg 汇报,他们均来自传统金融巨头,包括桥水基金、阿波罗全球管理、高盛和城堡投资。 Barry Silbert 于 2013 年创立灰度,于 2023 年底辞去灰度董事长一职,此次将接替 Mark Shifke 担任董事会主席,Shifke 将继续留任董事会,目前董事会成员已增至五人。公司表示正在考虑增加独立董事。 Barry Silbert 表示:「我很荣幸能够在公司乃至更广泛的数字资产生态系统的关键时刻重新加入灰度董事会。我始终坚信公司的长期定位以及引领公司前进的领导团队。」

  • SharpLink Gaming增持18,680枚以太坊,总持有498,884枚

    据链上分析师 Onchain Lens 监测,SharpLink Gaming(股票代码:SBET)今日再次增持18,680枚以太坊,价值约6,663万美元。此次增持后,该公司以太坊储备总量达到498,884枚,总价值约18亿美元。

  • Bullish向美国证交会提交IPO申请,拟募资6.29亿美元

    数字资产交易所Bullish及其子公司CoinDesk已向美国证券交易委员会(SEC)提交首次公开募股(IPO)申请。根据申请文件,Bullish计划发行2030万股,发行价区间为28-31美元/股,最高募资金额为6.29亿美元,对应公司估值约42亿美元。 Bullish业务范围包括数字资产现货交易、杠杆交易和衍生品交易,同时为稳定币发行机构提供流动性服务。财务数据显示,该公司2025年第一季度数字资产销售额达8020万美元,净亏损3.49亿美元。Bullish曾于2023年以7260万美元收购加密货币媒体平台CoinDesk。

  • 欧盟将对美国的贸易反制措施暂停6个月

    市场消息:欧盟将对美国的贸易反制措施暂停6个月

  • 去中心化操作系统 OpenMind 完成 2000 万美元融资,Pantera Capital 领投

    智能机器去中心化操作系统 OpenMind 宣布完成 2000 万美元融资,Pantera Capital 领投,Coinbase Ventures、Digital Currency Group 和 Ribbit 等参投。 据悉,这家初创公司正在开发一款名为 FABRIC 的“硬件无关”操作系统,旨在支持“智能机器融入日常生活”。该协议为支持人工智能的机器人提供了一种通信和协调的方式。

  • 加强个人境外收入监管 境外买卖股票收入也要缴税

    《金融时报》刊文,据了解,近期有纳税人收到了税务部门通知,告知其需要依法办理境外所得申报并缴纳相应税款。“根据我国个人所得税法,个人股票交易所得属于财产转让所得,应当适用20%的税率按次征收。其中,个人在境内二级市场的股票交易所得暂免征收个人所得税;在境外直接进行股票交易所得没有免税规定,需要在取得所得的次年申报纳税。”吉林财经大学税务学院院长张巍解释说。为了更加合理的征收,我国税务部门在征管时,允许纳税人按照纳税年度盈亏相抵,但不允许跨年互抵。依法纳税是每个公民应尽的义务。个人未申报或者未如实申报境外所得,除了会被税务机关要求补缴税款外,还会被加收滞纳金,情形严重的还可能被稽查部门立案检查,将面临税务处罚。纳税人如果发现自己此前申报个税时,存在少报、漏报境外所得的,要及时补正。

  • 美国SEC文件显示特斯拉批准向马斯克授予9600万股股票奖励

    美国SEC文件显示:特斯拉(TSLA.O)批准向马斯克授予9600万股股票奖励,马斯克将按每股23.34美元的价格购买已获授股票。

  • Binance Alpha:持有至少 200 币安 Alpha 积分的用户可申领 1000 个 DARK 代币空投

    据官方公告,Binance Alpha 是首个上线 DarkStar(DARK)的平台,Alpha 交易将于 2025 年 8 月 4 日 20:00(UTC+8)开始。 交易开始后,持有至少 200 个币安 Alpha 积分的用户可申领 1000 个 DARK 代币空投。先到先得。若活动未结束,则分数门槛将每小时自动降低 15 分。 请注意,申领空投将消耗 15 个币安 Alpha 积分。用户需在 Alpha 活动页面于 24 小时内确认申领,否则视为放弃领取空投。

  • 香港《稳定币条例》正式生效:储备资产须全额覆盖流通面值

    8月1日,香港《稳定币条例》正式生效,建立起稳定币发行人牌照制度,完善香港对虚拟资产活动的监管框架。大湾区国际资讯科技协会会长杨德斌表示,如今国际上稳定币的发展已经达到一定规模。香港在这个时点推出《稳定币条例》,是在监管方面与时俱进的体现。与国际标准接轨,中国香港在制定稳定币相关规定时也力求与全球其他国家和地区的标准接轨。根据香港《稳定币条例》,持牌人必须确保其发行的指定稳定币的储备资产的市值,始终不低于该类稳定币尚未赎回且流通中的面值。持牌人应考虑储备资产的风险状况,确保有适当的超额抵押以覆盖市场风险。

  • 亲兵与诸侯,Puffer UniFi (Based Rollup) 与主流 Rollup

    Based Rollup 与主流 Rollup 将形成不同的以太坊生态格局。