A Short History of Plonky2

If you’re interested in the development of the ideas behind Plonky2, read on for a very high-level version.

2018/2019

Eli Ben-Sasson and the Starkware team introduced STARKs in 2018, the first fully transparent, quantum-safe proof system with a scalable verifier. In 2019, the DEEP-FRI paper, describing further optimizations to FRI, the PCS powering STARKs, was released. STARKs demonstrated that a variant of PCPs (Probabilistically Checkable Proofs) known as IOPs (Interactive Oracle Proofs) could be far more performant than existing schemes like Groth16. STARKs are extraordinarily powerful and even five years after their invention, they power the leading ZK L2s in the space, like StarkNet and Polygon zkEVM.

At the beginning of 2019, Sean Bowe and Mary Maller published a breakthrough paper, Sonic, that gave a technique for building a SNARK with a universal trusted setup. These ideas led to the development of PLONK by Zac Williamson, Ariel Gabizon, and Oana Ciobotaru. Plonk was a huge breakthrough because it gave a far more efficient SNARK with a universal setup. Components from PLONK are still used heavily in Polygon, zkSync, and others.

One way of looking at this progression is that after Sonic, researchers realized that certain SNARKs have two components: the argument/IOP and the polynomial commitment scheme. The insight from Plonk (and Marlin) was that these components could be mixed and matched, and that it was possible to replace the argument component from Sonic with a more efficient variant.

FRI as PCS

A natural idea was to use FRI from STARKs as a polynomial commitment scheme. The modern approach used by Plonky2, ethSTARK, and others (using a delta parameter outside the unique decoding radius) was first described in the DEEP-FRI paper in 2019. Six months later, the Matter Labs team also published a version of a PCS using FRI, but this variant is less practical and not currently in use.

Fractal was published shortly afterward, and details the use of FRI as a PCS in a transparent SNARK. It uses the same IOP as Marlin and FRI as the PCS. Using the PLONK IOP instead was a natural choice, and Matter Labs did exactly this with RedShift a few months later. Note that RedShift used the PCS previously described in the DEEP-FRI paper.

RedShift was a nice idea - using PLONK + FRI made a lot of sense - but proof sizes were large and proof time didn’t represent a significant improvement over the state of the art. The bigger barrier was that recursion, necessary to parallelize proof generation, wasn’t really feasible. Fractal included recursion benchmarks for a SNARK using FRI and it took almost 10 minutes to generate a single recursive proof.

As a result, RedShift wasn’t performant enough to use in zkSync, the product developed by its authors. They remained using PLONK + KZG for almost 4 years, until 18 months after Plonky2 was developed.

The Plonky2 Breakthrough

In 2020, we were trying to implement an efficient proof system. We implemented Plonky, an implementation based on Halo, but we were struggling with the complexity of accumulation schemes using cycles of elliptic curves.

Daniel Lubarov had been interested in Fractal and STARKs for a long time, and believed that using FRI could offer a realistic path to radically improving prover performance. This wasn’t a consensus view - remember that Fractal had extremely slow recursive proofs.

However, Daniel, William Borgeaud, and Hamish Ivey-Law from the Mir team believed that it was possible to achieve huge performance gains through careful optimization and a deep understanding of how to build proof systems to run efficiently on hardware.

Using FRI achieved two things: first, it allowed us to avoid the complexity of accumulation schemes using cycles of elliptic curves, and second, it allowed us to use small fields that would be far faster on modern hardware. Plonky2 (PLONK + FRI) and Starky (hyper-performant STARKs) are the result of dozens of careful optimizations designed to achieve maximum performance.

What made Plonky2 so compelling was that it fixed the performance issues with recursion in Fractal and RedShift. For the first time, a FRI-based scheme could be used to generate super fast recursive proofs - in just 170ms on a Macbook Pro. This removed any barrier to using Plonky2 and Starky in production.

We built Plonky2 and Starky and achieved a 10-100x improvement in performance, depending on the application. Almost two years later, Starky remains the fastest prover in a third-party benchmark.

Plonky2, Starky and RedShift

So is Plonky2 just RedShift? It is in the sense that the RedShift paper laid claim to the idea of PLONK+FRI (though Fractal had already established using FRI in a SNARK). However, it’s completely different from the scheme actually described in the paper, and represents a massive performance improvement. It would be impossible to implement Plonky2 from the RedShift paper.

Starky is not RedShift at all - it’s a STARK and has nothing to do with PLONK. Starky is much more performant than Plonky2 and is used for all expensive transaction-level proofs on Polygon zkEVM. Plonky2 and Starky have never claimed to be new SNARKs or STARKs. They are PLONK and STARK implementations (hence the names) that are hyper-performant and represent a tremendous improvement over the previous state of the art.

Plonky2 and Starky are engineering and applied cryptography achievements, not academic papers. Claiming that Plonky2 is just RedShift minimizes the hard work from many people that went into building Plonky2. It’s indicative that Matter Labs, the creators of RedShift, didn’t move to a scheme like RedShift for almost four years after publishing the paper (and more than 18 months after Plonky2 was released).

Here’s an easier question: is Boojum just Plonky2? Of course, they even share some of the same code. 😁