In this post, we’re going to talk about zkSNARKs, which are a particular brand of Zero Knowledge Proof that’s becoming increasingly important in the blockchain space.

We’ll cover how they’re used and what they’re useful for, and we’ll take a look at a basic zkSNARK in a SNARK-building language called Circom.

Prerequisites

We assume that you’re encountered prime fields before, and remember their basic properties. If you can calculate \(4 \cdot 5 \equiv 6\) in \(\mathbb{F}_7\), you’re good to go.

What are ZKPs?

A zero knowledge protocol is a protocol that allows you to prove that you know some specific mathematical fact, without revealing any information about the fact itself. The proof generated in a zero knowledge protocol is called a zero knowledge proof.

Some examples of “mathematical facts” that we can create zero knowledge proofs for include things like:

• Knowledge of a three-coloring of a graph (i.e. I know a three-coloring of this publicly-known graph, and I’ll prove that I know it without showing you the coloring)
• Knowledge of the discrete logarithm of some residue modulo \(p\) (i.e. given public generator \(g\), public modulus \(p\), and some residue \(y\), I know \(x\) such that \(g^x \equiv y\) modulo \(p\))
• Knowledge of a private key corresponding to a publicly-known public key

The idea of a zero knowledge protocol might seem paradoxical at first glance: how can I prove I know something without showing you the thing that I know? However, it turns out that we actually use zero knowledge protocols all the time! For example, familiar tools like digital signatures are actually zero knowledge proofs. By signing a message, I prove that I know the private key that corresponds to a widely-known public key, but I don’t give away any information about the private key itself. In fact, public-key encryption only works because it is a zero knowledge protocol; if signatures revealed information about your private key, then malicious actors would be able to impersonate you by analyzing your signatures and recovering your private key.

Slightly more formally, suppose that you’ve computed \(f(\cdot) = y\) for some publicly known function \(f\) and some secret input \(\cdot\). A zero-knowledge protocol for the function \(f\) would allow you to prove to others that you know a secret input to \(f\) that results in \(y\), without revealing this secret input \(\cdot\).

For more on ZKPs, check out this post.

What are SNARKs?

Like we mentioned above, ZKPs are protocols that allow you to prove knowledge of a specific mathematical fact: discrete log, knowledge of private key, knowledge of three-coloring, etc. However, it’s important to note that early ZKPs only allowed you to prove one kind of mathematical fact at the time. That is, cryptographers developed one protocol which you could use to prove knowledge of discrete log, another protocol which you could use to prove knowledge of three-coloring, and another protocol for digital signatures. But what if we want to generate zero knowledge proofs for arbitrary mathematical functions? For example - what if I want a zero knowledge protocol that would allow me to prove that I know the pre-image of a SHA256 hash output? It would be intractable if, for every use case, I had to go to a cryptographer and ask them to custom-write me a new protocol.

zkSNARKs solve this problem. A zkSNARK is a gadget that can be used to generate a ZKP for any mathematical function. Basically, you feed the “code” of a function \(f\) into a zkSNARK, and the SNARK creates a protocol that allows you to generate zero-knowledge proofs for \(f\).

As an example, say we have a fake “hash” function \(h(x) = x^3 - x + 7\) that we’d like to generate zero knowledge proofs for. First, we can use a zkSNARK to generate a ZKP for \(h\). Then, we can use this generated ZKP to prove claims like “I know a value \(\cdot\) such that \(h(\cdot) = 67\)” - without revealing \(\cdot\). zkSNARKs also guarantee that this process is “succinct” and “non-interactive”: we can create this proof in linear time, and others can verify it in constant time, without needing to ask additional questions of us (the prover). Together, these properties form a zkSNARK: a Zero Knowledge Succinct Non-interactive ARgument of Knowledge.

These properties makes SNARKs useful for blockchain applications, where users can create proofs locally, and then upload short proofs for constant-time verification inside a smart contract, where computation is expensive.

How does Dark Forest use SNARKs?

A central mechanic in Dark Forest is that the cryptographic “fog of war.” The fog of war ensures that you don’t automatically know where all players, planets, and other points of interests are in the universe; you have to spend computational resources to discover them. This mechanic is secured by zkSNARKs.

In a universe with a fog of war, the locations of all players are private and hidden from each other. This means that players don’t upload the coordinates of their planets to the Ethereum blockchain, which can be publicly inspected. Instead, each player uploads the hash of their location to the blockchain. This ensures that players stay “committed” to a specific location, but also that the location can’t be determined from inspection of the Ethereum data layer.

Without zkSNARKs, there’s an obvious attack vector - if a player uploads a random string of bytes that doesn’t correspond to a real and valid location, and the integrity of the game is broken. To prevent this, Dark Forest requires players to submit zkSNARKs with every move to ensure that players are indeed submitting hashes corresponding to valid coordinates that they have knowledge of.

When players make moves, they’re also required to submit ZK proofs that their moves are “valid” - you can’t move too far or too fast. Without zkSNARKs, a malicious player could make illegal “teleport” moves by claiming that the hash they are moving from is next to the hash they’re moving to, even if the two locations are actually on opposite sides of the universe. Once again, requiring ZK proofs keeps players honest. To use a chess analogy, the required ZK proofs basically tell the contract, “I’m moving my knight; I’m not going to tell you where I moved my knight from, or where I moved it to, but this proof proves that it did in fact move in a legal L-shape.”

We’ll dive deeper into the Dark Forest construction and SNARKs in a future blog post!

Circom

Like we mentioned above, SNARKs are gadgets which take in a function and output a ZKP for said function. So how do we “feed” a function to a SNARK?

SNARKs functions are written as circuits in the Circom language. Here’s an example circuit for our “fake” hash function, \(h(x) = x^3 - x + 7\).

// file: circuit.circom

template BadHash() {
    signal private input x;
    signal x_squared;
    signal x_cubed;
    signal output out;

    x_squared <== x * x;
    x_cubed <== x_squared * x;
    out <== x_cubed - x + 7;
}

component main = BadHash();

Our zkSNARK takes in this circuit, chews it up, and spits out a proving key and a verifying key. The proving key allows a prover who is computing BadHash(x) = out to generate a proof that they do indeed know the pre-image of out. The verifying key allows anyone to inspect that proof, along with out, and conclude that the prover did honestly carry out the computation with a known secret input.

Concretely, suppose that the prover computes BadHash(4) = 67. The prover publishes their proof, along with out = 67, to the verifier; however, they do not publish the secret input x = 4. The verifier of this proof knows the source code of the BadHash circuit, and also receives out = 67 and a proof from the prover. The verifier can then inspect the proof to verify that the prover did indeed compute some valid x, x_squared, and x_cubed to arrive at out. However, the verifier won’t know the specific values that the prover used (x = 4, x_squared = 16, x_cubed = 64) - just that these values were computed correctly.

There are two things which make SNARK circuits different from normal “functions” that we’re used to.

First, you’ll notice that BadHash only uses three operations: multiplication, addition, and subtraction. At the base level, SNARK constraints are limited to only these operations. There are ways to do operations like division and modulo, but they all ultimately involve breaking operations down into sums and products. The fact that we’re limited to these operations is part of what makes SNARK programming thorny.

The second challenge is that each signal in a SNARK is an element of a prime field, and all operations happen inside that prime field. The most obvious implication of this is that there is no native notion of decimals, fractions, negative numbers, or numbers bigger than 77 digits. If you want one of these, you have to make them out of positive integers smaller than p. Another implication is that our operators “wrap around”: the result of 3 - 5 is p - 2, which is a 77 digit number. The prime is large enough (254) that most of the time this doesn’t matter, but occasionally it can cause subtle correctness bugs.

To actually make proofs, we use a library called SnarkJS, built by Jordi Baylina and Iden3. SnarkJS uses your circuit to generate proving and verification code in JavaScript and Solidity, as well as protocol paramters and proving and verification keys. This is out of the scope of this post, but you can find a tutorial on it here.

In the next posts, we’ll talk about the execution model of SNARKs, including the difference between calculation and constraint, and how to do operations like division and modulo.