深入探索Circle STARKs

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

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

但使用小字段也帶來了一些挑戰,如何在有限的字段大小下保證安全性。Circle STARKs方案提供了一種創新的解決方案,它利用了圓羣的特殊性質來構造高效安全的證明系統。

本文將深入探討Circle STARKs的原理和實現細節,包括:

• 小字段STARKs面臨的主要挑戰
• Circle FRI的基本原理
• Circle FFTs的實現
• Circle STARKs中的商運算和消失多項式
• 反向位序的調整
• Circle STARKs的效率分析

通過這些技術細節的討論,我們可以更好地理解Circle STARKs的創新之處,以及它在提升STARKs效率方面的重要貢獻。

使用小字段的挑戰

在基於橢圓曲線的協議中,我們可以選擇一個隨機的256位數作爲驗證參數。但在小字段STARKs中,可選擇的參數範圍大大縮小,容易被攻擊者窮舉。

有兩種解決方案:

1. 進行多次隨機檢查:在多個隨機坐標上重復驗證。這種方法簡單有效,但會降低效率。

2. 擴展字段:引入新的數學結構來擴大可選值的範圍。例如在Mersenne31字段上,我們可以定義α使得α^2=某個特定值,從而構造出更大的字段。

擴展字段主要用於FRI協議等需要隨機線性組合的場景。大部分運算仍在基礎字段上進行,保留了小字段的高效性。

Circle FRI的原理

Circle STARKs的核心創新在於Circle FRI。給定一個素數p,我們可以構造一個大小爲p的羣,該羣具有類似二對一映射的特性。

這個羣由滿足x^2 mod p等於某個特定值的點集組成。這些點遵循一種特殊的加法規則:

(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

雙倍點公式爲:

2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI首先將所有點收斂到一條直線上:

f0(x) = (F(x,y) + F(x,-y))/2

然後進行隨機線性組合得到一維多項式P(x)。

從第二輪開始,映射變爲:

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

這個映射每次都將點集大小減半,實現了類似常規FRI的效果。

Circle FFTs

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

這意味着Circle FFT的輸出系數並不像常規FFT那樣是單項式,而是特定於Circle FFT的基函數。

作爲開發者,我們可以忽略這些數學細節。只需將多項式存儲爲一組評估值,使用FFT進行低度擴展即可。

商運算和消失多項式

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

消失多項式也需要相應調整。在Circle STARKs中,消失多項式的形式爲:

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

反向位序的調整

爲了適應Circle FRI的折疊結構,需要調整反向位序。基本思路是反轉除最後一位外的每一位,用最後一位決定是否翻轉其他位。

效率分析

Circle STARKs在31位素數字段上非常高效。它充分利用了字段空間,減少了浪費。相比大字段SNARKs,Circle STARKs在業務邏輯和查找表方面更有優勢。

Binius等方案通過混合不同大小的字段實現了更高的效率,但增加了復雜度。Circle STARKs在概念上更簡單。

結論

Circle STARKs爲開發者提供了一種高效且相對簡單的STARKs實現方案。它巧妙地利用了圓羣的特性,在保持安全性的同時顯著提升了效率。

未來STARKs的優化方向可能包括:

• 最大化哈希函數等基礎密碼原語的效率
• 通過遞歸構造實現更多並行化
• 改進虛擬機的算術化以提升開發體驗

總的來說,Circle STARKs是STARKs技術發展中的一個重要裏程碑,爲構建更高效的零知識證明系統提供了新的思路。