探索Circle STARKs

近年來，STARKs協議設計的趨勢是轉向使用較小的字段。最早期的STARKs實現使用256位字段,但這種設計效率較低。爲解決這個問題,STARKs開始使用更小的字段,如Goldilocks、Mersenne31和BabyBear。

這種轉變顯著提升了證明速度。例如,Starkware能在M3筆記本上每秒證明62萬個Poseidon2哈希。這意味着只要信任Poseidon2作爲哈希函數,就可以解決高效ZK-EVM的難題。

本文將探討這些技術的工作原理,特別關注Circle STARKs方案。Circle STARKs具有與Mersenne31字段兼容的獨特屬性。

使用小字段的常見問題

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

爲防止攻擊,我們需要在攻擊者提供多項式後再選擇隨機點。在較小字段的STARKs中,可選的隨機點只有約20億個,對下定決心的攻擊者來說並不安全。

解決方案有兩個:

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

多次檢查簡單有效,但存在效率問題。擴展字段類似於復數,但基於有限域。這允許我們在更大的域中操作,提高安全性。

Regular FRI

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

FRI使用二對一映射將數據集大小減半。這種映射是可重復的,允許我們持續減少數據集大小。

Circle FRI

Circle STARKs的巧妙之處在於,給定質數p,可以找到大小爲p的羣,具有類似的二對一特性。這個羣由滿足特定條件的點組成。

從第二輪開始,映射發生變化:

f_0(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的地方是進行低度擴展。

Quotienting

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

Vanishing polynomials

在圓形STARK中,消失多項式爲:

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

Reverse bit order

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

效率

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

1. 用於業務邏輯的原生算術
2. 用於加密的原生算術
3. 查找參數

關鍵是充分利用計算跟蹤中的空間。2^31大小的字段減少了浪費空間。

結論

Circle STARKs對開發者來說並不比常規STARKs復雜。其背後的數學雖然復雜,但對開發者來說基本是隱藏的。

理解Circle FRI和FFTs可以作爲理解其他特殊FFTs的途徑。

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

• 對哈希函數等進行最大化效率的算術化
• 進行遞歸構造以啓用更多並行化
• 算術化虛擬機以改善開發者體驗