探索Circle STARKs

近年來，STARKs協議設計的趨勢是轉向使用較小的字段。最早期的STARKs生產實現使用的是256位字段,即對大數字進行模運算,這使得這些協議與基於橢圓曲線的籤名兼容。但是這種設計的效率比較低,一般情況下,處理計算這些大數字並沒有實際的用途,還會浪費很多的算力。爲了解決這個問題,STARKs開始轉向使用更小的字段:首先是Goldilocks,然後是Mersenne31和BabyBear。

這種轉變提升了證明速度,比如Starkware能夠在一臺M3筆記本電腦上每秒證明620,000個Poseidon2哈希值。這意味着,只要我們願意信任Poseidon2作爲哈希函數,那麼就可以解決開發高效的ZK-EVM中的難題。那麼這些技術是如何工作的?這些證明如何在較小的字段上建立?這些協議與Binius等解決方案相比如何?本文將探討這些細節,特別關注一種名爲Circle STARKs的方案,這種方案具有與Mersenne31字段兼容的獨特屬性。

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

在創建基於哈希的證明(或任何類型的證明)時,一個非常重要的技巧是通過對多項式在隨機點的評估結果進行證明,能夠間接驗證多項式的性質。這種方法可以大大簡化證明過程,因爲在隨機點的評估通常比處理整個多項式要容易得多。

例如,假設一個證明系統要求你生成一個對多項式的commitment,A,必須滿足A^3(x) + x - A(ωx) = x^N(ZK-SNARK協議中一種非常常見的證明類型)。協議可以要求你選擇一個隨機坐標r並證明A(r) + r - A(ωr) = r^N。然後反推A(r) = c,你證明了Q = (A - c)/(X - r)是一個多項式。

爲了防止攻擊,我們需要在攻擊者提供了A之後再選擇r。選擇的參數需要來自一個足夠大的集合,以確保攻擊者無法預測或猜測這些參數,從而提高系統的安全性。

在基於橢圓曲線的協議和2019年時期的STARKs中,這個問題很簡單:我們所有的數學運算都在256位的數字上進行,因此我們可以將r選擇爲一個隨機的256位數字,這樣就可以了。然而,在較小字段上的STARKs中,我們遇到了一個問題:只有大約20億種可能的r值可以選擇,因此一個想要僞造證明的攻擊者只需要嘗試20億次,雖然工作量很大,但對於一個下定決心的攻擊者來說,還是完全可以做到的!

這個問題有兩個解決方案:

• 進行多次隨機檢查
• 擴展字段

執行多次隨機檢查的方法是最簡單有效的:與其在一個坐標上進行檢查,不如在四個隨機坐標上重復檢查。這在理論上是可行的,但存在效率問題。如果你處理的是一個度數小於某個值的多項式,並且在某個大小的域上進行操作,攻擊者實際上可以構造看起來在這些位置上都很正常的惡意多項式。因此,他們能否成功破壞協議是一個概率性問題,因此需要增加檢查的輪數,以增強整體的安全性,確保能夠有效防御攻擊者的攻擊。

這引出了另一個解決方案:擴展域,擴展域類似於復數,但它是基於有限域的。我們引入一個新的值,記作α,並聲明其滿足某種關係,比如α^2=some value。通過這種方式,我們創建了一個新的數學結構,能夠在有限域上進行更復雜的運算。在這種擴展域中,乘法的計算變爲使用新值α的乘法。我們現在可以在擴展的域中操作值對,而不僅僅是單個數字。比如,如果我們在Mersenne或BabyBear這樣的字段上工作,這樣的擴展允許我們有更多的值選擇,從而提高安全性。爲了進一步提高字段的大小,我們可以重復應用相同的技術。由於我們已經使用了α,所以我們需要定義一個新的值,這在Mersenne31中表現爲選擇α使得α^2=some value。

通過擴展域,我們現在有了足夠多的值來選擇,滿足我們的安全需求。如果處理的是度數小於d的多項式,每輪可以提供104位的安全性。這意味着我們有足夠的安全保障。如果需要達到更高的安全級別,比如128位,我們可以在協議中加入一些額外的計算工作,以增強安全性。

擴展域僅在FRI(Fast Reed-Solomon Interactive)協議和其他需要隨機線性組合的場景中實際使用。大部分的數學運算仍然在基礎字段上進行,這些基礎字段通常是模p或q的字段。同時,幾乎所有哈希的數據都是在基礎字段上進行的,因此每個值只需哈希四字節。這樣做可以利用小字段的高效性,同時在需要進行安全性增強時,可以使用更大的字段。

Regular FRI

在構建SNARK或STARK時,第一步通常是arithmetization。這是將任意計算問題轉化爲一個方程,其中某些變量和系數是多項式。具體來說,這個方程通常會看起來像P(X,Y,Z)=0,其中P是一個多項式,X、Y和Z是給定的參數,而求解器需要提供X和Y的值。一旦有了這樣的方程,該方程的解就對應於底層計算問題的解。

要證明你有一個解,你需要證明你所提出的值確實是合理的多項式(而不是分數,或者在某些地方看起來像一個多項式,而在其他地方卻是不同的多項式,等等),並且這些多項式具有一定的最大度數。爲此,我們使用了一個逐步應用的隨機線性組合技巧:

• 假設你有一個多項式A的評估值,你想證明它的度數小於2^20
• 考慮多項式B(x^2) = A(x) + A(-x),C(x^2) = (A(x) - A(-x))/x
• D是B和C的隨機線性組合,即D=B+rC,其中r是一個隨機系數。

本質上,發生的事情是B隔離偶數系數A,和C隔離奇數系數。給定B和C,你可以恢復原始多項式A:A(x) = B(x^2) + xC(x^2)。如果A的度數確實小於2^20,那麼B和C的度數將分別爲A的度數和A的度數減去1。因爲偶次項和奇次項的組合不會增加度數。由於D是B和C的隨機線性組合,D的度數也應爲A的度數,這使得你可以通過D的度數來驗證A的度數是否符合要求。

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

FRI的工作原理是重復這個簡化過程。例如,如果你從證明多項式的度數爲d開始,通過一系列步驟,你將最終證明多項式的度數爲d/2。每次簡化後,生成的多項式的度數逐步減小。如果某個階段的輸出不是預期的多項式度數,那麼這一輪的檢查將失敗。如果有人試圖通過這種技術推送一個不是度數爲d的多項式,那麼在第二輪輸出中,其度數將有一定的概率不符合預期,第三輪中會更有可能出現不符合的情況,最終的檢查將失敗。這種設計可以有效地檢測並拒絕不符合要求的輸入。如果數據集在大多數位置上等於一個度數爲d的多項式,這個數據集有可能通過FRI驗證。然而,爲了構造這樣一個數據集,攻擊者需要知道實際的多項式,因此即使有輕微缺陷的證明也表明證明者能夠生成一個"真實"的證明。

讓我們更詳細地了解一下這裏發生的情況,以及使這一切正常運作所需的屬性。在每一步中,我們將多項式的次數減少一半,同時也將點集(我們關注的點的集合)減少一半。前者是使FRI(Fast Reed-Solomon Interactive)協議能夠正常工作的關鍵。後者則使得算法運行速度極快:由於每一輪的規模比上一輪減少一半,總的計算成本是O(N),而不是O(N*log(N))。

爲了實現域的逐步減少,使用了一個二對一映射,即每個點都映射到兩個點中的一個。這種映射允許我們將數據集的大小減少一半。這個二對一映射的一個重要優點是它是可重復的。也就是說,當我們應用這個映射時,得到的結果集仍然保留了相同的屬性。假設我們從一個乘法子羣(multiplicative subgroup)開始。這個子羣是一個集合S,其中每個元素x都有其倍數2x也在集合中。如果對集合S進行平方操作(即將集合中的每個元素x映射到x^2),新的集合S^2也會保留同樣的屬性。這種操作允許我們繼續減少數據集的大小,直到最終只剩下一個值。雖然理論上我們可以將數據集縮小到只剩一個值,但在實際操作中,通常會在到達一個較小的集合之前就停止。

你可以將這個操作想象成一個將圓周上的一條線(例如,線段或弧)沿圓周伸展的過程,使它繞圓周旋轉兩圈。例如,如果一個點在圓周上位於x度的位置,那麼在經過這個操作後,它會移動到2x度的位置。圓周上的每個點從0到179度的位置,都有一個對應的點在180到359度的位置,這兩個點會重合。這意味着,當你將一個點從x度映射到2x度時,它會與一個位於x+180度的位置重合。這個過程是可以重復的。也就是說,你可以多次應用這個映射操作,每次都將圓周上的點移動到它們的新位置。

爲了使映射技術有效,原始乘法子羣的大小需要具有大的2的冪作爲因子。BabyBear是一個具有特定模數的系統,其模數爲某個值,使得其最大乘法子羣包含所有非零值,因此子羣的大小爲2k−1(其中k是模數的位數)。這種大小的子羣非常適合上述技術,因爲它允許通過重復應用映射操作來有效地減少多項式的度數。在BabyBear中,你可以選擇大小爲2^k的子羣(或者直接使用整個集合),然後應用FRI方法將多項式的度數逐步減少到15,並在最後檢查多項式的度數。這種方法利用了模數的性質和乘法子羣的大小,使得計算過程非常高效。Mersenne31是另一個系統,其模數爲某個值,使得乘法子羣的大小爲2^31 - 1。在這種情況下,乘法子羣的大小只有一個2的冪作爲因子,這使得它只能被除以2一次。之後的處理不再適用上述技術,也就是說,無法像BabyBear那樣使用FFT進行有效的多項式度數減少。

Mersenne31域非常適合在現有的32位CPU/GPU操作中進行算術運算。因爲其模數的特性(例如2^31 - 1)使得很多運算可以利用高效的位操作來完成:如果兩個數字相加的結果超過了模數,可以通過將結果與模數進行位