A STARK breakthrough: Next-gen provers may be at least 100x faster

In the arena of zero-knowledge proofs, STARKs are the OG and the Iron Man suit: foundational and cutting-edge.

Most major zk provers in production are STARK-based: zkSync’s Boojum, Polygon’s zkProver, Aleo’s Varuna​, Aztec Protocol and RISC Zero’s Zeth all employ STARKs (Scalable Transparent ARguments of Knowledge) underneath.

Recent research has significantly advanced the scalability of STARKs — increasing proving capacity by 100 times — for what’s being called Stwo, short for STARK Two. 

Scalability, when it comes to provers, means generating and verifying proofs quickly and cheaply. The “Transparent” part of STARKs eliminates the need for trusted setups required by many SNARK-based provers.

Read more: Zero-knowledge proof systems have room for improvement, say cryptography researchers

Stwo, which will be available in 2025, will eventually replace the current prover, Stone — for “STARK One.”

The secret to Stwo’s speed and efficiency lies in its use of the eighth Mersenne prime (or M31) for computations, which fits well with modern computer architectures to significantly speed up operations compared to Stone.

A Mersenne prime is a prime number that is one less than a power of two. These primes are named after the French monk Marin Mersenne, who studied them in the early 17th century. Specifically, a Mersenne prime can be expressed in the form Mn​=2n−1, where n itself is an integer. Not all numbers of this form are prime, but those that are have significant properties and applications in number theory and computer science.

They fit naturally with the way data is handled in modern computers, which often use fixed-size binary word lengths such as 32-bit or 64-bit integers. Operations involving M31 can therefore be efficiently implemented using standard binary arithmetic.

Without getting too far into the weeds, the breakthrough in this new research is the use of something every child learns about at an early age: the Circle.

Circle STARKs — a collaboration between StarkWare and Polygon Labs — use a clever geometric method to make cryptographic proofs faster, and the M31 field makes these operations even more efficient. Together, they enable the Stark Two prover to generate proofs quickly and with less computational power.

The research won’t only benefit Starknet, but many other proving systems, according to Ventali Tan, co-founder of Lita, which is building the Valida zk-Virtual Machine.

“Stwo gives another confirmation of the speed and power of the FRI polynomial commitment scheme, which is the main cryptographic ingredient in STARKs,” Tan told Blockworks. “This is the same scheme used as the basis of several of the most performant proof systems of recent generations, such as Plonky2 and Plonky3 — Valida, as well as Succinct’s SP1, is built on Plonky3.”

Tan notes that support for the circle STARK protocol and the M31 field are already on the roadmap for Plonky3, being developed by Polygon Labs .

StarkWare’s Eli Ben-Sasson told Blockworks all VMs will eventually benefit from this improved speed. “However, ZK-friendly VMs such as Cairo are designed to maximize STARK-proving efficiency and this added efficiency will likely remain,” he said.

Other provers may benefit less directly, suggests Ian Miers, a research scientist at Aleo.

“Aleo uses a different proof system, Varuna, built on different techniques than StarkWare’s work,” Miers told Blockworks. “Many SNARKs, of which STARKs are a sub-variety, are optimized for rollups , where a server sees everyone’s transactions and compresses as many as possible to save gas fees.”

Privacy-preserving blockchains like Aleo are aiming to give users more control over their own data by cutting the rollup operator out of the middle.

“There are trade-offs here, and excelling in one area may not mean excelling in another,” Miers said.

Read more: Privacy is paramount, and zero-knowledge cryptography is the way

In the fast moving world of zero-knowledge cryptography, there’s only one thing for certain, Miers added.

“There will always be a newer, better zk proof system, and you will eventually need to upgrade,” he said.

Updated July 3, 2024 at 2:59 pm ET: Clarifying the collaboration between StarkWare and Polygon Labs was limited to the circle STARK research. Added comment from Eli Ben-Sasson.

Start your day with top crypto insights from David Canellis and Katherine Ross. Subscribe to the Empire newsletter .

Explore the growing intersection between crypto, macroeconomics, policy and finance with Ben Strack, Casey Wagner and Felix Jauvin. Subscribe to the On the Margin newsletter .

The Lightspeed newsletter is all things Solana, in your inbox, every day. Subscribe to daily Solana news from Jack Kubinec and Jeff Albus.