The Hunting of the SNARK (3/3)

Universal SNARKs, 2019–present, and PLONK benchmarks

Thomas Pocock
Oct 8 · 6 min read

A refresher on Part 2— the final punchline we want to reach is the enabling of Dark Contracts — allowing confidentiality and anonymity of arbitrary blockchain transactions.

But so far, SNARKs have required a new trusted setup for each new smart contract edit (a la Groth 16).

This overhead kills Project Dark Contract dead in the water.

The Universal SNARK

Because of this seemingly intractable feature of SNARKs (a new setup for each contract alteration), Dark Contracts looked in feasible — until January 2019, when Mary Maller and Sean Bowe et al released an amazing and unexpected new species of SNARK, which they named ‘Sonic’.

This new SNARK was universal — that is, with just one setup, it could validate any conceivable circuit (up to a predefined level of complexity).

Another big step forward in the short evolution of zero knowledge systems.

Sonic is Universal, But Slow

Unfortunately though, this magical ‘universality’ did not come for free.

Making Sonic universal added ~2 orders of magnitude onto proof construction times, compared with non-universal SNARKs.

And if your laptop needs to spend 30 minutes constructing a “spend” transaction for a private token, that’s bad news — you just won’t use it, will you?

So how to make these Universal SNARKs fast?

Sonic → PLONK

Fortunately, a chance meeting between Ariel Gabizon and Zac Williamson at Binary District workshop in London helped unlock another breakthrough — a SNARK by the name of PLONK.

Zac had three principal papers in his mind when he ran into Ariel— Sonic, AuroraLight (by Ariel), and a paper by Jens Groth and Jonathan Bootle about expressing problem statements as polynomial identities.

I’ll let him regale the tale below, but first —

How do you Build a SNARK?

To make a SNARK, you need some logical and consistent way to describe logical statements (ultimately these statements will come from higher-level smart contract code).

Usually this is done through arithmetical circuits — in a not dissimilar manner to the way that all computer programs you use on a daily basis are ultimately reduced to small pieces of arithmetic on the chip.

A circuit is composed of gates and wires:

  1. Gates take two numbers as inputs, either add or multiply them, and then emit the result through an output wire —
  2. Wires carry values into and out of gates

So our SNARK will need to include the following:

  1. A “local” consistency check — are all your gate equations satisfied?
  2. A “global” consistency check — do the wires correctly join the gates together to build the circuit in question?

Zac’s Notes on building PLONK

I asked Zac for his recollections of the process:

So, how fast is PLONK?

Very! Our implementation of PLONK is advanced enough to publish benchmarks for how long proof construction takes for sample circuit sizes:

PLONK is capable of chewing through a circuit with over one million gates in 23 seconds, on entirely standard hardware. No server farms or HPC clusters here — those figures came from a Microsoft Surface tablet.

To give some context, we think that a typical private transaction on Ethereum will clock in at ~128,000 to 512,000 PLONK gates. This means that PLONK can be used to programme complex logical statements in a manner that preserves perfect privacy.

To our knowledge, no other fully succinct, universal proving system comes close to these figures.

So what else is out there?

PLONK isn’t the only child of Sonic — in a summer that saw a gush of cryptographic techniques enter the fray, another fresh SNARK came into the world, created by Sonic’s original authors.

Along Came Marlin

Marlin is its name — a contemporary universal SNARK with higher efficiency than Sonic. It differs from PLONK in a couple of important ways:

  1. Circuit TypeMarlin validates the classical R1CS construction that has formed the foundation of SNARK proofs to date. PLONK instead uses fan-in-two gates with unlimited fan-out. Both models describe the same overall ‘universe’ of circuits, but in subtly different ways.
  2. The ‘global’ consistency check — PLONK uses a permutation argument to check that wire values are copied correctly along the circuit (essentially stitching wires onto other wires, an verifying they contain the same values), whilst Marlin checks that more general linear relations hold between the circuit multiplication gates. Marlin does this by the randomised sumcheck approach that has been used in papers like Aurora.

— thanks to Ariel Gabizon of Protocol Labs for this succinct explainer.

The Benchmarks

We’ve had a lot of community requests to directly compare the performance and issued benchmarks for Marin and PLONK.

Efficiency — Comparing the efficiency of different proving systems is always a bit subjective. But there is a simple heuristic we can use — proof construction times are generally dominated by the number of ‘elliptic curve scalar multiplication’ operations a prover must perform. If n is the number of addition + multiplication gates in a circuit, PLONK requires the prover perform 9n scalar multiplications. Marlin requires 21n . This does come with terms and conditions attached though — Marlin represents circuits in a very different way to PLONK, and there could be some scenarios where Marlin is more efficient than PLONK — if your circuit is composed from a lot of addition gates that have a very large fan-in (large fan-in meaning that the circuits contains gates that add lots of variables together in one go).

Before presenting them, there are some health warnings in doing so, and we urge the reader to consider carefully the effects of these assumptions:

  1. PLONK has been benchmarked over the BN254 curve (the only pairing-friendly curve that Ethereum smart-contracts can efficiently access), whilst Marlin has been run on the BLS12–381. On a purely like-for-like basis, we conservatively estimate that equivalent benchmarks on the BLS curve would raise PLONK’s metrics by (very roughly) 50% for the prover, and 100% for the verifier. This assumption is used to generate an estimated benchmark over BLS12–381
  2. PLONK was run using a highly optimised library built by AZTEC Protocol, much of which is implemented in highly efficient x64 assembly code. We also use an efficiently computable endomorphism available to short Weierstrass curves, to speed up our scalar multiplication algorithms.
Published benchmarks over 2¹⁷ gates

Get in Touch

Whether you’d like to participate in the ceremony, apply to work at AZTEC Protocol, find out more about using our cryptosystems in your dapp, or just chat, please get in touch at hello@aztecprotocol.com or join our Telegram and Discord channels.

AZTEC Protocol

Private transaction network on Ethereum. Email: hello@aztecprotocol.com, Discord: https://discordapp.com/invite/Z2kyTTu, Telegram: https://t.me/aztecprotocol

Thomas Pocock

Written by

CEO AZTEC Protocol • CFA Charterholder

AZTEC Protocol

Private transaction network on Ethereum. Email: hello@aztecprotocol.com, Discord: https://discordapp.com/invite/Z2kyTTu, Telegram: https://t.me/aztecprotocol

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade