深度解析STARK的完整安全性

原文：Safe and Sound — A Deep Dive into STARK Security

翻译及校对：「Starknet 中文社区」

非交互式 STARK 源于交互式预言机证明（IOP），在随机预言机模型中编译为非交互式证明。

本文解释了 ethSTARK 文档的最新更新，对随机预言机模型中 ethSTARK 协议的安全性进行了全面而具体的分析。

STARK 证明系统（即可扩展透明知识论证）是计算完整性的强大工具：它允许以无信任的方式验证在公共数据上执行的计算的正确性。在本文中，我们将深入探讨 STARK 证明所提供的安全性，对其进行定义，并探索证明方案安全性的技术。

（详情请阅读 ethSTARK 文档（1.2 版）第 6 节，以及布洛克等人就此主题所做的重要而全面的独立工作）。

我们试图通过安全分析实现什么？我们希望防止对 STARK 系统的「成功攻击」，这种攻击是由虚假陈述以及 STARK 验证器针对该（虚假）陈述而接受的 STARK 证明引起的。由于虚假陈述很危险，并且它们可能以各种规模和形式出现，所以我们希望能安全地防范所有的虚假陈述。任何虚假陈述，哪怕是微不足道的 1+1=3，只要与 STARK 验证器接受的 STARK 证明相结合，就会被视为对系统的成功攻击。（有密码学背景的人可能有兴趣知道，STARK 还能满足更强的安全概念，如知识可靠性，但为了简单起见，本篇文章将重点讨论关于可靠性的简单案例）。

我们如何正式定义 STARK 系统的安全性？我们通过分析 「可靠性误差」来确定。「可靠性误差」大致衡量了攻击者为成功发起攻击所需花费的预期「成本」（即为一个虚假陈述找到一个 STARK 证明，但该证明却被 STARK 验证器接受）。从数学上讲，可靠性误差是一个函数 (t)，它的输入是时间参数 t，代表攻击者为发起攻击而愿意花费的计算时间，输出则是攻击者攻击成功的概率（为虚假陈述找到令人信服的证明）。攻击者愿意花费的「成本」 t 越大，他的成功概率也就越高。

到目前为止，我们已经将 STARK 的安全性定义为一个函数 (t)，这与大家日常在加密推特上讨论安全性的方式不同。在推特上，你可能会听到这样的说法：「该方案有 96 比特的安全性。」这种说法如何转化为我们对安全性的定义呢？这没有统一的答案，因为人们对 「x 比特安全性」的理解略有不同：

严格解释的话，即意味着，对于任何 t 在 1 和 2⁹⁶之间的情况下，可靠性误差为 (t) 2⁹⁶ 。运行时间不超过 2⁹⁶ 的攻击者的成功概率很小，小于 2⁹⁶，即小于十亿分之一乘以十亿分之一。

一种更宽松、或许也更常见的解释则是，96 比特的安全性意味着对于任何 t，都存在 t/(t) 2⁹⁶ 的情况。这意味着成功概率与运行时间成（反）线性关系。如果攻击者的运行时间为 2⁸⁶，那么其成功概率最多为 2¹⁰。

在本文中，我们将讨论第二种方案。

那么，我们如何证明一个方案具备了 96 比特的安全性呢？为了回答这个问题，我们需要理解构建 STARK 的高层结构。STARK 由三个主要部分组成：IOP（交互式预言机证明）、默克尔树和 Fiat-Shamir 哈希；我们主要关注的重点部分是 IOP。一旦指定了这些组件部分，我们就可以编译它们来生成一个 STARK。我们将详细介绍这些组件，包括它们是什么以及如何将它们组合在一起。

首先我们要审查的组件是 IOP：IOP 类似于标准的交互式证明，在其中证明器和验证器进行多轮交互（我们仅限于公共币协议，即验证器只向证明器发送随机挑战）。在 IOP 中，验证器不会完全读取证明器的消息，而是从每个证明器信息中抽样一小部分比特。这就是后来编译的 STARK 能够实现简洁性的原因。

有了 IOP，如何从中构建 STARK？证明器的信息可能很长（实际上，它们比计算本身还要长）。为了压缩这些信息，我们使用默克尔树。默克尔树是一棵二进制哈希树，其中每个叶节点代表 IOP 中的一个查询或一个回答。树根是整个信息的承诺。当验证器想读取信息中的特定位置时，证明器会提供该位置的值和验证路径。验证器就可以使用该路径来验证该值是否正确。IOP 验证器只从证明器信息中读取少量的位置信息。因此，使用默克尔树可以实现简洁的协议（通信量小的协议）。

我们可以选择交互式 STARK，但为了简化生成 STARK 的过程，我们通常会选择非交互式 STARK，这样验证器在构建 STARK 时就无需等待外部信息。事实上，这是目前所有 STARK 系统的部署方式，也是 ethSTARK 协议的构建方式。非交互式 STARK 也是透明 SNARK 的一种特例（透明意味着无需可信设置来实例化它们；「Arthur Merlin 协议」或「公共硬币 IOP」）。为此，最后一个步骤是应用 Fiat-Shamir 算法将多轮交互压缩至单一消息，我们称之为 STARK 证明。Fiat-Shamir 变换是将一个交互式协议转换为非交互式协议的方法。证明器在「与哈希函数对话时」模拟交互式协议。为了得出第 i 轮的随机挑战，证明器哈希至第 i 轮的部分记录，并将输出解释为下一个挑战。

这就确保了证明器在挑战生成后无法更改自己的回答。然而，作弊的证明器拥有一些在交互式 IOP 中没有的新策略途径。证明器可以通过修改最后一个证明器信息来重新生成验证器挑战，这样就会得到一个新的记录，从而也会得到一个新的挑战。事实证明，IOP 的标准可靠性概念不足以证明 Fiat-Shamir 转换的安全性。

例如具有 96 轮的 IOP，并向验证器添加以下 hack：如果验证器的随机性的第一比特在 96 轮中每一轮都是 0，那么验证器就会接受（无需查看任何证明）。我们可以看到，向验证器添加这个 hack 只会在 IOP 的可靠性误差中添加一个 2⁹⁶ 的项。然而，经过 Fiat-Shamir 变换后，攻击者可以轻松修改证明器信息，确保每个哈希值都以 0 开头，从而在很短的时间内攻破系统。请放心，这种可怕的情况只是一个理论上的例子，并不适用于已部署的 STARK。那么，让我们来看看为什么我们的 STARK 终究是安全的呢。简而言之，我们将证明，攻击者最多运行 t 步，攻击成功的概率最多为 (t) t 2⁹⁶。

STARK 的安全性取决于其底层 IOP。但是，一个 IOP 具有 96 比特的安全性意味着什么呢？按照标准定义，IOP 的可靠性误差为 2⁹⁶：这意味着任何攻击者（无论运行时间长短）欺骗验证器的概率最多为 2-96。然而，正如我们所讨论的，IOP 的可靠性只是三个部分中的一个，这并不足以让从所有三个步骤编译出来的 STARK 获得 96 比特的安全性。相反，假设 STARK 有 96 比特逐轮可靠性误差（有时也使用一个被称为状态恢复可靠性的类似定义），则编译后的 STARK 的安全性就得到了证明。

直观地讲，「逐轮可靠性」（round-by-round soundness）表明每一轮都有 96 比特的安全性，而不仅仅是整个协议。说得详细一点，即逐轮可靠性指的是存在一个谓词，它能获取协议的部分记录，并告诉我们这个记录是否是「欺骗性的」：「空记录」不是「欺骗性」，而当且仅当验证器接受时，完整的记录是「欺骗性」。最后，对于任何不是「欺骗」验证器的部分记录，在下一轮中记录变成「欺骗性」 的概率至多为 2⁹⁶。如果存在具有这些属性的判定，我们会说协议具备 96 比特的逐轮可靠性（这个谓词不要求可以有效计算）。

在许多情况下，人们只分析 IOP 的可靠性，而不分析其逐轮可靠性。诚然，我们很难想到 IOP 具有标准可靠性而不具有逐轮可靠性的例子（人为制造的例子除外）。然而，当推导具体安全界限时，两者之间的差异可能会出现，每个比特都很重要。因此，要推导出严密而具体的界限，就必须对 IOP 的逐轮可靠性进行严密分析。这正是我们对FRI 协议和作为 STARK IOP 基础的 ethSTARK IOP 所做的工作。分析本身远非小事，并超出了本文讨论的范畴。使用新的分析，我们可以为我们的证明设置精确的参数。

逐轮可靠性确实为我们提供了所需的保障。证明器可以多次重新生成挑战，但我们知道，在任何一轮中，生成「欺骗性的记录概率都是 2⁹⁶。因此，如果证明器有 t 次时间（以哈希调用次数来衡量），那么它最多可以尝试 t 次来获得欺骗性记录，这就将其成功概率限制在 (t) t 2⁹⁶。

最后，要使所有这一切成立，我们需要确保证明器无法篡改默克尔树。我们可以表明，只要证明器在哈希函数中没有发现碰撞，他就无法在默克尔树中作弊。攻击者使用 t 次调用（随机哈希函数）找到碰撞的概率最多为 t2/2，这就是哈希函数的输出长度（由「生日悖论「造成）。这就是为什么我们需要设置哈希函数的长度为所需安全性的两倍。如此一来，如果我们有一个输出长度为 192 的哈希函数和一个逐轮可靠性为 96 比特的 IOP，我们就会得到一个编译后的 STARK，其可靠性误差 (t)=t2-⁹⁶ + t2 2¹⁹⁶。由于 t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵，因此这种方案拥有 95 比特的安全性。

综上所述，STARK 提供了一种功能强大的方法，用于以无信任的方式验证在公共数据上执行的计算的正确性。STARK 的安全性通常用「可靠性误差」来衡量，它代表了攻击者成功提供了一个虚假陈述并用证明说服验证器的概率。为了达到所需的安全级别，例如 96 比特，底层的 IOP 必须满足逐轮可靠性，确保每一轮都能保持高安全级别。我们分析了我们的 STARK 所基于的 IOP 的逐轮可靠性，从而得出了具体的安全界限。