原文標題：《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 位數字，這樣就可以了。然而，在較小字段上的STARK 中，我們遇到了一個問題：只有大約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。
代碼（你可以用Karatsuba改進它）
透過擴展域，我們現在有了足夠的值來選擇，滿足我們的安全需求。如果處理的是度數小於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 等於某個特定值的點集。
這些點遵循一種加法律，如果你最近做過三角學或複數乘法的相關內容，你可能會覺得這種規律很熟悉。
(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)。
這本來可以在二維空間中完成，但在一維空間中操作會使過程更有效率。
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 curveFFT 更為強大，因為它們可以在任何有限域（素數域、二進位域等）上運作。然而，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，也就是說，要使一個多項式成為該線性函數的倍數，它必須滿足比僅在該點為零更嚴格的條件。因此，你不能僅僅在一個點上證明評估結果。那我們該如何處理呢？
我們不得不接受這個挑戰，透過在兩個點上進行評估來證明，從而添加一個我們不需要關注的虛擬點。
線函數：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 是多項式。
Vanishing polynomials
在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 。不過，對於第一輪，你會進行不同的處理，因為第一輪是特別的。
Reverse bit order
在STARKs 中，多項式的評估通常不是按照「自然」 順序排列的（例如P (1),P (ω),P (ω2),…,P (ωn−1)，而是按照我稱之為逆位序（reverse bit order）的順序排列的：
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 證明。
在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, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
如果你觀察上一節的圓，你會發現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} 位元欄位的成本。在這裡，字段的大小為2^{31}，所以浪費的空間並不大。為SNARKs 設計的低算術複雜度雜湊（例如Poseidon）在任何欄位中都充分利用了追蹤中每個數字的每一位。
Binius 是比Circle STARKs 更好的解決方案，因為它允許你混合不同大小的字段，從而實現更有效率的位元打包。 Binius 還提供了在不增加查找表開銷的情況下進行32 位元加法的選項。然而，這些優勢的（在我看來）代價是會使概念變得更加複雜，而Circle STARKs（以及基於BabyBear 的常規STARKs）在概念上則相對簡單得多。
結論：我對Circle STARKs 的看法
Circle STARKs 對開發者來說並沒有比STARKs 複雜。在實作過程中，以上提到的三個問題基本上就是與常規FRI 的差異。儘管Circle FRI 操作的多項式背後的數學非常複雜，理解和欣賞這些數學需要一些時間，但這種複雜性實際上被隱藏得不那麼顯眼，開發者不會直接感受到。
理解Circle FRI 和Circle FFTs 也可以成為理解其他特殊FFTs 的途徑：最值得注意的是二進位域FFTs，如Binius和之前的LibSTARK使用的FFTs，還有一些更複雜的構造，如elliptic curve FFTs, 這些FFTs使用少對多的映射，能夠與elliptic curve 點運算很好地結合。
結合Mersenne31、BabyBear 和像Binius 這樣的二進位域技術，我們確實感覺我們正在接近STARKs 基礎層的效率極限。在這一點上，我預計STARK 的優化方向將會有以下重點：
對雜湊函數和簽章等進行最大化效率的算術化：將雜湊函數和數位簽章等基本的密碼學原語最佳化為最有效率的形式，使其在STARK 證明中使用時能夠達到最佳效能。這意味著要針對這些原語進行專門的最佳化，以減少計算量和提高效率。
進行遞歸構造以啟用更多並行化：遞歸構造指的是將STARK 證明過程遞歸地應用於不同的層級，從而提高並行處理能力。透過這種方式，可以更有效率地利用運算資源，加速證明過程。
算術化虛擬機器以改善開發者體驗：對虛擬機器進行算術化處理，使得開發者在建立和執行運算任務時可以更有效率、更簡單。這包括對虛擬機器進行最佳化，以便於在STARK 證明中使用，改善開發者在建置和測試智慧合約或其他運算任務時的體驗。
