ZkDai — Private DAI transactions on Ethereum using Zk-SNARKs

In this post, I aim to familiarise the reader with some tools to implement Zk-SNARKs on ethereum. For the sake of the illustration, I’d be walking through our project that my team worked on during ETHSingapore; ZkDai - perform ZCash like private DAI transactions on Ethereum.

Using ZkDai one can shield the transaction sender, recipient and the amount. We got the MakerDAO API sponsor prize for the project! Our submission, along with the demo video can be found here and the github repo here.

Recently, a lot has been written on zero knowledge proofs, however in spite of that, the math behind zero knowledge proofs remains to be “cryptic” and hard to grasp. For an uninitiated reader, Introduction to zk-SNARKs and Quadratic Arithmetic Programs serve as excellent resources to start reading about Zk-SNARKs and this post will help the reader put them to practice while treating the math behind as a black box.

What does a general-purpose succinct zero-knowledge proof do?
Suppose that you have a (public) function C, a (private) input w and a (public) output x. You want to prove that you know a w such that C(w) = x, without revealing what w is. Furthermore, for the proof to be succinct, you want it to be verifiable much more quickly than computing C itself. Now, when a prover wishes to prove to they know an answer to the computation C, they will generate a proof using the proving key, public inputs (x) and secret input (w). When the verifier wants to verify that answer that the computation is indeed correct, they would verify the proof using the verifier key, public inputs (x) and proof.

A Zk-SNARK computation needs to be initialized by a trusted party. This involves modifying the computation C into a circuit format and using a secret parameter lambda to generate the proving and verifying keys that are used later. Following this, lambda — also called the “toxic waste” needs to be destroyed — otherwise it will enable an adversary to generate fake proofs of the knowledge. For this reason, the Zcash team — a fork of bitcoin that’s based on zK-SNARKs and lets one perform “shielded” transactions conducted an elaborate ceremony to generate these keys. Zcash has optional shielded transactions that let you transfer hidden amounts to hidden addresses.

ZkDai Implementation

The implementation details behind ZkDai are directly inspired from the zerocash paper. Note that this is a very hacky 36 hour (sleep deprived and red bull infused) implementation, and it is possible for the approach to have flaws and(or) be highly inefficient in practice. I plan to iron out those kinks as I continue to work on the project.

ZkDai has the concept of a secret note. A note is denoted by a tuple that is a combination of 2 elements — public key of the note owner (pk) and value of the note in Dai (v).

Note = (pk, v)

A note resides on-chain as (Hash(Note), Encrypt(Note)). The second element Encrypt(Note) is the note encrypted with the public key of the note owner (in practice the encryption public key will most likely be different from pk used above). The encrypted version of the note is for the owner to identify that a particular note belongs to them.
Let’s call Hash(Note) as the secret note. Since only the hashed secret note is saved on-chain, it’s impossible to tell the pre-image that constitutes the hash and hence no one but the owner of the note is privy to the tuple (pk, v) constituting the note.

Spending a ZkDai note

The ZkDai notes are spent like UTXOs. To transfer a particular value to a receiver, you select some secret notes whose net value is at least the value that you want to transact with. This value will be propagated to the receiver in form of a new ZkDai note and the leftover value will become a new secret note (like UTXO) assigned to your key.

Now, this is where the zero-knowledge proofs come into picture. To be able to spend a particular note the owner needs to demonstrate the knowledge of:

1. Ownership of the secret key (sk) that corresponds to the public key (pk) that a note belongs to.
2. Value of the note

The public computation C then returns the hash of the note — that one that is also present on-chain. Putting it in the C(w) = x form of zero knowledge computation above, it becomes

C(sk, v) = h
where h = Hash(Note) and is publicly known
sk, v are private inputs

If you have a valid proof of this computation, you are in fact the proud owner of the secret note!

A more specific case (but without the loss of generality) would be to send a value to a receiver using a single secret note. This would entail generating 2 new notes:

N1 = (receiverPk, v’) and
N2 = (pk, v — v’)

Note N2 is the leftover change from the original note of value v, so like UTXOs, it will be assigned to the sender. So the 2 new private parameters for the zkp generation are receiverPk and v’. Also, slightly modifying the computation C such that it returns 1 when C(w) == x; the proof is valid if C(x, w) = 1 where x is the public input. So for ZkDai, the computation becomes

C(oldNote, newNote1, newNote2, sk, v, receiverPk, v’, change)
where oldNote, newNote1, newNote2 are public inputs.

The zero knowledge computation C then looks like

C(oldNote, newNote1, newNote2, sk, v, receiverPk, v’, change) {
    pk = computePublicKeyfromSecret(sk)
    oldNote == sha256(pk, v)
    v == v’ + change
    newNote1 == sha256(receiverPk, v’)
    newNote2 == sha256(pk, change)
    return 1
}

Once the zero knowledge proof is generated, it can be sent along with the encrypted versions of newNote1 and newNote2 in a transaction.

Note that this transaction hides the transaction graph. Sender is hidden in the sense that you can use a new eth address each time to perform a transaction that sends the zkp on-chain. You only need to demonstrate the knowledge of “sk” which is the secret key corresponding to the public key that owns the note i.e. zero knowledge proof is what proves ownership of a note, not the transaction sender. Recipient is always hidden since that information is encoded in the hashed note.

Implementing the zkSNARK on Ethereum

Zokrates is a toolbox for zkSNARKs on Ethereum. It helps you create off-chain programs (zero-knowledge proofs) and link them to the Ethereum blockchain. First, we will setup zokrates on our local machine and run it as a docker container.

git clone https://github.com/JacobEberhardt/ZoKrates
cd ZoKrates
docker build -t zokrates .
docker run — name zokrates -ti zokrates /bin/bash

At the time of writing, zokrates is at version 0.3.1

Now, we will write the computation function that a prover needs to prove (and the one that the verifier will verify) in the file zk-circuit.code. Some notes from ZoKrates docs before we proceed:

• The keyword field is the basic type we use, which is an element of a given prime field. A field value can only hold 254 bits due to the size of the underlying prime field we are using.
• The keyword private signals that we do not want to reveal this input, but still prove that we know its value.
• sha256packed — A function that takes 4 field elements as inputs, unpacks each of them to 128 bits (big endian), concatenates them and applies sha256. It then returns two field elements, each representing 128 bits of the result. sha256packed is a SHA256 implementation that is optimized for the use in the ZoKrates DSL.

We have to pass 512 bits of input to sha256. As a consequence, we use four field elements, each one encoding 128 bits, to represent our input. The four elements are then concatenated in ZoKrates and passed to SHA256. Given that the resulting hash is 256 bit long, we split it in two and return each value as a 128 bit number. The zk circuit will look like:

Copy the zk-circuit.code inside the zokrates container.
docker cp zk-circuit.code zokrates:/home/zokrates/

Go to the zokrates container and compile the circuit. zokrates-compile compiles the circuit into flattened conditions and produces two files: human-readable ‘.code’ file and binary file.

./zokrates compile -i zk-circuit.code
Compiling zk-circuit.code...
Compiled code written to ‘out’
Number of constraints: 165257

Now, we generate the proving and verification keys for the computation.

zokrates setup performs a trusted setup for a given constraint system. It uses a generator function to generates these keys from the arithmetic circuit and “toxic-waste” parameter lambda. (pk, vk) = G(λ, C).
./zokrates setup

You can check that 2 new files, proving.key and verification.key have been generated. The proving key can be made public for anyone to be able to generate proofs of the knowledge. Next, we will generate a verifier contract that will be deployed on the ethereum blockchain. Luckily, zokrates provides this functionality out of the box.
./zokrates export-verifier

Using verifying.key, it generates a solidity contract which contains the generated verification key and a public function verifyTx to verify a solution to the compiled program.

Now we shall generate the zk-proof. I wrote a script that prints the compute witness command that should be fed to the zokrates cli to generate the requisite proof.

The function getTransferZkParams(sender, noteValue, receiver, value) prints the compute-witness zokrates cli command that needs to be executed inside the zokrates docker container. For my example of

getTransferZkParams(
    ‘0x3644B986B3F5Ba3cb8D5627A22465942f8E06d09’, // sender
    ‘0xb’, // value of the secret note
    ‘0x9e8f633D0C46ED7170EF3B30E291c64a91a49C7E’, // receiver
    ‘0x9’ // value to be sent
);

Running the script zokcmd.js, yields the command

./zokrates compute-witness -a 232310020822901034104762510965330293111 290107346578087637545360782727286918188 910473606 239207701314920212136923811659422657801 0 11 210219292964116369102883671286459321076 227322991366389551999749449849806758625 2660197181 16319012648326391858874240100255177854 0 9 42022122505097917127364068979301637648 120910671520054972343429929459551033400 0 2

Here each input is a 128 bit number and represented in base 10. Now, running the command in the zokrates container to generate the witness; I get
Witness: ~out_0 1

Now, to generate the proof that’ll actually go as a transaction;
./zokrates generate-proof
The proof is written to proof.json .

The next step is to send this proof as a transaction along with the encrypted versions of the 2 new notes. The script for doing the same can be found here.

Finally, towards the end of the hackathon, I had 2 options — to get a couple hours of sleep before the judging began or writing in the functionality to be able to convert your secret ZkDai (we were calling it liquidating) into vanilla publicly visible DAI token for the owner to spend freely. Needless to say, I chose the latter :D The solidity code for the same can be found here. Details about gas, sample transaction etc can be found in the following tweet.

I know I have glossed over some details. If you have any thoughts, questions or feedback, head to the comments section! If you’d like to help me in developing ZkDai further, DM me on twitter. I would like to hear from you.