探索Circle STARKs

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

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

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

使用小字段的常見問題

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

爲防止攻擊,我們需要在攻擊者提供多項式後再選擇隨機點。在256位字段中這很簡單,但在小字段中,可選的隨機值太少,容易被攻擊者窮舉破解。

解決方案有兩種:

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

多次隨機檢查簡單有效,但效率較低。擴展字段則類似於復數,可以在有限域上進行更復雜的運算。

Regular FRI

FRI協議的第一步是將計算問題轉化爲多項式方程。然後證明所提出的多項式解確實滿足方程且度數不超過要求。

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

FRI的關鍵是使用二對一映射將數據集大小減半。這種映射需要能夠重復應用,直到最終只剩一個值。

Circle FRI

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

這些點遵循一種加法規律,類似於三角函數或復數乘法。

從第二輪開始,映射發生變化。每個x代表兩個點:(x,y)和(x,-y)。(x → 2x^2 - 1)就是點倍增法則。

Circle FFTs

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

作爲開發者,幾乎可以忽略這些細節。只需將多項式作爲評估值存儲,在需要低度擴展時使用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

在STARKs中,多項式評估通常按逆位序排列。Circle STARKs中需要調整這種排序,以反映其特殊的折疊結構。

效率

Circle STARKs非常高效。關鍵是充分利用計算跟蹤中的空間進行有用工作,而不留下大量空閒。

與Binius相比,Circle STARKs概念上更簡單,但效率稍低。

結論

Circle STARKs對開發者來說並不比常規STARKs復雜。理解Circle FRI和FFTs有助於理解其他特殊FFTs。

未來STARK優化可能集中在:

1. 最大化哈希函數等基本密碼原語的效率
2. 遞歸構造以提高並行化
3. 算術化虛擬機以改善開發體驗