STARKs 是如何工作的

STARK 是一类加密证明系统。它们可以实现可扩展性和隐私性，并且是后量子安全的。

在本文中，@EliBenSasson 以简化的方式向非数学人士解释了 STARK 的工作原理。

首先，说明事项

在深入之前，有几个重要的注意事项：

1. 重点主要在于我们如何生成 STARK 证明。

2. 我们会使用简化的例子来解释一个实际上非常复杂的数学过程。自然，过程中会有部分被跳过，有些类比并不完美。这就引出了第 3 点：

3. 我们强烈鼓励任何深入研究过这个主题的人提供他们自己关于 STARK 工作原理的最佳解释。教育再多也不为过！

4. STARK 可以在区块链世界之外使用。然而，出于我们的目的，本文将描述 STARK 在扩展区块链时的工作原理。

这是一个很长的解释，所以在开始之前，请给自己倒杯咖啡，伸展一下腿，按摩一下眼睛。

☕

好了，我们开始吧。

问题：区块链可能很慢

要理解 STARK 提供的解决方案，我们首先需要理解它们解决的问题之一：可扩展性。

去中心化区块链使用户能够进行数字活动并将数据存储在链上。在去中心化链中，所有运行它的参与方都会检查并验证每一次交互。像比特币和以太坊这样的去中心化区块链是安全的，因为每个人都检查所有数据。

例如，如果 Alice 向 Bob 发送了资金，网络中的每个节点都会重新执行这笔交易并验证其细节，如下所示：

• Alice 是否有足够的资金？

• 她的签名是否有效？

• 余额是否更新正确？

• 等等。

让每个人都验证这些数据对安全性很有利，但要求每个节点都重新执行每笔交易对于可扩展性来说却很糟糕。这里有个类比：

想象一所学校有 30 个学生正在参加数学考试。通常，一个老师批改试卷，每个人都信任那个分数。但如果那个老师不值得信任呢？如果其他老师怀疑他有理由给出假分数，比如，他收钱给某个特定学生最高分呢？

在这种情况下，其他老师都会想自己批改所有试卷，以确保他们的结果与给出的分数一致。想象一下这个负担。那会花费太多时间和精力。在更大的规模上，这根本行不通，30 个学生不行，300 或 3000 个学生当然也不行。

解决方案：提供有效性证明

与其让所有老师重新检查所有试卷，或让数千台计算机重新执行所有交易，有没有一种方式，让一方完成大部分工作，并向其他方证明工作正确完成？如果其他方可以运行一个简单的检查来确保交易的有效性和处理过程的完整性，这将为他们节省大量工作，同时允许他们承诺结果数据，而不损害安全性。这就是 STARK 实现的目标。

STARK 协议涉及两方：

1. Prover（证明者）：一台通过极其复杂和冗长的计算来处理交易，并生成 STARK 证明的计算机。

2. Verifier（验证者）：一个通过几个步骤检查 Prover 工作的软件。

当应用于区块链时，一旦证明被验证，系统就可以用处理交易产生的数据结果进行更新。

使用 STARK，Prover 可以是任何人，包括你不信任的人：一个国家、一家公司、一个匿名个体，甚至是 Darth Vader。他们无法为了恶意意图而扭曲数学。我们不信任 Darth，我们信任数学，当我们运行 Verifier 时，我们每个人都在运行这个数学。

通过抽样而不是重新执行计算来验证

验证 STARK 证明不需要重新执行所有已处理的交易。证明的构建方式允许 Verifier 运行一个相对较小的计算来检查是否有错误或无效数据的迹象。如果没有，Verifier 就可以确认所有已处理的交易都是有效的。

STARK 通过数学实现了这一点。数学协议混合并放大了数据，因此即使是最小的错误也会影响到证明的每个部分。这确保了任何无效数据都将变得可检测，就像一滴血就能揭示我们健康的关键信息一样。

这个过程让我们可以验证 Prover 的工作，而不是让网络的所有节点重新做一遍，效率有多高？如果我们处理 100 万笔交易，Verifier 可以用与执行 6 笔交易相同的计算量来检查 STARK 证明。

那么，这是如何实现的呢？STARK 如何处理 100 万笔交易，将它们压缩成一个可以用处理 6 笔交易的工作量来验证的证明，并且仍然确保没有错误或恶意行为未被检测到？

生成 STARK 证明

记录交易并执行步骤

正如我们所提到的，STARK 协议由两方操作：Prover 和 Verifier。

在过程的第一步，Prover 会批处理大量（巨大）的交易，并记录它们的数据。

想象一个简单的交易：Alice 向 Bob 发送 1 个 STRK 代币。

这笔交易涉及许多细小的执行步骤：

• 检查 Alice 的余额

• 验证她的签名

• 从 Alice 处扣减资金

• 向 Bob 添加资金

• 等等。

Prover 将逐步编码这些执行指令。例如：

• 位置 $A$ 和 $B$：Alice 和 Bob 的初始余额（100 和 50）。

• 位置 $C$：从 Alice 到 Bob 的转账金额（1 STRK）。

• 位置 $D$ 和 $E$：交易后 Alice 和 Bob 的更新余额（99 和 51）。

• 等等。

约束条件

确保交易有效且正确执行的方法从这个阶段开始。每笔交易必须遵循特定规则：余额必须合计正确；转账金额必须从账户中扣减并添加到账户，且保持一致和逻辑；两个账户的余额必须根据转账金额更新；签名必须匹配，等等。

这些条件和规则被称为约束。当且仅当所有约束都满足时，交易才算被正确处理。

理解约束如何帮助我们检测一致或不一致的一个有用类比是数独谜题。在数独中，你填入谜题的数字必须共同满足特定规则：每一行、每一列和每个小方格都必须包含 1 到 9 的所有数字，每个数字恰好出现一次。当你在数独中的某个位置填入了“错误”的数字时，一旦你查看该数字所在的行、列或方格，就很容易被检测出来。会立刻清楚某个特定约束被违反了。

当填入一个"错误"的数字时，一旦你查看行、列或方格，就很容易被检测出来

这并没有描述 STARK 的实际工作方式，但它是理解约束概念的一个有用方式。

这些约束如何应用于我们 Alice 向 Bob 转账 1 STRK 的例子？写入位置 $A$、$B$、$C$、$D$ 和 $E$ 的数据必须满足为确保交易有效且执行完整而设定的约束。例如：

1. Alice 和 Bob 的初始余额总和（$A+B$）必须等于他们最终余额的总和（$D+E$）。

2. Bob 的初始余额加上转账金额（$B+C$）必须等于他的最终余额（$E$）。

3. Alice 的初始余额减去转账金额（$A-C$）必须等于她的最终余额（$D$）。

4. 转账金额（$C$）必须为正且不超过 Alice 的余额。

如果由于任何原因（错误或恶意），任何数据不符合这些约束，它将在证明的这一部分显现出来。

例如，如果有人试图作弊，向 Bob 转账 1 STRK 而不从 Alice 的账户中扣减，那么两个约束将被违反：

• 约束 1 将被违反，因为 Alice 和 Bob 的初始余额总和（$A+B$）将不等于他们最终余额的总和（$D+E$）。

• 约束 3 也将被违反，因为 Alice 的初始余额减去转账金额（$A-C$）将不等于她的最终余额（$D$）。

如果某个执行步骤无效，它将不符合已定义的约束

Prover 完成所有交易所有步骤的记录后，我们现在有一个很长的数字序列，代表我们想要处理的数据。执行步骤的有效性通过它们与已定义约束的一致性来确认。如果无效交易或步骤混入了这个序列，它与约束的不一致将是明显的。然而，这种不一致仅会在序列中特定的相关位置显现。

就这些吗？

我们能确保检测到隐藏在一批 100 万笔交易中数以百万计（甚至数十亿）步骤中的单个无效步骤吗？还不能。为此，我们需要更多的数学。

扩展数据，放大错误

我们的 STARK 证明现在由一个很长的数字序列组成，这些数字代表我们正在处理的批次中所有交易的执行步骤。如果这些执行步骤中有任何一个不遵守给定的约束，它将在证明的相应部分被检测到。但如果我们处理 100 万笔交易，每笔交易涉及多个执行步骤（比如平均一千个），那么我们就有一个包含 10 亿个执行步骤的证明。我们得非常幸运才能抓住一个错误。它很容易被忽视。

为了使即使是单个错误也能突出并被注意到，我们的下一步将是放大和扩展数据。这将通过这样一种方式完成：使无效步骤将其与约束的不一致性传播到证明更远的地方。

校验位

这个阶段可以被认为是校验位的一个非常复杂的版本。将校验位视为长标识号码的内置安全方法，比如在书籍（ISBN）、汽车（VIN）或护照上找到的那些。为了防止拼写错误或数字交换，系统通过一个特定的数学公式运行主要数字串。该计算的结果作为“校验位”添加到数字的末尾。如果其中一个数字被误输入，公式将不匹配校验位，从而指示错误。

例如：假设 ID 号码的校验位公式是所有数字之和除以 10 后的余数。

如果我的身份证号码是 $123456$，那么 $1+2+3+4+5+6=21$。$21$ 除以 $10$ 余数为 $1$。这个 $1$ 就是校验位。因此，完整的身份证号码将是 $123456-1$。

它是如何捕捉错误的？

如果我输入了一个错误的数字，校验位在数学上就不匹配。例如，如果我不小心输入了 $123455-1$，就会出错。因为 $1+2+3+4+5+5=20$，校验位应该是 $0$，而不是 $1$。数学不匹配。

当正确输入数字时，校验位与我们对该数字运行的数学运算一致。当输入错误的数字时，校验位与之不一致。

这个过程不会告诉我哪个数字错了，但它会告诉我某个地方有错误。

当然，这是一个简化的例子，用于解释捕捉一串数字中错误的基本方法。对于 STARK 处理的数据规模——通常数以亿计的步骤——我们需要一个更强大、更复杂、更安全的方法版本。

为了实现这一点，我们以精心设计的模式添加许多这样的“校验位”。对于阅读本文的数学家和工程师，我们使用具有理想特性的纠错码。例如，我们可能会计算诸如：

• 序列中所有数字的总和

• 每第三个数字的总和

• 所有偶数的总和

• 序列前半部分的总和

• 等等

在这个过程结束时，我们证明的数字序列将同时包含正在处理的交易数据和随后附加的校验位。值得注意的是，附加的校验位序列比交易数据长得多。

我们的 STARK 证明准备好了吗？

到目前为止，Prover 通过记录执行步骤、指示它们与约束的一致性和应用纠错方法来暴露无效步骤（如果存在），已经处理了所有交易数据。然而，我们的目标是处理大量交易，而且我们的目标是尽可能确定它们都是有效的。要确保它们都是有效的，还有更多工作要做。

检查校验位

就像我们将约束应用于交易步骤一样，我们现在可以应用额外的数学检查来验证附加的值（这些复杂的校验位）也满足某些约束。例如，我们可以检查表示所有数字之和的条目（即校验位）是否等于所有数字前半部分之和的条目加上所有数字后半部分之和的条目。它们应该对应并保持一致，如果不满足此约束，我们将知道证明中某处有错误。我们可以以各种模式在放大数据的不同部分应用此类约束。

这个阶段可以检查的另一个例子：回想一下我们检查从 Alice 到 Bob 转账 1 STRK 的例子。该转账包括验证 Alice 和 Bob 初始余额、转账金额、更新余额等的执行步骤。

现在，假设我们正在处理 100 万笔交易，所有这些交易都是许多不同方之间不同金额的转账。对于 100 万笔转账，我们将有 100 万个记录每个执行步骤的条目：

• 发送方初始余额的 100 万个条目（我们称它们为 $a1$、$a2$、$a3$ 等）

• 接收方初始余额的 100 万个条目（我们称它们为 $b1$、$b2$、$b3$ 等）

• 转账金额的 100 万个条目（我们称这些为 $c1$、$c2$、$c3$ 等）

• 发送方更新余额的 100 万个条目（$d1$、$d2$、$d3$ 等）

• 接收方更新余额的 100 万个条目（$e1$、$e2$、$e3$ 等）

• 等等

每笔转账必须满足适用于我们检查的第一笔交易（即 Alice 向 Bob 转账 1 STRK）时的相同约束。例如：

• 发送方和接收方的初始余额总和（$A+B$）必须等于他们最终余额的总和（$D+E$）。

• 发送方的初始余额减去转账金额（$A-C$）必须等于他们的最终余额（$D$）。

• 等等。

这些约束将适用于转账 1、转账 2、转账 3，以此类推，适用于所有 100 万笔转账。

此外，在处理每笔转账的所有步骤并附加其校验位之后，我们现在可以将相同的约束应用于这些校验位。如果某些约束可以单独验证每笔转账的有效性，那么它们就可以验证总共 100 万笔转账的有效性。我们首先对所有执行步骤的条目求和。例如：

• $a'$ 将是所有发送账户初始余额的总和（$a1 + a2 + a3 + \dots$）

• $b'$ 将是所有接收账户初始余额的总和（$b1 + b2 + b3 + \dots$）

• $d'$ 将是所有发送账户更新余额的总和（$d1 + d2 + d3 + \dots$）

• $e'$ 将是所有接收账户更新余额的总和（$e1 + e2 + e3 + \dots$）

现在，所有转账中所有发送方和接收方的总余额之和必须等于转账后他们最终余额的总和，用数学表示就是：$a' + b' = d' + e'$！

就像我们对单笔交易的步骤应用约束一样，我们可以对附加的校验位本身应用更多约束。如果任何交易中的任何步骤不符合约束，它将导致每个步骤类别（发送方初始余额、发送方最终余额等）的总和出现不一致。

使长序列变得更长

此时，STARK 证明包含我们正在证明的所有交易的数据，以及我们对其应用数学运算后产生的附加校验位。Prover 非常努力地处理每笔交易；实际上，比我们直接在链上执行这些交易所需的工作量还要大。为什么要这么麻烦？

记住，我们的目标是以尽可能少的链上计算工作来提交新交易，同时验证其有效性。记住，我们想省去所有老师批改所有试卷以及所有节点重新执行所有交易的麻烦。我们的目标是让公众能够以相当于处理 6 笔交易的计算工作量来验证 100 万笔交易。

添加的冗余信息会捕获原始序列中一个微小的错误，例如无效的转账金额，并反复将其与大量后续计算和以各种模式存在的条目混合。结果，一个小的不一致性传播到整个证明，变得放大且不可能被忽略。

如果 Prover 想要作弊而不被抓住，它就需要开始更改更多的条目，并且要使得所有这些更改保持结果条目的一致性会变得越来越困难。当我们完成时，“所有数字之和”的条目是否仍然等于“前半部分之和”加上“后半部分之和”？

对于我们使用的特定校验位（对于工程师，我们使用基于低次多项式的 Reed-Solomon 码），我们可以在数学上证明，即使在一个条目上作弊，也会导致无法自圆其说。我们将检查的几乎每个校验位组合都不会对齐。

我们还没完成

所以现在我们的证明是一个极长的数字序列，是时候缩小它了。

折叠证明

我们的 Prover 一直在极努力地处理大量交易。计算工作花费在记录交易的执行步骤、验证其有效性、扩展其数据以及放大无效步骤（如果存在）以使它们在证明中可检测到。证明中任何地方没有不一致性，则表明没有错误或恶意行为混入这个批次。

我们现在拥有的证明极其庞大。现在，就像我们可以使用数学扩展步骤的原始序列一样，我们可以使用更多的数学来缩小我们最终得到的序列。

减少证明长度

这部分数学超出了本文的范围，但在这个阶段需要理解的重要事情是，我们使用数学来压缩我们收到的长数字序列，并且，就像到目前为止的所有先前步骤一样，它的完成方式有助于验证是否有任何错误混入了我们的证明。我们可以将这个称为“折叠”过程。

有多种方法可以“折叠”数字序列，Prover 会用其中一种方式“折叠”它生成的长序列。然后它一遍又一遍地重复这个步骤，每次缩小序列。每次折叠都会创建一个新的、更短的序列，由总结前一个序列的条目组成。在每个步骤，新条目是折叠序列中 10 个数字的“和”（这里“和”是广义的数学操作）。例如，如果初始序列有 10 亿个数字长，那么第一次折叠后大小将变为十分之一（1 亿），然后每次连续折叠都会再缩小 10 倍。经过 8 次折叠，从 10 亿长度开始的序列将变成 10 个数字长。

这种折叠、减少证明长度并检查最终结果的过程是一种称为 FRI（快速 Reed-Solomon IOPP）的数学协议。FRI 从一个次数的多项式转移到另一个次数减半的多项式，使用的点数减半。（对于那些熟悉快速傅里叶变换的人，我们“折叠”了该算法第一步的两个子序列；你需要阅读数学论文以了解更多细节）。

确保有效性

在这个“折叠”过程中，我们不仅减少了证明的长度，而且还在验证证明不包含任何错误。当 Prover 正确地写下交易数据以及我们对其应用的数学时，结果数字将形成一个模式。这个呈现出的模式可以被想象成一个存在于十亿维空间中的百万维雪花。这不是我们可以理解的东西，但数学让我们可以抽象地处理它。当我们折叠这个数字序列，或者说这个百万维雪花时，所有可能的折叠模式都会导致少数几个最终数字全部相等。换句话说，在一个所有交易和执行步骤都有效的证明中，一旦 Prover 一遍又一遍地完成序列折叠，最终结果中的所有 10 个数字都会神奇地变得相同。Verifier 可以轻松读取这 10 个数字并检查它们是否相同。这就是为我们省去重新执行所有 100 万笔交易麻烦的简便测试。

至少，如果你从一个真实的雪花开始，即如果 Prover 没有试图作弊，就会发生这种情况。但如果 Prover 没有诚信运作呢？

如果 Prover 被 Darth Vader 操作

到目前为止，我们已经解释了由像 Luke Skywalker 这样的人操作的诚实 Prover 会如何工作。但如果 Darth Vader 操作 Prover 呢？Vader 先生会知道 Verifier 只会抽样少量信息。那么，为什么不按照他的意愿随意填写序列中的数字，使其看起来像是对于将被检查的特定部分满足约束条件呢？毕竟，如果你从头开始填写一个类似数独的谜题，有很多种不同的填写方式。我们有没有办法揭露执行这种恶意行为的 Prover？我们有。

还记得从数字序列中呈现出的多维雪花模式吗？如果 Prover 试图作弊，它将无法创建那个神奇的雪花，因为它需要一个诚实的、一致的序列。没有整个序列的一致性，我们得不到那个雪花。然后，当 Prover 开始折叠过程时，它折叠的不是那个一致的雪花，而是一个变形丑陋、看起来不像百万维雪花的东西。折叠过程几乎总会导致一个糟糕的结果，数字不会全部相同。这个结果将表明证明中的某些内容——无论是步骤还是计算——是无效的。这就是折叠过程如何减少证明长度以及帮助我们确保证明有效性的方式。

STARK 证明准备好了吗？

在证明准备好发送给 Verifier 检查之前，还有一个小步骤。有趣的是，这个步骤对于使 STARK 具有后量子安全性至关重要。猜猜是什么？

我们的 Prover 已经计算了一大笔交易，记录了它们的步骤，验证了它们的有效性，然后对它们进行了“折叠”。现在是将证明密封并发送给 Verifier 的时候了！

哈希处理

Prover 生成了一个巨大的数据序列：已处理的交易及其 STARK 计算。但是 Prover 将所有信息记录在哪里？如果 Verifier 可以通过抽样来验证这些数据，那么将所有数据都提交到链上是没有意义的。与其运行所有这些复杂的计算，然后要求链上节点处理所有这些过多的数据，不如一开始就在本地处理 100 万笔交易更简单。我们也不能信任 Prover 会把它写下来，因为一旦 Verifier 查询证明中的样本条目，Prover 可以更改条目以使其看起来一致。在将数据提交给 Verifier 检查之前，我们需要将数据密封。

在这个阶段，我们要求 Prover 使用一种称为“Merkle 树”的加密指纹方法来提交一个数字序列。这种技术迫使 Prover 提交一个以后无法更改的数字序列。当从提交的序列中读取信息时，有一种有效的加密方法可以确保我们读取的是正确的信息，而不是 Prover 事后更改的内容。这是我们做出密码学假设的地方，也是唯一的地方——我们使用的哈希是安全的。其余所有内容都由数学证明，没有任何假设。

后量子安全性

在后量子世界中，许多密码学协议，包括一些零知识证明，可能会变得脆弱。STARK 有一个重要的优势：它们仅依赖哈希函数进行承诺，而哈希函数是后量子安全的。这使得 STARK 天生具有后量子安全性。相比之下，像 SNARK 这样的竞争性证明系统严重依赖椭圆曲线密码学，而椭圆曲线密码学容易受到量子攻击。STARK 独特地依赖数学而非复杂的密码学假设，这使得它们能够抵御量子威胁。

最后一步——验证证明和数据承诺

STARK Prover 现在生成了一个 STARK 证明。该证明证明了我们处理的交易，以及 Prover 对这些交易的正确处理。如果存在无效交易或恶意处理步骤，Verifier 将很容易检测到。

Prover 还生成了一个状态更新，代表所处理交易中涉及的所有账户的新状态。在这个阶段，STARK 证明和状态更新被发送到链上。链上的 Verifier 检查证明，一旦通过验证，Verifier 就指示链上可以接受新的状态更新。我们的过程完成了。

总结

总结一下，以下是 STARK 协议实现的目标：

• 处理并验证了大量交易，从而允许用结果的新状态更新链。

• 这个过程依赖于 Prover 完成计算的重活，留给 Verifier 较小的任务来检查 STARK 证明。

• Verifier 不会重新执行或处理交易数据。这意味着：

1. 该过程实现了可扩展性，因为可以在不重新执行交易的情况下接受大量数据上链。

2. 该过程实现了隐私性，因为 Verifier 可以依赖 STARK 证明，而无需访问底层数据来确认有效性。

StarkWare 自 2018 年以来一直使用 STARK 来驱动区块链。虽然最初专注于实现大规模扩展，但 STARK 技术现在也被用于在链上提供强大的隐私解决方案。此外，ZK-STARK 也可以支持后量子安全要求。提供这些能力使 STARK 成为区块链未来的强大基础。

如果你想用这项技术进行构建，我们随时准备提供帮助。联系我们！

如果你想更深入地了解 STARK 和 ZK，订购 Eli 的书籍。

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