探索Circle STARKs

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

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

使用小字段的常見問題

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

例如,假設要證明多項式A滿足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位字段中很簡單:選擇隨機256位數字即可。但在小字段中,可選的r值只有約20億種,攻擊者雖然工作量很大但仍可能嘗試所有可能。

有兩個解決方案:

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

多次檢查簡單有效,但存在效率問題。擴展字段類似復數,但基於有限域。引入新值α滿足某關係,如α^2=某值。這創建了新的數學結構,可在有限域上進行更復雜運算。擴展域僅在需要隨機線性組合時使用,大部分運算仍在基礎字段進行。

常規FRI

構建SNARK或STARK的第一步是將計算問題轉化爲多項式方程P(X,Y,Z)=0。解決方案需證明提出的值是合理的多項式,且度數有限。這通過逐步應用隨機線性組合實現:

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隔離A的偶數系數,C隔離奇數系數。給定B和C可恢復A:A(x) = B(x^2) + xC(x^2)。如果A度數<2^20,B和C的度數分別爲A的度數和A度數-1。D作爲隨機組合,度數應爲A的度數。

FRI通過將證明多項式度數爲d簡化爲證明度數爲d/2來簡化驗證。這個過程可重復多次,每次將問題簡化一半。如果某階段輸出不符合預期度數,那一輪檢查將失敗。

FRI每步將多項式次數和點集規模減半。前者是FRI工作的關鍵,後者使算法運行極快:總計算成本是O(N)而非O(N*log(N))。

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

BabyBear的模數使其最大乘法子羣包含所有非零值,大小爲2^k-1。這非常適合上述技術,可通過重復映射有效減少多項式度數。Mersenne31的乘法子羣大小爲2^31-1,只能除以2一次,之後無法使用該技術。

Mersenne31域非常適合32位CPU/GPU運算。其模數特性(如2^31-1)使許多運算可利用高效位操作:超過模數的結果可通過位移減小。乘法可用特定CPU指令高效處理。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)是點倍增法則。我們將圓上兩個相對點的x坐標轉換爲倍增後點的x坐標。

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中,由於沒有通過單點的線性函數,需要不同技巧。可以構造切線函數,但它在點上具有重數2。因此必須在兩點上評估來證明。

如果P在x1處等於y1,在x2處等於y2,我們選擇插值函數L在這兩點相等。然後證明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

反向位序

STARKs中多項式評估通常按反向位序排列。在circle STARKs中,折疊結構略有不同:

• 第一步:(x,y)與(x,-y)配對
• 第二步:x與-x配對
• 後續步驟:p與q配對,使Q^i(p) = -Q^i(q)

爲調整反向位序,需反轉除最後一位外的每一位,用最後一位決定是否翻轉其他位。

效率

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

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

效率關鍵在於充分利用計算跟蹤空間。這裏字段大小爲2^31,浪費空間不大。Poseidon等哈希在任何字段中都充分利用每個數字的每一位。

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

結論

Circle STARKs對開發者而言並不比STARKs復雜。實現中與常規FRI的主要區別在於上述三個問題。盡管背後數學復雜,但這種復雜性被很好地隱藏。

理解Circle FRI和FFTs可以成爲理解其他特殊FFTs的途徑,如二進制域FFTs和橢圓曲線FFTs。

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

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