Cointime

扫码下载App
iOS & Android

深度解析FOAKS当中的多项式承诺协议Brakedown

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

在许多依赖多项式承诺的零知识证明系统当中,使用了不同的承诺协议。根据 a16z 的 Justin Thaler 在 2022 年 8 月文章「Measuring SNARK performance: Frontends, backends, and the future」的评估,Brakedown 虽然有较大的 Proof Size,但是无疑是当下最快的多项式承诺协议。

FRI、KZG、Bulletproof 是更为常见的多项式承诺协议,但速度是它们的瓶颈。zkSync 采用的 Plonky、Polygon zkEVM 采用的 Plonky2、Scroll 采用的 Ultra-Plonk 等算法都是基于 KZG 的多项式承诺。Prover 涉及到大量的 FFT 计算和 MSM 运算生成多项式和承诺,这两者都会带来大量的计算负担。 虽然 MSM 有运行多线程加速的潜力,但需要大量内存,即使在高并行下也很慢,而大型 FFT 则严重依赖算法运行时数据的频繁洗牌,难以通过分布式加速跨计算集群加载。

正是由于有了更为快速的多项式承诺协议 Brakedown,才使这类运算的复杂度大幅降低。

FOAKS 即 Fast Objective Argument of Knowledges,是由 Fox Tech 提出的一种基于 Brakedown 的零知识证明系统框架。FOAKS 在 Orion 的基础上进一步减少 FFT 运算,目标是最终消除 FFT。此外,FOAKS 还设计出一种全新的非常精妙的证明递归方式来减少证明大小。FOAKS 框架的优势在于在实现线性证明时间的基础上有着较小的证明大小,非常适合应用于 zkRollup 场景当中。

下文我们将详细介绍 FOAKS 所使用的多项式承诺协议 Brakedown。

在密码学当中,承诺(Commitment)协议由证明者(Prover)对某一个秘密值进行承诺,生成一个公开的承诺值,这个承诺值具有绑定性(Binding)和隐藏性(Hiding),之后提交者需要打开此承诺并将消息发送到验证者,以验证承诺与消息之间的对应关系。这一点,使得承诺协议和哈希函数的作用有许多共通之处,但是承诺协议往往依赖于公钥密码学领域的数学结构。而多项式承诺(Polynomial Commitment)是一类对于多项式的承诺方案,也就是说被承诺值是多项式。而同时多项式承诺协议当中还包含了在给定的点取值并给出证明的算法,这就使得多项式承诺协议本身成为一类重要的密码学协议,是许多零知识证明系统的核心部分。

而在最新的密码学领域的研究当中,由于发现了张量积(Tensor Product)和多项式取值之间的联系,所以诞生了一系列与此相关的多项式承诺协议,Brakedown 是其中的代表性协议。

在详细介绍 Brakedown 的协议细节之前,需要先了解一些基础知识。我们需要先了解线性码(Linear Code)、抗碰撞哈希函数(Hash Function)、默克尔树(Merkle Tree)、张量积(Tensor Product)的运算以及多项式取值的张量积表示。

首先是线性码(Linear Code)。一个消息长度为 k,码字长度为 n 的线性码是一个线性子空间

C∈Fn,使得存在一个从消息到码字的单射,称为编码,记作 EC:Fk→C。任意的对于码字的线性组合仍然是一个码字。两个码字 u,v 的距离即他们的汉明距离,记作△(u,v)。

最短距离为 d=minu,v△(u,v)。这样的码记作[n,k,d]线性码,用 d /n 表示码的相对距离。

其次是抗碰撞哈希函数(Hash Function)与默克尔树(Merkle Tree)。

使用 H:{0,1}2λ→{0,1}λ表示一个哈希函数。默克尔树是一种特殊的数据结构,可以实现对于 2d个消息的承诺,生成一个哈希值 h,在打开任何消息时候需要 d+1 个哈希值。

默克尔树可以被表示为一个深度为 d 的二叉树,其中 L 个消息元素 m1,m2,...,ml分别对应树的叶子。树的每一个内部节点都由它的两个子节点进行哈希计算得出。打开消息 mi时,需要公开从 mi到根节点的路径。

用以下记号来表示:

  1. h←Merkle.Commit(m1,...,ml)
  2. (mi,πi)←Merkle.Open(m,i)
  3. {0,1}←Merkle.Verify(πi,mi,h)

图 1:默克尔树(Merkle Tree)

我们还需要了解张量积(Tensor Product)的运算是怎么做的。数学上,张量是向量和矩阵向高维空间的扩展,是很重要的研究对象,详细的讨论张量超出本文的研究范畴,这里只介绍向量和矩阵的张量积运算。

图 2:向量和矩阵的张量积运算

紧接着,我们需要知道多项式取值的张量积表示。

[GLS+]当中提到,多项式的取值可以被表示成张量积的形式。在这里我们考虑多线性多项式的承诺。

具体来讲,给定一个多项式,他在向量 x0,x1,...,xlogN-1的取值可以写成:

根据多线性的定义,每一个变量的次数是 0 或 1,因此,这里有 N 个单项式和系数,以及 logN 个变量。令

,其中 i0i1...ilogN-1是 i 的二进制表示。令 w 表示多项式系数,

。同样的,定义

于是有 X=r0⊗r1。

从而,多项式取值可以被表示成张量积的形式:ϕ(x0,x1,...,xlogN-1)=

最后,我们来看 FOAKS、Orion[XZS22]当中使用的 Brakedown 的过程。

首先,PC.Commit 将多项式系数 w 划分成 k×k 的矩阵形式,并将其编码(参考「预备知识」中的线性码),记作 C2。之后对于 C2的每一列 C2[:,i]进行承诺建立一个默克尔树,然后再对于每一个列形成的默克尔树树根建立另一个默克尔树,作为最终的承诺。

在取值证明的计算中,需要证明两点,一是近似性(Proximity),二是一致性(Consistency)。近似性保证了承诺的矩阵确实和编码后的一个码字足够接近。一致性保证 y=

近似性检验:近似性检验由两步组成。首先,验证者发送一个随机向量 0 给证明者,证明者计算 Y0与 C1的内积,也就是以 Y0的分量为系数对 C1的行计算线性组合。由于线性码的性质,Cy0是 Yy0的码字。之后,证明者证明 Cy0确实是从被承诺的码字计算出的。为了证明这一点,验证者随机选取 t 列,证明者打开对应的列并提供默克尔树证明。验证者检查这些列和 Y0的内积和 Cy0当中对应位置相等。[BCG20]当中证明如果使用的线性码有常数的相对距离,那么被承诺的矩阵就以压倒性的概率与一个码字接近(压倒性的概率是指,命题的否命题成立的概率是可忽略的)。

一致性检验:一致性检验和近似性检验的流程完全类似。不同之处在于,不使用随机向量 Y0而是直接使用 r0来完成线性组合的部分。类似的,c1也是消息 y1的一个线性码,并且有

ϕ(x)=。[BCG20]当中证明,通过一致性检验,如果被承诺的矩阵与一个码字接近,则以压倒性概率成立 y=ϕ(x)。

以伪代码形式,我们给出 Brakedown 协议的流程:

Public input:The evaluation point X,parsed as a tensor product X=r0⊗r1;

Private input:The polynomial ϕ ,the coefficient of is denoted by w.

Let C be the [n,k,d]-limear code,EC:FkFn be the encoding function,N=k×k. If N is not a perfect square,we can pad it to the next perfect square. We use a python style notationmat[:,i] to select the i-th column of a matrix mat。

  1. function PC. Commit(ϕ):
  2. Parse w as a k×k matrix. The prover locally computes the tensor code encoding C1,C2 ,C1 is a k×n matrix,C2 is a n×n 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 receives a random vector Y0∈Fk from the verifier
  8. Proximity
  9. Consistency
  10. Prover sends C1,y1,C0,y0 to the verifier.
  11. Verifier randomly samples t[n] as an array Î and send it to prover
  12. for idx∈Î 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: ∀idx∈Î,CY0[idx]==and EC(Yy0)==CY0
  16. Consistency:∀idx∈Î,C1[idx]==and EC(Y1)==C1
  17. y==
  18. ∀idx∈Î, 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.

结语:多项式承诺是一类非常重要的密码学协议,被广泛的应用在许多密码学系统当中,尤其是零知识证明系统。本文详细介绍了多项式承诺 Brakedown 协议以及和其相关的数学知识,作为 FOAKS 很重要的底层组件,Brakedown 对 FOAKS 的实例化性能的提升起到了重要作用。

参考文献

[GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r1cs. Cryptology ePrint Archive. https://ia.cr/2021/1043.

[XZS22]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology–

CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010

[BCG20]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part II 18. Springer International Publishing, 2020.

Justin Thaler from A16zcrypto, Measuring SNARK performance: Frontends, backends, and the future

https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

张量积的介绍:https://blog.csdn.net/chenxy_bwave/article/details/127288938

评论

所有评论

推荐阅读

  • 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美元的价格购买已获授股票。

  • 区块链扩展的下一个前沿:深入探索ZK Rollups

    · 虽然零知识证明(ZKPs)有望打造一个更加私密和可扩展的区块链生态系统,但许多关于零知识(ZK)的方面被误解或与普遍认知中的实施方式不同。 · ZKPs 主要有两个方面:「零知识」和「简洁性」。虽然这种说法没有错,但大多数 ZK rollups 只利用了简洁性属性,交易数据和账户信息并没有完全保持零知识或私密。 · 对于各种类型的 DApps,ZK rollups 可能不是最佳的开发堆栈选择。例如,生成 ZKPs 可能成为快速终结的瓶颈,从而降低 Web3 游戏的性能,而基于状态差异发布的数据可用性保证方法可能会损害 DeFi 借贷协议的服务。

  • 专注于零知识证明的区块链Gevulot完成600万美元种子轮融资,Variant领投

    专注于零知识证明的区块链Gevulot完成600万美元种子轮融资,Variant领投,RockawayX、Volt Capital 和 Stake Facilities 以及 Polygon Labs 首席执行官 Marc Boiron 和 Manta Network 创始人 Shumo Chu 等个人支持者参与。 Gevulot 没有透露其估值。 Gevulot 计划将资金分配给其L1区块链的推出,该区块链使开发人员能够利用ZK 证明并将计算任务委托给先进的硬件运营商网络。

  • 中科大首次实现以器件无关量子随机数产生器,消除非交互式零知识证明安全隐患

    中国科学技术大学潘建伟院士等研究者首次实现一套以器件无关量子随机数产生器作为熵源,以后量子密码作为身份认证的随机数信标公共服务,将其应用到零知识证明领域中,消除了非交互式零知识证明中实现真随机数的困难所带来的安全隐患,提高了非交互式零知识证明的安全性。非交互式零知识证明广泛应用于数字签名、区块链和身份认证等领域,由于真随机数生成器难以实现,通常会使用确定性的伪随机数算法来替代。 据了解,此次研究工作首次将量子非局域性、量子安全算法和零知识证明3个不同的领域结合起来,大幅提升了零知识证明的安全性,其中构建的面向公众的随机数服务在密码学、彩票业和社会公益等领域有着重要的应用潜力。