The first generation of SNARKs, 2010–2016
Part 1 of this series introduced the importance of blockchain privacy and the notion of a ZK-SNARK.
The Circuit-Specific SNARK
Zero knowledge proofs were first theorised about by Goldwasser, Micali and Rackoff in 1989. In 2010 Jens Groth published a paper on what he then called NIZK (Non-Interactive Zero Knowledge), and a major paper by Ben Sasson et al provided the theoretical underpinning for the first proving system for ZCash.
ZCash later switched to Groth’s new technique (known as Groth16).
The ZCash circuit takes input notes, creates output notes, and checks their difference sums to zero. Groth16 provides the argument used to validate that every spender is behaving according to this rule.
SNARKs: They’re Generally Quick
SNARKs can be fast in the wild.
What exactly does ‘fast’ mean?
- Constant (and small) proof sizes: the data representing those transactions is small, remaining the same size even as the circuit gets bigger — that allows them to be sent fast, and stored easily
- Quick verification: validating SNARKs can be done quickly by the verifier (in the context of cryptocurrency, we mean the blockchain)
SNARKs: The Achilles’ Heel
But all SNARKs are born with a congenital weakness.
In a loose sense, what makes SNARKs so nimble is a product of their gestation — at setup, they require the creation of a so-called ‘Reference String’, which provides a highly structured form of randomness. Spenders have to use this reference string every time they want to prepare a transaction for execution.
Going a bit deeper, this Reference String is a large list of ‘elliptic curve numbers’. Whilst these numbers are created out of randomness, internally the numbers in this list have strong algebraic relationships to one another. These relationships are used as short-cuts for the complex mathematics required to create ‘proofs’.
Going even deeper, the AZTEC reference string looks like this:
(x.[1], x².[1], …, x¹⁰⁰⁶⁶³⁹⁶.[1])
You can see these algebraic relations — each term is the prior term, multiplied by x. This numberx is a hidden random variable, and [1] represents an elliptic curve ‘generator’ point that we’re multiplying by powers of x .
If the source of this randomness were ever revealed, an attacker could simply fake proofs — on a blockchain, that means thieving money with impunity.
The Importance of Setup Ceremonies
How do we nip this weakness in the bud?
Instead of just one trusted person / company building the reference string, and being forever subject to suspicion, we instead use the collaborative forces of a large number of participants (say 200 — a slightly arbitrary number).
These participants should be as disconnected as possible — socially, geographically — so as to give users absolute certainty that no collusion occurred. Ideally it should include well-known participants with long histories to stop Sybil attackers, as well as random participants around the world with a low likelihood of connection to more than a handful of other participants.
Together, the participants run a Ceremony of Multiparty Computation, to build that Reference String. One by one, each ‘injects’ their own randomly-generated numbers into the transcript.
See here for a guide to the Ceremony’s security properties.
Sign up to join AZTEC’s October 2019 Ceremony
Groth16: Quick but not Adaptable
From 2010 to 2016 the evolution of these zero knowledge arguments was extraordinary — but all suffered from a major drawback.
Each new circuit required a fresh ‘trusted setup’.
That’s right — if you’re a smart contract programmer, then for each contract you program, you’ll need a fresh ceremony. Even smart contract upgrades — any alteration to ZK logic, would require a new setup.
Of course, this doesn’t really matter to ZCash — they have built one highly focussed implementation of Groth16, and the rules of ZCash won’t change.
But AZTEC wants cryptography usable by all — and it’s clearly prohibitively costly and time consuming, as well as a drain on public patience and a huge audit overhead, if a new ceremony is required for each new smart contract.
AZTEC’s Goal: Dark Contracts
AZTEC wants to enable Dark Contract programming for all developers — we want you to be able to just get on and build private smart contract systems, digital assets, etc, without worrying about the cryptography.
With Groth16 requiring a new setup for each smart contract upgrade — that’s just an intolerable amount of work, mathematical complexity and security risk for smart contract developers to undertake.
— this next article introduces the concept of the Universal SNARK, and the events that led to this summer’s publication of PLONK.
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.
