任意计算的STARKs

Question

我最近一直在读维塔利克的系列“斯塔克斯”( 1，2和3.)。对于像我这样的门外汉来说，这是一个很好的，也是可以理解的。

残酷地总结了我目前对

的理解

Vitalik概述了以下技术来证明某些任意计算的正确性：

• 用多项式P(x)的值对计算轨迹进行编码。
• 定义一个约束检查多项式C(z)，这样，如果计算正确，我们将对计算范围内的所有x值进行C(F(x)) = 0。我将使用Q来表示合成多项式C(F(x))的程度。(通常，C可以采用多个参数，例如，当我们需要Fibonacci序列时，C(z1, z2, z3) = z3 - z2 - z1检查Fibonacci序列的正确计算)。
• 因为C(F(x))必须是1..N中所有x的0，所以我们定义了Z(x) = (x - 1) (x - 2) .. (x - N)：C(F(x))必须等于Z(x)与某些D(x)相乘。D相对容易从C(F(_))和P中计算。
• 验证程序使用M (例如，M = 100 Q)提交P和D的第一个D35值的表。
• 验证器在多个值x上探测表，在不同的点检查C(P(x)) = Z(x) D(x)，以确信计算是正确执行的。

到目前一切尚好。我想我懂了。Vitalik详细解释了使用约束检查多项式可以完成的两种特定检查：

• 范围检查(0 <= P(x) <= H适用于1..N中的所有x，带有C(z) = z (z - 1) (z - 2) .. (Z - H) ).
• Fibonacci计算，使用C(z1, z2, z3) = z3 - z2 - z1。

我对推广

的随机尝试

可悲的是，维塔利克的解释到此为止，还没有解释如何将斯塔克斯推广为证明任意计算。我对如何做到这一点有直觉，但我看不出如何能有效地完成它。

例如，我想我们可以定义两个“操作数多项式”L(x)和R(x)，然后：

• 要求P(x)为0或1，用于1..N中的所有x (这可以通过范围检查轻松完成，Vitalik已经解释了如何做)。
• 此外，在(1 - (P(L(x))P(R(x)))) - P(x) = 0中的所有x都需要1..N。在这样做时，我们要求每个P(x)都等于P(L(x)) NAND P(R(x))。由于任何逻辑电路都可以用NANDs来构造，所以L和R的适当选择应该使任何计算都可以证明。

然而，这个想法的最大问题是，P和约束检查多项式之间的组合的程度N^2是很大的，按D80的顺序排列。对于验证者来说，复杂性很快就会变得难以控制。

我接下来在哪里读？

我想知道我在哪里可以读懂如何定义一个约束检查多项式，它实际上可以验证任何计算。在我看来，整个“在随机位置访问内存”的过程非常棘手，我很想进一步学习。

Answer 1

你的方法当然是根据香农定理工作的。也许，通用计算的一个较少人工的模型是使用图灵机，其字母表为N符号。这允许我们免除P(x)，因为x的所有值都可以自然地落在我们的字母表中。然后，我们可以使用值x_{p,t}来表示图灵机磁带在p位置的符号。

为了使规则r在时间t的磁带位置p上的可验证执行，该规则告诉我们在磁带读取x时写入y_r(x)，然后通过s_r(x)移动磁带并执行规则r'_r(x)，我们可以为y_r(x)构造一个插值多项式，然后使用指示多项式\delta_i(x)创建验证多项式f_{r,t}(\mathbf x)=y_r(x_{p,t})-x_{p,t+1}+\sum_{i=1}^N\delta_i(x_{p,t})f_{i,t+1}(\mathbf x).

然而，在大多数计算中，对于Shannon模型和图灵模型，验证都会变得非常困难。这是因为我们试图写下一个多项式族，它验证了大量可能的计算过程，因此这个家族本身必须是巨大的。

实际上，STARKs最好用于验证验证多项式庞大的痕迹，这自然导致了整数加法、减法和乘法或离散集成员资格(有一些技巧可以应付递归计算)。即使在这些对表示友好的情况下，验证开销仍然可以是底层操作的重要倍数。