探索Circle STARKs

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

使用小字段可以大幅提升證明速度。例如Starkware能在M3筆記本上每秒證明62萬個Poseidon2哈希。但小字段也帶來了新的挑戰,如何在有限的選擇空間中保證安全性。

本文將探討Circle STARKs,這是一種與Mersenne31字段兼容的新方案。Circle STARKs通過在圓上的點羣上操作,解決了小字段帶來的安全性問題。

Circle FRI

Circle FRI的核心思想是在圓上定義一個大小爲p的點羣,這個羣具有二對一映射的性質。羣中的點滿足x^2 + y^2 = 1 (mod p)。

Circle FRI的映射過程如下:

1. 首先將所有點收斂到x軸上
2. 進行隨機線性組合得到一維多項式P(x)
3. 從第二輪開始使用映射 f_0(2x^2-1) = (F(x) + F(-x))/2

這個過程每次將點集的大小減半,類似於常規FRI。

Circle FFTs

Circle羣也支持FFT,其構造與Circle FRI類似。不同之處在於Circle FFT處理的不是嚴格意義上的多項式,而是Riemann-Roch空間。

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

作爲開發者,可以忽略這些數學細節,只需將多項式存儲爲評估值集合即可。

其他技術細節

• Circle STARKs中的商運算需要在兩個點上進行評估
• 消失多項式的構造方式不同
• 使用修改後的反向位序來適應Circle STARKs的折疊結構

效率

Circle STARKs在31位素數字段上非常高效:

• 充分利用了計算空間
• 適用於業務邏輯和加密計算
• 支持高效的查找表操作

相比之下,Binius方案在效率上略勝一籌,但概念更爲復雜。

總結

Circle STARKs對開發者來說並不比常規STARKs復雜。它爲小字段STARKs提供了一種優雅的解決方案,有望推動STARKs技術向更高效率發展。

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

• 優化哈希函數等基礎密碼原語
• 使用遞歸構造提高並行性
• 改進虛擬機的算術化以提升開發體驗