How does zocrates process zk-SNARK step by step?

Question

I'm trying to understand my zokrates code and how it processes zk-SNARK step by step in accordance to this article.

The article breaks down the zk-SNARK into three steps.

1. A key generator, G, takes in a secrete parameter lambda and a program C to produce the pk, which is the proving key, and the vk, which is the verification key:

(pk, vk) = G(C, lambda)

C here is just a function that takes in the preimage and the returns true if the hash value is the same as the preimage:

// w is the preimage, x is the hashed value of w
function C(x, w) {
  return ( sha256(w) == x );
}

2. The prover uses the preimage s, the known hash H and the proving key pk and generates the proof prf through the proof generating algorithem P:

prf = P(pk, H, s)

3. Finally, the verifier runs the verification function using the proof from the prover:

V(vk, H, prf)

The result is true if the prf is correct, which essentially proves that the prover knows the witness.

Now, I have a zokrates code here that takes it two values "a" and "b".

def main(private field a, field b) -> (field):
  field h = if a * a == b then 1 else 0 fi
  return h

1. My first question is, what are these two values equivalent to in the aforementioned example? Is one of them lambda? Also, is the expression "a * a == b" equivalent to the function C mentioned above? I'm having difficulty understanding what these values and the expression are.

When I execute:

~/zokrates setup

I get the following output:

zokrates@0a96d8e9989b:~/code/square$ ~/zokrates setup
Performing setup...
def main(_0, _1) -> (1):
    (1 * _0) * (1 * _0) == 1 * _4
    # _2, _3 = ConditionEq((-1) * _1 + 1 * _4)
    ((-1) * _1 + 1 * _4) * (1 * _3) == 1 * _2
    (1 * ~one + (-1) * _2) * ((-1) * _1 + 1 * _4) == 0
    (1 * ~one) * (1 * ~one + (-1) * _2) == 1 * ~out_0
     return ~out_0
WARNING: You are using the G16 scheme which is subject to malleability. See zokrates.github.io/reference/proving_schemes.html#g16-malleability for implications.
Has generated 7 points
Setup completed.

I'm not sure where the proving key and the verification key are in this output. How does fit into the example above, in terms of what the lambda value is or the C function is?:

2. My second question is, what exactly am I doing when I am "creating a witness"?

When I execute the following, a witness is supposed to be created:

~/zokrates compute-witness -a <a> <b> ... <n>

I was under the impression that a "witness" is the preimage that the prover already has. Isn't "witness" something that prover is wanting to prove to the verifier that she has knowledge of this?

The output given to me when I executed the command was this:

zokrates@0a96d8e9989b:~/code/square$ ~/zokrates compute-witness -a a b
Computing witness...
def main(_0, _1) -> (1):
    (1 * _0) * (1 * _0) == 1 * _4
    # _2, _3 = ConditionEq((-1) * _1 + 1 * _4)
    ((-1) * _1 + 1 * _4) * (1 * _3) == 1 * _2
    (1 * ~one + (-1) * _2) * ((-1) * _1 + 1 * _4) == 0
    (1 * ~one) * (1 * ~one + (-1) * _2) == 1 * ~out_0
     return ~out_0
Could not parse argument: a

What exactly is happening here?

Answer 1

Disclaimer I am adding this answer on the off chance that it helps future readers.

Answer to the q. 1:

G is what is called the "trusted setup" phase. In trusted setup, a secret (the lambda) is used to create proving and verifying keys (pk, vk); that secret is also called "toxic waste" and has to be destroyed or the owner will be able to create fake proofs.

(pk, vk) = G(C, lambda)

the second part of your question:

is the expression "a * a == b" equivalent to the function C

not exactly; the following code is the function C; it accepts a witness (private field a) and x (field b) and returns 0 or 1 to indicated success or failure.

def main(private field a, field b) -> (field):
  field h = if a * a == b then 1 else 0 fi
  return h

the third part of the first question:

not sure where the proving key and the verification key are in this output

they are not outputted to terminal, but to two separate files. What you see as the command output is the conversion of the function C to R1CS in the Trusted Setup phase (G).

To answer the second question, I recommend reading the Zokrates example on "Zokrates RNG" as it contains a hypothetical scenario in which Alice is trying to prove to Bob in a Zero Knowledge manner. The separation will help to better understand what "witness" and compute witness steps are.