Cointime

扫码下载App
iOS & Android

Round 3-5 原理与代码讲解

项目方

由 EthStorage 特别赞助,Antalpha Labs 与 706 Creators 联合举办的 ZKP 零知识证明共学正顺利开展,大家踊跃讨论,互相帮助,积极主动分享—— 本篇文章就是由热心共学小伙伴 keep 带来关于 python 实现 PLONK 协议的讲解。

在 PLONK 协议中,Round 1 ~ 2 分别是对算术约束和复制约束的承诺,相对容易理解;在 Round 3 ~ 5 中,则主要是把门约束和门之间的一致性约束组合到一起,形成一个超大的多项式承诺。

1. 点值形式多项式的加法和乘法

有两个函数 f(x), g(x) ,  其系数形式如下:

其点值形式表示如下:

1.1 多项式加法

采用系数形式相加,容易得到 $f(x)+g(x)= 2x^2+1$。

采用点值形式相加,将相同 x 坐标对应的 y 值相加,得到:

不难看出,采用点值表示的多项式相加只要 将相同 x 坐标对应的 y 值相加即可,且结果与系数形式等价。

1.2 多项式乘法

采用系数形式相乘, 容易得到 $f(x)* g(x)= x^4+x^2$。

采用点值形式相乘,将相同 x 坐标对应的 y 值相乘,得到:

不难看出,采用点值表示的多项式相乘只要 将相同 x 坐标对应的 y 值相乘即可,且结果与系数形式等价。

2. Round3 Coset Operation

fft_extend/to_coset_extended_lagrange 的作用

  1. 将多项式的点值形式先转换为系数形式
  2. 再在系数形式后面补上 3* order 个 0,产生的多项式如下,然后再将系数多项式经过 fft 变成点值形式返回:
def to_coset_extended_lagrange(self, offset):        assert self.basis == Basis.LAGRANGE        group_order = len(self.values)        x_powers = self.ifft().values  # step1: 将多项式的点值形式通过 ifft 转换成系数形式 (f(x) = a_0+ a_1*x + a_2*x^2 + a_3*x^3 + ...+a_[order-1]*x^(order-1)        x_powers = [(offset**i * x) for i, x in enumerate(x_powers)] + [Scalar(0)] * (            group_order * 3        ) # step2: 将多项式表示为 f'(x) = a_0 + a_1*(offset *x) + a_2*(offsset*x)^2 + a_3*(offsset*x)^3 + ... +a_[order-1] * (offset *x)^(order-1) + 0*x^(order) +....+ 0*x^(4*order-1)        return Polynomial(x_powers, Basis.MONOMIAL).fft()  # 返回的结果用点值形式表示

对于

的多项式,假设 offset=1,扩展后的多项式满足

。简单的理解,就是将横坐标

映射到

def coset_extended_lagrange_test():    lagrange_poly = Polynomial(        # TODO(keep), 采用点值法表示,w =19540430494807482326159819597004422086093766032135589407132600596362845576832, 多项式点的坐标分别为 (w^0,1),(w^1,2),(w^2,3),....(w^7,8)        list(map(Scalar, [1, 2, 3, 4, 5, 6, 7, 8])), Basis.LAGRANGE         )    #原始多项式的点值表示:[1, 2, 3, 4, 5, 6, 7, 8]    print(f"original lagrange poly:{lagrange_poly.values}")    #原始多项式的系数表示:[10944121435919637611123202872628637544274182200208017171849102093287904247813, 16407567355707715082381689537916387329395994555403796510305004205827931381005, 21888242871839275220042445260109153167277707414472061641729655619866599103259, 16407567355707715086789610508212631171937308527291741914242101339246350165720, 10944121435919637611123202872628637544274182200208017171849102093287904247808, 5480675516131560135456795237044643916611055873124292429456102847329458329896, 2203960485148121921270656985943972701968548566709209392357, 5480675516131560139864716207340887759152369845012237833393199980747877114611]    print(f"original coeff poly:{lagrange_poly.ifft().values}")    #offset=1, 4 倍扩展后的多项式的点值表示,注意在 1/4/8/..的位置上值分别为 1/2/3... :[1, 10720100502214316017824502944044954065324060999235831025903844423091840349399, 9455244345631016631523862383826656817909262240618707851288319855253023724499, 2154739387933033111708037291544134707206872172371185076448386251812704236397, 2, 16557012320615716805371654510058109663243542056334255754346494402848129196434, 10961351032263120273117550959237409754492768732192557560880754261368126052155, 18363557546045068101357792595864568178482043948267994234220586583038506555553, 3, 6786126665617168635281695348901695604305505508243066572076512701156119512476, 12432998526208258595130464331726862113180416131685271896346981464741203555842, 17583891563112296716989958068669721717716064856305856073868243673723776631415, 4, 15235092695697612903221424418341788996225933052563558331936298540020231085964, 8526477789819225339470181130720054257555649678225561659213114114555273578202, 5748412396315429947679827564037304002141735973269128964907214524925412184424, 5, 8063712871896466710084708497040886506504371635794542014797783122244927830807, 12432998526208258595130464331726862113180416131685271896346981464741203555842, 6384725622872180445960462185068028976157210952995327774999033041321834967027, 6, 7423125919204651450688116196486815080908642277508115891487414498838949167610, 10961351032263120273117550959237409754492768732192557560880754261368126052155, 9959267747632339428749389803973233433288807182891237168523575569690515042210, 7, 1013927586174909651228671251775444917323622993703484604051271120508846640523, 9455244345631016631523862383826656817909262240618707851288319855253023724499, 12991963608384419706057798792240747034085871118455836070949939695446237712242, 8, 21753872925936258715284849814379405520357779078281283180193197937594190199291, 13327305889333084549971686500727188725472913714445501098547591469023253739310, 14366413615062333430482356679631362305114851397107572010875837406344246653236]    lagrange_coset_poly= lagrange_poly.to_coset_extended_lagrange(Scalar(1))    print(f"lagrange_coset_poly, offset=1:{lagrange_coset_poly.values}")    #offset=3, 4倍扩展后的多项式的点值表示,:[20675515612179202962216070186424682162618199731614332091699429061672282694725, 12176233492423905554052088791734959941094267405154917767703273057334496166085, 5917415089377289121590408955785178409647352913589873293489444488775637989917, 2752516302388842277837843623414582965521620079164918619152523122629779608930, 4169562684247585045898683445974163076520306259872602444382940816087435294801, 405974129629722533167980246725276196790448647122578773059926554710976033469, 16015793353021219580113202927438566307249046400631465629394870428808273269385, 10229243472545473685325496616621056338434159122035619201636505490363604037700, 4169562684247576371110213902966280955214409584396047496175782248639266976338, 5253968865549839538799666481628166409324748755474067887542850034795390306731, 5448982845895345419151791205795466600592293409442070602404591982746410109803, 6744796520889898167112801401869255476407161332739834968662727069566758151892, 1212727259660075433733434172128159555676224428122393086708711186165050793241, 322967646151623184877638486520441134119498412968113624552408193959018243483, 18024183386365665400514884144185330956959959158139700997404651630096754818232, 19482052846986908588806741073994758113640633859705256434234817575288965077623, 1212727259660075433733434172128159555676224428122393086708711186165050794882, 15659316895809636090874968052002070000216252850695980391535423378600348077893, 18315716487236118541742198333943662698829243458507744564312431379090458965882, 10510595262562575074793025571744230189431857025973620441791605645111860961441, 17718680187591687002644623685987545382281998381222741064605327309226848205368, 20159325449435371029217238441388109380740194409091738508163099259089186272494, 18587891620308261463443330180410826574514602508103652153546608225475836828557, 394344664035779568888350307535643007895240871168234908270745822756040235999, 17718680187591695677433093228995427503587895056699296012812485876675016525145, 18932442747777939648604146512737863718784200643866598521373172345132630858224, 14094371321169798076091610182981744959720702465139535664999676136322953049480, 18314296007598656137037071170514820954670799413013319519063761129019823716627, 20675515612179202962216070186424682162618199731614332091699429061672282698004, 14642742260579063309391895968292213573123846477290141900862663922681188024125, 13036860255822678508584602795745598935228621688526128812938746661562717446865, 19125126410348967389184293215334753308191985897863333281980130891566402192292]    lagrange_coset_poly= lagrange_poly.to_coset_extended_lagrange(Scalar(3))    print(f"lagrange_coset_poly, offset =3 :{lagrange_coset_poly.values}")    #offset =3, 消除4倍扩展后,多项式的系数表示,前8项系数不为0,剩余部分的系数均为0:[10944121435919637611123202872628637544274182200208017171849102093287904247813, 16407567355707715082381689537916387329395994555403796510305004205827931381005, 21888242871839275220042445260109153167277707414472061641729655619866599103259, 16407567355707715086789610508212631171937308527291741914242101339246350165720, 10944121435919637611123202872628637544274182200208017171849102093287904247808, 5480675516131560135456795237044643916611055873124292429456102847329458329896, 2203960485148121921270656985943972701968548566709209392357, 5480675516131560139864716207340887759152369845012237833393199980747877114611, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]    # 前8项系数与原始多项式的系数相同。    coeff_coset_poly1 = lagrange_coset_poly.coset_extended_lagrange_to_coeffs(Scalar(3))    print(f"coeff_coset_poly, offset =3:{coeff_coset_poly1.values}")

3. Round3 扩展 ZH(x)

如果 offset =1,ZH 扩展后的多项式在

处的值都是 0,考虑到 ZH(x) 是计算商多项式的分母 ( 见下图 ), 为了使 ZH(x) 不为 0,因此取 offset != 1,可以简单的理解为取横坐标=

4. Round5 计算 r(x)

5. Round5 计算 q(x)

评论

所有评论

推荐阅读

  • USDC Treasury新增铸造3.16亿枚USDC

    过去 3 小时内,USDC Treasury 新增铸造 316,765,680 枚 USDC。

  • 8月5日隔夜重要动态一览

    21:00-7:00关键词:OpenMind、欧盟、降息

  • The ETF Store总裁:白宫正在准备一项行政命令,旨在惩罚歧视加密货币公司的银行

    The ETF Store总裁Nate Geraci在X平台发文表示,白宫正在准备一项行政命令,旨在惩罚那些歧视加密货币公司的银行。

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

  • Web3数据和AI公司Validation Cloud完成1000万美元新一轮融资

    Web3数据和AI公司Validation Cloud宣布从True Global Ventures获得1000万美元融资,该公司计划利用这笔资金扩展其AI产品,实现对Web3数据的无缝访问。 据介绍,该公司的产品平台由三个部分组成:质押、节点API以及数据和AI。在质押方面,Validation Cloud的质押资产已超过10亿美元。Validation Cloud的一些客户包括 Chainlink、Aptos、Consensys、Stellar和Hedera。