Blockchain in Travel Industry — Part 3: Zero Knowledge Proof Hands-on Tutorial

In this article we want to go through each step of of the previous post where we write about our vision for Zero-Knowledge Proofs in Travel Industry. We now want to go through each step in a hands-on way. You just need some very basic programming knowledge as well as a running installation of the ZoKrates toolbox. We will start with defining the challenge, compute a valid witness, create the proving and verification key, construct the proof and of course the verification smart contract which we will upload to the Ropsten testnet. The easiest way to use ZoKrates is inside a docker container that is already provided on docker hub. Install instructions can be found here: https://zokrates.github.io/gettingstarted.html. Note that, as of writing this post, comparison operators like >= are not provided by the docker version of ZoKrates. So you might need to build from sources.

Revisiting all ZoKrates steps to follow along

In the last post we roughly outlined 5 needed steps to construct and validate a zero knowledge proof. We now revisit all steps as well as the requirements needed to follow along.

Step 0: Install ZoKrates

Follow the introduction of the ZoKrates project page (https://zokrates.github.io/gettingstarted.html):

To download and directly run a docker container:

docker run -ti zokrates/zokrates /bin/bash

or to be sure to run the most recent version build the container from source:

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

Step 1: Parameterise the challenge and compile the code

We assume that we have a business that only accept high quality partners in terms of average customer rating. A partner would be accepted if this rating is at least 4 of 5 stars. On the other side the package is aimed for cost-aware customers. So in order to keep a minimum margin, the product price should be between 100 and 150 money units. We can transfer this into a parameterised representation as:

def main(private field price, private field rating) -> (field):
  field minPrice = 100
  field maxPrice = 150
  field minRating = 4
field result = if price >= minPrice && price <= maxPrice && rating >= minRating then 1 else 0 fi
return result

What happens here?

The function accepts two fields price and rating. Those fields are private which means any proof constructed on basis of this function will not contain any reconstructable information about those two variables. The function returns 1 if and only if the passed price is between the limits minPrice and maxPrice and the passed rating is above 4 stars. Those values are hard-coded here for sake of simplicity. The used programming language is a domain specific language (DSL) used by the ZoKrates toolbox. ZoKrates than finds a flatten solution and later the R1CS representation.

Each program that we want to construct a proof for has to be transfered from the above high-level domain specific language into a arithmetically validatable representation. ZoKrates uses a rank 1 constraint system (R1CS) for this. Finding this arithmetical representation means interpreting each step of the above program as mathematically basic operations:

Graph representation of the program as a sequence of arithmetical computations.

Luckily, ZoKrates is doing this job for us. We just have to save above code in a file kpibounds.code. If we wrote the code on the local machine we have to copy the code into the running container. First we have to find out the ID of the container by

docker container ls

The first column contains the container ID:

CONTAINER ID        IMAGE               COMMAND             CREATED             STATUS              PORTS               NAMES
919576e7e615        zokrates            "/bin/bash"         2 hours ago         Up 2 hours                              friendly_napier

We can than copy the local source code to the container by

docker cp path/to/kpibounds.code 919576e7e615:/home/zokrates

Now we have everything at hand an can run the compilation by:

./zokrates compile -i kpibounds.code

We will obtain quite cryptic output from ZoKrates. The last lines will look something like:

...
(1 * ~one) * (1 * ~one + 21888242871839275222246405745257275088548364400416034343698204186575808495616 * _2305) == 1 * _2306
(1 * _2305) * (1 * ~one) == 1 * _2307
(1 * _2306) * () == 1 * _2308
(1 * ~one) * (1 * _2307 + 1 * _2308) == 1 * _2309
(1 * ~one) * (1 * _2309) == 1 * ~out_0
return (1 * ~one) * (1 * ~out_0)
Compiled code written to 'out'
Human readable code to 'out.code'
Number of constraints: 2305

The R1CS representation of the above code consists of 2305 contraints. Quite a lot for a rather simplistic example, right? But the good message here is that the verification size does not scale with the number of constraints. Since we will only upload the verification and compute the proof only off-chain we don’t have to bother a lot here.

2. Computing Witness

In order to construct the proof we need a valid solution in the flattened code format. Here again ZoKrates gives us a one-line tool for that:

./zokrates compute-witness -a 120 4

“-a” means that we pass over the (private) arguments. The first is the price of our product and the second argument our average customer rating. We than again get the R1CS representation of the witness from ZoKrates:

...
# _2305 = Rust::Identity(1 * _2304)
(1 * ~one) * (1 * ~one + 21888242871839275222246405745257275088548364400416034343698204186575808495616 * _2305) == 1 * _2306
(1 * _2305) * (1 * ~one) == 1 * _2307
(1 * _2306) * () == 1 * _2308
(1 * ~one) * (1 * _2307 + 1 * _2308) == 1 * _2309
(1 * ~one) * (1 * _2309) == 1 * ~out_0
return (1 * ~one) * (1 * ~out_0)
Witness:
~out_0 1

The last line is important since it states that the witness is valid. If we would pass values that do not fulfil the requirements like

./zokrates compute-witness -a 120 3

an “unvalid” witness would be created, indicated by:

...
Witness:
~out_0 0

3. Setup

As the second requirement to construct the proof and the verification program we need to compute the corresponding key pairs. This is, again, a single command:

./zokrates setup

ZoKrates returns the keys in the files proving.key and verification.key.

4. Constructing the Proof

Now we have everything we need to construct the proof. And guess what… It’s again a single line:

./zokrates generate-proof

which outputs:

...
"H":["0x99b2d8f0e11c030ec383d6993a745c6ca6a2d2c96ff968aca54c7f12f1af6b9", "0xee87810b5bafcb94259b5fb18db449e737250d8814f2bd3f6423a04dab91a74"],
"K":["0x2256ad47f190e9da72bee9e6a1b56785dd7c0b4f402effe5dcc9895aff280528", "0x104fc9c7ba4f4a70b2f0c26c76baa014f4ffbaf82a3f49fc60cee407e78c5a17"]
},
"input":[0]
}

The “input”: [0] here refers to public inputs. Since we declared all inputs as private and don’t require public inputs, this is correct.

Internally ZoKrates uses libsnark, a C++ library which constructs zkSnarks from R1CS representations. This only works if we have previously computed the witness as well as the proving key. As a result the proof is saved in a json file proof.json. This can later be used to upload it to the verification step.

5. Verification

And now, finally we will make use of the Ethereum blockchain as a publically readable ledger. We will upload a verification smart contract to the Ropsten test network.

To create the verification code we need the verification key that we created in the same setup phase when we also found the proving key. With this we can run:

./zokrates export-verifier

which gives us a new file, verifier.sol directly in solidity code. We upload that code via the remix IDE (https://remix.ethereum.org/) to Ropsten:

Uploading the verification smart contract via remix IDE. Remeber to change the compiler version!

Note that you have to manually chose an older Solidity compiler version. In this example we chose 0.4.24. The whole code (including a required library for operations on a specific elliptic curve) is 599 lines long which seems to be quite a lot for verifying a proof that only two variables satisfy three constraints. But the good message is that the verification smart contract can be used unlimited times. After deploying the smart contract we have to wait a few seconds (depending on the chosen gas price) and will receive the confirmation like:

Confirmation that the verification smart contract was successfully uploaded. The deployment only has to be done once.

We can now interact with the verifyTx function of the just uploaded smart contract. This function accepts the proof parameters that we obtained form step 4. We continue using Remix and thus have to manually copy and paste the parameters from the proof.json into the web interface:

Using the Remix IDE to input the proof parameters.

After sending the transaction we again have to wait a few seconds and can than see that the verification was successful. The verification smart contract also sends an success event via the Ethereum Event System:

The verification smart contract successfully verified the correctness of the proof. This means that we can be sure that the prover has a valid set of KPIs — but we will never know how exactly those numbers look like!

That’s it. In our example we started off with a company A that wants to make sure that a it only works together with a company B if certain criterea are fulfiled. Company B can prove this by uploading the proof to the verification smart contract and nobody else would be able to know the exact numbers of company B.

In the next article (Part 4) we will describe our approach to State Channels, a technique that may help solving the scaling challenge of present blockchains by performing high-throughput off-chain transactions.