原文標題：Exploring circle STARKs

原文作者：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://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