探索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。在256位字段中這很簡單,但在小字段中只有約20億種r可選,攻擊者可能破解。

解決方案有兩種:

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

多次檢查簡單有效,但可能需要增加輪數以提高安全性。擴展域類似復數,但基於有限域。通過引入新值α,創建更復雜的數學結構,提供更多選擇。

Regular FRI

FRI協議的第一步是將計算問題轉化爲多項式方程P(X,Y,Z)=0。然後證明提出的值是合理的多項式,且度數有限。

FRI通過將證明多項式度數爲d的問題簡化爲證明度數爲d/2的問題來簡化驗證。這個過程可重復多次,每次將問題簡化一半。

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)

Circle FRI的映射從第二輪開始變爲: 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空間,而非嚴格多項式。

Circle FFT的系數是特定基礎:{1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, ...}

開發者幾乎可以忽略這點,只需將多項式作爲評估值集合存儲。FFT主要用於低度擴展。

Quotienting

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

Vanishing polynomials

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

Reverse bit order

Circle STARKs中需要調整反向位序以反映折疊結構,即反轉除最後一位外的每一位,用最後一位決定是否翻轉其他位。

效率

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

1. 業務邏輯的原生算術
2. 密碼學的原生算術(如Poseidon哈希)
3. 查找參數

2^31大小的字段減少了空間浪費。Binius在混合字段大小方面更優,但概念更復雜。

結論

Circle STARKs對開發者並不比STARKs復雜。理解其數學需要時間,但復雜性被很好地隱藏。

結合Mersenne31、BabyBear和二進制域技術,STARKs基礎層效率接近極限。未來優化方向可能包括:

• 最大化哈希函數等的算術化效率
• 遞歸構造以提高並行化
• 算術化虛擬機以改善開發體驗