Vitalik 新作：探索 Circle STARKs

2024-07-25 00:07:40

原文標題：《 Exploring circle STARKs 》

撰文：Vitalik Buterin，以太坊聯合創始人

編譯：Chris，Techub News

想要理解這篇文章的前提是你們已經了解了 SNARKs 和 STARKs 的基本原理。如果你對此不太熟悉，建議你先閱讀本文的前幾部分來了解相關基礎知識。

近年來，STARKs 協議設計的趨勢是轉向使用較小的字段。最早期的 STARKs 生產實現使用的是 256 位字段，即對大數字（如 21888...95617）進行模運算，這使得這些協議與基於 elliptic curve 的籤名兼容。但是這種設計的效率比較低，一般情況下，處理計算這些大數字並沒有實際的用途，還會浪費很多的算力，比如處理 X（代表某個數字）和處理四倍的 X ，處理 X 只需要九分之一的計算時間。為了解決這個問題，STARKs 开始轉向使用更小的字段：首先是 Goldilocks ，然後是 Mersenne31 和 BabyBear 。

這種轉變提升了證明速度，比如 Starkware 能夠在一臺 M3 筆記本電腦上每秒證明 620,000 個 Poseidon2 哈希值。這意味着，只要我們愿意信任 Poseidon2 作為哈希函數，那么就可以解決开發高效的 ZK-EVM 中的難題。那么這些技術是如何工作的？這些證明如何在較小的字段上建立？這些協議與 Binius 等解決方案相比如何？本文將探討這些細節，特別關注一種名為 Circle STARKs （在 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 是一種用於增強協議安全性的技術，通過將某些參數設為某種哈希值來避免攻擊。選擇的參數需要來自一個足夠大的集合，以確保攻擊者無法預測或猜測這些參數，從而提高系統的安全性。

在基於 elliptic curve 的協議和 2019 年時期的 STARKs 中，這個問題很簡單：我們所有的數學運算都在 256 位的數字上進行，因此我們可以將 r 選擇為一個隨機的 256 位數字，這樣就可以了。然而，在較小字段上的 STARKs 中，我們遇到了一個問題：只有大約 20 億種可能的 r 值可以選擇，因此一個想要僞造證明的攻擊者只需要嘗試 20 億次，雖然工作量很大，但對於一個下定決心的攻擊者來說，還是完全可以做到的！

這個問題有兩個解決方案：

進行多次隨機檢查
擴展字段

執行多次隨機檢查的方法是最簡單有效的：與其在一個坐標上進行檢查，不如在四個隨機坐標上重復檢查。這在理論上是可行的，但存在效率問題。如果你處理的是一個度數小於某個值的多項式，並且在某個大小的域上進行操作，攻擊者實際上可以構造看起來在這些位置上都很正常的惡意多項式。因此，他們能否成功破壞協議是一個概率性問題，因此需要增加檢查的輪數，以增強整體的安全性，確保能夠有效防御攻擊者的攻擊。

這引出了另一個解決方案：擴展域，擴展域類似於復數，但它是基於有限域的。我們引入一個新的值，記作 α\alphaα，並聲明其滿足某種關系，比如 α2=some value\alpha^2 = \text {some value}α2=some value。通過這種方式，我們創建了一個新的數學結構，能夠在有限域上進行更復雜的運算。在這種擴展域中，乘法的計算變為使用新值 α\alphaα 的乘法。我們現在可以在擴展的域中操作值對，而不僅僅是單個數字。比如，如果我們在 Mersenne 或 BabyBear 這樣的字段上工作，這樣的擴展允許我們有更多的值選擇，從而提高安全性。為了進一步提高字段的大小，我們可以重復應用相同的技術。由於我們已經使用了 α\alphaα，所以我們需要定義一個新的值，這在 Mersenne31 中表現為選擇 α\alphaα 使得 α2=some value\alpha^2 = \text {some value}α2=some value。

通過擴展域，我們現在有了足夠多的值來選擇，滿足我們的安全需求。如果處理的是度數小於 ddd 的多項式，每輪可以提供 104 位的安全性。這意味着我們有足夠的安全保障。如果需要達到更高的安全級別，比如 128 位，我們可以在協議中加入一些額外的計算工作，以增強安全性。

擴展域僅在 FRI（Fast Reed-Solomon Interactive）協議和其他需要隨機线性組合的場景中實際使用。大部分的數學運算仍然在基礎字段上進行，這些基礎字段通常是模 ppp 或 qqq 的字段。同時，幾乎所有哈希的數據都是在基礎字段上進行的，因此每個值只需哈希四字節。這樣做可以利用小字段的高效性，同時在需要進行安全性增強時，可以使用更大的字段。

Regular FRI

在構建 SNARK 或 STARK 時，第一步通常是 arithmetization 。這是將任意計算問題轉化為一個方程，其中某些變量和系數是多項式。具體來說，這個方程通常會看起來像 P (X,Y,Z)=0P (X, Y, Z) = 0P (X,Y,Z)=0，其中 P 是一個多項式，X、Y 和 Z 是給定的參數，而求解器需要提供 X 和 Y 的值。一旦有了這樣的方程，該方程的解就對應於底層計算問題的解。

要證明你有一個解，你需要證明你所提出的值確實是合理的多項式（而不是分數，或者在某些地方看起來像一個多項式，而在其他地方卻是不同的多項式，等等），並且這些多項式具有一定的最大度數。為此，我們使用了一個逐步應用的隨機线性組合技巧：

假設你有一個多項式 A 的評估值，你想證明它的度數小於 2^{20}
考慮多項式 B (x^2) = A (x) + A (-x)，C (x^2) = \frac {A (x) - A (-x)}{x}
D 是 B 和 C 的隨機线性組合，即 D=B+rCD = B + rCD=B+rC，其中 r 是一個隨機系數。

本質上，發生的事情是 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（Fast Reed-Solomon Interactive）協議能夠正常工作的關鍵。後者則使得算法運行速度極快：由於每一輪的規模比上一輪減少一半，總的計算成本是 O (N)，而不是 O (N*log (N))。

為了實現域的逐步減少，使用了一個二對一映射，即每個點都映射到兩個點中的一個。這種映射允許我們將數據集的大小減少一半。這個二對一映射的一個重要優點是它是可重復的。也就是說，當我們應用這個映射時，得到的結果集仍然保留了相同的屬性。假設我們從一個乘法子群（multiplicative subgroup）开始。這個子群是一個集合 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 的應用變得更加高效。

Circle FRI

這就是 Circle STARKs 的巧妙之處，給定一個質數 p，可以找到一個大小為 p 的群體，該群體具有類似的二對一特性。這個群體是由所有滿足某些特定條件的點組成的，例如，x^2 mod p 等於某個特定值的點集。

這些點遵循一種加法規律，如果你最近做過三角學或復數乘法的相關內容，你可能會覺得這種規律很熟悉。

雙倍形式是：

現在，讓我們專注於這個圓上奇數位置上的點：

首先，我們將所有點收斂到一條直线上。我們在常規 FRI 中使用的 B (x²) 和 C (x²) 公式的等效形式是：

然後，我們可以進行隨機线性組合，得到一個一維的 P (x)，這個多項式在 x 线的一個子集上定義：

從第二輪开始，映射發生了變化：

這個映射實際上每次都將上述集合的大小減少一半，這裏發生的事情是，每個 x 在某種意義上代表了兩個點：(x, y) 和 (x, -y)。而 (x → 2x^2 - 1) 就是上面的點倍增法則。因此，我們將圓上兩個相對點的 x 坐標，轉換為倍增後的點的 x 坐標。

例如，如果我們取圓上第二個從右邊數的值 2，並應用映射 2 → 2 (2^2) - 1 = 7，我們得到的結果是 7。如果我們回到原始圓上，(2, 11) 是從右邊數第三個點，所以將其倍增後，我們得到的是從右邊數第六個點，即 (7, 13)。

這本可以在二維空間中完成，但在一維空間中操作會使過程更高效。

Circle FFTs

一種與 FRI 密切相關的算法是 FFT ，它將一個度小於 n 的多項式的 n 個評估值轉換為該多項式的 n 個系數。FFT 的過程與 FRI 相似，不同之處在於，FFT 在每一步中不是生成隨機线性組合 f_0 和 f_1 ，而是遞歸地對它們進行半大小的 FFT，並將 FFT (f_0) 的輸出作為偶數系數，將 FFT (f_1) 的輸出作為奇數系數。

Circle group 也支持 FFT，這種 FFT 的構造方式與 FRI 類似。然而，一個關鍵區別在於，Circle FFT（和 Circle FRI）所處理的對象並不嚴格是多項式。相反，它們是數學上稱為 Riemann-Roch space 的東西：在這種情況下，多項式是模圓的 ( x^2 + y^2 - 1 = 0 ）。也就是說，我們將 x^2 + y^2 - 1 的任何倍數視為零。另一種理解方式是：我們只允許 y 的一次冪：一旦出現 y^2 項，我們就將其替換為 1 - x^2 。

這還意味着，Circle FFT 輸出的系數並不像常規 FRI 那樣是單項式（例如，如果常規 FRI 輸出為 [6, 2, 8, 3]，那么我們知道這意味着 P (x) = 3x^3 + 8x^2 + 2x + 6 ）。相反，Circle FFT 的系數是特定於 Circle FFT 的基礎：{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 獲取更大的評估值集。

Circle FFT 不是唯一的特殊 FFT 類型。 Elliptic curve FFT 更為強大，因為它們可以在任何有限域（素數域、二進制域等）上工作。然而，ECFFT 更復雜且效率較低，因此由於我們可以在 p = 2^{31}-1 上使用 Circle FFT，所以我們選擇使用它。

從這裏开始，我們將深入一些更為晦澀的細節，實現 Circle STARKs 實現的細節與常規 STARKs 有所不同。

Quotienting

在 STARK 協議中，常見的一種操作是對特定點進行商運算，這些點可以是故意選擇的，也可以是隨機選擇的。例如，如果你想證明 P (x)=y，可以通過以下步驟進行：

計算商：給定多項式 P (x) 和常數 y，計算商 Q ={P - y}/{X - x}，其中 X 是選擇的點。

證明多項式：證明 Q 是一個多項式，而不是一個分數值。通過這種方式，證明了 P (x)=y 是成立的。

此外，在 DEEP-FRI 協議中，隨機選擇評估點是為了減少 Merkle 分支的數量，從而提高 FRI 協議的安全性和效率。

在處理 circle group 的 STARK 協議時，由於沒有可以通過單一點的线性函數，需要採用不同的技巧來替代傳統的商運算方法。這通常需要使用 circle group 特有的幾何性質來設計新的算法。

在 circle group 中，你可以構造一個切线函數，使其在某個點 (P_x, P_y) 切於該點，但這個函數會通過該點具有重數 2，也就是說，要使一個多項式成為該线性函數的倍數，它必須滿足比僅在該點為零更嚴格的條件。因此，你不能僅僅在一個點上證明評估結果。那么我們該如何處理呢？

我們不得不接受這個挑战，通過在兩個點上進行評估來證明，從而添加一個我們不需要關注的虛擬點。

如果我們有一個多項式 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 是一個多項式。

Vanishing polynomials

在 STARK 中，你試圖證明的多項式方程通常看起來像是 C (P (x), P ({next}(x))) = Z (x) ⋅ H (x) ，其中 Z (x) 是一個在整個原始評估域上都等於零的多項式。在常規 STARK 中，這個函數就是 x^n - 1 。在圓形 STARK 中，相應的函數是：

注意，你可以從折疊函數中推導出消失多項式：在常規 STARK 中，你重復使用 x → x^2 ，而在圓形 STARK 中，你重復使用 x → 2x^2 - 1 。不過，對於第一輪，你會進行不同的處理，因為第一輪是特殊的。

Reverse bit order

在 STARKs 中，多項式的評估通常不是按照 “自然” 順序排列的（例如 P (1),P (ω),P (ω2),…,P (ωn−1)，而是按照我稱之為逆位序（reverse bit order）的順序排列的：

如果我們設置 n=16，並且只關注我們在哪些 ω 的冪次上進行評估，那么列表看起來如下：

這種排序具有一個關鍵屬性，即在 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 證明。

在 circle STARKs 中，折疊結構略有不同：在第一步中，我們將 (x, y) 與 (x, -y) 配對；在第二步中，將 x 與 -x 配對；在隨後的步驟中，將 p 與 q 配對，選擇 p 和 q 使得 Q^i (p) = -Q^i (q)，其中 Q^i 是重復 x → 2x^2-1 i 次的映射。如果我們從圓上的位置來考慮這些點，那么在每一步中，這看起來就像是第一個點與最後一個點配對，第二個點與倒數第二個點配對，依此類推。

為了調整反向位序以反映這種折疊結構，我們需要反轉除了最後一位的每一位。我們保留最後一位，並用它來決定是否翻轉其他位。

一個大小為 16 的折疊反向位序如下：

如果你觀察上一節中的圓，你會發現 0、15、8 和 7 這幾個點（從右側开始逆時針方向）是 (x, y)、(x, -y)、(-x, -y) 和 (-x, y) 的形式，這正是我們所需要的。

效率

在 Circle STARKs（以及一般的 31 位素數 STARKs）中，這些協議非常高效。一個在 Circle STARK 中被證明的計算通常涉及幾種類型的計算：

1. 原生算術：用於業務邏輯，例如計數。

2. 原生算術：用於加密學，例如像 Poseidon 這樣的哈希函數。

3. 查找參數：一種通用的高效計算方法，通過從表中讀取值來實現各種計算。

效率的關鍵衡量標准是：在計算跟蹤中，你是充分利用了整個空間來進行有用的工作，還是留下了大量的空闲空間。在大型字段的 SNARKs 中，往往存在大量的空闲空間：業務邏輯和查找表通常涉及對小數字的計算（這些數字往往小於 N，N 是一個計算步驟的總數，因此在實踐中小於 2^{25}），但你仍然需要支付使用大小為 2^{256} 位字段的成本。在這裏，字段的大