Why starky?

  • Easy to understand basic framework structure, every STARK is just a table, where each row represents a state and constraints represent state transitions. Actual implementation details are well-isolated and basic things could be written without any knowledge about underlying cryptographic concepts.

  • Integrated with Plonky2. Starky naturally produces large proofs, but these proofs can be easily compressed by Plonky2. Also some functions can be offloaded to an already existing Plonky gates.

  • CTLs are already implemented in recent versions. For more complicated proofs CTLs allow task-based proof decomposition. This decomposition leads to tremendously more homogenous data in each table, bringing constraint complexity down and improving proof generation efficiency.

  • Ease of decomposition allows wide code reuse. While customized solutions work really well, it’s always better to create scaffolding from already working parts and then customize them one-by-one.

  • Modularity also brings the ability to parallelize development. Team effort not only slashes development time, but enables code cross-review and simplify onboarding of new team members.

  • Streamlined development process. Starky imposes some limitations on project structure, but it also serves as a starting point with a defined set of actions to reach your goal. While not as flexible as Plonky2 itself, Starky handles most of the business-oriented projects well enough. Research projects may benefit from more flexibility, but Starky gets things done.

Pure tech reasons

The real power comes from the combination of starky and plonky2 - only using one of them leaves a lot of performance gains on the table:

Most people know that the FRI blowup factor presents a tradeoff - a small blowup factor means a faster prover, slower verifier, and bigger proofs, while a big blowup factor means a slower prover, faster verifier, and smaller proofs. It’s also relatively well-known that the blowup factor increases in increments of powers of two (for FFT reasons), so increasing the blowup factor means making the prover around twice as slow.

What people don’t know is that the maximum degree of any one constraint in your circuit is limited by the blowup factor. Specifically, it can be at most the blowup factor plus one. What this means is that the blowup factor provides another tradeoff - by increasing the blowup factor, you gain access to more complex “custom gates”, which often allows for smaller circuits. However, this comes at the cost of a ~2x slowdown in “raw” prover time, so it’s only worth it for circuits that can be made more than twice as small with higher-degree custom gates.

In practice, this is not the case for most computations. Most of the time, if you want the fastest prover, you want to crank the blowup factor as far down as humanly possible - ideally all the way down to 2 (any less and FRI doesn’t work). However, this is the case for FRI recursion, which is dominated by SNARK-friendly hashing. Therefore, the prover with the fastest recursion is not the same as the prover with the fastest “raw” prover time

Plonky2 uses a blowup factor of 8 so that it can utilize a custom gate to do an entire round of Poseidon in a single row of the circuit, and it builds atop PLONK because it provides the flexibility needed to pack those gates into the smallest area possible. This leads to a proof system that’s blazing fast at recursion, but slower at pretty much everything else.

Starky, on the other hand, is a STARK, not a PLONK. That means it doesn’t need the overhead from copy constraints and permutation polynomials that PLONK does. By removing this overhead, starky can turn the blowup factor all the way down to 2 while still being able to write meaningfully-expressive degree-3 constraints. This leads to the fastest “raw” proving time for the vast majority of statements, even though it’s slower than plonky2 when it comes to recursion.

The real magic happens when we combine them - since starky and plonky2 are defined over the same field and hash functions, plonky2 is incidentally quite good at verifying starky proofs - and since plonky2 is also good at recursion, it’s good at merging starky proofs too. Therefore, by combining the two, we can have our cake and eat it too - we can prove our statements with starky, which is fastest at that, and then merge them together with plonky2, which is fastest at that.

If we only use plonky2, we’re leaving a ton of performance gains on the table. Only by using it together with starky do we fully take advantage of the FRI blowup factor.

Last updated