Implementing Zero Knowledge Lottery’s Circom circuits PART 1 / 2

THE CODE IN THIS BLOG POST IS NOT AUDITED AND SHOULD NOT BE USED IN PRODUCTION

In Zero Knowledge Lottery we introduced a revolutionary zero knowledge lottery scheme. As discussed in the article, it’s possible to implement the scheme by modifying Tornado Cash Nova’s (Nova) code. In this two part blog series we’ll first explain how Nova’s circuits work (PART 1) and then implement the ZK-Lottery on top of it (PART 2).

Transacting with Unspent Transaction outputs

Unlike Ethereum, but similar to Bitcoin, Nova operates with UTXO’s (Unspent Transaction Output). The idea with UTXO’s is that instead of a single account balance, the user have multiples of immutable notes (like bills) that can be destroyed in order to generate new notes. However, unlike bills, the UTXO’s can be worth any number of monetary units. You can read more about UTXO’s from Investopedia. Unfortunately using a simple bank balance or Ethereum’s account balance is not possible in zero knowledge circuit design if we want to maintain zero knowledge.

A simple but a very multipurpose UTXO transaction is one with two inputs and two outputs:

This circuit could for example have 1 ETH and 3 ETH inputs and then two UTXO’s with 2 ETH each. Similarly to Bitcoin, Nova will verify that the sum(inputs) == sum(outputs) is true as one criteria to make a transaction valid. This is a conservation law; money inflows have to equal money outflows. If the outputs could be bigger than inputs the user could be able to mint money and this would be a critical vulnerability in the system! Interestingly, the readers of Zero Knowledge Lottery might remember that this equality does not hold in ZK-lottery as an intended feature…

In addition to the conservation law, Nova will check that the input UTXO’s have been deposited to the system beforehand.

Constraint programming

Writing a zero knowledge circuit is all about figuring out what kind of inputs are allowed and what kind of inputs are not allowed. We need to come up with a program that is able to distinguish these from each other. Coming up with such inputs itself is left outside the circuit. The circuit only checks if given inputs are valid, nothing more. In Nova, JavaScript or Solidity code are responsible for generating the valid inputs which the circuit only confirms. If the inputs are invalid, the zero knowledge proof generation will fail. You cannot generate a zero knowledge proof with invalid inputs.

A simple circuit could take in three inputs (which are also called signals) and verify that sum of the first two signals equal the third: A + B = C. In order to be able to generate a zero knowledge proof, you cannot provide any other values to the circuit to get a proof out. We can then hide all these inputs (zero knowledge) from someone looking at the proof. They would only find out that you know any three values that fit this equation. This is called constraint programming, we are making a program that constraints given inputs into a certain range.

The Circuits in Tornado Cash are written in Circom language. Circom is a language that is used to define arithmetic circuits that can be compiled into R1CS which can then be used to generate and verify Zero Knowledge proofs.

Tornado Cash Nova circuit

Let’s start going through how UTXO’s and their verification works in Tornado Cash Nova’s transaction circuit. We’ll be going through this code snippet by snippet and explain what each snippet does.

The code starts by defining constant parameters:

Here we define four constant variables. Level is the depth of the Merkle tree (if you are not familiar with the concept of Merkle trees, check Bitcoin Internals: Verifying Merkle Roots using Merkle Proofs in JavaScript) that is being used to store nullifiers (explained later), nInsand nOutsare the number of inputs and outputs respectively and zeroLeafis value of an empty node in the Merkle tree. That is defined as follows:

Here FIELD_SIZE is a prime number that defines the biggest variable size that we can use in our circuits. It’s a 248 bit number. This is related to zkSnark internals.

We can then form a simple 2 inputs 2 outputs UTXO transaction as:

We can also create bigger transactions, like one with 16 inputs and 2 outputs as follows:

Nova only supports these two transaction types: 2-in-2-out and 16-in-2-out. If needed, it could be easily modified to support even more. However, these two probably work well enough alone. Bitcoin’s UTXO system does not have this kind of limitation.

Let’s move forward with the circuit and define all the inputs:

Looking at the variables it can be seen that input UTXO’s have six variables: nullifier, amount, private key, blinding, Merkle tree path indices and Merkle tree path elements. While for outputs we only need four: commitment, amount, public key and blinding. The reason for this is that we do not need to prove the existence of the outputs, but we need to prove that the user has access to the inputs they are claiming they have.

We can also see from the above code that there are public and private inputs to the circuit. Public signals are variables that are public for everyone, if one takes a look on the blockchain, one can see these public variables are open for everyone to see. Private values are only available to the proof creator. After a proof has been generated these values cannot be deduced from the proof anymore and they do not need to be published anywhere (but the creator should keep track of them as otherwise the money gets lost!).

Next we need to define some Circom components that we are going to use in input verification.

In Circom, components are kind of like functions, but their syntax is quite different to traditional languages. Instead of calling them once, you set the components input variables once, and once they are all defined, the function gets executed and you can use the components output variable. We’ll describe what each of these components do when we get to that part of the code.

Verifying Nova’s Inputs

Enough with definitions, let’s look at the actual verification code. We’ll start by verifying that the user knows the private keys that correspond to each public key of an input. We do this by using the Keypair component that takes in a private key and then outputs the public key.

The Keypair() calculates the public key as a Poseidon hash of a private key.

Nova is using Poseidon Hash because it’s designed to be easy to verify in Zero Knowledge proofs. In theory we could use almost any other hash function here as well, but the verification time for such hash would just be longer.

Then we calculate the notes commitment that will be used as part of the nullifier. We calculate Poseidon hash out of input amount, public key and the blinding. The blinding number is a random number which we need to avoid an attacker deduce the commitment by just brute forcing Poseidon hash with your public key and some monetary value number.

Then we compute the nullifier. In Tornado Cash Nova the nullifier is defined as hash of multiple values:

nullifier = PoseidonHash(commitment, merklePath, sign(privKey, commitment, merklePath))

while in classic Tornado Cash circuit the nullifier is just a hash of a random number that the user knows.

The point of the nullifier is to identify that a note has been spent. The nullifier is public information and will be published on chain. The solidity contracts are also managing a Merkle tree that is keeping track of all existing nullifiers. In Nova it’s important that when a UTXO has been spent it will be marked as spent with the nullifier. It’s necessary that we need to identify each UTXO separately as well as otherwise users could create different values UTXO’s and then spend the higher value twice by spending the nullifiers separately. This was not an issue in Tornado Cash as all the notes are worth the same. Thus in Nova we need to make the nullifier in a way that binds together all the variables used in the proof, this is what the hash of all the values is about.

Here’s the code to verify that the calculated nullifier matches the claimed inputNullifier[tx] provided by the user directly:

Next we will check that the inputs can be found in the public Merkle tree. Nova’s contract is maintaining the nullifier tree that contains a nullifier for each input. Once an input is spent it’s nullifier will be marked as spent and it cannot be used anymore. The spending of these nullifiers is public information but only the owner of the note knows what hides behind the nullifier. It’s not possible to deduce the preimage of the nullifier. As the contract keeps track of which nullifiers are already spent, we do not need to manage that in the circuit. We just need to check that the nullifiers inputNullifier[tx]are found in the public root.

Then we’ll check that the root that we have calculated inTree[tx].root matches the root that is publicly visible for everyone. But this is only important if the input amount is something other than zero, as if it’s zero we don’t require the user to know a valid UTXO with zero value. This is why we use ForceEqualIfEnabled component in the end to check that the equality holds if the module is enabled.

Zero valued UTXO’s are important to allow users to use a higher number of UTXO’s than they are actually using. We perform this above code for all transaction inputs tx in a loop and sum together the input amounts. This sumIns will tell us how much total money there is in all of the inputs:

We don’t need to verify the input amount in input UTXO’s as we can just check that the note can be found in the nullifier Merkle tree. The note can only get there after it has been validated.

Nova’s output verification

Let’s move to output verification. The verification of the outputs is a lot simpler. We just check

1) That output commitments match the private values (amount, public key and blinding) that the user is providing the circuit with

2) And that output amount can fit into 248 bits as we are using 248 bit variables in Circom while 256 bit variables are used in the contract. If the user were to provide a value bigger than 248 bits but smaller than 256 bits, it would appear as a really small number in Circom while being a huge value in Solidity side!

We also sum the output amounts to know how much currency the user is wanting to move to output. Here’s the same in Circom:

We previously checked that the input notes are valid, but we did not check that the notes are unique. We have to prevent users from supplying the same valid UTXO multiple times. We can stop this from happening simply by checking that there are no duplicates. This check could also be done on Solidity contract side, but to simplify the solidity code, we can do it in Circom:

Finally, we’ll check that the total monetary flows match up. The variable publicAmount indicates how much money is flowing to the system or out of it. As Nova is not a closed system with a fixed amount of currency, this is used to track external money flow. This means that the 2 input 2 output UTXO system I described above is a lie… :) we actually have the following system:

Nova’s UTXO system has 2 inputs and a public input going into it and two outputs and a public output flowing out of it.

[Public Input] is the amount of external ETH coming into the contract (deposits) and [Public Output] is the amount of ETH that is flowing out of the contract (withdrawals). To incorporate this in the circuit, we’ll check that the money flows are balanced:

That’s the Tornado Cash Nova circuit. It’s quite simple when you are just looking at the Circom code as most of the magic has been abstracted away by the language. In PART 2 we’ll implement the real deal.

Follow @Qhuesten on twitter to find out when new blog posts are published.