Author: Vitalik Buterin, Translator: Kurt Pan, XPTY
This article assumes that you are familiar with the basics of how SNARK and STARK work; if you are not familiar, it is recommended to read the first few sections of this article. Special thanks to Eli ben-Sasson, Shahar Papini, Avihu Levy, and others at starkware for their feedback and discussions.
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
This transformation This has resulted in significant improvements in proof speed, most notably Starkware's ability to prove 620,000 Poseidon2 hashes per second on an M3 laptop. Specifically this means that as long as we are willing to trust Poseidon2 as part of the hash function, one of the most difficult parts of building an efficient ZK-EVM has been efficiently solved. But how do these techniques work, and how are cryptographic proofs (which often require large integers for security) built on these domains? And how do these protocols compare to more exotic constructs like Binius? This article will explore some of the subtle differences, focusing specifically on a construct called Circle STARKs (implemented in Starkware's stwo, Polygon's plonky3, and my own python implementation), which have some unique properties designed to Compatible with the efficient Mersenne31 domain.
https://x.com/StarkWareLtd/status/1807776563188162562
< /li>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
One of the most important "tricks" when doing hash-based proofs (or indeed any kind of proof) is to prove something about the evaluation of the polynomial at random points instead of proving something about the underlying polynomial .
There are two natural solutions to this problem:
< /p>
The implementation here is not optimal (it can be optimized with Karatsuba), it just shows the principle
These Dots follow the law of addition, and if you've studied trigonometry or complex multiplication recently, you may find this law familiar:
- https://unacademy.com/content/cbse-class-11/study -material/mathematics/algebra-of-complex-numbers-multiplication/
From the second round onwards, the mapping changes:
From here, let’s get into some more esoteric details, for those who implement circle STARK, vs. conventional These details will be different compared to STARK.
Therefore, circle STARK is actually very close to optimal! Binius is even more powerful as it allows mixing and matching domains of different sizes, giving more efficient bit packing for everything. Binius also provides the option to perform 32-bit additions without the overhead of a lookup table. However, these gains come at the cost of (in my opinion) significantly higher theoretical complexity, whereas circle STARK (and regular STARK based on BabyBear) are conceptually quite simple.
Compared with regular STARK, Circle STARK does not bring much additional complexity to developers. During the implementation process, the above three issues are basically the only differences I see compared to conventional FRI. The math behind the "polynomials" that Circle FRI operates on is quite counter-intuitive and takes a while to understand and appreciate. But it happens that this complexity is hidden so that developers don't see too much of it. The complexity of Circle mathematics is encapsulated, not systematic.
https://vitalik.eth.limo/general/2022/02/28/ complexity.html
Understanding circle FRI and circle FFT is also a good intellectual approach to understanding other "exotic FFTs": the most noteworthy is a binary domain FFT, previously used in Binius and LibSTARK, as well as more bizarre constructs, such as the elliptic curve FFT, which uses several to one mappings and works well with elliptic curve point operations.
https://github.com/ethereum/research/blob/master/binius/ binary_ntt.py#L60
https://github.com/elibensasson/libSTARK
https://arxiv.org/abs/2107.08473
By combining Mersenne31, BabyBear and binary domain technology such as Binius, we do feel that we are approaching the limits of STARK's "base layer" efficiency. At this point in time, I expect the frontier of STARK optimization to shift towards the most efficient arithmeticization of primitives like hash functions and signatures (and optimizing those primitives themselves for this purpose), recursive constructions to unlock more parallelization, Arithmetize virtual machines to improve developer experience, and other high-level tasks.
The premise for understanding this article is that you already know the basic principles of SNARKs and STARKs. If you are not familiar with them, it is recommended that you read the first few parts of this article to understand the basics.
JinseFinanceETH, interpretation of Vitalik’s latest article Golden Finance, the soul of Ethereum and the essence of the crypto world remain.
JinseFinanceThis post is primarily intended for readers who are generally familiar with cryptography in the 2019 era, especially SNARKs and STARKs.
JinseFinanceVitalik has joined forces with four co-authors to unveil in a research paper that introduces a technological marvel known as "privacy pools," designed to address one of the most pressing issues in the blockchain sphere.
CatherineThe new update includes “The Scourge” which would help to solve MEV issues.
BeincryptoWhat a decade of essays – covering everything from Soulbound tokens to superrational DAOs – says about Ethereum and crypto.
CoindeskThe inventor of Ethereum Vitalik Buterin and his father Dmitry “Dima” Buterin talked about the crypto market, volatility, and speculators. ...
BitcoinistCompared with PoW, PoS is a better blockchain security mechanism.
链向资讯Compared with PoW, PoS is a better blockchain security mechanism.
FtftxThe small southeast European nation is beginning to sift through the murky waters of blockchain regulation by granting the Ethereum co-founder citizenship.
Cointelegraph
