探索Circle STARKs

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

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

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

使用小字段的常見問題

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

爲防止攻擊,我們需要在攻擊者提供多項式後再選擇隨機點。在較小字段的STARKs中,可選的隨機值只有約20億個,對於堅定的攻擊者來說是可行的。

解決方案有兩個:

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

進行多次檢查簡單有效,但存在效率問題。擴展字段類似復數,但基於有限域。這樣可以在有限域上進行更復雜的運算,提高安全性。

Regular FRI

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

FRI的工作原理是重復這個簡化過程。如果某個階段的輸出不是預期的多項式度數,那麼這一輪的檢查將失敗。

爲實現域的逐步減少,使用了二對一映射。這種映射允許將數據集大小減半,同時保留相同屬性。

Circle FRI

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

這些點遵循一種加法規律。從第二輪開始,映射發生變化。這個映射每次都將集合大小減半。

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. 查找參數:通過從表中讀取值實現各種計算

效率的關鍵是充分利用整個計算空間進行有用工作。

結論

Circle STARKs對開發者來說並不比STARKs復雜。主要區別在於上述三個問題。盡管背後數學復雜,但這種復雜性被很好地隱藏了。

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

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