Zero Knowledge - zkSNARKs

What are zkSNARKs?

zkSNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) are cryptographic proofs that let you prove you know something without revealing what that something is.

They're "succinct" because the proofs are tiny (just a few hundred bytes) and verify almost instantly, even if the underlying computation took hours.

They're "non-interactive" because the prover can create the proof once, and anyone can verify it later without further communication.

The "arguments of knowledge" part is crucial - it means the prover must actually know the secret information (called the witness), not just that such information exists. This prevents cheating through brute force or other means.

Understanding zero-knowledge: The Where's Waldo analogy

To grasp how you can prove something without revealing it, consider this relatable example:

Imagine your friend is struggling with a Where's Waldo puzzle. You claim "I know where Waldo is!" but your friend doesn't believe you. You could just point to Waldo, but then your friend would learn the solution too.

Here's how you could prove your knowledge without revealing the answer:

1. Ask your friend to turn around

2. Place the book flat on the floor

3. Take a huge sheet of paper (say, 1 square meter) with a tiny hole cut in it

4. Position the paper over the book so only Waldo's face shows through the hole

5. Have your friend turn back around

Your friend can now see Waldo's face through the hole, proving you know where he is. But with the rest of the page covered, they have no idea where on the page Waldo actually is. You've provided proof with zero knowledge.

Why zkSNARKs matter: Real-world applications

Before diving into how zkSNARKs work, it's worth understanding why they're so revolutionary. Zero-knowledge proofs enable a new category of applications:

Proving statements on private data:

• Prove your bank balance exceeds X without revealing the actual amount

• Verify you're over 18 without disclosing your birthdate or identity

• Match DNA samples without exposing genetic information

• Demonstrate creditworthiness without sharing financial history

Anonymous authorization:

• Access restricted websites without revealing username/password

• Prove citizenship of an allowed country without specifying which one

• Use monthly transit passes without trackable card IDs

• Authenticate as a group member without identifying yourself

Privacy-preserving payments:

• Complete transactions with no link to identity (as in Zcash)

• Pay taxes without revealing income details

• Make donations anonymously while proving tax-deductible status

Scalable computation:

• Outsource expensive computations and verify results without re-executing

• Transform blockchains from "everyone computes" to "one computes, everyone verifies"

• Prove correct execution of complex programs with minimal verification cost

In MetaPoll's case, we use zkSNARKs specifically for computational integrity - proving voting results are correct without revealing individual votes.

The three roles in zero-knowledge proofs

Every zero-knowledge proof involves three key components:

The Witness: The secret information that the prover knows. In the Waldo example, it's Waldo's exact location on the page. In MetaPoll's VCIP (Voter Compute Integrity Proof), it's the details of the computation being performed.

The Prover: The party who knows the witness and wants to convince others of this knowledge without revealing the secret. You, in the Waldo example. In MetaPoll, it's the system performing the vote counting computation.

The Verifier: The party who wants to be convinced that the prover knows the witness, without learning what it is. Your friend in the Waldo example. In MetaPoll, it's anyone who wants to verify that votes were counted correctly.

A brief history of zkSNARKs

The story of zkSNARKs begins in 1985, when Shafi Goldwasser, Silvio Micali, and Charles Rackoff introduced the concept of zero-knowledge proofs in their groundbreaking paper "The Knowledge Complexity of Interactive Proof Systems." This work, which would later earn Goldwasser and Micali the Turing Award, showed it was possible to prove knowledge of information without revealing the information itself.

However, these early zero-knowledge proofs were interactive - the prover and verifier had to exchange multiple messages back and forth.

The path to zkSNARKs required making these zero knowledge proofs non-interactive and succinct.

The first SNARK

The term "zkSNARK" itself was coined in January 2012 by a team of researchers including Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer in their paper "From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again." This paper presented the first construction of what we now call zkSNARKs - proofs that are:

• Zero-knowledge (reveal nothing beyond the validity of the statement)

• Succinct (small size and fast to verify)

• Non-interactive (single message from prover to verifier)

• Arguments of Knowledge (computationally sound proofs)

Groth16 makes a breakthrough

The next crucial development: Jens Groth published "On the Size of Pairing-based Non-interactive Arguments," introducing what became known as Groth16. This protocol dramatically improved upon previous zkSNARKs with:

• Proofs consisting of only 3 elliptic curve elements (just ~200 bytes)

• Verification requiring just 3 pairings (milliseconds on a laptop)

• The smallest proof size and fastest verification time of any zkSNARK

Groth16 quickly became the gold standard for zkSNARK implementations. Its first major deployment was in Zcash, the privacy-focused cryptocurrency that launched in 2016. The combination of Groth16's efficiency and Zcash's privacy needs marked the transition of zkSNARKs from theoretical construct to production technology.

Despite requiring a trusted setup for each circuit (unlike newer "universal" zkSNARKs), Groth16 remains widely deployed today due to its unmatched verification efficiency - a critical property for blockchain applications where thousands of nodes must verify each proof.

How zkSNARKs work mathematically

The Waldo example from earlier in this article is interactive - you and your friend need to be in the same room. zkSNARKs achieve something similar but non-interactively through polynomial magic.

The key insight: polynomials are mathematical objects that can encode unlimited information, and polynomial equations can represent unlimited computational checks.

If $P(x) + Q(x) = R(x)$ is true as polynomials, then:

• $P(0) + Q(0) = R(0)$

• $P(1) + Q(1) = R(1)$

• $P(2) + Q(2) = R(2)$

• And so on forever...

So we can encode an entire computation into polynomial equations, then prove these equations hold without revealing the polynomials themselves.

The polynomial commitment process

1. Arithmetization: Transform the computation into polynomial equations. A complex calculation becomes something like $P(x+1) - P(x) = Z(x) * H(x)$ .

2. Commitment: Create a cryptographic "hash" of these polynomials. These commitments are tiny (32-48 bytes) regardless of polynomial size.

3. Proof generation: Prove the equations hold by demonstrating they're satisfied at random points. Thanks to the Schwartz-Zippel lemma, if polynomial equations hold at random points, they certainly hold everywhere.

4. Verification: Anyone can check these proofs quickly, confirming the computation was done correctly without seeing the computation itself.

MetaPoll's use of zkSNARKs: VCIP

In MetaPoll, we use zkSNARKs specifically for the Voter Compute Integrity Proof (VCIP). Here's how it works:

• The Witness: The actual vote tallying computation - which votes were cast, how they were aggregated

• The Prover: MetaPoll's counting system, which performs the aggregation computation and generates a proof

• The Verifier: Any user who wants to confirm votes were aggregated correctly

The zkSNARK proves: "The published voting results are the correct result of counting all valid votes" without revealing individual votes or the private information in the counting process.

The zkSNARK specifically ensures computational integrity: everyone can verify the count is correct without seeing how each person voted. Essentially, acting as the integrity layer for MetaPoll - the mathematical guarantee that the final tally is computed correctly.

Why this matters

The combination of zkSNARKs for computational integrity and other methods for voting privacy creates a system that is:

• Transparent: Anyone can verify the MetaPoll results are correct

• Private: Individual votes remain confidential

• Trustless: No need to trust that the vote counters are honest - math proves they counted correctly

MetaPoll delivers a fundamental advance in voting technology: results that are simultaneously more transparent and more private than traditional systems.

Sources for further reading

• Vitalik's introduction to how zk-SNARKs are possible

• Why and How zk-SNARK Works: Definitive Explanation - Maksym Petkus provides a comprehensive, step-by-step explanation from basic concepts to the full protocol

• Zcash's explanation of their zkSNARK implementation

• a16z's zero-knowledge canon