Proving knowledge of a pre-image

Share on facebook
Share on twitter
Share on pinterest
Share on linkedin

We’ll implement an operation that’s very typical in blockchain use-cases: proving knowledge of the pre-image for a given hash digest. In particular, we’ll show how ZoKrates and the Ethereum blockchain can be used to allow a prover to demonstrate that he knows a hash pre-image for a digest chosen by a verifier, without revealing what the pre-image is.

Computing a Hash using ZoKrates

We will start this tutorial by using ZoKrates to compute the hash for an arbitrarily chosen pre-image, being the number 5 in this example.

First, we create a new file named hashexample.zok with the following content:

import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> (field[2]):
    h = sha256packed([a, b, c, d])
    return h

The first line imports the sha256packed a SHA256 implementation that is optimized for the use in the ZoKrates DSL. In this example, we have four input fields because we want to pass 512 bits of input to SHA256. Still, a field value can only hold 254 bits due to the size of the underlying prime field we are using. As a consequence, we use four field elements, each one encoding 128 bits, to represent our input.

 _______________________________________
|               512bits                 |
            original input
 _______________________________________
| 128bits | 128bits | 128bits | 128bits |
     a         b         c         d

The four elements are then concatenated in ZoKrates and passed to SHA256.

h = sha256packed([a, b, c, d])

The resulting hash is 256 bit long, so we have to split it in two and return each value as a 128-bit number specifying the output value field[2]

def main(private ....... ) -> (field[2]):

Compile the program into an arithmetic circuit using the compile command.

zokrates compile -i hashexample.zok

Then create a witness file using the command compile. Using the flag -a, we pass arguments to the program. Recall that our goal is to compute the hash for the number 5. Consequently we set ab and c to 0 and d to 5.

zokrates compute-witness -a 0 0 0 5

Finally, we can check the witness file for the return values:

grep '~out' witness

which should lead to the following output:

~out_1 65303172752238645975888084098459749904
~out_0 263561599766550617289250058199814760685

Concatenating the outputs as 128 bit numbers, we arrive at the following value as the hash for our selected pre-image :

0xc6481e22c5ff4164af680b8cfaa5e8ed3120eeff89c4f307c4a6faaae059ce10

Prove knowledge of pre-image

Our goal is to prove that a prover knows a pre-image for a digest chosen by a verifier, without revealing what the pre-image is. Without loss of generality, let’s now assume that the verifier wants the digest to be the one we found in our example above.

~out_1 65303172752238645975888084098459749904
~out_0 263561599766550617289250058199814760685

First, the verifier has to specify what hash he is interested in. Therefore, we have to adjust the zkSNARK circuit, compiled by ZoKrates, such that in addition to computing the digest, it also validates it against the digest of interest provided by the verifier. This leads to the following update for proveimage.zok:

import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> (field):
    h = sha256packed([a, b, c, d])
    h[0] == 263561599766550617289250058199814760685
    h[1] == 65303172752238645975888084098459749904
    return 1

Now we compare the result of sha256packed with the hard-coded correct solution defined by the verifier. The lines which we added are treated as assertions: the verifier will not accept proof where these constraints were not satisfied. This program only returns one if all of the computed bits are equal.

So, having defined the program, the verifier is now ready to compile the code:

zokrates compile -i proveimage.zok

Based on that, the verifier can run the setup phase and export-verifier, which export a smart contract as a Solidity file.

  • setup creates a verifiation.key file and a proving.key file. The verifier gives the proving key to the prover.
  • export-verifier creates a verifier.sol contract that contains our verification key and a function verifyTx. The verifier deploys this smart contract to the Ethereum network.
zokrates setup
zokrates export-verifier

Now the verifier and the prover know the correct pre-image is 5. Once it is necessary, the prover will need just to provides the correct pre-image as an argument to the program proveimage.zok and construct the proof with command generate-proof which creates a file, proof.json, consisting of the three elliptic curve points that make up the zkSNARKs proof. The verify function in the smart contract deployed by the verifier accepts these three values, along with an array of public inputs.

zokrates compute-witness -a 0 0 0 5
zokrates generate-proof

If we use a different pre-image zokrates will output the following error.

zokrate compute-witness -a 0 0 0 1
....
....
....432 * _60518 + 67108864 * _60519 + 134217728 * _60520 + 268435456 * _60521 + 536870912 * _60522 + 1073741824 * _60523 + 2147483648 * _60524
    (1 * ~one) * (1 * ~one) == 1 * ~out_0
     return ~out_0
Execution failed:
  Expected 263561599766550617289250058199814760685 to equal 192679394205378567678278285373543227086

As the inputs were declared as private in the program, they do not appear in the proof thanks to the zero-knowledge property of the protocol. In the example we’re considering, all inputs are private, and there is a single return value of 1. Hence the prover has to define his public input array, then submit his proof by calling verifyTx.

The verifier monitors the smart verification contract for the Verified event, which is emitted upon successful verification of a transaction. As soon as he observes the event triggered by a transaction from prover’s public address, he can be sure that prover has a valid pre-image for the hash he set in the smart contract.

All the information are taken from zokrates.github.io

Condividi
Share on facebook
Share on twitter
Share on pinterest
Share on linkedin

Chi è Nils Lewin

Mi chiamo Nicola Bombaci alias Nils Lewin, sono un ingegnere informatico con la passione per la musica e l’audio. Durante la mia crescita professionale ho deciso di fondere questi due mondi apparentemente diversi tra loro.
Articoli Correlati

Lascia una risposta

Iscriviti alla newsletter

Resta sempre aggiornato sulle ultime novità