密码学 101：STARKs

• 原文链接：https://medium.com/@francomangone18/cryptography-101-starks-df79507f98ea
• 译者：AI翻译官，校对：翻译小组
• 本文永久链接：learnblockchain.cn/article…

这是关于密码学的一系列文章的一部分。如果这是你看到的第一篇文章，我强烈建议从系列的开头开始阅读。

我们花了整整四篇文章讨论 SNARKs——所以到现在为止，我们应该非常熟悉这些框架背后的重要思想。主要是，证明的简洁性（通俗地说，简短性）非常吸引人。此外，它们还非常通用，因为它们依赖于算术电路来构建陈述。

但是，它们有一些我们可能需要担心的小问题。试图避免这些问题是深入探讨今天文章主题：STARKs 的动机之一。

免责声明

我会避免在这里深入探讨 STARKs 背后的一些想法。即便如此，这仍然会相当复杂……但我觉得这是一个很好的起点。像往常一样，把这篇文章看作是你继续自行探索的坚实基础！

什么是 STARK？

这次，缩写代表Scalable Transparent ARguments of Knowledge。

可扩展？透明？这些是什么意思？让我们做一个快速的比较练习，以更好地理解这些概念。

SNARKs vs STARKs

我想这里有两个主要的考虑点。首先，SNARKs需要一个可信设置。

作为提醒，可信设置是指某个参与者需要生成一些公共参数，并在此过程中丢弃一个秘密值。如果该秘密值没有被丢弃，那么他们可以随时伪造虚假证明，这无疑是一个很大的风险！

可信设置可能会非常谨慎地进行，但仍然总是存在秘密值未被丢弃的可能性，这确实削弱了我们创建的任何协议。因此，它们有时甚至被称为有毒废物。

相比之下，透明协议不需要可信设置。因此，它们消除了可信设置带来的潜在威胁。听起来很有趣，对吧？

另一方面，还有可扩展性的问题，这是我们在谈论 SNARKs 时甚至没有提到的一个术语。我们没有讨论的是：验证者如何知道验证什么？

答案是他们被允许读取所使用的算术电路。你可以想象，随着电路变大，这需要越来越多的时间——实际上，它需要线性时间。而电路可以变得非常大。所以这可能是一个很大的不行。

STARKs试图通过采取不同的方法来缓解这个问题。计算不是被建模为算术电路，而是作为状态转换函数，这在合适的情况下允许更快的验证时间。让我们仔细看看。

状态转换函数

总的来说，算术电路只是表示计算的一种方式。还有其他策略可以实现相同的目的。

让我们想象一下，我们有一些计算可以表示为一系列步骤。你从某个初始状态开始，一次又一次地应用单一函数，直到达到最终状态。像这样：

整个计算由这个单一函数驱动——这就是，状态转换函数。没有什么能阻止我们编写一个算术电路来表示相同的计算——但请注意，这样的电路会比仅表示一个步骤的状态转换函数大得多。因此，读取前者需要更多的时间，而读取后者则不需要。

这就是为什么 STARKs 的缩写中有可扩展的原因：验证者可以在亚线性时间内运行。

那么，这个状态转换函数正式来说是什么呢？它只是一个这样的函数：

其中状态由一个长度为 $w$ 的向量表示，当然是由某个有限域的元素组成的。每个状态都是从前一个状态计算出来的：

我们关注的只是检查计算是否正确。或者，回到我们对 Plonk 的分析 ，检查计算轨迹是否满足一组约束。在这种情况下，约束总是由相同的状态转换函数给出的！

我们的计算轨迹将看起来像一个有$w$ 列和 T行的表格，代表我们经历的所有状态：

+---------------------+------+------+  
|                    |  x0  |  x1  |  
+---------------------+------+------+  
| 初始状态 (S_0)      |  1   |  1   |  
+---------------------+------+------+  
| 第一步 (S_1)        |  2   |  3   |  
+---------------------+------+------+  
| 第二步 (S_2)        |  5   |  8   |  
+---------------------+------+------+  
| 第三步 (S_3)        |  13  |  21  |  
+---------------------+------+------+  
| 第四步 (S_4)        |  34  |  55  |  
+---------------------+------+------+  
| 第五步 (S_5)        |  89  |  144 |  
+---------------------+------+------+

你可能认出来了——这是斐波那契数列！我们可以继续应用相同的状态转换函数来不断生成序列中的数字。

编码计算

当然，下一步与编码这个轨迹有关，以便稍后验证者可以检查由状态转换函数给出的约束是否成立。这个过程称为算术化。

在 Plonk 中，我们也进行了算术化。具体的技术实际上被称为 PLONKish 算术化 。

为了编码这些状态的转换，我们将使用一种称为算术中间表示的技术，简称_AIR。这个高大上的算法作为一个两步过程**工作：

• 将轨迹的每一列编码为一个多项式。
• 构建约束多项式。

在本系列的这一点上，我们对第一步已经非常熟悉。我们所需要做的就是将每一行的值分配给一些索引输入值 t（代表步骤），如下所示：

这就是，步骤 t 时状态的第 i 个分量

与 SNARKs 一样，步骤 t 实际上不是一个整数，而是一个单位根！所以，它实际上属于集合：

自然地，我们将获得 w 个多项式，每列一个——它们被称为轨迹多项式（因此用T来表示它们）。当然，我们通过 插值 获得它们。

第二部分涉及对状态转换函数本身进行编码。仔细观察，我们会发现它由 w 个独立函数 组成，每个状态组件对应一个函数：

每个这些函数组件都需要使用 轨迹多项式 写成一个约束。让我们以斐波那契例子作为练习。很容易看出，该函数可以表示为：

基于此，我们可以定义这些多项式，它们应该在单位根处评估为 0：

记住，乘以 omega 会将我们移动到下一步！

因此，如果验证者能够查询轨迹多项式在 $t$ 和 $ωt$ 处的值，他们应该能够检查表达式是否真的评估为0，这确保了计算满足状态转换函数 ！

如果验证者拥有这些约束多项式，他们可以简单地运行上述检查。但由于我们稍后会讨论的原因，他们从未真正得到这些多项式。我们现在知道的是，约束多项式可以从轨迹多项式中导出——所以让我们想象这样做是为了减少冗余。

好的，我们已经编码了我们的轨迹。还有一些额外的操作需要进行——但我们稍后会讨论。就像 Plonk 一样，编码对于我们创建一个框架是必要的，在这个框架中，验证者可以查询一些值并进行一些检查。

这是否让你想起了什么？是的，我们需要一个 _...