深入探索Circle STARKs

近年來，STARKs協議設計的趨勢是轉向使用較小的字段。最早期的STARKs實現使用256位字段,這使得這些協議與基於橢圓曲線的籤名兼容。但這種設計效率較低,處理大數字會浪費很多算力。爲解決這個問題,STARKs開始轉向使用更小的字段:先是Goldilocks,然後是Mersenne31和BabyBear。

這種轉變顯著提升了證明速度。例如Starkware能在M3筆記本上每秒證明62萬個Poseidon2哈希值。這意味着只要信任Poseidon2作爲哈希函數,就可以解決高效ZK-EVM的難題。那麼這些技術如何工作?如何在小字段上建立證明?本文將探討這些細節,特別關注Circle STARKs方案。

使用小字段的常見問題

在創建基於哈希的證明時,一個重要技巧是通過證明多項式在隨機點的評估結果來間接驗證多項式性質。這大大簡化了證明過程。

例如,假設要求生成一個多項式A的承諾,滿足A^3(x) + x - A(ωx) = x^N。協議可以要求選擇隨機坐標r並證明A(r) + r - A(ωr) = r^N。然後反推A(r) = c,證明Q = (A - c)/(X - r)是一個多項式。

爲防止攻擊,需要在攻擊者提供A之後再選擇r。在大字段協議中,可以選擇隨機256位數字作爲r。但在小字段STARKs中,只有約20億種r值可選,攻擊者可以嘗試所有可能。

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

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

多次隨機檢查簡單有效,但存在效率問題。擴展字段類似復數,但基於有限域。引入新值α滿足α^2=某個值,創建新的數學結構。這允許我們有更多值選擇,提高安全性。

Regular FRI

FRI協議的第一步通常是算術化,將計算問題轉化爲方程P(X,Y,Z)=0,其中P是多項式,X、Y、Z是參數。解決方程對應解決原問題。

要證明解的正確性,需證明提出的值是合理的多項式且具有最大度數。使用隨機線性組合技巧:

• 假設有多項式A的評估值,要證明其度數<2^20
• 考慮B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D是B和C的隨機線性組合:D = B + rC

本質上B隔離偶數系數,C隔離奇數系數。B和C可恢復A。如果A度數<2^20,B和C的度數分別爲A的度數和A度數-1。D作爲隨機組合,其度數應爲A的度數。

FRI重復這個簡化過程,每次將問題簡化一半。這種設計有效檢測不符合要求的輸入。

Circle FRI

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

這些點遵循加法規律:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) 雙倍形式是:2 * (x,y) = (2x^2 - 1, 2xy)

我們專注於圓上奇數位置的點,將所有點收斂到一條直線上: f0(x) = (F(x,y) + F(x,-y))/2

然後進行隨機線性組合,得到一維多項式P(x)。

從第二輪開始,映射變爲: f0(2x^2-1) = (F(x) + F(-x))/2

這個映射每次將集合大小減半。每個x代表兩個點:(x,y)和(x,-y)。(x → 2x^2 - 1)就是點倍增法則。

Circle FFTs

Circle group也支持FFT,構造方式與FRI類似。但Circle FFT處理的對象是Riemann-Roch空間,而非嚴格多項式。

作爲開發者,可以基本忽略這點。STARKs只需將多項式存儲爲評估值集。FFT主要用於低度擴展:給定N個值,生成k*N個同一多項式上的值。

Quotienting

在Circle STARKs中,由於沒有單點線性函數,需採用不同技巧替代傳統商運算。通過在兩點評估來證明,添加一個虛擬點。

如果多項式P在x1處等於y1,在x2處等於y2,選擇插值函數L在這兩點相等。然後證明P-L在兩點爲零,通過L除以得到商Q是多項式。

Vanishing polynomials

Circle STARKs中的消失多項式爲: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

這可從折疊函數推導:重復使用x → 2x^2 - 1。

Reverse bit order

Circle STARKs中的反向位序需調整:反轉除最後一位的每一位,用最後一位決定是否翻轉其他位。

16大小的折疊反向位序爲: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

效率

Circle STARKs非常高效。計算通常涉及:

1. 業務邏輯的原生算術
2. 密碼學的原生算術
3. 查找參數

效率關鍵在於充分利用計算跟蹤空間。31位素數字段減少了浪費。Binius混合不同大小字段效率更高,但概念更復雜。

結論

Circle STARKs對開發者並不復雜。理解背後數學需時間,但復雜性被很好隱藏。它也是理解其他特殊FFTs的途徑。

目前STARKs基礎層效率接近極限。未來優化方向可能包括:

• 最大化哈希函數等基本密碼原語的效率
• 遞歸構造以增加並行化
• 算術化虛擬機以改善開發體驗