Vitalik最新文章：探祕 Circle STARKs
發表於 2024-07-24 09:49 作者： XPTY
作者：Vitalik Buterin，譯者：Kurt Pan，XPTY
本文假設你熟悉 SNARK 和 STARK 工作原理的基礎知識；如果你並不熟悉，建議閱讀此文的前幾節。特別感謝 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/
這一轉變已經使得證明速度大幅提升，最顯著的是 Starkware 能夠在一台 M3 的筆記本電腦上 每秒證明 620,000 個 Poseidon2 哈希。具體來說這意味着，只要我們愿意信任 Poseidon2 作爲哈希函數的部分，那么構建一個高效的 ZK-EVM 中最困難的部分之一就已經得到了高效解決。但這些技術是如何工作的，密碼學證明（通常需要大整數來保證安全性）是如何在這些域上構建的？以及這些協議與更奇特的 構造（比如 Binius）又如何比較？這篇文章將探討其中的一些微妙差別，會特別關注一種稱爲 Circle STARKs 的構造（在 Starkware 的 stwo、Polygon 的 plonky3 和 我自己的python 實現 中有實現），其具有一些獨特的性質，旨在與高效的 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
小域常見的問題
在進行基於哈希的證明（或實際上任何類型的證明）時，最重要的“技巧”之一是用證明有關多項式在隨機點的求值以代替證明有關底層多項式的事情。
https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
這個問題有兩個自然的解決方案：
執行多次隨機檢驗 擴域
- https://www2.clarku.edu/faculty/djoyce/complex/mult.html
這裏實現不是最優的（可以用Karatsuba優化），只是展示原理
常規 FRI
https://eccc.weizmann.ac.il/report/2017/134/
Circle FRI
- https://elibensasson.blog/why-im-excited-by-circle-stark-and-stwo/
這些點遵循加法律，如果你最近學過 三角學 或 復數乘法，你可能會覺得這個定律很熟悉：
- 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
從這裏开始，讓我們來了解一些更深奧的細節，對於實現circle STARK 的人來說，與常規 STARK 相比，這些細節會有所不同。
取商
https://eprint.iacr.org/2019/336
消失多項式
反轉比特序
效率
因此，circle STARK 實際上非常接近最優了！Binius 甚至更強大，因爲它允許混合搭配不同大小的域，從而爲所有東西給出更高效的位打包。Binius 還提供了執行 32 比特加法的選項，且無需產生查找表的开銷。然而，這些收益是以（在我看來）顯著更高的理論復雜性爲代價的，而circle STARK（以及基於 BabyBear 的常規 STARK）在概念上是相當簡單的。
結論：我對 circle STARKs 怎么看？
與常規 STARK 相比，Circle STARK 並不會給开發者帶來太多額外的復雜性。在實現的過程中，上述三個問題基本上就是我看到的與常規 FRI 相比的唯一區別。Circle FRI 所操作的“多項式”背後的數學原理是相當反直覺的，需要一段時間才能理解和領悟。但恰好這種復雜性被隱藏起來了使得开發者不會看到太多。Circle 數學的復雜性是封裝過的，而不是系統性的。
https://vitalik.eth.limo/general/2022/02/28/complexity.html
理解circle FRI 和circle FFT 還是理解其他“奇異 FFT”的良好智力途徑：最值得注意的是 二進制域 FFT，之前在 Binius 和 LibSTARK 中使用，還有更奇詭的構造，如 橢圓曲线 FFT，其使用幾對一映射，可以很好地與橢圓曲线點運算配合使用。
https://github.com/ethereum/research/blob/master/binius/binary_ntt.py#L60
https://github.com/elibensasson/libSTARK
https://arxiv.org/abs/2107.08473
通過結合 Mersenne31、BabyBear 和 二進制域技術比如Binius，我們確實感覺得到正在接近 STARK “基礎層”效率的極限。在這個時間點，我預計 STARK 優化的前沿將轉向對哈希函數和籤名等原語進行最高效的算術化（並爲此目的優化這些原語本身）、進行遞歸構造以解鎖更多並行化、對虛擬機進行算術化以提升开發者體驗，以及其他上層任務。
標題：Vitalik最新文章：探祕 Circle STARKs
地址：https://www.coinsdeep.com/article/146100.html
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。