Scaling Solutions

Privacy Solutions

Polygon ID
New

A Blockchain-native Identity System

Frameworks

Polygon Edge

A modular and extensible framework

Polygon dApps

Add Polygon PoS Network to Metamask

PoS DApps

Hermez DApps

Polygon Team

Nov 7, 2022Polygon ZK

The ZK Whiteboard Sessions recently published Module 13 of their dev-driven educational series for everything Zero Knowledge. The episode, titled “Fast Recursion with Plonky2,” features Polygon’s own Brendan Farmer and William Borgeaud, part of the team working on Plonky2.

Unveiled by Polygon in January, Plonky2 represented a major step forward for ZK proving systems. That major step forward is worth examining in greater detail. More precisely, how does Plonky2 optimize for speed and cost? And how do these optimizations open up the design space of ZK systems more generally?

Plonky2 is a proving system that generates zero-knowledge proofs (ZKPs). Plonky2 is able to unlock the scaling benefits of both SNARKS and STARKs, the two major types of zero-knowledge proofs. In this piece, we will dive deeply into how Plonky2 both turbo-charges performance and creates a wider range of implementation possibilities.

We’ll get into the details of what we mean by “recursive” in a moment. Let’s first recognize that every zero-knowledge proving system has two essential components. The first is the method for writing a program inside of an arithmetic circuit. The second component is the polynomial commitment scheme (PCS). This is the cryptographic toolkit that allows us to make our proofs succinct.

In selecting a polynomial commitment scheme for Plonky2, the Zero team needed something fast.

Many ZK rollups use KZG as their commitment scheme. One issue with KZG is that the resulting finite field is elliptic curve-based, and elliptic curve cryptography is limiting in a number of ways. For one thing, the elliptic curves that are most efficient for recursion aren’t natively supported by Ethereum. Moreover, elliptic curves require using larger finite fields (at least 256 bits) that are less efficient on modern CPUs.[1]

Instead of opting for KZG or another commitment scheme typical of SNARKs, Polygon Zero selected FRI, the commitment scheme typically associated with STARKs.

When it comes to speed, FRI offers an interesting tradeoff: It allows for fast proof-generation time, but the resulting proof is very large. And large proofs are expensive (and cumbersome) to post to the Ethereum Mainnet. FRI can also generate very small proofs, but it does so more slowly.

So which does one choose—a large proof, generated quickly? Or a small proof, generated slowly? In the case of Plonky2, the answer is yes.

Plonky2 uses large proofs when speed matters and small proofs when size matters. All the steps in recursion use different parameters to optimize for a given layer of proofing. Plonky2 thus takes full advantage of the distinctive time-space tradeoff available in FRI. It’s this flexibility that makes Plonky2 so useful across an array of implementations.

So given that Plonky2 unlocks the performance-enhancing powers of FRI, how do you make proof generation *even faster*? As Brendan puts it in the ZK Whiteboard Sessions: If you want to get really fast, you have to pay attention to what is really fast in hardware. Which is to say, you can build a tool that generates ZK proofs faster by optimizing for the hardware of users. And commercially-available CPUs perform arithmetic natively in 64-bits.

Prior iterations of recursive proof composition have required a trusted setup and cycles of expensive, pairing-friendly elliptic curves. But not so with Plonky2. This is due in part to the Goldilocks Field, a finite field modulus suggested by Polygon’s Hamish Ivey-Law.

**The Goldilocks Field **

*p* = 2 ^{64} - 2 ^{32 }+ 1

The Goldilocks Field optimizes for speed on the hardware side in two ways: it’s 64-bit, meaning any field element smaller than prime (*p*) fits in 64 bits. And the algebraic structure of this *p* allows for very efficient arithmetic on CPUs.

In a field operations performance measure, simply using Goldilocks’s 64-bit field instead of a 256-bit field like those in KZG Commitments improved proving speed by 40x.

Before we dive into using Plonky2 in an actual blockchain architecture, we need to understand the recursive properties of ZKPs. In a ZK-proof context, “recursion” simply means using a single proof to prove a set of separate proofs. Recursion is a major key to using ZKPs for blockchain scaling because it lets us turn a large set of transaction proofs into a single proof, vastly reducing the cost of validating transactions. Plonky2 was built for recursion.

Now that we understand FRI, the Goldilocks Field, and recursion, let’s look at how four transactions may be batched and recursively proven using Plonky2. At the top of the diagram are our transactions and at the bottom is Ethereum’s Mainnet.

The best way to write VMs in a ZK circuit is not with Plonky2, but with Starky, a complementary proving system also developed by Polygon Zero. Because Plonky2 is optimized for recursion and relational interconnectivity, it’s more robust than what’s needed to generate proofs for individual transactions. Starky uses the same finite field and hash functions as Plonky2 but without the computation-heavy arithmetizations. And so at the transaction level, Starky generates proofs in parallel. Plonky2 is then used at each additional layer for recursion.

Pairs of proofs are then converted into a single proof using Plonky2 with a lower rate. Because the smallest rate compatible with the transition constraints renders the fastest (and largest) proof. Those large proofs are again converted into a single proof using a higher rate, which generates the smallest proof size possible for posting to Ethereum’s Mainnet.

Fast when it needs to be. Small when it needs to be. Just right.

There’s a lot of talk in the L2 scaling space about hypothetical throughputs that might eventually be demonstrated. In the case of Plonky2, Polygon’s ZK teams have already provided publicly verifiable benchmarks. Back in 2020, the first recursive proofs posted to Ethereum took 60 seconds to generate. Today, Plonky2 generates a recursive proof on a MacBook Pro in 170ms.

Tune in to the Polygon Blog for more in this series, to get the latest on zero-knowledge proofs, and help us bring the world to Ethereum!

*Special thanks to Polygon Zero researcher Dmitry Vagner for feedback and review.*

Website | Twitter | Ecosystem Twitter| Developer Twitter | Studios Twitter | Telegram | Reddit | Discord| Instagram | Facebook | LinkedIn

[1] There is the possibility of using elliptic curves defined over the extension of a smaller field. Researchers have found curves like this over an extension of the Goldilocks field, but this approach hasn’t been explored for recursive SNARKs.