探索Circle STARKs

Circle STARKs是一種新型的STARK證明系統,它利用了圓羣的特殊性質來構建高效的證明。本文將探討Circle STARKs的工作原理及其優勢。

背景

近年來,STARKs協議設計趨向使用較小的數學字段,如Goldilocks、Mersenne31和BabyBear等。這種轉變大大提升了證明速度,例如Starkware能在M3筆記本上每秒證明62萬個Poseidon2哈希。

但使用小字段也帶來了一些挑戰,如何在有限的隨機性空間內保證安全性。Circle STARKs通過巧妙的設計解決了這一問題。

Circle STARKs的核心原理

Circle STARKs的核心思想是利用圓羣的二對一映射性質。給定一個質數p,我們可以找到一個大小爲p的羣,該羣具有類似的二對一特性。這個羣由所有滿足x^2 + y^2 = 1 mod p的點(x,y)組成。

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

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

利用這種映射,我們可以構造出類似FRI的證明系統,但在更小的字段上工作。

Circle FFTs

Circle羣還支持FFT運算,但處理的對象不是嚴格意義上的多項式,而是所謂的Riemann-Roch空間。這意味着我們將x^2 + y^2 - 1的任何倍數視爲零。

這導致Circle FFT輸出的系數不同於常規FFT,而是基於特定的基{1, y, x, xy, 2x^2 - 1, ...}。但作爲開發者,我們幾乎可以完全忽略這一點,只需將多項式作爲評估值集合來處理即可。

Circle STARKs的特殊技巧

商運算

由於圓羣沒有可以通過單一點的線性函數,Circle STARKs採用了不同的商運算技巧。我們通過在兩個點上進行評估來證明,從而添加一個不需要關注的虛擬點。

消失多項式

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

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

反向位序

爲了適應Circle STARKs的特殊折疊結構,我們需要調整反向位序。具體方法是反轉除了最後一位的每一位,並用最後一位決定是否翻轉其他位。

Circle STARKs的效率

Circle STARKs在31位素數字段上工作,比大字段STARKs更高效。它充分利用了字段空間,減少了空閒空間的浪費。雖然Binius等方案在某些方面更優,但Circle STARKs概念更簡單。

結論

Circle STARKs爲開發者提供了一種概念簡單但高效的STARK變體。它很好地平衡了效率和易用性,是STARK技術發展的重要一步。未來STARK優化可能會集中在以下方向:

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

Circle STARKs的出現爲我們提供了一個理解和探索更多特殊FFT技術的窗口,推動了STARK技術向更高效和實用的方向發展。