Implementing Zero Knowledge Lottery’s Circom circuits PART 2 / 2
THE CODE IN THIS BLOG POST IS NOT AUDITED AND SHOULD NOT BE USED IN PRODUCTION
This is part 2 of the blog series, read Implementing Zero Knowledge Lottery’s Circom circuits PART 1 / 2 before continuing with this.
Now as we have described how the existing Tornado Cash Nova’s circuit works, let’s discuss how we transform it into a more complex ZK-Lottery circuit. We’ll start by listing features from Zero Knowledge Lottery and then we’ll code them into the circuit.
Similarly to the Nova’s circuit, we need the following features:
1) User MAY deposit funds to the contract
2) User MAY withdraw funds from the contract
3) User MAY transfer funds privately inside the contract
And then we want to add the following new features:
4) Users MUST participate in the lottery when they deposit into the contract. The user will choose a block number indicating the time of the lottery. The chosen block number has to be higher than the current block number.
5) User MAY withdraw funds only after the lottery has completed for the given UTXO
6) User MAY participate the lottery again inside the system
7) User MAY move the lottery block number forward if the lottery has not been conducted yet
8) User MAY transfer UTXO’s with upcoming lottery to another user
It would also be beneficial to implement recursive proofs as described in Recursive ZK-SNARKs: Improving Tornado Cash Security and Note Management. This would enable better privacy for users. However, as these have not been implemented in Circom yet, we won’t be adding them to this circuit.
To implement these new features, we need to have two different types UTXO’s in the system:
1) A UTXO that has been deposited into the contract with specified lottery block number
2) A UTXO that has passed the lottery and can be transacted and withdrawn freely in the contract
We can denote these additions in the circuit with only one additional variable for each UTXO: blockNum.
- If the
blockNumis in the future, this transaction is a transaction that has not passed the lottery phase yet. - If the
blockNumis in the past, it’s a transaction that has passed the lottery phase, but has not been claimed yet. - We also add a special case
blockNum == 0for UTXO’s that have passed the lottery phase already. We don’t require them to enter the lottery anymore. They may later enter the lottery again if the user so desires.
This addition makes our UTXO’s look as following:
The various transaction types of ZK-Lottery
In classic Tornado Cash all the notes are the same, in Nova’s circuit the monetary values differ and in ZK-Lottery monetary values and lottery block numbers change across UTXO’s. While in Nova you can split UTXO’s into smaller pieces and while this is also possible in ZK-lottery we also need to make sure that the blockNum changes in valid ways. For example, if the lottery has passed (currentBlockNum > lotteryBlockNum), then we allow user to move the profits into an output UTXO where blockNum == 0 (normal Nova like UTXO) or blockNum > currentBlockNum (enter lottery again), but changing blockNum to something smaller than currentBlockNum is not allowed (except to 0!).
In Nova’s circuit, the user provides the circuit with two lists: input UTXO’s and output UTXO’s. We then check individually that each input and output are valid and check that the overall cash flow is correct. In ZK-Lottery we also need to check that the money flowing from each transaction type to another is correct. Given just inputs and outputs, the circuit needs to figure out how much money is flowing from which input to which output, as each UTXO can have a different transaction type. While this is a solvable problem, it’s quite a difficult problem to solve. It’s also possible to have lists that do not match and the problem does not have a solution. Luckily, we do not need to solve this in the circuit, we can directly ask the user to provide a mapping which input UTXO should be converted into which output UTXO.
We’ll need to add inputOutput signal to the circuit. The variable is a two dimensional array that indicates how much money is flowing from which input to which output. The circuit can then easily loop through this array and check that the rules are being followed. This allows the user to do many different operations inside one circuit while revealing nothing to the observers. We could achieve this same thing by making multiple circuits, one for each transaction type conversion, but this would leak information on which operation the user is currently using! This is not acceptable for us as we aim to maximize privacy.
The Input Output mapping for a UTXO with two inputs and two outputs could look as follows:
╔══════════════╦═══════════════╦══════════╦══════════╗
║ ║ Public Output ║ Output 0 ║ Output 1 ║
╠══════════════╬═══════════════╬══════════╬══════════╣
║ Public Input ║ 0 ║ 1 ETH ║ 2 ETH ║
║ Input 0 ║ 0 ║ 0 ║ 4 ETH ║
║ Input 1 ║ 0 ║ 0 ║ 0 ║
╚══════════════╩═══════════════╩══════════╩══════════╝Here the user sources 3 ETH from Public Input (the first row, 1 ETH + 2 ETH), and moves 1 ETH to Output UTXO 0 and 2 ETH to Output UTXO 1. The user also moves 4 ETH from Input 0 to Output 1.
We also need to give the circuit similar input and output UTXO specifications that Nova uses. Given that the current block number in chain is 1000, here are valid inputs and outputs the user could give to the circuit:
publicAmount = -3 ETH // The user deposited 3 eth to the contract╔══════════╦════════╦══════════╦══════════╦══════════╗
║ ║ Amount ║ pubkey ║ blockNum ║ blinding ║
╠══════════╬════════╬══════════╬══════════╬══════════╣
║ Input 0 ║ 4 ETH ║ 0x0123… ║ 0 ║ 4434… ║
║ Input 1 ║ 0 ║ 0x0123… ║ 0 ║ 3241… ║
║ Output 0 ║ 1 ETH ║ 0x0123… ║ 2000 ║ 9548… ║
║ Output 1 ║ 6 ETH ║ 0x0123… ║ 3000 ║ 6020… ║
╚══════════╩════════╩══════════╩══════════╩══════════╝
To check that these input and output sums are correct, we have to verify that the Input Output mapping match the values in the input and output lists:
1) The sum of Public Output column subtracted by the sum of Public Input row must match publicAmount: (0 + 0 + 0) -(0 + 1 + 2) = -3 ✅
2) The sum of Input 0 row must equal to the Input 0 amount: 0 + 0 + 4 = 4 ✅
3) The sum of Input 1 row must equal to the Input 1 amount: 0 + 0 + 0 = 0 ✅
4) The sum of Output 0 column must equal to the Output 0: 1 + 0 + 0 = 1 ✅
5) The sum of Output 1 column must equal to the Output 1: 2 + 4 + 0 = 6 ✅
In addition to these, we have to check that:
- We have 3 ETH coming from outside to the system. This is done in the contract level.
- Total of 3 ETH MUST enter the lottery: In out example case they do as
blockNums for outputs are higher than current block number: 2000 > 1000 and 3000 > 1000 - When funds are moved inside the system, we can only move funds either to 0
blockNums, or into higherblockNums than our current block or outside the system. In our example case we are not moving funds to 0blockNum, but we have one input that has 0blockNum. This UTXO must have come from the lottery in the past. This does not need to be checked as it has been checked before.
Coming up with random numbers
To be able to perform a lottery draw, we need to have a fair way to generate random numbers. Coming up with a good scheme to generate random numbers is a difficult task and it’s not going to be part of this blog post. However, it’s an interesting challenge and its implementation is crucial for the security of ZK-Lottery. Currently, the most promising path towards solving this would be to use Ethereum’s beacon chain’s random numbers. To onboard them into the ZK-lottery, one has to be able to provide a proof such as
There exist a canonical beacon chain block 2000 that has a random number 198323
Explaining how this would work is worth another blog post. It’s important that we are not simply providing the random number as a public signal to the circuit, as this would leak the block number when a lottery was held and we don’t want to be doing that.
For this blog post, we assume that we have access to a Merkle root containing unbiased and uncensorable random numbers along with their respective block numbers.
To resolve a lottery of a UTXO input, the user simply fetches a random number and provides a Merkle proof of it.
Resolving a draw in lottery
After we have access to random numbers, we need to figure out how to convert a random number into a money sum that the player won. To implement this we create calculateReturn function that takes in a random number and a ticket price. Ticket price is the UTXO’s input amount that was entered into a lottery. The current design of ZK-Lottery allows any ticket price, but to keep ZK-Lottery above water (as discussed in another blog post), we might want to restrict this parameter based on how much liquidity there is in the contract.
There are multiple ways to develop calculateReturn. Here are our design goals in coming up with a good payout distribution:
1) The return percentage of the distribution needs to be less than 100%, since the casino needs to accrue profit over time.
2) Due to Ethereum network fees, we don’t want to return really small sums
3) In the most cases we want to return users back with about the same amount of funds that they put in, but not exactly the same amount
4) We want a possibility of very high returns
5) It should be easy to calculate in a Circom circuit
So we came up with the following distribution. This function returns 96.88% and it has a small probability to return over 6x return on the investment, however, most of the time it will return values near the original deposit.
Here’s Javascript implementation of the function:
The function starts by converting a 248 bit random number into a binary array of all ones and zeros with Num2Bits. Then we will sum the first 128 bits to generate binomial distribution of 128 coin flips. We do this again for the next 72 bits, add the previous 28 coin flips again and sum all together. Finally we throw another 20 coin flips to figure out whether the user has won a jackpot that is worth 5x extra on top of the other coin flips
The Num2Bits function that converts a number into its binary format is implemented as follows
We can then implement the calculation in Circom with very similar code:
It could be interesting to allow users to customize this distribution to their liking. For example the user could increase the jackpot winning probability while increasing the chance of going bust, but we won’t be implementing that here.
The lottery logic
On top of Nova’s signals, we add the following extra input fields to cover needs of the lottery:
The RNG Merkle tree needs to map each block number to a random number. The tree does not need to have every possible block number in it, only the ones that are used by the users. However, by not having some random numbers in it, leaks information about which blocks are used for lotteries. In order to fit both block number and the random number in each leaf, we grow the tree out of hash of the both values: leaf = Poseidon(blockNumber, rngNumber) :
Then exactly like we did with the nullifier tree for Nova’s circuit, we check that this block number and random number can be found in the RNG Merkle tree:
We can then check that our calculated Merkle root is the same as the one we have in the smart contract. This equality is only important if the input amount is nonzero and also the lottery block number is nonzero. As if the input is not worth anything, the player cannot win anything. And if the block number is 0, then the UTXO is not participating in the lottery.
Next comes an interesting part. After a lottery draw, the input value of a UTXO changes! The amount of currency coming in can be smaller or bigger than the output amount!
If a UTXO goes through the lottery we will use the CasinoReturn for its value and otherwise we use the original value. In pseudo code:
Here we are using the random number directly in the CasinoReturn function. This means that if users have chosen the same block number, their lottery outcome will be the same. This is something we might want to avoid in a real production version of the ZK-Lottery and we could XOR users’ commitment with the random number to ensure that different UTXO’s will always result in different lottery outcomes.
The implementation of this pseudo code is quite a bit more verbose in Circom as Circom is a very explicit language. We have to compose this logic using the following components: LessThan, LessEqThan, OR and Mux1. LessThan component compares two signals and returns true if the first signal is smaller than the second. LessEqThan does the same except it also considers equality. OR component is also quite straight forward primitive, it will return true if either of the input signals is non-zero. Lastly, we have a Mux1 component to choose our lottery winning amount if the lottery has occurred and the normal input amount if not. Mux1 outputs the input variable c[0] if input variable s is false and c[1] if the variable s is true.
So to split our pseudo code into these individual elements we get:
Very explicit and cumbersome! Here the same in Circom for each input:
Now as we have an inAmountsAfterLottery array that contains up to date input amounts, we can check that the user has provided us with the correct InOutAmount array that corresponds to these input values. The input output mapping contains the values as if they have gone through the lottery already. This means that the user has to calculate the lottery rewards outside the circuit to claim them. This is possible as the lottery is deterministic given the input values, and all the input values are available for the user to see. The ZK-Lottery user interface should manage this all for the user.
Outputs also need to match, but here we don’t need to calculate anything to do with the lottery, as the output amounts given to the circuit are calculated in a way that they already contain the lottery results:
You might notice and wonder what the +1's are. They come from the fact that the InOutAmount arrays’ first row and first column are related to the public amount and not to the UTXO’s. Thus the InOutAmount array is one bigger in both dimensions compared to the input and output lists.
Next we check that funds coming from outside the UTXO’s ( txIn = 0, the first row of the array)) go to the lottery. We are checking this by doing currentBlockNum < outBlockNum comparisons for each monetary flow from outside to outputs. We perform this check only if the input amount is bigger than zero, as we don’t care where zero funds go, this is done with the last equality check in the snippet:
Moving funds inside ZK-Lottery
The logic to check that the transacting rules inside the system are followed is a bit more complex. For each input UTXO -> output UTXO money flow, we want to check that the flow is allowed. The following equation makes sure all transacting rules are being followed:
Let’s dissect this and explain why each part is required. Here are all the transaction types that we want to allow and the logic that enforces only such transactions:
1) If the block number for the lottery has passed inBlockNum < currentBlockNum, the user should be able to enter a new lottery block number (outBlockNum > currentBlockNum): inBlockNum < currentBlockNum && outBlockNum > currentBlockNum
2) If the block number for the lottery has passed inBlockNum < currentBlockNum the user should be able to move the output into a UTXO that does not have the lottery anymore (outBlockNum == 0): inBlockNum < currentBlockNum && outBlockNum == 0
3) The user should be able move their lottery block number forward if the lottery has not already happened: outBlockNum > inBlockNum && outBlockNum > currentBlockNum
4) If the UTXO is not outputting any value, user can move it anywhere and we don’t care: inOutAmount == 0
When you combine these logical statements together you can form the logical statement above. Here’s the Circom code that does this check for all the inputs and outputs:
Lastly, similar to the Nova’s circuit we need to verify that the funds flowing in and out of the system equals the public amount.
And here we go, that’s the ZK-Lottery circuit in all its glory. You can find the complete circuit code from ZK-Lottery-Circuits.
ZK-Lottery, a system where a user can move funds into and take an arbitrary amount of funds out with having a plausible explanation where the funds came from.
Follow @Qhuesten on twitter to find out when new blog posts are published.
