Vitalik最新文章：探秘 Circle STARKs

作者：Vitalik Buterin，譯者：Kurt Pan，XPTY

本文假設(shè)你熟悉 SNARK 和 STARK 工作原理的基礎(chǔ)知識；如果你并不熟悉，建議閱讀此文的前幾節(jié)。特別感謝 Eli ben-Sasson、Shahar Papini、Avihu Levy 和 starkware 的其他人員提供的反饋和討論。

• https://vitalik.eth.limo/general/2024/04/29/binius.html

• https://en.wikipedia.org/wiki/Karatsuba_algorithm

• https://polygon.technology/blog/plonky2-a-deep-dive

• https://blog.icme.io/small-fields-for-zero-knowledge/

這一轉(zhuǎn)變已經(jīng)使得證明速度大幅提升，最顯著的是 Starkware 能夠在一臺 M3 的筆記本電腦上 每秒證明 620,000 個 Poseidon2 哈希。具體來說這意味著，只要我們愿意信任 Poseidon2 作為哈希函數(shù)的部分，那么構(gòu)建一個高效的 ZK-EVM 中最困難的部分之一就已經(jīng)得到了高效解決。但這些技術(shù)是如何工作的，密碼學(xué)證明（通常需要大整數(shù)來保證安全性）是如何在這些域上構(gòu)建的？以及這些協(xié)議與更奇特的 構(gòu)造（比如 Binius）又如何比較？這篇文章將探討其中的一些微妙差別，會特別關(guān)注一種稱為 Circle STARKs 的構(gòu)造（在 Starkware 的 stwo、Polygon 的 plonky3 和 我自己的python 實(shí)現(xiàn) 中有實(shí)現(xiàn)），其具有一些獨(dú)特的性質(zhì)，旨在與高效的 Mersenne31 域兼容。

• https://x.com/StarkWareLtd/status/1807776563188162562

• https://vitalik.eth.limo/general/2022/08/04/zkevm.html

• https://vitalik.eth.limo/general/2024/04/29/binius.html

• https://www.irreducible.com/posts/binius-hardware-optimized-snark

• https://eprint.iacr.org/2024/278

• https://github.com/starkware-libs/stwo

• https://github.com/Plonky3/Plonky3

• https://github.com/ethereum/research/tree/master/circlestark

小域常見的問題

在進(jìn)行基于哈希的證明（或?qū)嶋H上任何類型的證明）時，最重要的“技巧”之一是用證明有關(guān)多項(xiàng)式在隨機(jī)點(diǎn)的求值以代替證明有關(guān)底層多項(xiàng)式的事情。

• https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic

這個問題有兩個自然的解決方案：

• 執(zhí)行多次隨機(jī)檢驗(yàn)
• 擴(kuò)域

• https://www2.clarku.edu/faculty/djoyce/complex/mult.html
  

這些點(diǎn)遵循加法律，如果你最近學(xué)過 三角學(xué) 或 復(fù)數(shù)乘法，你可能會覺得這個定律很熟悉：

- https://unacademy.com/content/cbse-class-11/study-material/mathematics/algebra-of-complex-numbers-multiplication/

從第二輪往后，映射改變：

Circle FFTs

• https://vitalik.eth.limo/general/2019/05/12/fft.html

• https://www.researchgate.net/publication/353344649_Elliptic_Curve_Fast_Fourier_Transform_ECFFT_Part_I_Fast_Polynomial_Algorithms_over_all_Finite_Fields

從這里開始，讓我們來了解一些更深奧的細(xì)節(jié)，對于實(shí)現(xiàn)circle STARK 的人來說，與常規(guī) STARK 相比，這些細(xì)節(jié)會有所不同。

取商

• https://eprint.iacr.org/2019/336

消失多項(xiàng)式

反轉(zhuǎn)比特序

效率

因此，circle STARK 實(shí)際上非常接近最優(yōu)了！Binius 甚至更強(qiáng)大，因?yàn)樗试S混合搭配不同大小的域，從而為所有東西給出更高效的位打包。Binius 還提供了執(zhí)行 32 比特加法的選項(xiàng)，且無需產(chǎn)生查找表的開銷。然而，這些收益是以（在我看來）顯著更高的理論復(fù)雜性為代價的，而circle STARK（以及基于 BabyBear 的常規(guī) STARK）在概念上是相當(dāng)簡單的。

結(jié)論：我對 circle STARKs 怎么看？

與常規(guī) STARK 相比，Circle STARK 并不會給開發(fā)者帶來太多額外的復(fù)雜性。在實(shí)現(xiàn)的過程中，上述三個問題基本上就是我看到的與常規(guī) FRI 相比的唯一區(qū)別。Circle FRI 所操作的“多項(xiàng)式”背后的數(shù)學(xué)原理是相當(dāng)反直覺的，需要一段時間才能理解和領(lǐng)悟。但恰好這種復(fù)雜性被隱藏起來了使得開發(fā)者不會看到太多。Circle 數(shù)學(xué)的復(fù)雜性是封裝過的，而不是系統(tǒng)性的。

• https://vitalik.eth.limo/general/2022/02/28/complexity.html

理解circle FRI 和circle FFT 還是理解其他“奇異 FFT”的良好智力途徑：最值得注意的是 二進(jìn)制域 FFT，之前在 Binius 和 LibSTARK 中使用，還有更奇詭的構(gòu)造，如 橢圓曲線 FFT，其使用幾對一映射，可以很好地與橢圓曲線點(diǎn)運(yùn)算配合使用。

• https://github.com/ethereum/research/blob/master/binius/binary_ntt.py#L60

• https://github.com/elibensasson/libSTARK

• https://arxiv.org/abs/2107.08473

通過結(jié)合 Mersenne31、BabyBear 和 二進(jìn)制域技術(shù)比如Binius，我們確實(shí)感覺得到正在接近 STARK “基礎(chǔ)層”效率的極限。在這個時間點(diǎn)，我預(yù)計(jì) STARK 優(yōu)化的前沿將轉(zhuǎn)向?qū)：瘮?shù)和簽名等原語進(jìn)行最高效的算術(shù)化（并為此目的優(yōu)化這些原語本身）、進(jìn)行遞歸構(gòu)造以解鎖更多并行化、對虛擬機(jī)進(jìn)行算術(shù)化以提升開發(fā)者體驗(yàn)，以及其他上層任務(wù)。