正文

寒武纪密码学证明大爆发，数十个零知识证明系统该如何选？

洒脱喜2020-01-09 10:22:21

写在前面：原文作者Eli Ben-Sasson教授是StarkWare公司的联合创始人兼首席科学家，在这篇文章中，他概述了近20个零知识证明系统，并给出了他对这些证明系统的看法，这篇文章也被Zcash创始人Zooko、《精通比特币》作者Andreas M. Antonopoulos等人强烈推荐。

图虫创意-238338601599107110 （图片来自：tuchong.com）

注：文章最初发表在nakamoto.com，内容较适合拥有密码学背景的人阅读，以下为译文:

一、介绍

35亿年之前，地球上的生命还都是原始单细胞生物。然后，在经历被称为寒武纪生命大爆发的时期中，我们今天认识的几乎所有动物种系都出现了。

通过类比，我们目前在计算完整性的密码学证明（CI）领域也经历了“寒武纪爆炸”，其中一个子集就包括零知识证明。几年之前，一年的时间里大约会出现1-3个新的零知识证明系统，而现在已发展到每个月（甚至有时会是周为单位）就能看到近似数量新系统的出现。在2019年，我们了解到的新零知识证明机构，例如有 Libra 、 Sonic 、 SuperSonic 、 PLONK 、 SLONK 、 Halo 、 Marlin 、 Fractal 、 Spartan 、简洁Aurora ，以及 OpenZKP 、 Hodor 和 GenSTARK 等实现。哦，好吧，在差不多写完这篇文章的时候， RedShift 以及 AirAssembly 也已经出现。

如何理解这些奇妙的创新呢？这篇文章的目的是确定代码中实现的所有CI系统的共同点，并讨论一些不同的因素。

请注意，这篇文章将有些技术性，因为它假设读者掌握了一些密码学背景！不过，对于感兴趣的非密码学读者来说，它可能也是值得粗略一览的，你可以凭此了解该领域所使用的一些行话。

尽管如此，我们的描述将是简短的，并且故意避开数学方面的东西。这篇文章的另一个主要目的，是解释为什么我们StarkWare公司会把科学、工程学及产品方面的所有核心都放到CI领域的一个特定子家族上，从此之后，我们会称之为 对称STARKs（symmetric STARKs） 。

共同的祖先

计算完整性证明系统，有助于解决困扰去中心化区块链的两大基本问题：隐私及 可扩展性 。零知识证明（ZKP） ^[1] 通过屏蔽计算的某些输入而不损害完整性来提供隐私。而简洁可验证CI系统，通过指数级压缩验证大批量交易完整性所需的计算量，以此提供可扩展性。

所有在代码中实现的CI系统，都具有两个共同点：它们都使用被称为 Arithmetization 的东西，并且所有的密码都强制使用一个称为“低阶顺应性”（LDC） ^[2] 的概念。

Arithmetization是指通过证明算法来减少计算语句。你可以从这样的概念性陈述开始：

“I know the keys that allow me to spend a shielded Zcash transaction”（我知道允许我花费一笔屏蔽Zcash交易的密钥）

然后将它转换为包含一组有界次多项式的代数陈述，如：

““I know four polynomials A(X), B(X), C(X), D(X), each of degree less than 1,000, such that this equality holds: A(X)*B²(X)-C(X) = (X¹⁰⁰⁰–1)*D(X)”” （我知道四个多项式A（X），B（X），C（X），D（X），它们每个阶数都小于1000，所以这个等式成立：A(X)*B²(X)-C(X) = (X¹⁰⁰⁰–1)*D(X)）

低阶顺应性（LDC）是指使用密码学来确保prover实际选择低阶多项式 ^[3] ，并在verifier请求的随机选择点上评估这些多项式。在上面的例子中（本文会持续提及），一个好的LDC解决方案向我们保证，当询问有关x₀的问题时，它将使用a₀、b₀、c₀、d₀的值来回答输入x₀上的A、B、C和D的正确值。棘手的部分是，prover可能在看到查询x₀后选择A、B、C和D，或者可能决定用任意的a₀、B₀、C₀、D₀来回答，而它们会安抚verifier，并且与预先选择的低阶多项式的任何求值都不对应。所以，所有的密码学都是为了防止这种攻击向量。（需要prover发送完整A、B、C和D的简单解决方案，既不提供可扩展性，也不提供隐私性。）

有鉴于此，CI宇宙可根据以下三种方式绘制出来：（i）用于强制LDC的密码学原语，（ii）用这些原语构建的特定LDC解决方案以及（iii）这些选择所允许的Arithmetization。

二、比较维度（Dimensions of Comparison）

2、1 密码学假设

从30000英尺的高空来看，不同CI系统之间最大的理论区别因素，就在于它们的安全性需要 对称密码学原语 还是 非对称密码学原语 （见图1）。典型的对称原语有SHA2、Keccak（SHA3）或Blake，我们假设它们是抗碰撞哈希（CRH）函数，它们是伪随机的，行为类似于随机预言机。非对称假设包括求解模素数、RSA模或椭圆曲线群的离散对数问题的困难性（hardness），RSA ring乘法群大小的计算困难，以及类似于“指数知识”假设，“自适应根”假设这样的奇异变体问题。

图1：密码学假设家族树

CI系统之间的这种对称/不对称划分，会带来很多结果，其中包括：

A. 计算效率

今天在代码 ^[4] 中实现的非对称密码学原语的安全性，要求在大型代数域上对LDC问题进行运算与求解：大型素数域和它们上面的大型椭圆曲线，其中每个域/组元素都有数百（bit）位长，或整数环中每个元素都有数千（bit）位长。

相比之下，仅依赖对称假设的构造对包含smooth ^[5] 子组的任何代数域（环域或有限域）进行算术运算并执行LDC，包括非常小的二进制域和2个smooth素数域（64位或更少），其中算术运算速度是很快的。

结论：对称CI系统可以对任何字段进行算术运算，从而提高效率 。

B. 后量子安全性

当一台具有足够大状态（以量子位测量）的量子计算机出现时，当前在CI-verse中使用的所有非对称密码学原语将被有效地破坏。另一方面，对称密码学原语似乎是后量子安全的。

结论：只有对称系统才是合理的后量子安全系统 。

图2：密码学假设及由它们支撑的经济价值

C. 经得起考验

Lindy效应理论提出：

“一些不易腐烂的东西，比如一项技术或一个想法，其未来预期寿命与其当前年龄成正比。”

或者用通俗的话来说，旧东西要比新东西存活的时间要更长。在密码学领域，这可以被翻译成这样一种说法，即依赖于较老的、经实战测试的原语系统，要比那些轮胎被踢得较少的较新假设要更安全，也更容易存活下来（见图2）。从这个角度来看，非对称密码学假设的新变体，如未知阶群、一般群模型和指数假设的知识，要比较旧的假设（如用于数字签名、基于身份的加密和SSH初始化的更标准的DLP和RSA假设）更年轻。这些假设，相较于对称假设（如存在抗碰撞的哈希算法）要更经不起未来的考验，因为后一种假设（甚至是特定的哈希函数）是用来保护计算机、网络、互联网和电子商务而存在的。

此外，这些假设之间有严格的数学层次。CRH假设在这个层次中是主宰的，因为如果这个假设被破坏（意味着没有安全的密码哈希函数被发现），那么，特别是RSA和DLP假设也会被破坏，这些假设的前提是存在一个好的CRH!

同样，DLP假设支配着指数知识（KoE）假设，因为如果前者（DLP）假设不能成立，那么后者（KoE）也不能成立。类似地，RSA假设支配着未知阶群（GoUO）假设，因为如果RSA被破坏，那么GoUO也会被破坏。

结论：新的不对称密码学假设，对于金融基础设施而言，会是具有更高风险的基础 ；

D. 论证长度

以上各点都有利于对称CI结构而不是非对称CI结构。但在一个方面，非对称结构会表现得更好。与之相关联的通信复杂性（或论证长度）会小1-3个数量级（尼尔森定律 ^[6] ）。知名的是， Groth16 SNARK在128位安全级别的估计level上小于200字节，而今天存在的所有对称结构需要几十KB才能有相同的安全级别。需要注意的是，并不是所有的非对称结构都会有200字节那么简洁。Groth16 结构通过（i）消除了对可信设置的需求（透明性）和（ii）处理通用电路（Groth16要求每个电路有一个可信设置）已经得到了改进。但这些较新的结构有更长的参数，其大小在半KB（如PLONK）到两位数KB之间，接近对称结构的论证长度。

结论：非对称电路专用系统（Groth16）最短，它要比所有非对称通用系统和所有对称系统都要短 。

然后重申下上面的要点：

对称CI系统可以对任何字段进行算术运算，从而提高效率；
只有对称系统才是合理的后量子安全系统；
新的不对称假设，对于金融基础设施而言，会是具有更高风险的基础；
非对称电路专用系统（Groth16）最短，它要比所有非对称通用系统和所有对称系统都要短。

2、2 低阶顺应性（LDC）方案

实现低阶顺应性的主要方法有两种：（i）隐藏查询，（ii）承诺方案（见图3）。让我们来讨论一下差异。

图3: 隐藏查询& 承诺方案

隐藏查询（Hiding Queries）

这种方法是Zcash式SNARKs，如Pinocchio、libSNARK、Groth16和建立在它们之上的系统，例如Zcash的Sapling，以太坊的Zokrates等所使用的方法。为了让prover正确回答，我们使用同态加密隐藏或加密x₀，并提供足够的信息，以便prover能够在x₀上计算A、B、C和D。

实际上，给 prover的是一个x₀幂的加密序列（即，x₀¹ , x₀², … x₀¹⁰⁰⁰的加密），这样prover就可以计算任意阶-1000多项式，但最多只能计算1000阶多项式。粗略地说，系统是安全的，因为prover不知道x₀是什么，而这个x₀是随机（预先）选择的，因此如果prover试图欺骗，那么它们很有可能会暴露出来。这里需要一个可信的预处理设置阶段来采样x₀，并加密上面的幂序列（以及附加信息），从而得到至少与被证明的计算电路一样大的证明密钥（还有一个更短的验证密钥）。一旦设置完成并释放了密钥，每个证明都是一个单一的、简洁的、非交互的知识论证（简称SNARK）。请注意，这个系统确实需要某种形式的交互，以预处理阶段的形式，因为理论上的原因这是不可避免的。还请注意，该系统是不透明的，这意味着用于对x₀进行采样和加密的熵，不能仅仅是公开的随机coin，因为任何知道x₀的一方，都可以破坏该系统并证明其错误性。因此，在不暴露x₀的情况下生成x₀及其幂的加密，是构成潜在单点故障的一个安全问题。

承诺方案（Commitment Scheme）

这种方法要求prover通过向verifier发送一些加密构造的承诺消息来提交一组低阶多项式（在上面的示例中是A、B、C和D）。有了这个承诺，verifier现在对随机选择的x₀取样并询问prover，现在prover 用a₀、b₀、c₀和d₀，以及使verifier确信由prover揭示的四个值符合先前发送给verifier的承诺的附加密码信息来回答。

这种方案是自然交互的，而且许多方案都是透明的（verifier生成的所有消息都只是公开的随机coin）。透明性允许人们通过Fiat-Shamir启发式（它将SHA 2/3这样的伪随机函数视为提供“公共”随机性的随机预言机）将协议压缩为非交互式协议，或者使用其他随机性公共源（如区块头）。最流行的透明承诺方案是通过Merkle树，这种方法看似是后量子安全的，但会导致在许多对称系统中出现较大的论证长度（因为所有认证路径都需要被揭示并附上每个prover的答案）。这是大多数STARK（如libSTARK和简洁Aurora）以及简洁证明系统（如ZKBoo、Ligero、Aurora和Fractal）使用的方法（即使这些系统不满足STARK的正式可扩展性定义）。

特别是，我们在StarkWare建造的STARKs（比如我们即将部署的StarkDEX alpha版本和StarkExchange）就属于这一类。人们也可以使用非对称密码学原语来构造承诺方案，例如基于椭圆曲线组上离散对数问题的难度（这是BulletProof和Halo所采用的方法）以及未知阶假设组（如DARK和SuperSonic采用的）。使用非对称承诺方案具有前面提到的优点和缺点：证明较短，但计算时间较长，易受量子计算影响，具有较新（且较少研究）的假设，以及在某些情况下会有透明度的损失。

2、3 Arithmetization

密码学假设和LDC方法的选择，也以三种明显的方式影响arithmetization可能性的范围（见图4）：

图4:Arithmetization效应

A. NP (电路）vs. NEXP（程序）

大多数已实现的CI系统将计算问题简化为算术电路，然后将其转换为一组约束（一般是下面我们将讨论的R1CS约束）。此方法允许特定于电路的优化，但要求verifier或其信任的某个实体执行与正在验证的计算（电路）一样大的计算。对于Zcash的Sapling电路这样的多用途电路来说，这种算法就足够了。但是，像libSTARK、简洁Aurora和StarkWare正在构建的可扩展且透明（没有可信设置）的系统而言，必须要使用简洁的计算表示，这种表示类似于一般的计算机程序，并且其描述要比被验证的计算要小指数级。现有的两种实现：（i）libSTARK、genSTARK以及StaskWS系统所使用代数中间表示（AIR）方法，以及（ii）简洁Aurora的简洁R1CS，最好被描述为通用计算机程序（与电路相反）的arithmetization。这些简洁表示足以捕捉非确定性指数时间（NEXP）的复杂类，它比由电路描述的非确定性多项式时间（NP）类更具有指数表现力，也更强大。

B. Alphabet大小和类型

如上所述，所使用的密码学假设在很大程度上也决定了哪些代数域可用作我们进行算术运算的alphabet。例如，如果我们使用双线性配对，那么我们将用于arithmetization的alphabet是一个椭圆曲线点的循环组，这个组必须是大素数大小，这意味着我们需要对这个域进行算术运算。再举一个例子，SuperSonic系统（在其某个版本中）使用了RSA整数，在这种情况下，Alphabet 将是一个大的素数字段。相比之下，当使用Merkle树时，Alphabet的大小可以是任意的，允许在任何有限域上进行算术运算。这包括上面的例子，也包括任意素数域，小素数域的扩展，如二进制域。字段类型是很重要的，因为字段越小，证明和验证时间就越快。

C. R1CS vs. 一般多项式约束

Zcash型SNARKs利用椭圆曲线上的双线性配对来计算约束。双线性配对的这种特殊使用 ^[7] ，限制了二次秩1约束系统（R1CS）的门运算。R1CS的简单性和普遍性使得许多其他系统对电路使用这种算术形式，尽管可以使用更普遍的约束形式，如任意秩二次型（ arbitrary rank quadratic form）或更高阶的约束。

三、 STARK vs. SNARK

下面我们来澄清一下 STARKs和SNARKs之间的差异。这两个术语都有具体的数学定义，某些结构可以实例化为STARKs或SNARKs，或者两者兼而有之。不同的术语强调证明系统的不同性质。让我们更详细地检查一下（参见图5）。

图5:STARK vs. SNARK

STARK

这里的 S 代表可扩展性，这意味着随着批处理大小n的增加，证明时间大小与n是呈准线性关系的，同时验证时间大小与n是呈多对数 ^[8] 关系的。

STARK中的 T 代表透明性，这意味着所有verifier消息都是公共随机coin(没有可信设置)。根据这个定义，如果有任何预处理设置，它必须简洁（多对数），并且必须仅包括抽样公共随机coin。

SNARK

这里的 S 代表简洁性，这意味着在n（不要求准线性证明时间）中验证时间大小是对数的，而 N 表示非交互，这意味着在预处理阶段（可能是非透明的）之后，证明系统不能允许任何进一步的交互。注意，根据这个定义，允许非简洁的可信设置阶段，一般来说，系统不需要透明，但必须是非交互的（在完成预处理阶段之后，这是不可避免的）。

纵观CI-verse（见图5），有人注意到它的一些成员是STARKs，其它一些成员则是SNARKs，有些则是两者都是，而其它成员则都不是（例如，验证时间大小与n的关系要比多对数要差的方案）。如果你对隐私（ZKP）应用是感兴趣的，那么ZK-SNARKs和ZK-STARKs，甚至是那些不具备STARK可扩展性也没有SNARK的的（弱）简洁性的系统，都可以很好地工作，例如Monero（门罗币）使用的Bulletproofs（防弹证明）就是这样一个显著的例子，其中验证时间与电路大小成线性关系。而当谈到代码成熟度时， SNARKs会拥有优势，因为有很多好的开源库可供构建。但是，如果你对可扩展性应用感兴趣，那么我们会建议使用对称STARKs，因为在编写本文时，它们有最快的证明时间，并且保证验证过程（或建立系统）的任何部分都不需要超过多对数处理时间。如果你想建立具有最小信任假设的系统，那么，同样，你也会想要使用对称STARK，因为唯一需要的成分是一些CRH和公共随机性的来源。

四、总结

图6: 总结

我们很幸运地经历了计算完整性密码学证明系统宇宙的惊人寒武纪爆发，我们认为系统和创新的扩散，将继续以越来越快的速度进行。

此外，随着未来新的见解及结构的出现，以上描述CI宇宙扩展及变化的尝试很可能会过时。话虽如此，纵观当今的CI领域，我们所看到的最大分界线是 (i) 需要非对称密码假设的系统，它们会导致证明时间更短，但证明成本更高，它们具有较新的假设，这些假设是易受量子计算影响的，其中有很多是不透明的，以及（ii）只依赖对称假设的系统，这使得它们在计算上是高效、透明，且可能是后量子安全的，而根据Lindy效应来看，它们也可能是最经得起未来考验的。

关于使用哪个证明系统的争论远未结束，但在StarkWare看来，我们会说：对于简短论证，可以使用Groth16/PLONK SNARKs，而对于其它的情况，则使用对称STARKs。

作者：Eli Ben-Sasson

特别感谢Justin Drake对文章草稿发表的评论。

脚注

1.术语ZKP经常被误用来指代所有的CI系统，甚至是一些非正式ZKP系统。为了避免这种混淆，我们使用了定义松散的术语“密码学证明”和“计算完整性（CI）证明”； ↵

[[2]]你可以在这里读到STARK算术化和低阶顺应性：

Arithmetization：博客[ 1 , 2 ], 演讲幻灯片以及视频演讲；低阶顺应性：博客文章（关于STARKs）；

↵

一元多项式的使用可以被广泛地推广到多元多项式和代数几何码，但是为了简单起见，我们坚持使用最简单的一元情况；

↵

我们特别将基于格的构造排除在讨论之外，因为它们还没有代码基础。这种结构是非对称的，而且似乎也是后量子安全的，并且通常使用小（素数）域。

↵