探索Circle STARKs

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

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

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

使用小字段的常見問題

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

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

有兩種解決方案:

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

多次檢查簡單有效,但效率較低。擴展字段類似復數,允許在有限域上進行更復雜的運算。這提高了安全性,同時保留了小字段的高效性。

Circle FRI

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

這些點遵循一種加法規律: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

雙倍形式是: 2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI將所有點收斂到一條直線上,然後進行隨機線性組合,得到一維多項式P(x)。

從第二輪開始,映射變爲: f0(2x^2-1) = (F(x) + F(-x)) / 2

這個映射每次將集合大小減半,將圓上兩個相對點的x坐標轉換爲倍增後點的x坐標。

Circle FFTs

Circle group也支持FFT,構造方式與FRI類似。一個關鍵區別是,Circle FFT處理的不是嚴格意義上的多項式,而是Riemann-Roch空間。

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

商運算

在STARK中,常見的操作是對特定點進行商運算。在circle group中,由於沒有單一點的線性函數,需要採用不同技巧。

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

消失多項式

在circle STARK中,相應的消失多項式函數是:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

反向位序

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

效率

Circle STARKs非常高效。一個被證明的計算通常涉及:

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

效率的關鍵是充分利用計算跟蹤中的空間。Circle STARKs在2^31大小的字段中浪費的空間較少。

結論

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

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

• 最大化哈希函數等原語的效率
• 遞歸構造以提高並行性
• 算術化虛擬機以改善開發體驗