原文作者：FoxTechCEO康水跃，FoxTech首席科学家孟铉济
前言：如果密码学家没有发现张量积和多项式取值之间的联系，那就很难出现多项式承诺协议Brakedown，也就不可能诞生基于Brakedown的Orion、以及FOAKS这类全新的快速算法。
在许多依赖多项式承诺的零知识证明系统当中，使用了不同的承诺协议。根据a16z的JustinThaler在2022年8月文章“MeasuringSNARKperformance:Frontends,backends,andthefuture”的评估，Brakedown虽然有较大的ProofSize，但是无疑是当下最快的多项式承诺协议。
FRI、KZG、Bulletproof是更为常见的多项式承诺协议，但速度是它们的瓶颈。zkSync采用的Plonky、PolygonzkEVM采用的Plonky2、Scroll采用的Ultra-Plonk等算法都是基于KZG的多项式承诺。Prover涉及到大量的FFT计算和MSM运算生成多项式和承诺，这两者都会带来大量的计算负担。虽然MSM有运行多线程加速的潜力，但需要大量内存，即使在高并行下也很慢，而大型FFT则严重依赖算法运行时数据的频繁洗牌，难以通过分布式加速跨计算集群加载。
正是由于有了更为快速的多项式承诺协议Brakedown，才使这类运算的复杂度大幅降低。
FOAKS即FastObjectiveArgumentofKnowledges，是由FoxTech提出的一种基于Brakedown的零知识证明系统框架。FOAKS在Orion的基础上进一步减少FFT运算，目标是最终消除FFT。此外，FOAKS还设计出一种全新的非常精妙的证明递归方式来减少证明大小。FOAKS框架的优势在于在实现线性证明时间的基础上有着较小的证明大小，非常适合应用于zkRollup场景当中。
奇虎360公开“基于联盟区块链的标识解析方法”专利:8月30日消息，北京奇虎科技有限公司、中国信息通信研究院日前联合公开一种“基于联盟区块链的标识解析方法、装置、存储介质及服务器”专利，申请日期为2021年4月29日，申请公布号：CN113315811A。天眼查App显示，该专利属于计算机技术领域。方法包括在第一对外节点接收到标识解析请求的情况下，从第一对外节点对应的本地数据库中查询是否存在与标识解析请求中的标识符对应的IPFS哈希值。
若未查询到IPFS哈希值，则基于标识解析请求向联盟区块链中除第一对外节点之外的其他节点发送第一查询请求；接收由联盟区块链中响应于第一查询请求的节点发送的IPFS哈希值，并基于IPFS哈希值通过第一对外节点访问IPFS服务，以获取IPFS哈希值对应的标识解析信息由此可有效提高对标识解析过程的安全性，保证通过标识解析得到的数据不易被篡改。（邮箱网）[2021/8/30 22:45:51]
下文我们将详细介绍FOAKS所使用的多项式承诺协议Brakedown。
在密码学当中，承诺协议由证明者对某一个秘密值进行承诺，生成一个公开的承诺值，这个承诺值具有绑定性和隐藏性，之后提交者需要打开此承诺并将消息发送到验证者，以验证承诺与消息之间的对应关系。这一点，使得承诺协议和哈希函数的作用有许多共通之处，但是承诺协议往往依赖于公钥密码学领域的数学结构。而多项式承诺是一类对于多项式的承诺方案，也就是说被承诺值是多项式。而同时多项式承诺协议当中还包含了在给定的点取值并给出证明的算法，这就使得多项式承诺协议本身成为一类重要的密码学协议，是许多零知识证明系统的核心部分。
而在最新的密码学领域的研究当中，由于发现了张量积和多项式取值之间的联系，所以诞生了一系列与此相关的多项式承诺协议，Brakedown是其中的代表性协议。
Etherscan现支持以太坊域名服务ENS反向解析:5月12日消息，以太坊域名服务（Ethereum Name Service，简称ENS）发推称，Etherscan目前支持ENS反向解析。ENS反向解析可使用户的ENS域名成为跨DApp的以太坊账户的便携式用户名。除Etherscan外，使用此功能的其他DApp包括Uniswap、Opensea、Aavegotchi和Snapshot Labs等。目前，要使用该服务，用户必须手动启用反向解决，之后将更改为自动启动；DApp须在其UI代码中使用PR。
注：正向解析（Forward resolution，FR）是将一个ENS域名解析到以太坊地址等资源，反向解析（Reverse resolution，RR）是指将一个以太坊地址解析到一个ENS域名。[2021/5/12 21:52:40]
在详细介绍Brakedown的协议细节之前，需要先了解一些基础知识。我们需要先了解线性码、抗碰撞哈希函数、默克尔树、张量积的运算以及多项式取值的张量积表示。
首先是线性码。一个消息长度为k，码字长度为n的线性码是一个线性子空间
C∈Fn，使得存在一个从消息到码字的单射，称为编码，记作EC：Fk→C。任意的对于码字的线性组合仍然是一个码字。两个码字u，v的距离即他们的汉明距离，记作△(u,v)。
最短距离为d=minu,v△(u,v)。这样的码记作线性码，用d/n表示码的相对距离。
其次是抗碰撞哈希函数与默克尔树。
使用H:{0,1}2λ→{0,1}λ表示一个哈希函数。默克尔树是一种特殊的数据结构，可以实现对于2d个消息的承诺，生成一个哈希值h，在打开任何消息时候需要d+1个哈希值。
浪潮集团王伟兵：标识解析、标识密码、区块链是构建工业区块链三个技术要素:金色财经现场报道，12月5日，2020世界区块链大会于武汉举办，会上浪潮集团区块链技术研究院首席架构师王伟兵演讲表示，消费互联网是实现人和人的连接的，工业互联网从技术上看更偏重物，工业互联网数量多，管理难度大，面向物的标识解析和密码学适合应用。标识解析的本质是提供名称映射的分布式数据库，构建工业区块链的三个技术要素是标识解析、标识密码、区块链。标识解析需要目录服务、数据共享，标识密码主要做设备身份认证、设备写入链，区块链则增强安全，完成可信交易。[2020/12/5 14:06:24]
默克尔树可以被表示为一个深度为d的二叉树，其中L个消息元素m1,m2,...,ml分别对应树的叶子。树的每一个内部节点都由它的两个子节点进行哈希计算得出。打开消息mi时，需要公开从mi到根节点的路径。
用以下记号来表示：
h←Merkle.Commit(m1,...,ml)
(mi,πi)←Merkle.Open(m,i)
{0,1}←Merkle.Verify(πi,mi,h)
图1：默克尔树
我们还需要了解张量积的运算是怎么做的。数学上，张量是向量和矩阵向高维空间的扩展，是很重要的研究对象，详细的讨论张量超出本文的研究范畴，这里只介绍向量和矩阵的张量积运算。
动态 | 以太坊域名服务ENS将加入多代币支持，未来可解析至比特币地址:go-ethereum和以太坊域名服务（ENS）核心开发者Nick Johnson今天在Twitter 宣布，已经提交了ENS以太坊域名的多代币支持，该提议通过后ENS以太坊域名将支持解析域名到多个区块链地址，其中甚至可以包括比特币地址。这也意味着，ENS以太坊域名将可能成为跨链的域名系统，用户可以通过一个域名在多个区块链间互通，未来只需要向其他人展示自己的ENS以太坊域名即可。目前已经有多个数字加密货币钱包支持ENS以太坊域名，在使用以太坊钱包进行转账时，不需要再输入冗长的以太坊0x 地址，而只需要输入短地址即可。[2019/9/9]
图2：向量和矩阵的张量积运算
紧接着，我们需要知道多项式取值的张量积表示。
当中提到，多项式的取值可以被表示成张量积的形式。在这里我们考虑多线性多项式的承诺。
具体来讲，给定一个多项式，他在向量x0,x1,...,xlogN-1的取值可以写成：
根据多线性的定义，每一个变量的次数是0或1，因此，这里有N个单项式和系数，以及logN个变量。令
，其中i0i1...ilogN-1是i的二进制表示。令w表示多项式系数，
分析 | USDT听证会解析:瑞海君看币观点：一、预计听证会围绕的主题有如下两个：
1.Bitfinex和Tether不顾美国法律和监管，为纽约州居民提供了相关服务。
2.Bitfinex和Tether之前在美国的业务，触犯了美国的反法（这个才是对USDT具有巨大杀伤力的议题）。
二、?今晚可能达成的几种结果：
1.BFX和Tether违规为美国居民提供服务罪名成立，会导致两家共识会继续被调查，且会被美国要求提供更多的运营资料，的事情没结果，但是也要提交更多资料自正清白，这是利空！会导致USDT这个雷持续悬在整个币圈的头上，然后美国来一条新闻，币圈震动一次，简直就是噩梦。（概率中性）
行情影响：短暂反弹，然后继续震荡阴跌。
2.两项罪名都没结果，短暂利好，BFX继续和美国扯皮，大家松一口气暂时?，价格可能出现反弹。（可能性较大）
行情影响：短暂反弹，后市宽幅震荡为主。
3.两项罪名都成立，不可想像（可能性较小）！
行情影响：区块链局。
罪名直接成立可能性也较小，调查没那么快，所以请大家系好安全带，等待靴子落地，两只靴子到底如何落地，落地几支，只有静候今晚的听证会了。[2019/7/29]
同样的，定义
令
。于是有X=r0?r1。
从而，多项式取值可以被表示成张量积的形式：?(x0,x1,...,xlogN-1)=<w,r0?r1>。
最后，我们来看FOAKS、Orion当中使用的Brakedown的过程。
首先，PC.Commit将多项式系数w划分成k×k的矩阵形式，并将其编码，记作C2。之后对于C2的每一列C2进行承诺建立一个默克尔树，然后再对于每一个列形成的默克尔树树根建立另一个默克尔树，作为最终的承诺。
在取值证明的计算中，需要证明两点，一是近似性，二是一致性。近似性保证了承诺的矩阵确实和编码后的一个码字足够接近。一致性保证y=<w,r0?r1>。
近似性检验：近似性检验由两步组成。首先，验证者发送一个随机向量0给证明者，证明者计算Y0与C1的内积，也就是以Y0的分量为系数对C1的行计算线性组合。由于线性码的性质，Cy0是Yy0的码字。之后，证明者证明Cy0确实是从被承诺的码字计算出的。为了证明这一点，验证者随机选取t列，证明者打开对应的列并提供默克尔树证明。验证者检查这些列和Y0的内积和Cy0当中对应位置相等。当中证明如果使用的线性码有常数的相对距离，那么被承诺的矩阵就以压倒性的概率与一个码字接近。
一致性检验：一致性检验和近似性检验的流程完全类似。不同之处在于，不使用随机向量Y0而是直接使用r0来完成线性组合的部分。类似的，c1也是消息y1的一个线性码，并且有
?(x)=<y1,r1>。当中证明，通过一致性检验，如果被承诺的矩阵与一个码字接近，则以压倒性概率成立y=?(x)。
以伪代码形式，我们给出Brakedown协议的流程：
Publicinput：TheevaluationpointX，parsedasatensorproductX=r0?r1;
Privateinput：Thepolynomial?，thecoefficientofisdenotedbyw.
LetCbethe-limearcode，EC：FkFnbetheencodingfunction，N=k×k.IfNisnotaperfectsquare，wecanpadittothenextperfectsquare.Weuseapythonstylenotationmattoselectthei-thcolumnofamatrixmat。
functionPC.Commit(?)：
Parsewasak×kmatrix.TheproverlocallycomputesthetensorcodeencodingC1，C2，C1isak×nmatrix，C2isan×nmatrix.
fori∈do
ComputetheMerkletreerootRoott=Merkle.Commit(C2)
ComputeaMerkletreerootR=Merkle.Commit(),andoutputRasthecommitment.
functionPC.Prover(?,X,R)
TheproverreceivesarandomvectorY0∈Fkfromtheverifier
Proximity
Consistency
ProversendsC1,y1,C0,y0totheverifier.
Verifierrandomlysamplestasanarray?andsendittoprover
foridx∈?do
ProversendsC1andtheMerkletreeproofofRootidxforC2underRtoverifier
functionPC.VERIFY_EVAL(πX,X,y=?(X),R)
Proximity:?idx∈?,CY0==<Y0,C1>andEC(Yy0)==CY0
Consistency:?idx∈?,C1==<Y0,C1>andEC(Y1)==C1
y==<r1,y1>
?idx∈?,EC(C1)isconsistentwithROOTidx,andROOTidx’sMerkletreeproofisvalid.
Outputacceptifallconditionsaboveholds.Otherwiseoutputreject.
结语：多项式承诺是一类非常重要的密码学协议，被广泛的应用在许多密码学系统当中，尤其是零知识证明系统。本文详细介绍了多项式承诺Brakedown协议以及和其相关的数学知识，作为FOAKS很重要的底层组件，Brakedown对FOAKS的实例化性能的提升起到了重要作用。
参考文献
:AlexanderGolovnev,JonathanLee,SrinathSetty,JustinThaler,andRiadS.Wahby.Brakedown:Linear-timeandpost-quantumsnarksforr1cs.CryptologyePrintArchive.https://ia.cr/2021/1043.
:XieT,ZhangY,SongD.Orion:Zeroknowledgeproofwithlinearprovertime//AdvancesinCryptology–CRYPTO2022:42ndAnnualInternationalCryptologyConference,CRYPTO2022,SantaBarbara,CA,USA,August15–18,2022,Proceedings,PartIV.Cham:SpringerNatureSwitzerland,2022:299-328.https://eprint.iacr.org/2022/1010
:Bootle,Jonathan,AlessandroChiesa,andJensGroth."Linear-timeargumentswithsublinearverificationfromtensorcodes."TheoryofCryptography:18thInternationalConference,TCC2020,Durham,NC,USA,November16–19,2020,Proceedings,PartII18.SpringerInternationalPublishing,2020.
JustinThalerfromA16zcrypto,MeasuringSNARKperformance:Frontends,backends,andthefuturehttps://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/
张量积的介绍：https://blog.csdn.net/chenxy_bwave/article/details/127288938
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。