探索Circle STARKs

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

這種轉變提升了證明速度。例如,Starkware能在M3筆記本電腦上每秒證明620,000個Poseidon2哈希值。這意味着,只要我們願意信任Poseidon2作爲哈希函數,就可以解決開發高效ZK-EVM的難題。

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

使用較小數學字段的常見問題

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

爲防止攻擊,我們需要在攻擊者提供多項式後再選擇隨機點。在較小字段的STARKs中,可選擇的隨機值數量有限,這給安全性帶來挑戰。

解決方案有兩個:

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

擴展字段類似於復數,但基於有限域。通過引入新值α,我們創建了一個新的數學結構,能在有限域上進行更復雜的運算。這種擴展允許我們有更多的值選擇,從而提高安全性。

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從不要求您了解系數。您只需將多項式作爲在特定域上的一組評估值進行存儲。

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. 查找參數

效率的關鍵是充分利用計算跟蹤中的整個空間進行有用工作。Circle STARKs在這方面表現良好。

結論

Circle STARKs對開發者來說並沒有比STARKs復雜。盡管背後的數學很復雜,但這種復雜性實際上被很好地隱藏了。

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

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