翻译自：

https://www.starknet.io/en/posts/developers/safe-and-sound-a-deep-dive-into-stark-security

• 非交互式 STARK 最初是 交互式 Oracle 证明 (IOP)，在随机 Oracle 模型中编译为非交互式证明。

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

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

（请阅读 ethSTARK 文档（版本 1.2）中的第 6 节，了解完整的详细信息以及  Block 等人关于该主题的重要且全面的独立工作。）

我们试图通过安全分析实现什么目标？我们希望防止对 STARK 系统的“成功攻击”，这种攻击是通过虚假陈述和 STARK 验证者接受的针对该（虚假）陈述的 STARK 证明来实现的。由于虚假陈述是危险的，并且它们可以有各种大小和形状，因此我们希望防范 所有 虚假陈述。任何虚假陈述，即使是像 1+1=3 这样微不足道的陈述，再加上 STARK 验证者对该陈述接受的 STARK 证明，都被视为对系统的成功攻击。（具有密码学背景的人可能有兴趣知道 STARK 还满足更强的安全概念，例如 知识健全性，但为了简单起见，本文重点关注更简单的健全性情况。）

我们如何正式定义 STARK 系统的安全性？我们通过分析“健全性错误”来做到这一点，该错误粗略地衡量了攻击者构建成功攻击所需花费的预期“成本”（即找到虚假陈述的 STARK 证明，但该陈述仍被 STARK 验证者接受） 。从数学上来说，健全性误差是一个函数 e ( *t )，它以时间参数“ t”*作为输入，代表攻击者愿意花费的计算时间来发起攻击，并输出攻击者成功的概率与攻击（找到虚假陈述的令人信服的证据）。 随着攻击者愿意花费的“成本”  t的增加，他的成功概率也会增加。

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

• 非常严格的翻译意味着对于 1 到 2⁹⁶ 之间的任何 t  ，健全性误差为 e ( t )  ≤ 2⁹⁶  。这意味着任何攻击者运行时间最多为 2⁹⁶ 的成功概率很小，小于 1/2⁹⁶，小于十亿分之一十亿乘十亿。

• 更宽松、也许更常见的翻译是，96 位安全性意味着对于任何 t，它都满足 t / e ( t )  ≥ 2⁹⁶。这意味着成功概率与运行时间成（反）线性关系。例如，如果攻击者的运行时间为 2⁸⁶，则其成功概率最多为 1/21⁰。

在这篇博文中，我们将讨论第二个选项。

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

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

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

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

这确保了证明者在生成挑战后无法更改其响应。然而，作弊证明者有一些交互式 IOP 所没有的新策略途径。证明者可以通过修改最后的证明者消息来重新生成验证者挑战，这将给出新的记录，从而给出新的挑战。事实证明，IOP 的标准稳健性概念不足以证明 Fiat-Shamir 变换的安全性。

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

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

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

在许多情况下，仅分析 IOP 的健全性，而不分析其逐轮的健全性。诚然，很难想象 IOP 具有标准健全性但不具有逐轮健全性的例子（除了人为的例子）。然而，在推导每一位都很重要的具体安全边界时，两者之间的差异可能会出现。因此，为了得出严格而具体的界限，必须对 IOP 的逐轮健全性进行严格分析。这正是我们对 FRI 协议 以及作为 STARK IOP 基础的 ethSTARK IOP 所做的事情。分析本身绝非微不足道，超出了本文的范围。使用新的分析，我们可以为我们的证明设置精确的参数。

逐轮的稳健性确实给了我们想要的保证。证明者可以多次重新生成挑战，但我们知道对于任何一轮，生成“愚弄”记录的概率是 1/2⁹⁶。因此，如果证明者的时间为 t（以哈希调用次数来衡量），那么它最多可以尝试 t 次来获得欺骗性的记录，这将其成功概率限制为 e(t) ≤  min*{t /2⁹⁶ ,1}*。

最后，为了让这一切成立，我们需要确保证明者无法篡改 Merkle 树。可以证明，只要证明者发现哈希函数中没有冲突，它就无法在 Merkle 树中作弊。攻击者使用t次调用（对随机哈希函数）发现冲突的概率  最多为 min{ t²/ 2ˢ,1}，其中 s 是哈希函数的输出长度（这是由于“生日悖论”） ）。这就是为什么我们将哈希函数的长度设置为所需安全性的两倍。因此，如果我们有一个输出长度为 192 位的哈希函数和一个逐轮健全性为 96 位的 IOP，我们会得到一个编译后的 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 的健全性，这使我们能够得出具体的安全界限。

翻译自：

https://www.starknet.io/en/posts/developers/safe-and-sound-a-deep-dive-into-stark-security

• 非交互式 STARK 最初是 交互式 Oracle 证明 (IOP)，在随机 Oracle 模型中编译为非交互式证明。

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

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

（请阅读 ethSTARK 文档（版本 1.2）中的第 6 节，了解完整的详细信息以及  Block 等人关于该主题的重要且全面的独立工作。）

我们试图通过安全分析实现什么目标？我们希望防止对 STARK 系统的“成功攻击”，这种攻击是通过虚假陈述和 STARK 验证者接受的针对该（虚假）陈述的 STARK 证明来实现的。由于虚假陈述是危险的，并且它们可以有各种大小和形状，因此我们希望防范 所有 虚假陈述。任何虚假陈述，即使是像 1+1=3 这样微不足道的陈述，再加上 STARK 验证者对该陈述接受的 STARK 证明，都被视为对系统的成功攻击。（具有密码学背景的人可能有兴趣知道 STARK 还满足更强的安全概念，例如 知识健全性，但为了简单起见，本文重点关注更简单的健全性情况。）

我们如何正式定义 STARK 系统的安全性？我们通过分析“健全性错误”来做到这一点，该错误粗略地衡量了攻击者构建成功攻击所需花费的预期“成本”（即找到虚假陈述的 STARK 证明，但该陈述仍被 STARK 验证者接受） 。从数学上来说，健全性误差是一个函数 e ( *t )，它以时间参数“ t”*作为输入，代表攻击者愿意花费的计算时间来发起攻击，并输出攻击者成功的概率与攻击（找到虚假陈述的令人信服的证据）。 随着攻击者愿意花费的“成本”  t的增加，他的成功概率也会增加。

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

• 非常严格的翻译意味着对于 1 到 2⁹⁶ 之间的任何 t  ，健全性误差为 e ( t )  ≤ 2⁹⁶  。这意味着任何攻击者运行时间最多为 2⁹⁶ 的成功概率很小，小于 1/2⁹⁶，小于十亿分之一十亿乘十亿。

• 更宽松、也许更常见的翻译是，96 位安全性意味着对于任何 t，它都满足 t / e ( t )  ≥ 2⁹⁶。这意味着成功概率与运行时间成（反）线性关系。例如，如果攻击者的运行时间为 2⁸⁶，则其成功概率最多为 1/21⁰。

在这篇博文中，我们将讨论第二个选项。

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

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

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

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

这确保了证明者在生成挑战后无法更改其响应。然而，作弊证明者有一些交互式 IOP 所没有的新策略途径。证明者可以通过修改最后的证明者消息来重新生成验证者挑战，这将给出新的记录，从而给出新的挑战。事实证明，IOP 的标准稳健性概念不足以证明 Fiat-Shamir 变换的安全性。

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

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

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

在许多情况下，仅分析 IOP 的健全性，而不分析其逐轮的健全性。诚然，很难想象 IOP 具有标准健全性但不具有逐轮健全性的例子（除了人为的例子）。然而，在推导每一位都很重要的具体安全边界时，两者之间的差异可能会出现。因此，为了得出严格而具体的界限，必须对 IOP 的逐轮健全性进行严格分析。这正是我们对 FRI 协议 以及作为 STARK IOP 基础的 ethSTARK IOP 所做的事情。分析本身绝非微不足道，超出了本文的范围。使用新的分析，我们可以为我们的证明设置精确的参数。

逐轮的稳健性确实给了我们想要的保证。证明者可以多次重新生成挑战，但我们知道对于任何一轮，生成“愚弄”记录的概率是 1/2⁹⁶。因此，如果证明者的时间为 t（以哈希调用次数来衡量），那么它最多可以尝试 t 次来获得欺骗性的记录，这将其成功概率限制为 e(t) ≤  min*{t /2⁹⁶ ,1}*。

最后，为了让这一切成立，我们需要确保证明者无法篡改 Merkle 树。可以证明，只要证明者发现哈希函数中没有冲突，它就无法在 Merkle 树中作弊。攻击者使用t次调用（对随机哈希函数）发现冲突的概率  最多为 min{ t²/ 2ˢ,1}，其中 s 是哈希函数的输出长度（这是由于“生日悖论”） ）。这就是为什么我们将哈希函数的长度设置为所需安全性的两倍。因此，如果我们有一个输出长度为 192 位的哈希函数和一个逐轮健全性为 96 位的 IOP，我们会得到一个编译后的 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 的健全性，这使我们能够得出具体的安全界限。