cft

The zk-SNARK Algorithm For Zero Knowledge Verification

Zero knowledge verification system using zk-SNARKs


user

Vincent T

3 years ago | 2 min read

A zk-SNARK consists of 3 algorithms G, P, V defined as follows:

The key generator G takes a secret parameter λ (lambda) and a program C, and generates two publicly available keys, a proving key pk, and a verification key vk. These keys are public parameters that only need to be generated once for a given program C.

The prover P takes as input the proving key pk, a public input x and a private witness w. The algorithm generates a proof prf = P(pk, x, w) that the prover knows a witness w and that the witness satisfies the program.

The verifier V computes V(vk, x, prf) which returns true if the proof is correct, and false otherwise. Thus this function returns true if the prover knows a witness w satisfying C(x,w) == true.

Note here the secret parameter lambda used in the generator. This parameter can be tricky to use zk-SNARKs in real-world applications. The reason for this is that anyone who knows this parameter can generate fake proofs.

Specifically, given any program C and public input x a person who knows lambda can generate a proof fake_prf such that V(vk, x, fake_prf) evaluates to true without knowledge of the secret w. Thus actually running the generator requires a very secure process to make sure no one learns about and saves the parameter anywhere.

A basic function can be written in Javascript following the above framework:

function C(x, w) {

return ( sha256(w) == x );

}

This also makes use of the sha256 hashing algorithm as a function for w.

In the next formula, we use the generator function to create the 2 keys.

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

For lambda we can assign it a parameter value, that only we know. This must be a secret that only the system knows, while making pk and vk public.

The prover must now run the proving algorithm:

prf = P(pk, H, s)

The verifier then runs the verification function to prove this:

V(vk, H, prf)

The result will be true if indeed there is provability in the function.

In the context of our system, the witness can attest to the prover that they are who they are to the verifier. The prover can prove their claim as witnessed by the identity verification system. All this is done without the verifier needing to know what the data value is.


(Photo Banner Credit: Mikhail Nilov)



Upvote


user
Created by

Vincent T

Involved in blockchain development and imaging technology.


people
Post

Upvote

Downvote

Comment

Bookmark

Share


Related Articles