From Zero to Hero in Zero Knowledge Proofs [Part 9]

This is the ninth part of the series that takes you from absolute ground zero in ZKPs to a fairly advanced level. We will start from the absolute basics and then move onward and upward. Subscribe to get regular updates!

Bring out your coding hats today. Image credits

In the previous post, we discussed the Trusted Setup Ceremony and handling toxic waste in zk-SNARKS. Today, we will go through a basic zk-snarks pseudo-code program to help you better grasp the concepts.

Scenario

Let’s go back to our example of Peggy and Victor.

Peggy knows a secret s that hashes to H. Victor also knows the hash H but wants to make sure that Peggy knows the secret s that hashes to H.

The easiest way to prove this is that Peggy gives the secret s to Victor, and he can run the hash function to check whether:

H=hash(s)

However, if Peggy doesn’t want to share the secret s with Victor, but still wants to prove that she knows s, then she can use zk-SNARK for this.

If we convert Peggy’s problem into a program C, this is how it would look like:

function C(H, s) 
{  
    return ( sha256(s) == H );
}

The program takes in a public hash H and a secret value s and returns true if the SHA–256 hash of s equals H.

Translating Peggy’s problem using the function C(H,s) we see that Peggy needs to create a proof that she possesses s such that C(H, s) == true, without having to reveal s. This is the general problem that zk-SNARKs solve.

A zk-SNARK for our example program

For Peggy to prove to Victor that she knows the s that hashes to H using a zk-SNARK, Victor first needs to create the setup which will allow for the proofs to be created and verified.

The first step that Victor will take is to run the generator function G to create the proving key pk and verification key vk.

Victor will randomly generate lambda and use that as input to the function G.

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

The parameter lambda needs to be handled with care because if Peggy learns the value of lambda she will be able to create fake proofs. Victor will share pk and vk with Alice.

Peggy will now play the role of the prover. She needs to prove that she knows the value s that hashes to the known hash H. She runs the proving algorithm P using the inputs pk, H, and s to generate the proof prf:

prf = P(pk, H, s)

Finally, Peggy will forward this proof to Victor who can verify it using the Verification algorithm V which would return true in this case since Peggy properly knew the secret s.

V(vk, H, prf) 

Victor can now be confident that Peggy knows the secret, but Peggy did not need to reveal the secret to Victor.

This, in essence, is how zk-SNARK works.

In the next post, we will go into the details of how a SNARK proof is actually created under the hood and what mathematical and computing concepts are used there. See you next week. Till then, ciao!

Hey there, thanks for reading this far. If you liked this article, don’t forget to follow and leave a clap.

I am building Plurality Network, the user context layer on web3. Join our discord to get alpha!

Follow me here, on LinkedIn, on X, or on Farcaster to get the latest blockchain technical content in simple, bite-sized reads.