这篇文章适用于具有一定密码学背景的人。它调查了不断扩展的证明系统密码学以及对称STARK在其中的作用。基于2019年11月在旧金山发表的演讲。
1.简介
35亿年来，地球上的生命都是由单细胞生物组成的。然后，在地质学上的一眨眼之间，在所谓的寒武纪大爆发期间，几乎所有我们今天认识的动物门类都出现了。
通过类比，我们目前正在经历计算完整性(CI)加密证明领域的寒武纪大爆发，其中一个子集包括零知识证明。几年前，每年大约有1-3个新系统，而现在这个速度已经加快了很多，如果不是每周，我们每个月都能看到同样的数量。到目前为止，在2019年，我们已经了解了Libra,Sonic,SuperSonic,PLONK,SLONK,Halo,Marlin,Fractal,Spartan,SuccinctAurora等新结构，以及OpenZKP,Hodor和GenSTARK等实现。哦，当墨水在这篇文章上干燥时，RedShift和AirAssembly出现了。
如何理解所有这些了不起的创新?这篇文章的目的是找出所有用代码实现的CI系统的共同点，并讨论一些区别因素。
请注意，本文将有点技术性，因为它假定有一些密码学背景!然而，对于感兴趣的非密码学家来说，这可能值得略读一下，以了解该领域使用的术语。尽管如此，我们的描述将是简短的，并且从数学的角度来看故意不精确。这篇文章的另一个主要目的是解释为什么我们公司StarkWare将其所有的科学、工程和产品芯片放在CI-verse的一个特定子家族上，从此称为对称STARKs。
共同的祖先
计算完整性证明系统可以帮助解决困扰去中心化区块链的两个基本问题:隐私和可扩展性。零知识证明(ZKPs1)通过屏蔽计算的某些输入而不损害完整性来提供隐私。简洁可验证的CI系统通过指数级压缩验证大量事务完整性所需的计算量来提供可伸缩性。
所有用代码实现的CI系统都有两个共同点:都使用所谓的算术化，并且所有加密都强制执行称为“低程度遵从性”(LDC)2的概念。
Cardano创始人：2022年下半年将实现端到端小额信贷交易:12月26日消息，Cardano创始人、IOHK联合创始人兼首席执行官Charles Hoskinson在平安夜发布的YouTube视频中，谈到了如何在2022年下半年在Cardano上实现端到端小额信贷交易。“我在2022年下半年的目标是想出如何将所有的部分整合在一起，在Cardano上实现端到端的小额信贷交易。所以一个真实的人在肯尼亚或者某个地方，拥有区块链身份和信用评分，交易的另一边则是稳定币，Cardano是结算轨道。点对点，人对人，点击一个按钮，贷款就给他们了。他们把钱还回去，钱就会到另一边去。”（Cryptoglobe）[2021/12/26 8:04:40]
算术化是对证明算法所做的计算陈述的简化。你可以从这样一个概念性的陈述开始:
“我知道允许我进行加密Zcash交易的密钥”
并将其转化为包含一组有界多项式的代数语句，如:
“我知道四个多项式A(X)，B(X)，C(X)，D(X)，每一个都小于1000度，因此这个等式成立:A(X)*B2(X)-C(X)=(X1??-1)*D(X)”
低次遵从意味着使用密码学来确保证明者实际上选择了低次多项式3，并在验证者请求的随机选择的点上评估这些多项式。在上面的例子中(我们将在这篇文章中继续提到)，一个好的最不发达国家解决方案向我们保证，当证明者被问及x0时，它将回答a0,b0,c0,d0，这些值是输入x0时a,b,c和d的正确值。棘手的部分是，证明者可能在看到查询x0后选择a,B,C和D，或者可能决定用任意的a0,B0,C0,D0来安抚验证者，并且不对应于预先选择的低次多项式的任何评估。所以，所有的加密技术都是为了防止这种攻击媒介。(要求证明者发送完整的A、B、C和D的平凡解决方案既不能提供可伸缩性，也不能提供隐私。)
考虑到这一点，CI-verse可以根据(i)用于强制LDC的加密原语，(ii)使用这些原语构建的特定LDC解决方案以及(iii)这些选择允许的算法类型来绘制。
2.比较维度
i.密码学假设
从30000英尺的角度来看，不同CI系统之间最大的理论区别因素是它们的安全性是需要对称基元还是不对称基元(参见图1)。典型的对称基元是SHA2、Keccak(SHA3)或Blake，我们假设它们是抗碰撞哈希(CRH)函数、伪随机函数，其行为就像随机的oracle。非对称假设包括求解以素数、RSA模数或椭圆曲线群为模的离散对数问题的难度，计算RSA环的乘法群的大小的难度，以及此类问题的更奇特的变体，如“指数知识”假设，“自适应根”假设等。
Cardano创始人：随着PAB上线，Cardano将面临巨大流量:11月1日消息，Cardano创始人Charles Hoskinson在AMA中介绍了9月12日上线的新ERC-20 Cardano转换器桥。该桥发布时，将迁移到Cardano的首个代币是SingularityNET。Hoskinson表示，“大量工作正在进行中，我们将继续向Hydra添加资源，我们一直在努力确定一些团队，以便我们能够加速、并行工作流程，因为这是一个高度的商业优先事项。”这将是一次至关重要的升级，因为“它将能够卸载（offload）即将推出的所有应用程序的大量交易流量。随着PAB的上线，Cardano将会受到巨大流量的冲击。Hydra是一种必需品。”（AMBCrypto）[2021/11/1 6:24:20]
图1:密码学假设家谱
CI系统之间的这种对称/不对称划分有许多后果，其中包括:
A.计算效率
今天在代码中实现的非对称原语的安全性需要在大型代数域上进行算术运算并解决LDC问题:大型素域和它们上面的大型椭圆曲线，其中每个域/组元素都是数百位长，或者整数环，其中每个元素都是数千位长。相比之下，仅依赖对称假设的构造在任何代数域(环或有限域)上进行算术运算并执行LDC，这些代数域包含光滑的5子群，包括非常小的二进制域和2-光滑素域(64位或更少)，其中算术运算很快。
结论:对称CI系统可以在任何领域进行算术运算，从而提高效率。
B.后量子安全
如果有足够大的量子计算机(以量子位为单位)出现，那么目前在ci领域中使用的所有不对称原语都将被有效地打破。另一方面，对称原语似乎是后量子安全的(可能每比特安全性具有更大的种子和状态)。
结论:只有对称系统才是后量子安全的。
图2:加密假设及其支持的经济价值
Cardano创始人：非洲可能是DeFi发展的未来:12月13日消息，Cardano创始人、IOHK首席执行官Charles Hoskinson透露，该公司的长期发展重点将放在非洲，并称非洲可能是去中心化金融（DeFi）发展的未来。(Cointelegraph)[2020/12/13 15:02:25]
C.能否经得住时间的考验
林迪效应理论认为，“一些不易腐烂的东西，比如技术或想法，未来的预期寿命与它们当前的年龄成正比。”或者用简单的英语来说，旧的东西比新的东西存活的时间更长。在密码学领域，这可以被翻译为说依赖于旧的、经过战斗测试的原语的系统比那些经过较少考验的新假设更安全，更经得起未来的考验(见图2)。从这个角度来看，不对称假设的新变体，如未知顺序的组，一般的群体模型和指数假设的知识是年轻的，并且比旧的假设(如用于数字签名，基于身份的加密和SSH初始化的更标准的DLP和RSA假设)更轻的经济车。这些假设不如对称假设(如抗碰撞哈希的存在)具有前瞻性，因为后者的假设(甚至是特定的哈希函数)是用于保护计算机、网络、互联网和电子商务的基础。
此外，这些假设之间有严格的数学层次关系。CRH假设在这个层次结构中占主导地位，因为如果这个假设被打破(意味着没有找到安全的加密哈希函数)，那么RSA和DLP假设也会被打破，因为这些假设意味着存在一个好的CRH!同样，DLP假设支配着指数知识(KoE)假设，因为如果前者(DLP)假设不成立，那么后者(KoE)也不成立。同样，RSA假设优于未知顺序组(GoUO)假设，因为如果RSA被破坏，那么GoUO也会被破坏。
结论:新的不对称假设是金融基础设施风险更高的基础。
D.参数长度
以上所有观点都倾向于对称CI结构而非对称CI结构。但在一个领域，不对称结构表现得更好。与之相关的沟通复杂性(或参数长度)要小1-3个数量级(尽管有尼尔森定律6)。众所周知，Groth16SNARK在估计的128位安全级别上小于200字节，而目前存在的所有对称结构都需要数十千字节才能达到相同的安全级别。应该注意的是，并非所有的非对称结构都像200字节那样简洁。最近的结构改进了Groth16，通过(i)消除了对可信设置(透明度)的需要和/或(ii)处理一般电路(Groth16每个电路需要一个可信设置)。但是这些较新的结构具有更长的参数，其大小在半千字节(PLONK的情况就是如此)到两位数的千字节之间，接近对称结构的参数长度。
结论:非对称电路专用系统(Groth16)最短，比所有非对称通用系统和所有对称系统都短。
重申上述要点:
对称CI系统可以对任何领域进行算术运算，从而提高效率
只有对称系统才是后量子安全的
新的不对称假设为金融基础设施奠定了一个风险更高的基础
非对称电路专用系统(Groth16)最短，比所有非对称通用系统和所有对称系统都短
ii.低程度合规计划
实现低程度遵从性有两种主要方法:(i)隐藏查询和(ii)承诺方案(参见图3)。让我们来看看它们之间的区别。
图3:隐藏查询和承诺方案
隐藏查询
这种方法(在这里形式化)是Zcash风格的snark(如Pinocchio,libSNARK,Groth16)以及基于它们的系统(如Zcash的Sapling，以太坊的Zokrates等)所使用的方法。为了让证明者正确回答，我们使用同态加密来隐藏或加密x0，并提供足够的信息，以便证明者可以计算x0上的A,B,C和D。实际上，给证明者的是x0的幂的加密序列(即x01，x02，…x01??)，因此证明者可以计算任何1000次多项式，但只能计算最多1000次的多项式。粗略地说，这个系统是安全的，因为证明者不知道x0是什么，这个x0是随机(预先)选择的，所以如果证明者试图作弊，那么他们很有可能会被暴露。这里需要一个可信的预处理设置阶段来对x0进行采样并加密上述幂次序列(以及其他信息)，从而产生一个至少与被证明的计算电路一样大的证明密钥(也有一个短得多的验证密钥)。一旦设置完成，密钥被释放，每个证明都是一个单一的、简洁的、非交互式的知识论证(简称SNARK)。请注意，这个系统确实需要某种形式的交互，以预处理阶段的形式，这是不可避免的理论原因。还要注意的是，该系统并不透明，这意味着用于采样和加密x0的熵不能仅仅是公共随机硬币，因为任何知道x0的人都可以破坏该系统并证明错误。因此，在不泄露x0的情况下生成x0及其功率的加密是一个构成潜在单点故障的安全问题。
承诺方案
这种方法要求证明者通过向验证者发送一些加密的承诺消息来提交一组低次多项式(A、B、C和D，在上面的例子中)。有了这个承诺，验证者现在采样并询问证明者随机选择的x0，现在证明者回复a0,b0,c0和d0以及额外的加密信息，这些信息使验证者相信证明者透露的四个值符合早先发送给验证者的承诺。这些方案是自然交互的，其中许多是透明的(验证者生成的所有消息都是公共随机硬币)。透明度允许人们通过Fiat-Shamir启发式(将伪随机函数(如SHA2/3)视为提供“公共”随机性的随机oracle)将协议压缩为非交互式协议，或者使用其他公共随机性来源，如块头。最流行的透明承诺方案是通过Merkle树，这种方法似乎是后量子安全的，但会导致许多对称系统中出现的大参数长度(由于需要显示所有身份验证路径并伴随每个证明者答案)。这是大多数STARK使用的方法，如libSTARK和简洁的Aurora，以及简洁的证明系统，如ZKBoo,Ligero,Aurora和Fractal(即使这些系统不满足STARK的正式可扩展性定义)。特别是，我们在StarkWare上构建的STARKs(就像我们即将部署的StarkDEXalpha和StarkExchange)属于这一类。人们可以使用不对称原语来构建承诺方案，例如，基于椭圆曲线群上离散对数问题的硬度的方案(这是BulletProofs和Halo采用的方法)，以及未知阶假设的组(如DARK和SuperSonic所做的)。使用不对称承诺方案有前面提到的优点和缺点:较短的证明但较长的计算时间、量子敏感性、较新的(和较少研究的)假设，以及在某些情况下，透明度的丧失。
iii.算术化
加密假设和LDC方法的选择也会以三种明显的方式影响算术可能性的范围(参见图4):
图4:算术化效果
A.NP(电路)vs.NEXP(程序)
大多数实现的CI系统将计算问题简化为算术电路，然后将其转换为一组约束(通常是R1CS约束，下面将讨论)。这种方法允许特定电路的优化，但要求验证者或受其信任的某些实体执行与被验证的计算(电路)一样大的计算。对于像Zcash的树苗电路这样的多用途电路，这种算法就足够了。但是，像libSTARK、简洁的Aurora和StarkWare正在构建的系统这样的可扩展和透明(不受信任的设置)的系统，必须使用简洁的计算表示，类似于一般的计算机程序，其描述比正在验证的计算要小得多。实现这一目标的两种现有方法是:(i)libSTARK、genSTARK和StarkWare系统使用的代数中间表示(AIRs)，以及(ii)简洁R1CS的简洁aurora，最好被描述为通用计算机程序的算术运算(与电路相反)。这些简洁的表示足以捕获非确定性指数时间(NEXP)的复杂性类，它比电路描述的非确定性多项式时间(NP)类更具指数性和强大。
B.字母的大小和类型
如上所述，所使用的密码学假设也在很大程度上决定了哪些代数域可以作为我们进行算术运算的字母表。例如，如果我们使用双线性配对，那么我们将用于算术化的字母表是椭圆曲线点的一个循环群，这个群必须是大素数，这意味着我们需要在这个域上进行算术化。再举一个例子，超音速系统(在它的一个版本中)使用RSA整数，在这种情况下，字母表将是一个大的素数字段。相比之下，当使用Merkle树时，字母表的大小可以是任意的，允许在任何有限的域上进行算术运算。这包括上面的例子，也包括任意素数域，小素数域的扩展，如二进制域。字段类型很重要，因为较小的字段会导致更快的证明和验证时间。
C.R1CS与一般多项式约束
zcash风格的snark利用椭圆曲线上的双线性对来对计算约束进行算法化。这种双线性对的特殊使用?将算法限制在二次秩-1约束系统(R1CS)的门上。R1CS的简单性和普遍性使得许多其他系统在电路中使用这种形式的算法，即使可以使用更一般形式的约束，如任意秩二次型，或更高程度的约束。
3.STARKvs.SNARK
这是一个很好的机会来澄清stark和SNARKs之间的区别。这两个术语都有具体的数学定义，某些结构可以实例化为stark或snark，或两者兼而有之。不同的术语强调证明系统的不同性质。让我们更详细地检查一下(参见图5)。
图5:STARKvs.SNARK
STARK
这里的S代表可扩展性，这意味着随着批大小n的增加，在n中准线性证明时间尺度，同时在n中多对数?验证时间尺度。STARK中的T代表透明度，这意味着所有验证者消息都是公共随机币(没有可信设置)。根据这个定义，如果有任何预处理设置，那么它必须是简洁的(多对数的)，并且必须仅包含对公共随机硬币的采样。
SNARK
这里的S代表简洁，这意味着验证时间尺度在n上是多对数的(不要求准线性证明时间)，n意味着非交互，这意味着在预处理阶段(可能是不透明的)之后，证明系统不能允许任何进一步的交互。请注意，根据这个定义，允许非简洁的可信设置阶段，一般来说，系统不必是透明的，但它必须是非交互式的(在完成预处理阶段之后，这是不可避免的)。
看看CI-verse(见图5)，人们注意到它的一些成员是STARKs，其他成员是SNARKs，有些是两者都是，而另一些则两者都不是(例如，如果验证时间尺度比n的多对数更差)。如果你对隐私(ZKP)应用感兴趣，那么ZK-SNARKs和ZK-STARKs甚至既没有STARK的可扩展性也没有SNARK的简便性(较弱)的系统都可以很好地服务;门罗币使用的防弹技术就是一个值得注意的例子，其验证时间与电路尺寸呈线性关系。当谈到代码成熟度时，snark有一个优势，因为有相当多好的开源库可供构建。但是，如果您对可伸缩性应用程序感兴趣(您需要为不断增长的批处理大小构建)，那么我们建议使用对称stark，因为在编写时，它们具有最快的证明时间，并且保证验证过程(或设置系统)的任何部分都不需要超过多对数的处理时间。如果你想构建具有最小信任假设的系统，那么，再一次，你想使用对称的STARK，因为需要的唯一成分是一些CRH和公共随机性的来源。
4.总结
图6:总结
我们有幸经历了计算完整性证明系统宇宙的寒武纪大爆发，所有的注都是系统和创新的扩散将以越来越快的速度继续下去。此外，随着明天出现新的见解和结构，这种描述扩展和变化的CI-verse的尝试可能会过时。话虽如此，调查今天的ci空间，我们看到的最大的分水岭是(i)需要非对称加密假设的系统-这导致更短的证明，但证明成本更高，有更新的假设，这些假设是量子敏感的，其中许多是不透明的;(ii)系统只依赖于对称假设，使它们在计算上高效，透明，似乎是后量子安全的，而且是最未来的证明(根据林迪效应度量)。
关于使用哪种论证体系的争论远未结束。但在StarkWare，我们说:对于简短的参数，使用Groth16/PLONKSNARKs。其他的都是对称的STARKs。
伊莱·本·萨森，StarkWare公司
特别感谢JustinDrake对早期草稿的评论。
Billions项目组
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。