Detailed explanation of Circle STARK and Stwo: Prover performance improved by 100 times

Source: Starknet Chinese

Introduction

The middle three paragraphs of this article (below) explain the mathematical principles and formulas of Circle STARK, which have not been translated. Please read the original text for details:

• STARK Efficiency means small numbers

• Efficiency means Optimizing multiplicative structures

• Thinking outside the box (domain)

Why Circle STARK and Stwo are exciting ?

The research results published last month are one of the most exciting scaling breakthroughs since Ethereum launched STARK. The mathematics of this research are complex, but the use of the classic circle (see Figure 1) increases STARK’s proof power by a factor of 100 or more.

The research was a collaboration between Ulrich Haböck of Polygon Labs and David Levit and Shahar Papini of StarkWare, and will be widely applicable. StarkWare is also proud to quickly bring it to practical use by building and open-sourcing the Stwo prover. In this article, I will try my best to explain the mathematics and why it is important in the simplest way possible.

STARK’s scalability and transparency< br>

I first introduced the term STARK at the Stanford Blockchain Conference in 2017. STARK defines a set of protocols to ensure computational integrity, with particular emphasis on scalability and transparency—corresponding to the S and T in STARK, respectively. Scalability includes the rapid and low-cost generation and verification of computational integrity proofs, enabling public use without relying on extensive or expensive processes. This feature is critical for applying integrity checks across different entities and drives StarkWare’s improvements in blockchain computing.

STARK's transparency means the elimination of "trust settings"; all procedures are based on open randomness, thereby reducing trust assumptions. This is critical to maintaining the integrity of calculations, especially against influential entities that may exploit system parameters.

Scalability and transparency together define the core of STARK technology, providing a secure, scalable, transparent and public verification method. Ensuring that proven systems adhere to these principles is critical to maintaining efficient, reliable operations. Whether you call your system STARK or something else, be aware of the significant benefits of both scalability and transparency, and ask your local attestation provider if their attestation system offers both. characteristic.

From Circle STARK to Stwo?

Stwo (aka STARK Two) is a new generation of Starknet provers designed to enhance, accelerate, and ultimately replace the current prover - Stone (aka STARK One). The Stwo is expected to be 100 times more efficient than the Stone and will use M31-based Circle STARK technology (mentioned above) as well as more. Other innovations include log-up and total sum-checking protocols (such as recent work by Haböck and Papini), simultaneous processing of multiple polynomials of different degrees ("mixed degrees"), and new foundations for coding circuits and virtual machines facility. So, in addition to expecting STARK proofs to be 100 times larger than Stone, we can also expect many other benefits that Stwo will bring, such as more flexibility to adopt new compilers and virtual machines, thereby increasing development speed. Click to learn more about Stwo.

The blueprint for a significant reduction in network costs involves mechanisms to reduce transaction fees, some of which will take effect immediately. The plan contains multiple steps, some of which are being advanced simultaneously, and will solve the problem of expensive transaction fees from multiple aspects.

KZG Commitment vs. Pairing-Based SNARKs?

KZG commitment is the main competitor to the FRI protocol used by Stone, Stwo and other STARKs, and is the mathematical basis for many pairing-based SNARKs . Its main advantage is the extreme simplicity of the final proof, which requires only about 200 bytes (versus FRI and current STARK requiring many kilobytes). Another advantage is that it has optimized support on Ethereum in a precompiled form for specific KZG parameter settings, integrated into the core Ethereum protocol via DankSharding. These optimization supports explain why many STARK systems (such as those used by Polygon, RiscZero, and ZKsync) end up wrapped inside a SNARK — in order to take advantage of Ethereum-specific precompiled optimization support. As long as there is specific optimization support for certain proof systems, teams will consider encapsulating their STARKs inside SNARKs, and we can expect more similar situations to happen. However, M31 multiplication is 100x or more faster than KZG secure primes (current best practices require such primes to be over 380 bytes!), so KZG and pairing-based systems are at a disadvantage in scale and throughput. It is unlikely to be as efficient as the Stwo in terms of volume. While the beauty of the scope of innovation in the field of elliptic curve mathematics and pairing-based SNARKs is breathtaking, we should remember that such SNARKs are not only inefficient, but also require a trusted setup and are vulnerable to attacks by quantum computers. In other words, STARK based on small finite fields is a better choice in terms of efficiency, security, and future adaptability.

Some final thoughts

Circle STARK marks an exciting progress in the field of STARK technology, moving from theory to practice. Circle STARK is also the latest milestone in the ongoing evolution of increasingly complex STARK proofs. As we move forward, these proofs will face new challenges and open up applications we have never imagined.

It is extremely exciting to see profound and fascinating mathematics being applied to the system to bring exponential growth to the expansion of the blockchain. ZK technology in the blockchain field has adopted cutting-edge "moon mathematics" more than once and used it to create innovative products. For example, Zcash deploys the first ZK-SNARK system deployed for general purpose circuits, which can provide financial privacy on the blockchain; STARK is the first and most efficient future-proof scaling technology on Ethereum; Cairo is used to write provable A new generation smart contract language for code. So I’m really excited to see what amazing applications and novel math Circle STARK and Stwo will unlock beyond expectations!