SNARK安全性和性能

A SNARK（简洁非交互式知识论证）是一种加密工具，在系统设计中开辟了令人兴奋的新可能性，尤其是在去中心化环境中。SNARKs允许数据被不受信 entities处理，这些实体可以证明数据是有效的，并已经正确处理。一个天真的证明方法是发布数据，允许任何想要验证其有效性的人直接进行处理。

SNARK以更优的成本达到相同的效果。例如，在一个层二（L2）可验证的Rollup中，Rollup服务处理区块链事务。该服务定期将用户的账户余额发布到层一区块链。每次发布余额更新时，它会附加一个SNARK证明，证明它知道一系列有效的交易，使旧的账户余额变为更新的余额。这样，区块链验证者无需进行繁重的验证交易有效性（例如，检查每笔交易的数字签名）或显式处理交易以计算更新的余额。

我之前的帖子专注于SNARK证明者的性能——这是SNARK适用性的主要决定因素。尽管运行SNARK证明者可能计算密集，以至于生成大规模计算的证明可能不可行，但SNARK验证通常比直接检查和处理数据便宜得多。然而，SNARK验证的成本差异很大。本文将解析这些成本，并比较不同SNARK的安全属性。

特别地，我解释了在具有合理后量子安全性（PQ-SNARKs）的实用SNARK中，安全性与验证成本之间存在显著的紧张关系。此外，在某些情况下，这种紧张关系目前正在偏向于验证成本而非安全性。为了使SNARK发挥其潜力，部署的系统必须是安全的，用户必须对其安全性充满信心。最后，我提出了一些简单的行动，Web3社区可以采取这些行动来帮助确保这些属性在长期内保持。

定量安全措施

当生产出一个令人信服的虚假声明证明在计算上不可行时，SNARK是安全的。例如，在L2 rollup的背景下，攻击者如果想盗取我的资金，可能会证明一个类似于“我知道一笔数字签名的交易，将所有Justin的资产转移到我的账户”的虚假声明。

SNARK的安全级别是通过找到一个令人信服的虚假声明证明所需的工作量来衡量的。与其他加密原语（如数字签名）类似，这种工作量的对数被称为“安全位数”。例如，30位安全性意味着攻击该SNARK需要大约230≈10亿的“工作步骤”。这本质上是对现实世界安全性的近似度量，因为一个工作步骤的概念可能有所不同，而且内存需求或并行机会等实际考虑也没有被考虑在内。

以及定性安全措施

安全位数是SNARK安全性的一个_定量_度量。SNARKs在其_定性_安全属性上也有所不同。

例如，有些SNARKs需要一个受信任的设置仪式来生成结构化的证明密钥。完全不需要受信任设置的SNARK被称为透明的。

为了确保非透明的SNARK安全，通常至少需要仪式中的一个参与者是诚实的，这意味着他们生成并丢弃了一个“陷门”，如果与所有其他参与者的陷门组合在一起，将使得找到任何虚假声明的令人信服的SNARK“证明”变得简单。可信设置正在进行中，以使这种假设尽可能温和，参与者数量可以达到数百或数千。

SNARKs在对抗量子攻击的脆弱性方面也存在差异。具体而言，许多SNARKs（例如，Groth16、PlonK、Marlin、Bulletproofs、Nova）依赖于离散对数难以计算的假设（在某些情况下，还有其他附加假设）。计算离散对数是量子计算机能够高效完成的事情。因此，这些SNARK不是后量子安全的（非PQ）。

虽然急需努力转向后量子加密方案，但这种需求主要是由需要在未来几十年内保持加密消息秘密驱动的。一个攻击者如果今天存储一个拦截的消息并等待一个量子计算机在五十年后到来，可以使用计算机解密这条五十年前的消息。SNARK的情况则截然不同。今天使用非PQ的SNARK不应该影响未来五十年区块链的安全，即使量子计算机在那时到来。

多项式承诺

所有SNARK都使用一种称为_多项式承诺方案的加密原语，而这个组件通常是性能瓶颈。（详情，请参见我的上一篇文章。）此外，SNARK的透明性和合理的后量子安全性仅由其使用的多项式承诺方案决定。

一个显著的例子是所谓的KZG多项式承诺，它被PlonK、Marlin及许多其他项目使用。KZG承诺既不透明，也不是后量子安全的。其他承诺方案是透明的，但不是后量子的，包括Bulletproofs、Hyrax和Dory。

还有其他方案即透明又合理的后量子。这些包括FRI、Ligero、Ligero++、Brakedown和Orion。所有这些方案都基于纠错码。他们只使用哈希作为加密原语。他们还共享以下属性：验证成本（以哈希评估和域操作的数量来衡量）与安全位数的增长是线性的。大致而言，这些后量子多项式承诺的单个“迭代”只实现少量（比如说2-4）位安全性。因此，该协议必须重复许多次以“增强”安全级别，验证成本随每次重复而增加。因此，为了控制PQ-SNARKs的验证成本（从而控制区块链应用中的Gas成本），协议设计者有动机保持较低的安全水平。

除了少数例外，这种具体安全性和验证成本之间的紧张关系在非PQ SNARK中（无论透明和非透明）并不出现。非PQ-SNARK使用的椭圆曲线组中，计算离散对数被认为很难完成，并且其安全级别由所使用的组确定。适当的椭圆曲线组的大小，因此每个组操作的成本，随着所需安全级别的提高而增长。然而，证明中的_组元素数量与组的选用无关。

在PQ-SNARK中，哈希评估的大小不仅与所需安全水平呈线性增长，纳入证明并由验证者执行的评估数量也是如此。

部署的SNARKs的具体验证成本和安全性

部署的SNARK的具体验证成本和安全级别变化很大。以下是一些示例：

验证者成本

我之前的帖子提到两个具体验证成本的例子：PlonK证明在以太坊验证的成本低于300,000个gas，而StarkWare的证明成本约为500万个gas。StarkWare的证明是透明和后量子合理的，而PlonK的则不是。然而，如下所述，StarkWare的证明在以太坊上的安全级别远低于PlonK的证明。

具体安全性

以太坊预编译中唯一的椭圆曲线是altbn128，因此这是所有在以太坊上部署的非PQ SNARK使用的曲线，包括Aztec和zkSync。该曲线——因此也包括使用它的部署SNARK——最初被认为提供大约128位的安全性。

但由于改善的攻击（其精确运行时间是难以确定的），该曲线现在被广泛认为提供100到110位的安全性。当前EIP被考虑引入不同曲线的预编译，仍被认为能够接近128位的安全性。这些曲线已经在非以太坊项目的SNARK中使用，包括ZCash、Algorand、Dfinity、Filecoin和Aleo。

相比之下，根据链上的数据，StarkWare的PQ-SNARK（在被称为SHARP系统中，SHARed Prover的缩写）已被配置为针对80位的安全性。这个安全级别是在FRI的统计有效性的一些假设下维持的（我将在本帖子后面讨论）。

“80位安全性”这个术语在这个上下文中是模糊的，因此让我来解释一下。大致而言，这意味着攻击者可以通过评估哈希函数280次（即Ethereum使用的哈希函数KECCAK-256）来生成一个令人信服的虚假声明证明。更具体地说，准备进行2k次哈希评估的攻击者可以以约2k-80的概率生成一个令人信服的证明。例如，通过270次哈希评估，可以找到一个关于虚假声明的SNARK“证明”的概率约为2-10=1/1024。

这一概念在其他上下文中比“80位安全性”这个术语所指的要弱得多。例如，配置为80位安全性的抗碰撞哈希函数（CRHF）会产生160位输出。如果哈希函数设计良好，最快的碰撞发现程序将是生日攻击，这是一种可以通过大约2160/2=280哈希评估发现碰撞的暴力方法。然而，使用2k次哈希评估，生日攻击找到碰撞的概率仅为22k-160。

例如，270次哈希评估将以2-20≈1/1,000,000的概率发现碰撞。这远小于攻击者伪造一个配置为80位安全的PQ-SNARK证明的概率1/1,000。

这两种“80位安全性”概念在抵抗独立攻击的鲁棒性方面也存在显著差异。例如，假设有1,000个独立方分别通过执行270次哈希评估攻击PQ-SNARK。由于每个成功的概率约为1/1,000，至少其中一个成功的可能性很高。如果每个成功的概率仅为1/1,000,000，这种情况便不会出现。

设计良好的椭圆曲线组预计类似于CRHF表现，生日类攻击如Pollard的rho算法是最著名的。 这意味着在提供128位安全性的组中，2k组操作仅能以22k-256的概率为离散对数问题的一个实例提供解决方案。例如，270次组操作仅能以2-116的概率找到离散对数。此外，每组操作的速度慢于CRHF的评估。

今天可行的哈希评估数量是多少？

在2020年1月，使用GPU计算接近264个SHA-1评估的成本为$45,000。这使得270个SHA-1评估的成本在GPU上达到数百万美元（在以太坊合并后可能更低，因为远离GPU主导的工作量证明挖矿的过渡可能会降低对GPU计算的需求，进而降低成本）。

随着有效性Rollup已经存储数亿美元的用户资金，找到一个令人信服的虚假声明证明可能会带来数百万美元的利润。配置PQ-SNARK为80位安全性，在激进的假设下其与利润攻击的安全性存在10位的余地。

另一个数据点是，比特币网络的哈希率目前约为267个哈希评估每秒，这意味着比特币矿工整体每两个小时执行280个SHA-256评估。当然，这一惊人的数字源于对比特币挖矿中ASIC的巨大投资。

假设每小时生成six bitcoin blocks（六个比特币区块），若以当前每个区块的奖励为6.25比特币，那么这280个SHA-256评估的成本至多为$22,00026*6.25≈$1.6百万。否则，在当前价格下，比特币挖矿将不会盈利。

促进健康生态系统的提议

在Rollup中使用SNARK的主要目的是实现区块链的可扩展性，而无需用户盲目信任Rollup服务。由于Rollup服务编写了作为SNARK验证者的智能合约，公众必须能够检查该合约并确认其确实验证了适当声明的SNARK证明。公共对智能合约的审查可能还需要确保Rollup服务无法审查其用户。提出的抗审查方法需要Rollup的智能合约允许用户在Rollup服务未能处理其交易时强制提取其资金。

考虑到这些协议的复杂性，这种公共审查的范式对专家提出了一定的要求，让他们公开并坦诚地讨论已部署合约的安全性。

但是，在PQ-SNARK中，由于安全性和验证者性能之间的紧张关系，专家们可能很难确定部署协议的安全级别：安全级别（以及验证成本）依赖于SNARK的内部参数。而至少对于StarkWare的智能合约来说，这些参数（称为logBlowupFactor、proofOfWorkBits和n_Queries）并未直接在智能合约代码中明确规定，而是作为公共数据传递给智能合约。据我所知，从链上信息中识别这些参数的最简单方法是通过四个步骤：

1. 在像Etherscan这样的区块浏览器上查看适当的智能合约，
2. 点击一个适当的“验证证明”交易，
3. 解码该交易的输入数据，和
4. 找出如何_解释_解码的输入数据以了解关键的SNARK参数，这些参数共同决定了安全级别。

最后一步涉及到寻找实现该事务的适当Solidity代码，这本身可能是一项复杂的任务。（在我准备调查 演讲关于Rollup时，Etherscan能按照上述步骤2解码SHARP验证者交易的相关输入数据，但现在看来不起作用了。）

提议1：审查

考虑到这一点，我向Web3社区的第一个建议是，使审查部署的后量子SNARK安全级别变得更加容易。这可能涉及改进理解链上数据的工具，以及项目自己透明度的提高，以使这些参数众所周知。

提议2：更强的规范

80位的安全性过低，尤其是对于270次哈希评估就能成功攻击的弱版本——考虑到对加密原语历史上惊人攻击的漫长历史，更是如此。如上所述，关于配对友好椭圆曲线（如altbn128）的更好攻击就是其中之一。一个更著名的例子是SHA-1，其安全性标定为80位，但最终证明其实现的安全性仅约60位。考虑到这种历史，PQ-SNARK设计者在配置安全级别时应该保留超过10位的余地，尤其是在安全分析受到了关于FRI统计安全性强假设的影响。

即便是PQ-SNARK，通过增加验证成本总可以实现合适的安全级别。例如，提高SHARP验证者的安全性从80位提升到128位（在有关FRI统计有效性的假设下）会将Gas成本增加大约一倍，从略超500万增至略超1000万。如果没有关于FRI的假设，Gas成本将再增加一倍，超过2000万。

因此，我的下一个建议是，Web3社区应该围绕部署的SNARKs制定更强的规范。我个人的建议是至少100位，如果SNARK的安全基于非标准假设，至少128位。我并不是首次提出这样的建议。

在此，我愿意将“标准假设”狭义地分类为在随机oracle模型中无条件安全的，如果部署的SNARK中的随机oracle是用标准哈希函数（如KECCAK-256）实例化的。随机oracle模型是一个理想化的设置，旨在捕捉设计良好的加密哈希函数的行为。它常用于分析PQ-SNARK的安全性。

非标准假设的一个例子是关于某些协议（如FRI）定量安全性的猜想（稍后描述），无论是在互动设置中还是作为随机oracle模型中的非互动协议。

SNARK设计者正在以许多令人兴奋的方式进行创新，其中一些可能在安全性方面推动了边界——例如，使用尚未经过如此多密码分析的SNARK友好哈希函数。我并不是呼吁停止这种努力——远非如此。但是，这些原语应该以远超已知、可行攻击的安全级别实例化10位以上。

使用SNARK的Rollup通常被描述为继承其L1的安全性。但是，如果它们的配置安全级别远低于L1所使用的任何加密原语，那么这就很难成立。随着SNARK的增加采用，我们应确保以与我们谈论它们的方式一致的方式来部署它们。只要仔细分析SNARK，适当配置并正确实现，它们的安全性与今天使用的任何加密原语一样。

附带说明：更深入探讨PQ-SNARK安全性

StarkWare的PQ-SNARKs中的80位安全性是这样的。 这些PQ-SNARK使用一种称为FRI的多项式承诺方案，而StarkWare的SHARP验证者在对一个假设的情况下以48位安全性运行FRI。大致而言，该假设是FRI的有效性简单攻击是最优的。在此攻击中，一个作弊的证明者只需花费少量精力，就可以生成一个“FRI证明”，该证明以2-48的概率通过验证者随机选择的检查。

StarkWare将FRI与一种称为“研磨”的技术结合在一起。这要求诚实的证明者在生成FRI证明之前生成一个32位的工作证明。研磨的好处是，它大大增加了作弊证明者进行上述FRI简单攻击所需的工作量，约为232个哈希评估。

由于（预期中）成功的FRI简单攻击需要进行248次尝试，因此要伪造FRI证明，作弊证明者大约需要完成248*232=280个哈希评估。

最后，让我们仔细分析FRI产生的48位安全性。FRI验证者对承诺的多项式进行“查询”。FRI验证成本随查询的数量而线性增长。例如，36个FRI验证者查询的成本大约是9个查询的4倍。但查询越多，安全性就越高。“每查询安全位数”的数量取决于FRI的另一个参数，称为代码率。

具体来说，FRI使用一种称为Reed-Solomon代码的代码率r，其中_r_始终是一个严格介于0和1之间的数值。FRI证明者的成本与_r_呈反比，因此代码率为1/16会导致证明者的速度大约只有1/4的速度和所需的存储空间更多。

SHARP验证者以1/16的代码率和12个验证查询运行FRI。StarkWare推测每个FRI验证查询增加了log2(1/r)位的安全性。在这个假说之下，12个验证查询提供了12 log2(16) = 48位的安全性。 但是，目前的分析仅确定每个验证查询增加了稍微少于log2(_1/r 1/2)位的安全性。因此，12个FRI验证查询只提供少于12 log2(4) = 24位的“可证明”安全性。

缓解安全性与性能之间紧张关系的提议

实用PQ-SNARK的验证成本随着所需安全位数的增加而线性增长。一种缓解这种紧张关系的前景良好的技术是SNARK组成——我在上一篇文章中描述过，它是解决证明者与验证者成本之间紧张关系的手段，但它也可以解决安全性的问题。

两个例子

Polygon Hermez正在将PQ-SNARK与PlonK组合。 该思想是，证明者首先生成一个PQ-SNARK证明π。如果PQ-SNARK配置为具有快速证明者和适当的安全级别，那么π将是巨大的。因此，证明者不会将π发送给验证者。相反，它使用PlonK来证明它知道π。

这意味着将PlonK应用于一个以π作为输入的电路，检查PQ-SNARK验证者是否会接受π。由于PQ-SNARK的多对数验证成本，PlonK适用于一个小电路，因此PlonK证明者快速。由于PlonK证明小且验证便宜，因此验证成本较低。

不幸的是，使用PlonK会破坏透明性和后量子安全性。我们可以考虑用PQ-SNARK本身替代PlonK来证明对π的知识（实际上Polygon使用的PQ-SNARK以这种方式自我组成）。

在PQ-SNARK的第二次应用中，为了证明对π的知识，系统可以配置为以合理大小的证明实现适当的安全性，例如，选择在FRI中使用一个非常小的代码率。关键点是，尽管小的代码率对于证明者时间是不利的，但PQ-SNARK的第二次应用仅针对一个小电路，因此总证明者时间应保持较小。

我们对组成SNARK安全性的理论理解还有很大提升空间。然而，目前尚不存在已知的攻击，其速度超过对单个组成SNARK的攻击。例如，如果将PQ-SNARK与PlonK组合，我们并不知道更好的攻击，除了攻击PQ-SNARK（即找到一个虚假的SNARK证明π）或攻击PlonK（即找到一个 PlonK证明该虚假声明“我知道一个PQ-SNARK证明π，验证者本来会接受。”）

以这种方式组合SNARK日益流行，期望协议设计者能利用它来提高安全性。

\\*\

Justin Thaler 是乔治城大学的副教授。在加入乔治城大学之前，他在纽约的雅虎实验室担任研究科学家两年，此前他在加州大学伯克利分校的 Simons Institute for the Theory of Computing 担任研究员。

_编辑：Tim Sullivan @tim_org_

\\*\

• 原文链接： a16zcrypto.com/posts/art...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～