探索Circle STARKs

近年來，STARKs協議設計趨向使用較小的字段。最早期的STARKs實現使用256位字段,與基於橢圓曲線的籤名兼容。但這種設計效率較低,處理大數字會浪費算力。爲解決這個問題,STARKs開始轉向使用更小的字段:首先是Goldilocks,然後是Mersenne31和BabyBear。

這種轉變提升了證明速度。例如Starkware能在M3筆記本上每秒證明620,000個Poseidon2哈希值。只要我們信任Poseidon2作爲哈希函數,就可以解決開發高效ZK-EVM的難題。那麼這些技術如何工作?這些證明如何在較小字段上建立?本文將探討這些細節,特別關注Circle STARKs方案。

使用較小數學字段的常見問題

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

例如,假設要求生成多項式A的commitment,必須滿足A^3(x) + x - A(ωx) = x^N。協議可要求選擇隨機坐標r並證明A(r) + r - A(ωr) = r^N。然後反推A(r) = c,證明Q = (A - c)/(X - r)是一個多項式。

爲防止攻擊,需要在攻擊者提供A後再選擇r。在基於橢圓曲線的協議中,可選擇隨機256位數。但在較小字段的STARKs中,只有約20億個r值可選,攻擊者可能通過窮舉破解。

解決方案有兩個:

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

多次隨機檢查簡單有效,但存在效率問題。擴展域類似復數,但基於有限域。引入新值α,聲明α^2=某值。這樣可在有限域上進行更復雜運算。擴展域僅在FRI協議等場景中使用,大部分數學運算仍在基礎字段進行。

常規FRI

構建SNARK或STARK時,第一步是算術化,將計算問題轉化爲多項式方程。要證明有解,需證明所提出值是合理的多項式且具有最大度數。爲此使用逐步應用的隨機線性組合技巧:

1. 假設有多項式A的評估值,要證明度數<2^20
2. 考慮B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D是B和C的隨機線性組合:D = B + rC

本質上,B隔離偶數系數,C隔離奇數系數。給定B和C可恢復A。如果A度數<2^20,B和C度數分別爲A度數和A度數-1。D作爲隨機線性組合,度數應爲A度數。

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

爲實現域的逐步減少,使用二對一映射。這種映射允許將數據集大小減少一半,且是可重復的。從乘法子羣開始,對集合S進行平方操作,新集合S^2保留同樣屬性。這允許持續減少數據集大小,直到最終只剩一個值。

BabyBear模數使其最大乘法子羣包含所有非零值,子羣大小爲2k-1。可選擇2^k大小的子羣,然後應用FRI方法將多項式度數逐步減少到15。Mersenne31模數使乘法子羣大小爲2^31-1,只能被除以2一次,之後無法使用上述技術。

Mersenne31域適合32位CPU/GPU運算。其模數特性使許多運算可利用高效位操作完成。在Mersenne31域中,算術運算比BabyBear域快約1.3倍。如果能在Mersenne31域實現FRI,將顯著提升計算效率。

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)

我們專注於圓上奇數位置的點。首先將所有點收斂到一條直線上: f0(x) = (F(x,y) + F(x,-y))/2

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

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

這個映射每次將集合大小減半。每個x代表兩個點:(x,y)和(x,-y)。(x → 2x^2 - 1)就是點倍增法則。

Circle FFTs

Circle group也支持FFT,構造方式與FRI類似。Circle FFT處理的對象是Riemann-Roch空間:多項式模圓(x^2 + y^2 - 1 = 0)。

Circle FFT輸出的系數是特定基礎:{1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

開發者幾乎可忽略這點。STARKs只需將多項式作爲評估值集存儲。FFT用於低度擴展:給定N個值,生成k*N個同一多項式上的值。

商運算

在STARK協議中,常見操作是對特定點進行商運算。例如,證明P(x)=y:

1. 計算商Q = (P - y)/(X - x)
2. 證明Q是多項式而非分數

在circle group STARK中,由於沒有單一點的線性函數,需採用不同技巧替代傳統商運算方法。通過在兩點上評估來證明,添加一個不需關注的虛擬點。

如果多項式P在x1處等於y1,在x2處等於y2,選擇插值函數L在x1處等於y1,在x2處等於y2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

然後證明P - L在這兩點爲零,通過L除以L來證明商Q是多項式。

消失多項式

在STARK中,多項式方程通常形如C(P(x), P(next(x))) = Z(x) · H(x),Z(x)在整個評估域上爲零。

在圓形STARK中,相應函數是: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

消失多項式可從折疊函數推導:常規STARK重復使用x → x^2,圓形STARK重復使用x → 2x^2 - 1。

反向位序

STARKs中,多項式評估通常按反向位序排列。例如n=16時: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

這種排序使FRI評估過程中早期分組的值在排序中相鄰,節省空間。

在circle STARKs中,折疊結構略有不同。調整反向位序以反映這種結構,需反轉除最後一位的每一位,用最後一位決定是否翻轉其他位。

大小爲16的折疊反向位序: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

效率

Circle STARKs非常高效。計算通常涉及:

1. 原生算術:用於業務邏輯
2. 原生算術:用於加密學
3. 查找參數:通用高效計算方法

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

Binius比Circle STARKs更好,允許混合不同大小字段,實現更高效位打包。但代價是概念更復雜,Circle STARKs概念相對簡單。

結論

Circle STARKs對開發者並不比STARKs復雜。理解Circle FRI和Circle FFTs可作爲理解其他特殊FFTs的途徑。

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

1. 最大化哈希函數和籤名等的算術化效率
2. 遞歸構造以啓用更多並行化
3. 算術化虛擬機以改善開發者體驗