# 深入了解 STARK 安全性

By [xm98](https://paragraph.com/@xm98) · 2023-11-03

---

*   非交互式 STARK 以_交互式_预言机_证明_ （IOP） 开始，在随机预言机模型中被编译为非交互式证明。
    
*   这篇文章解释了 ethSTARK 文档的最新更新，该文档对随机预言机模型中 [ethSTARK](https://eprint.iacr.org/2021/582.pdf) 协议的安全性进行了全面而具体的分析。
    

**STARK 安全解释**
==============

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

（阅读 ethSTARK 文档（1.2 版）中的第 6 节，了解完整的详细信息，以及 Block 等人关于该主题的重要而全面的[独立工作](https://eprint.iacr.org/2023/1071.pdf)。

我们试图通过安全分析实现什么？我们希望防止对 STARK 系统的“成功攻击”，这是由虚假陈述和 STARK 验证者接受的 STARK 证明给出的（虚假）陈述。由于虚假陈述是危险的，它们可以有各种大小和形状，我们希望防止_所有_虚假陈述。任何虚假陈述，即使是 1+1=3 这样微不足道的陈述，再加上 STARK 验证者接受的 STARK 证明，都被视为对系统的成功攻击。（那些具有密码学背景的人可能有兴趣知道 STARK 也满足更强的安全概念，例如知识健全性，但为了简单起见，本文侧重于更简单的\*[健全](https://eprint.iacr.org/2016/116.pdf)_性情况。_)\*

我们如何正式定义 STARK 系统的安全性？我们通过分析“健全性误差”来做到这一点，该误差大致衡量攻击者为构建成功攻击而需要花费的预期“成本”（即，为虚假陈述找到 STARK 证明，但 STARK 验证者仍然接受）。从数学上讲，健全性误差是一个函数 _e_（t），它得到一个时间参数“\*t”\*作为输入，表示攻击者愿意花费多少时间进行攻击，并输出攻击者成功攻击的成功概率（找到令人信服的虚假陈述证据）。_随着攻击者愿意花费的“成本”越来越大，他的成功概率也会增加。_

到目前为止，我们已将 STARK 的安全性定义为函数 \*e（t），\*这不是您在加密 Twitter 上自然讨论安全性的方式。在那里，您可能听说过“该方案具有 96 位安全性”形式的陈述。这样的声明如何转化为我们的安全定义？对此没有一个答案，因为人们对“_x_位安全”的解释略有不同：

*   一个非常严格的转换意味着对于 1 和 2⁹⁶ 之间的任何 t，健全性误差为 _e_（_t_） _≤ 1/2⁹⁶_ 。_这意味着任何攻击者运行时间最多 2⁹⁶ 的成功概率很小，小于 1/2⁹⁶，小于十亿分之一乘以十亿乘以十亿。_
    
*   一个更轻松，也许更常见的翻译是，96 位的安全性意味着对于任何 t，它都持有 t/_e_（_t） ≥ 2⁹⁶。这意味着成功概率与运行时间（反比）成线性关系。例如，如果攻击者的运行时间为 2⁸⁶，则其成功概率最多为 1/2¹⁰。_
    

在这篇博文中，我们将介绍第二种选择。

**从 IOPS 到具有 96 位安全性的 STARK**
=============================

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

我们将要审查的第一个组件是 IOP：IOP 类似于标准的交互式证明，其中证明者和验证者进行多轮交互（我们将自己限制在公共硬币协议中，其中验证者只向证明者发送随机挑战）。在 IOP 中，验证器不会完全读取证明者消息，而是从每个证明者消息中抽取少量位。这就是后来编译的 STARK 的简洁性。

所以我们有一个 IOP，你如何从中构建 STARK？证明者消息可能很长（实际上，它们比计算本身更长）。为了压缩消息，我们使用 Merkle 树。默克尔树是一种二进制哈希树，其中每个叶节点表示 IOP 中的查询或答案。树的根是对整个信息的承诺。当验证程序想要读取消息中的特定位置时，证明者会提供该位置的值和身份验证路径。然后，验证程序可以使用路径来验证该值是否正确。IOP 验证程序仅从证明者消息中读取少量位置。因此，使用默克尔树会产生一个简洁的协议（一个具有小通信的协议）。

**压缩回合**
========

人们可能会选择交互式 STARK，这意味着但通常将它们设置为非交互式以简化生成它们的过程很方便，这样证明者在构建一个时就不需要等待外部消息。事实上，这是目前所有 STARK 系统的部署方式，也是 ethSTARK 协议的构建方式。非交互式 STARK 也是透明 SNARK 的一个特例（透明意味着不需要可信的设置来实例化它们;这也被称为“Arthur Merlin 协议”或“公共硬币 IOP”）。为此，最后一步是应用 Fiat-Shamir 将轮次压缩为单个消息，我们称之为 STARK 证明。Fiat-Shamir 变换将交互式协议转换为非交互式协议。证明者在“与哈希函数对话”时模拟交互式协议。为了推导出第 i 轮的随机_质询，证明者对第 i 轮的部分转录进行哈希处理，并将输出解释为下一个质询。_

这确保了证明者在生成质询后无法更改其响应。然而，作弊证明者有一些新的策略途径，这是交互式 IOP 所没有的。证明者可以通过修改上一条证明者消息来重新生成验证者质询，这将提供新的成绩单，从而也提供新的质询。事实证明，IOP的标准健全性概念并不足以证明菲亚特-沙米尔变换的安全性。

例如，考虑一个有 96 轮的 IOP，对验证器进行以下“黑客攻击”：如果验证器随机性的第一位在 96 轮中的每一轮都是 0，那么验证器接受（不查看任何证明）。可以看出，将此 hack 添加到验证器中只会为 IOP 的健全性误差添加 _1/2⁹⁶_ 的项。然而，在 Fiat-Shamir 转换之后，攻击者可以很容易地修改证明者消息，以确保每个哈希值都以零开头，从而在很短的时间内破坏系统。请放心，这种可怕的场景只是一个理论上的例子，不适用于已部署的 STARK。那么，让我们看看为什么我们的斯塔克毕竟是安全的？简而言之，我们将证明，运行最多 t 步的攻击者将以最多 _e（t） ≤ t / 2⁹⁶_ 的概率成功攻击。详情如下。

**IOPS 和逐轮稳健性**
===============

STARK 的安全性取决于其基础 IOP。但是，IOP 具有 96 位的安全性意味着什么？标准定义会说 IOP 具有健全性误差 1/2⁹⁶：这意味着任何攻击者（无论运行时间如何）愚弄验证器的概率最多为 _1/2⁹⁶_。_然而，正如我们所讨论的，IOP 健全性只是三个组成部分中的一个，这还不足以为从所有三个步骤编译的 STARK 获得 96 位的安全性。相反，假设 STARK 具有 96 位逐轮健全性误差（有时使用称为状态恢复健全性的类似定义），则证明编译的 STARK 的安全性。_

直观地说，逐轮的健全性表明每一轮都有 96 位的安全性，而不仅仅是整体协议。更详细地说，逐轮表示存在一个谓词，该谓词获取协议的部分转录，并告诉我们该转录是否是“愚弄”：空的转录不是“愚弄”，当且仅当验证者接受它时，完整的转录是“愚弄”。最后，对于任何不是“愚弄”验证者的部分成绩单，在下一轮中，成绩单变得“愚弄”的概率最多为 _1/2⁹⁶_。如果存在具有这些属性的谓词，我们说该协议具有 96 位逐轮健全性（谓词不需要有效可计算）。

在许多情况下，只分析眼压的健全性，而不分析其逐轮的健全性。诚然，很难想象 IOP 具有标准健全性但没有逐轮健全性的例子（人为的例子除外）。但是，当推导出每个位都很重要的具体安全边界时，两者之间的差异可能会出现。因此，为了得出严格而具体的界限，必须对 IOP 的逐轮稳健性进行严格分析。这正是我们对 [FRI 协议](https://www.youtube.com/watch?v=c3EHV3iJQSE)所做的，然后是 ethSTARK IOP，这是我们 STARK IOP 的基础。分析本身远非微不足道，也超出了本文的范围。使用新的分析，我们可以为证明设置精确的参数。

一轮又一轮的稳健性确实为我们提供了所需的保证。证明者可以多次重新生成挑战，但我们知道，对于任何一轮，生成“愚弄”成绩单的概率都是 _1/2⁹⁶_。因此，如果证明者有时间 _t_，即以哈希调用次数来衡量，那么它最多可以尝试 t 次来获得愚弄的成绩单，这将其成功概率限制在 _e（t） ≤_ min\*{t /2⁹⁶，1}\*。

**添加所有错误项**
===========

最后，为了保持所有这些，我们需要确保证明者不能篡改默克尔树。可以证明，只要证明者在哈希函数中没有发现冲突，它就不能在默克尔树中作弊。攻击者使用 _t_ 调用（对随机哈希函数）发现冲突的概率最多为 min{_t²/ 2s，1}，其中 s_ 是哈希函数的输出长度（这是由于“生日悖论”）。这就是为什么我们将哈希函数的长度设置为所需安全性的两倍。因此，如果我们有一个输出长度为 192 位的哈希函数和一个 IOP 的 96 位，我们得到一个编译后的 STARK，其健全性误差为 _e_（t） = _t_ /2⁹⁶ + min{t² / 2¹⁹²，1}。 _特别是，这样的方案具有 95 位的安全性，因为我们用来定义安全性的函数，即 t/e（t），满足不等式 t/e（t） ≥ t/（t /2⁹⁶ + min{t² / 2¹⁹²，1}），并且这个不等式的右侧在 t=2⁹⁶ 时达到其最小值，对于这个 t 值，我们有 t/e（t） ≥ 2⁹⁵。_

**总结**
======

总之，STARK提供了一种强大的方法，可以验证以无信任的方式对公共数据执行的计算的正确性。STARK的安全性通常以“健全性错误”来衡量，该错误表示攻击者成功提供虚假陈述并用证据说服验证者的可能性。为了达到所需的安全级别（例如 96 位），底层 IOP 必须满足逐轮的健全性，确保每一轮都保持高级别的安全性。我们逐轮分析了 SATRK 背后的 IOP 的稳健性，这使我们能够得出具体的安全边界。

---

*Originally published on [xm98](https://paragraph.com/@xm98/stark)*