@adlrocha - S(Z)okrates is more than just a philosopher

Zero Knowledge Proofs in action.

book lot on black wooden shelf

A few months ago I introduced through “The ZKP Game” a set of cryptographic primitives that are gaining a lot of attention in the blockchain world, zero-knowledge proofs. In that publication we did a walk through the theoretical basis of these primitives, but we didn’t introduce how to use them in practice. Today I want to share with you one of the projects that helped me the most in my quest of understanding how Zero Knowledge Proofs (and in particular zkSNARKs) practically operated, Zokrates.

Disclaimer: If you have the chance, read “Letters from a Stoic” from the actual philosopher… one of my favorite books ever.

The philo(z)opher

ZoKrates is a toolbox for zkSNARKs on Ethereum. It helps you use verifiable computation in your DApp, from the specification of your program in a high level language to generating proofs of computation to verifying those proofs in Solidity.

i.e. with Zokrates we are able to easily generate zk proofs, publish them on-chain in a smart contract, and validate them on-chain. The best way to understand how Zokrates and the use of zkSNARKs in Ethereum work is to follow their “Getting Started” docs.

The easiest way to start playing with Zokrates is using their Docker image, that way you don’t have to worry about installations and dependencies. Use the following command to start interacting with Zokrates:

docker run -ti zokrates/zokrates /bin/bash 

Once inside the console, you can try to run ./zokrates to see the type of commands we have available:

compile            Compiles into flattened conditions. Produces two files: human-readable '.ztf' file for debugging and binary file
compute-witness    Calculates a witness for a given constraint system
export-verifier    Exports a verifier as Solidity smart contract
generate-proof     Calculates a proof for a given constraint system and witness.
help               Prints this message or the help of the given subcommand(s)
print-proof        Prints proof in chosen format [remix, json]
setup              Performs a trusted setup for a given constraint system

You can see how Zokrates offers all the utilities required to start playing with zkSNARKs. From compiling into flattened conditions the computations you want to include in your proof, to the generation of the proving and verification keys in the setup phase, to building proofs, and the implementation of the verification code that should be included in the Ethereum smart contract in order to perform on-chain validations of proofs.

A toy example

Let’s illustrate its operation with a simple example: imagine that you authenticate users in your new system through their password, but instead of storing directly their password in your database, the moment users set their password, you apply the following function (fn = pass · pass · 2) in order to obfuscate it before storing it. From there on, in order to authenticate to your service, users just need to proof knowledge of their password, but you don’t want to gain knowledge of their specific password, nor make them transmit it in the open. As you just read about Zokrates and zkSNARKS in your favorite newsletter, you decide to use these cryptographic primitives to implement your authentication system.

The first thing you would do is to implement your desired program using Zokrates’ DSL. Create a file called, for instance, auth.zok, and add the following piece of code:

def main(private field pass, field stored) -> (field):
  field result = if pass * pass * 2 == stored then 1 else 0 fi
  return result

This piece of code implements the computation we want to run in our proving system. Our “private” argument is a user pass, and the public information is the output of our function computation, i.e. the piece of information stored in our database. For a user to successfully authenticate we will require him to show knowledge of his password (i.e. they will have to build a valid proof using their password that would have to be validated successfully by our verifier).

Once implemented our desired computation, we need to compile the code in order to build the flattened constraints understood by our SNARKs. To do this we just run:

./zokrates compile -i auth.zok

If you recall from the theoretical overview we did of zkSNARKs in the ZKP Game, this cryptographic primitive requires of an initial setup phase to generate a proving and verifying key in order to be able to start building proofs and validating them. This stage is critical because if done wrong or in an insecure manner could lead to a malicious agent being able to generate fake proofs. I recommend this article to deeply understand zkSNARK’s setup phase. To perform the system’s setup we build:

./zokrates setup

This command should have generated two files: a “proving.key” and a “verification.key” from our computation (compiled in the “out” file). The proving key is used by users to generate new proofs, while the verification key is used in the validation process.

We are going now to compute a witness in order to test the operation of our computation. Imagine that I am a user whose password is 42 (the answer to life). We compute a correct witness as such:

./zokrates compute-witness -a 42 3528

As an output we obtain a “1” because my password equals the “supposedly” stored data in the database (the 3528). If instead of this pair of numbers we computed the witness with any other random pair of them we would get a “0” (as in “you failed the computation”).

We are going to build now the proof required by the user to authenticate in the system with:

./zokrates generate-proof 

This function uses the proving key and the computation flattened constraints to build it. If the proof is generated successfully you will see a proof.json file with the values for the proof. These are the parameters to be shown by a user in order to be successfully verified and authenticated by the system (explore the concept of Elliptic Cure Pairings to better understand the mathematical meaning of these parameters of the proof).

So we have our proof. How can we verify it? Zokrates includes the following command to export a verifier for your computation in Solidity:

./zokrates export-verifier 

This generates a file verifier.sol with the verifier Solidity code. Formally, you could translate this code to any other programming language in order to validate your desired proofs. Easy, right? With these few simple commands we’ve been able to generate our own ZKP cryptosystems, thank to our favorite philosopher. Here’s the Solidity code of the verifier function:

function verify(uint[] memory input, Proof memory proof) internal returns (uint) {                                                                                                                                                   
        uint256 snark_scalar_field = 21888242871839275222246405745257275088548364400416034343698204186575808495617;                                                                                                                      
        VerifyingKey memory vk = verifyingKey();                                                                                                                                                                                         
        require(input.length + 1 == vk.gamma_abc.length);                                                                                                                                                                                
        // Compute the linear combination vk_x                                                                                                                                                                                           
        Pairing.G1Point memory vk_x = Pairing.G1Point(0, 0);                                                                                                                                                                             
        for (uint i = 0; i < input.length; i++) {                                                                                                                                                                                        
            require(input[i] < snark_scalar_field);                                                                                                                                                                                      
            vk_x = Pairing.addition(vk_x, Pairing.scalar_mul(vk.gamma_abc[i + 1], input[i]));                                                                                                                                            
        }                                                                                                                                                                                                                                
        vk_x = Pairing.addition(vk_x, vk.gamma_abc[0]);                                                                                                                                                                                  
        if(!Pairing.pairingProd4(                                                                                                                                                                                                        
             proof.a, proof.b,                                                                                                                                                                                                           
             Pairing.negate(vk_x), vk.gamma,
             Pairing.negate(proof.c), vk.delta,
             Pairing.negate(vk.a), vk.b)) return 1;
        return 0;
    }

An attempt to extend Zokrates: Gokrates

It was a while since I last used Zokrates before this publication, and since them it has evolved a lot including more proving schemes, more available primitives for the computations, etc. One of the things I tried with Zokrates was to try and build a tool to export the verifier in Golang (instead of just in Solidity) so that I could validate proofs inside Hyperledger Fabric smart contracts. I called the project Gokrates. Due to a extreme lack of time, and the appearance of other priorities, I didn’t manage to fully finish the project, but it really helped me understand the maths behind zkSNARK. I may take back this project one day, in the meantime, if someone has the time to contribute and help me extend Gokrates, feel free to do so.

More complex examples

Using Zokrates DSL you can build more complex examples than the one I shared in this publication. Have a look at this example of “Proving knowledge of a hash preimage” if you want to build the next ZCash implemented in Solidity. Start exploring Zokrates and its standard library, and start having fun building zero knowledge proofs in your DApps. It has never been this easy to start using these complex cryptographic primitives. Kudos to the development team behind this project.