探索Circle STARKs

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

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

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

使用小字段的常見問題

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

然而,在小字段上進行這種隨機採樣存在安全性問題。例如Mersenne31字段只有約20億個可能的採樣點,對於下定決心的攻擊者來說是可行的。

有兩種解決方案:

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

多次檢查簡單有效,但存在效率問題。擴展字段則可以提供更多的採樣點選擇,從而提高安全性。

常規FRI

FRI協議的第一步是將計算問題轉化爲多項式方程。然後證明提出的多項式解確實是合理的多項式,且具有一定的最大度數。

FRI通過逐步將證明多項式度數爲d的問題簡化爲證明度數爲d/2的問題來實現這一點。這個過程可以重復多次,每次將問題規模減半。

FRI的每一步都將多項式次數和點集規模減半。前者是FRI工作的關鍵,後者使算法運行速度極快。

Circle FRI

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

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

f_0(2x^2-1) = (F(x) + F(-x))/2

這個映射每次都將點集大小減少一半。

Circle FFTs

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

作爲開發者,你幾乎可以忽略這一點。STARKs只需要你將多項式作爲評估值集合存儲。唯一需要FFT的地方是進行低度擴展。

商運算

在Circle STARKs中,由於沒有可以通過單點的線性函數,需要採用不同的技巧來替代傳統的商運算方法。

我們不得不在兩個點上進行評估來證明,從而添加一個不需要關注的虛擬點。

消失多項式

在Circle STARKs中,消失多項式的形式爲:

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

逆位序

Circle STARKs中的逆位序需要調整以反映其特殊的折疊結構。具體來說,需要反轉除最後一位外的每一位,並用最後一位決定是否翻轉其他位。

效率

Circle STARKs非常高效。與大字段SNARKs相比,它們可以更充分地利用計算跟蹤中的空間。

Binius在某些方面比Circle STARKs更好,但代價是概念更復雜。相比之下,Circle STARKs在概念上相對簡單。

結論

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

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

1. 最大化哈希函數和籤名的效率
2. 遞歸構造以提高並行性
3. 優化虛擬機以改善開發體驗