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.
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.
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.
nOutsare the number of inputs and outputs respectively and
zeroLeafis value of an empty node in the Merkle tree. That is defined as follows:
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:
Merkle tree path indices and
Merkle tree path elements. While for outputs we only need four:
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
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.
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
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:
[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.