您数字货币与 Web3的直通车

Vitalik新作：探索Circle STARKs

07,242024(UTC)LikeDislikeComment

原文标题：《ExploringcircleSTARKs》

撰文：VitalikButerin，以太坊联合创始人

编译：Chris，TechubNews

想要理解这篇文章的前提是你们已经了解了SNARKs和STARKs的基本原理。如果你对此不太熟悉，建议你先阅读本文的前几部分来了解相关基础知识。

近年来，STARKs协议设计的趋势是转向使用较小的字段。最早期的STARKs生产实现使用的是256位字段，即对大数字（如21888...95617）进行模运算，这使得这些协议与基于ellipticcurve的签名兼容。但是这种设计的效率比较低，一般情况下，处理计算这些大数字并没有实际的用途，还会浪费很多的算力，比如处理X（代表某个数字）和处理四倍的X，处理X只需要九分之一的计算时间。为了解决这个问题，STARKs开始转向使用更小的字段：首先是Goldilocks，然后是Mersenne31和BabyBear。

这种转变提升了证明速度，比如Starkware能够在一台M3笔记本电脑上每秒证明620,000个Poseidon2哈希值。这意味着，只要我们愿意信任Poseidon2作为哈希函数，那么就可以解决开发高效的ZK-EVM中的难题。那么这些技术是如何工作的？这些证明如何在较小的字段上建立？这些协议与Binius等解决方案相比如何？本文将探讨这些细节，特别关注一种名为CircleSTARKs（在Starkware的stwo、Polygon的plonky3以及我自己在Python中实现的版本）的方案，这种方案具有与Mersenne31字段兼容的独特属性。

在创建基于哈希的证明（或任何类型的证明）时，一个非常重要的技巧是通过对多项式在随机点的评估结果进行证明，能够间接验证多项式的性质。这种方法可以大大简化证明过程，因为在随机点的评估通常比处理整个多项式要容易得多。

例如，假设一个证明系统要求你生成一个对多项式的commitment，A，必须满足A^3(x)+x-A(\omega*x)=x^N（ZK-SNARK协议中一种非常常见的证明类型）。协议可以要求你选择一个随机坐标?并证明A(r)+r-A(\omega*r)=r^N。然后反推A(r)=c，你证明了Q=\frac{A-c}{X-r}是一个多项式。

如果你事先了解了协议的细节或内部机制，你可能会找到方法绕过或破解这些协议。接下来可能会提到具体的操作或方法来实现这一点。比如，为了满足A(\omega*r)方程，你可以设置A(r)为0，然后让A成为经过这两个点的直线。

为了防止这些攻击，我们需要在攻击者提供了A之后再选择r（Fiat-Shamir是一种用于增强协议安全性的技术，通过将某些参数设为某种哈希值来避免攻击。选择的参数需要来自一个足够大的集合，以确保攻击者无法预测或猜测这些参数，从而提高系统的安全性。

在基于ellipticcurve的协议和2019年时期的STARKs中，这个问题很简单：我们所有的数学运算都在256位的数字上进行，因此我们可以将r选择为一个随机的256位数字，这样就可以了。然而，在较小字段上的STARKs中，我们遇到了一个问题：只有大约20亿种可能的r值可以选择，因此一个想要伪造证明的攻击者只需要尝试20亿次，虽然工作量很大，但对于一个下定决心的攻击者来说，还是完全可以做到的！

这个问题有两个解决方案：

执行多次随机检查的方法是最简单有效的：与其在一个坐标上进行检查，不如在四个随机坐标上重复检查。这在理论上是可行的，但存在效率问题。如果你处理的是一个度数小于某个值的多项式，并且在某个大小的域上进行操作，攻击者实际上可以构造看起来在这些位置上都很正常的恶意多项式。因此，他们能否成功破坏协议是一个概率性问题，因此需要增加检查的轮数，以增强整体的安全性，确保能够有效防御攻击者的攻击。

这引出了另一个解决方案：扩展域，扩展域类似于复数，但它是基于有限域的。我们引入一个新的值，记作α\alphaα，并声明其满足某种关系，比如α2=somevalue\alpha^2=\text{somevalue}α2=somevalue。通过这种方式，我们创建了一个新的数学结构，能够在有限域上进行更复杂的运算。在这种扩展域中，乘法的计算变为使用新值α\alphaα的乘法。我们现在可以在扩展的域中操作值对，而不仅仅是单个数字。比如，如果我们在Mersenne或BabyBear这样的字段上工作，这样的扩展允许我们有更多的值选择，从而提高安全性。为了进一步提高字段的大小，我们可以重复应用相同的技术。由于我们已经使用了α\alphaα，所以我们需要定义一个新的值，这在Mersenne31中表现为选择α\alphaα使得α2=somevalue\alpha^2=\text{somevalue}α2=somevalue。

代码（你可以用Karatsuba改进它）

通过扩展域，我们现在有了足够多的值来选择，满足我们的安全需求。如果处理的是度数小于ddd的多项式，每轮可以提供104位的安全性。这意味着我们有足够的安全保障。如果需要达到更高的安全级别，比如128位，我们可以在协议中加入一些额外的计算工作，以增强安全性。

扩展域仅在FRI（FastReed-SolomonInteractive）协议和其他需要随机线性组合的场景中实际使用。大部分的数学运算仍然在基础字段上进行，这些基础字段通常是模ppp或qqq的字段。同时，几乎所有哈希的数据都是在基础字段上进行的，因此每个值只需哈希四字节。这样做可以利用小字段的高效性，同时在需要进行安全性增强时，可以使用更大的字段。

在构建SNARK或STARK时，第一步通常是arithmetization。这是将任意计算问题转化为一个方程，其中某些变量和系数是多项式。具体来说，这个方程通常会看起来像P(X,Y,Z)=0P(X,Y,Z)=0P(X,Y,Z)=0，其中P是一个多项式，X、Y和Z是给定的参数，而求解器需要提供X和Y的值。一旦有了这样的方程，该方程的解就对应于底层计算问题的解。

要证明你有一个解，你需要证明你所提出的值确实是合理的多项式（而不是分数，或者在某些地方看起来像一个多项式，而在其他地方却是不同的多项式，等等），并且这些多项式具有一定的最大度数。为此，我们使用了一个逐步应用的随机线性组合技巧：

本质上，发生的事情是B隔离偶数系数A，和?隔离奇数系数。给定B和C，你可以恢复原始多项式A：A(x)=B(x^2)+xC(x^2)。如果A的度数确实小于2^{20}，那么B和C的度数将分别为A的度数和A的度数减去1。因为偶次项和奇次项的组合不会增加度数。由于D是B和C的随机线性组合，D的度数也应为A的度数，这使得你可以通过D的度数来验证A的度数是否符合要求。

首先，FRI通过将证明多项式度数为d的问题简化为证明多项式度数为d/2的问题，从而简化了验证过程。这个过程可以重复多次，每次都将问题简化一半。

FRI的工作原理是重复这个简化过程。例如，如果你从证明多项式的度数为d开始，通过一系列步骤，你将最终证明多项式的度数为d/2。每次简化后，生成的多项式的度数逐步减小。如果某个阶段的输出不是预期的多项式度数，那么这一轮的检查将失败。如果有人试图通过这种技术推送一个不是度数为d的多项式，那么在第二轮输出中，其度数将有一定的概率不符合预期，第三轮中会更有可能出现不符合的情况，最终的检查将失败。这种设计可以有效地检测并拒绝不符合要求的输入。如果数据集在大多数位置上等于一个度数为d的多项式，这个数据集有可能通过FRI验证。然而，为了构造这样一个数据集，攻击者需要知道实际的多项式，因此即使有轻微缺陷的证明也表明证明者能够生成一个“真实”的证明。

让我们更详细地了解一下这里发生的情况，以及使这一切正常运作所需的属性。在每一步中，我们将多项式的次数减少一半，同时也将点集（我们关注的点的集合）减少一半。前者是使FRI（FastReed-SolomonInteractive）协议能够正常工作的关键。后者则使得算法运行速度极快：由于每一轮的规模比上一轮减少一半，总的计算成本是O(N)，而不是O(N*log(N))。

为了实现域的逐步减少，使用了一个二对一映射，即每个点都映射到两个点中的一个。这种映射允许我们将数据集的大小减少一半。这个二对一映射的一个重要优点是它是可重复的。也就是说，当我们应用这个映射时，得到的结果集仍然保留了相同的属性。假设我们从一个乘法子群（multiplicativesubgroup）开始。这个子群是一个集合S，其中每个元素x都有其倍数2x也在集合中。如果对集合S进行平方操作（即将集合中的每个元素x映射到x^2），新的集合S^2也会保留同样的属性。这种操作允许我们继续减少数据集的大小，直到最终只剩下一个值。虽然理论上我们可以将数据集缩小到只剩一个值，但在实际操作中，通常会在到达一个较小的集合之前就停止。

你可以将这个操作想象成一个将圆周上的一条线（例如，线段或弧）沿圆周伸展的过程，使它绕圆周旋转两圈。例如，如果一个点在圆周上位于x度的位置，那么在经过这个操作后，它会移动到2x度的位置。圆周上的每个点从0到179度的位置，都有一个对应的点在180到359度的位置，这两个点会重合。这意味着，当你将一个点从x度映射到2x度时，它会与一个位于x+180度的位置重合。这个过程是可以重复的。也就是说，你可以多次应用这个映射操作，每次都将圆周上的点移动到它们的新位置。

为了使映射技术有效，原始乘法子群的大小需要具有大的2的幂作为因子。BabyBear是一个具有特定模数的系统，其模数为某个值，使得其最大乘法子群包含所有非零值，因此子群的大小为2k−1（其中k是模数的位数）。这种大小的子群非常适合上述技术，因为它允许通过重复应用映射操作来有效地减少多项式的度数。在BabyBear中，你可以选择大小为2^k的子群（或者直接使用整个集合），然后应用FRI方法将多项式的度数逐步减少到15，并在最后检查多项式的度数。这种方法利用了模数的性质和乘法子群的大小，使得计算过程非常高效。Mersenne31是另一个系统，其模数为某个值，使得乘法子群的大小为2^31-1。在这种情况下，乘法子群的大小只有一个2的幂作为因子，这使得它只能被除以2一次。之后的处理不再适用上述技术，也就是说，无法像BabyBear那样使用FFT进行有效的多项式度数减少。

Mersenne31域非常适合在现有的32位CPU/GPU操作中进行算术运算。因为其模数的特性（例如2^{31}-1）使得很多运算可以利用高效的位操作来完成：如果两个数字相加的结果超过了模数，可以通过将结果与模数进行位移操作来减小到合适的范围。位移操作是一种非常高效的运算。乘法运算中，可以使用特定的CPU指令（通常称为高位位移指令）来处理结果。这些指令可以高效地计算乘法的高位部分，从而提高了运算的效率。在Mersenne31域中，由于上述特性，算术运算比在BabyBear域中快约1.3倍。Mersenne31提供了更高的计算效率。如果可以在Mersenne31域中实现FRI，这将显著提升计算效率，使得FRI的应用变得更加高效。

这就是CircleSTARKs的巧妙之处，给定一个质数p，可以找到一个大小为p的群体，该群体具有类似的二对一特性。这个群体是由所有满足某些特定条件的点组成的，例如，x^2modp等于某个特定值的点集。

这些点遵循一种加法规律，如果你最近做过三角学或复数乘法的相关内容，你可能会觉得这种规律很熟悉。

(x_1,y_1)+(x_2,y_2)=(x_1x_2-y_1y_2,x_1y_2+x_2y_1)

双倍形式是：

2*(x,y)=(2x^2-1,2xy)

现在，让我们专注于这个圆上奇数位置上的点：

首先，我们将所有点收敛到一条直线上。我们在常规FRI中使用的B(x²)和C(x²)公式的等效形式是：

f_0(x)=\frac{F(x,y)+F(x,-y)}{2}

然后，我们可以进行随机线性组合，得到一个一维的P(x)，这个多项式在x线的一个子集上定义：

从第二轮开始，映射发生了变化：

f_0(2x^2-1)=\frac{F(x)+F(-x)}{2}

这个映射实际上每次都将上述集合的大小减少一半，这里发生的事情是，每个x在某种意义上代表了两个点：(x,y)和(x,-y)。而(x→2x^2-1)就是上面的点倍增法则。因此，我们将圆上两个相对点的x坐标，转换为倍增后的点的x坐标。

例如，如果我们取圆上第二个从右边数的值2，并应用映射2→2(2^2)-1=7，我们得到的结果是7。如果我们回到原始圆上，(2,11)是从右边数第三个点，所以将其倍增后，我们得到的是从右边数第六个点，即(7,13)。

这本可以在二维空间中完成，但在一维空间中操作会使过程更高效。

一种与FRI密切相关的算法是FFT，它将一个度小于n的多项式的n个评估值转换为该多项式的n个系数。FFT的过程与FRI相似，不同之处在于，FFT在每一步中不是生成随机线性组合f_0和f_1，而是递归地对它们进行半大小的FFT，并将FFT(f_0)的输出作为偶数系数，将FFT(f_1)的输出作为奇数系数。

Circlegroup也支持FFT，这种FFT的构造方式与FRI类似。然而，一个关键区别在于，CircleFFT（和CircleFRI）所处理的对象并不严格是多项式。相反，它们是数学上称为Riemann-Rochspace的东西：在这种情况下，多项式是模圆的(x^2+y^2-1=0）。也就是说，我们将x^2+y^2-1的任何倍数视为零。另一种理解方式是：我们只允许y的一次幂：一旦出现y^2项，我们就将其替换为1-x^2。

这还意味着，CircleFFT输出的系数并不像常规FRI那样是单项式（例如，如果常规FRI输出为[6,2,8,3]，那么我们知道这意味着P(x)=3x^3+8x^2+2x+6）。相反，CircleFFT的系数是特定于CircleFFT的基础：{1,y,x,xy,2x^2-1,2x^2y-y,2x^3-x,2x^3y-xy,8x^4-8x^2+1...}

好消息是，作为开发者，您几乎可以完全忽略这一点。STARKs从不要求您了解系数。相反，您只需将多项式作为在特定域上的一组评估值进行存储。唯一需要使用FFT的地方是进行（Riemann-Roch空间的类似）低度扩展：给定N个值，生成k*N个值，这些值都在同一多项式上。在这种情况下，您可以使用FFT生成系数，将（k-1)n个零附加到这些系数上，然后使用逆FFT获取更大的评估值集。

CircleFFT不是唯一的特殊FFT类型。EllipticcurveFFT更为强大，因为它们可以在任何有限域（素数域、二进制域等）上工作。然而，ECFFT更复杂且效率较低，因此由于我们可以在p=2^{31}-1上使用CircleFFT，所以我们选择使用它。

从这里开始，我们将深入一些更为晦涩的细节，实现CircleSTARKs实现的细节与常规STARKs有所不同。

在STARK协议中，常见的一种操作是对特定点进行商运算，这些点可以是故意选择的，也可以是随机选择的。例如，如果你想证明P(x)=y，可以通过以下步骤进行：

计算商：给定多项式P(x)和常数y，计算商Q={P-y}/{X-x}，其中X是选择的点。

证明多项式：证明Q是一个多项式，而不是一个分数值。通过这种方式，证明了P(x)=y是成立的。

此外，在DEEP-FRI协议中，随机选择评估点是为了减少Merkle分支的数量，从而提高FRI协议的安全性和效率。

在处理circlegroup的STARK协议时，由于没有可以通过单一点的线性函数，需要采用不同的技巧来替代传统的商运算方法。这通常需要使用circlegroup特有的几何性质来设计新的算法。

在circlegroup中，你可以构造一个切线函数，使其在某个点(P_x,P_y)切于该点，但这个函数会通过该点具有重数2，也就是说，要使一个多项式成为该线性函数的倍数，它必须满足比仅在该点为零更严格的条件。因此，你不能仅仅在一个点上证明评估结果。那么我们该如何处理呢？

我们不得不接受这个挑战，通过在两个点上进行评估来证明，从而添加一个我们不需要关注的虚拟点。

线函数：ax+by+c。如果你把它变成一个方程，强制它等于0，那么你可能会把它认出是高中数学中所谓的标准形式中的一条线。

如果我们有一个多项式P在x_1处等于y_1，在x_2处等于y_2，我们可以选择一个插值函数L，它在x_1处等于y_1，在x_2处等于y_2。这可以简单地表示为L=\frac{y_2-y_1}{x_2-x_1}\cdot(x-x_1)+y_1。

然后我们证明P在x_1处等于y_1，在x_2处等于y_2，通过减去L（使得P-L在这两个点上都为零），再通过L（即x_2-x_1之间的线性函数）除以L来证明商Q是一个多项式。

在STARK中，你试图证明的多项式方程通常看起来像是C(P(x),P({next}(x)))=Z(x)⋅H(x)，其中Z(x)是一个在整个原始评估域上都等于零的多项式。在常规STARK中，这个函数就是x^n-1。在圆形STARK中，相应的函数是：

Z_1(x,y)=y

Z_2(x,y)=x

Z_{n+1}(x,y)=(2*Z_n(x,y)^2)-1

注意，你可以从折叠函数中推导出消失多项式：在常规STARK中，你重复使用x→x^2，而在圆形STARK中，你重复使用x→2x^2-1。不过，对于第一轮，你会进行不同的处理，因为第一轮是特殊的。

在STARKs中，多项式的评估通常不是按照“自然”顺序排列的（例如P(1),P(ω),P(ω2),…,P(ωn−1)，而是按照我称之为逆位序（reversebitorder）的顺序排列的：

P(\omega^{\frac{3n}{8}})

如果我们设置n=16，并且只关注我们在哪些ω的幂次上进行评估，那么列表看起来如下：

{0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}

这种排序具有一个关键属性，即在FRI评估过程中早期分组在一起的值在排序中会相邻。例如，FRI的第一步将x和-x分组。在n=16的情况下，ω^8=-1，这意味着P(ω^i))和(P(-ω^i)=P(ω^{i+8})\)。正如我们所见，这些正是紧挨在一起的对。FRI的第二步将P(ω^i)、P(ω^{i+4})、P(ω^{i+8})和P(ω^{i+12})分组。这些正是我们看到的四个一组的情况，以此类推。这样做使得FRI更加节省空间，因为它允许你为折叠在一起的值（或者，如果你一次折叠k轮，则为所有2^k个值）提供一个Merkle证明。

在circleSTARKs中，折叠结构略有不同：在第一步中，我们将(x,y)与(x,-y)配对；在第二步中，将x与-x配对；在随后的步骤中，将p与q配对，选择p和q使得Q^i(p)=-Q^i(q)，其中Q^i是重复x→2x^2-1i次的映射。如果我们从圆上的位置来考虑这些点，那么在每一步中，这看起来就像是第一个点与最后一个点配对，第二个点与倒数第二个点配对，依此类推。

为了调整反向位序以反映这种折叠结构，我们需要反转除了最后一位的每一位。我们保留最后一位，并用它来决定是否翻转其他位。

一个大小为16的折叠反向位序如下：

{0,15,8,7,4,11,12,3,2,13,10,5,6,9,14,1}

如果你观察上一节中的圆，你会发现0、15、8和7这几个点（从右侧开始逆时针方向）是(x,y)、(x,-y)、(-x,-y)和(-x,y)的形式，这正是我们所需要的。

在CircleSTARKs（以及一般的31位素数STARKs）中，这些协议非常高效。一个在CircleSTARK中被证明的计算通常涉及几种类型的计算：

1.原生算术：用于业务逻辑，例如计数。

2.原生算术：用于加密学，例如像Poseidon这样的哈希函数。

3.查找参数：一种通用的高效计算方法，通过从表中读取值来实现各种计算。

效率的关键衡量标准是：在计算跟踪中，你是充分利用了整个空间来进行有用的工作，还是留下了大量的空闲空间。在大型字段的SNARKs中，往往存在大量的空闲空间：业务逻辑和查找表通常涉及对小数字的计算（这些数字往往小于N，N是一个计算步骤的总数，因此在实践中小于2^{25}），但你仍然需要支付使用大小为2^{256}位字段的成本。在这里，字段的大小为2^{31}，所以浪费的空间并不大。为SNARKs设计的低算术复杂度哈希（例如Poseidon）在任何字段中都充分利用了跟踪中每个数字的每一位。

Binius是比CircleSTARKs更好的解决方案，因为它允许你混合不同大小的字段，从而实现更高效的位打包。Binius还提供了在不增加查找表开销的情况下进行32位加法的选项。然而，这些优势的（在我看来）代价是会使概念变得更加复杂，而CircleSTARKs（以及基于BabyBear的常规STARKs）在概念上则相对简单得多。

CircleSTARKs对开发者来说并没有比STARKs复杂。在实现过程中，以上提到的三个问题基本上就是与常规FRI的区别。尽管CircleFRI操作的多项式背后的数学非常复杂，理解和欣赏这些数学需要一些时间，但这种复杂性实际上被隐藏得不那么显眼，开发者不会直接感受到。

理解CircleFRI和CircleFFTs也可以成为理解其他特殊FFTs的途径：最值得注意的是二进制域FFTs，如Binius和之前的LibSTARK使用的FFTs，还有一些更复杂的构造，如ellipticcurveFFTs,这些FFTs使用少对多的映射，能够与ellipticcurve点运算很好地结合。

结合Mersenne31、BabyBear和像Binius这样的二进制域技术，我们确实感觉我们正在接近STARKs基础层的效率极限。在这一点上，我预计STARK的优化方向将会有以下几个重点：

对哈希函数和签名等进行最大化效率的算术化：将哈希函数和数字签名等基本的密码学原语优化为最高效的形式，使其在STARK证明中使用时能够达到最佳性能。这意味着要针对这些原语进行专门的优化，以减少计算量和提高效率。

进行递归构造以启用更多并行化：递归构造指的是将STARK证明过程递归地应用于不同的层级，从而提高并行处理能力。通过这种方式，可以更高效地利用计算资源，加速证明过程。

算术化虚拟机以改善开发者体验：对虚拟机进行算术化处理，使得开发者在创建和运行计算任务时可以更加高效、简单。这包括对虚拟机进行优化，以便于在STARK证明中使用，改善开发者在构建和测试智能合约或其他计算任务时的体验。