Background

https://www.zkcamp.xyz/blog/lifecycle-of-zkp

Example

Peggy knows some secret value “w” which, when hashed, results in “x.” Peggy needs to prove to Victor that she knows “w” without actually revealing “w.” Peggy can use a zero-knowledge proof for this.

We can convert the above scenario into a simple program:

function C(x, w) {
  return sha256(w) == x;
}

The program takes in “x” (the hash of the secret value) and the secret value “w.” It returns true if the SHA-256 hash of “w” equals “x.”

So, Peggy needs to prove that she knows a value “w” that will result in the program above returning true.

Completeness

• The program “C” returns “true” when Peggy’s secret input value (“w”) is the right value.

• So, Peggy’s proof will be accepted by Victor.

Soundness

• If the program “C” returns “false,” then the Verifier algorithm will return false and Victor will not accept the invalid proof.

Zero Knowledge

• Victor is able to verify that Peggy knows “w” without gaining any knowledge of the value “w.”

Of course, the devil is in the details. Understanding how these black boxes work is not trivial, but not impossible either. We will be breaking down different components and aspects of zero knowledge technology in future posts.

The Basic Elements of Zero-Knowledge Proofs

In order to explain the solution to this problem, we need to understand the basic elements of zero-knowledge proofs — specifically “zk-SNARK” proofs.

zk-SNARK is an acronym that stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.” Let’s break that down:

• ZK = Zero knowledge: We can prove a fact without revealing that fact.

• S = Succinct: The proofs for even very large programs are small (eg. a few hundred bytes) and can be verified within a few milliseconds.

• N = Non-interactive: There is no need for back-and-forth communication between a prover and verifier (eg. such as in the “Color Blindness” example above). Instead, a prover simply hands over a proof to the verifier and the verifier can compute whether the proof is valid or invalid.

• AR = Argument: For technical reasons, the proofs are called “arguments” because they are not technically “proofs” in the traditional sense — but they functionally serve the same purpose. The difference between “proof” and “argument” is very technical and out of scope for this post.

• K = Knowledge: This refers to the information that the prover knows.

Roughly speaking, a zk-SNARK consists of three algorithms: Setup, Verify, and Prove. We’ll take a look at each of them now.

Setup

The Setup algorithm generates two keys: the proving key (“pk”) and verification key (“vk”). In order to generate these keys, it takes as inputs a secret parameter (“lambda”) and a program C (such as the one we defined above, which returns true if the hash of “w” matches “x”).

$$(pk,vk)= Setup(lambda, C)$$

The proving and verification keys created by the generator are public and used by the prover and verifier, respectively, to generate the proof and verify the proof.

If the lambda is leaked, anyone who has access to it can generate fake proofs. This is why zk-SNARKs require what is called a “trusted setup” phase where the keys are generated, but we have to trust that the lambda value was discarded properly and not leaked.

Prove

The prove algorithm is responsible for generating the zero-knowledge proof. It takes as inputs the proving key (“pk”), the private witness “w,” and a public value “x” to generate the proof.

$$proof =Prove(pk,x,w)$$

• The witness (“w”) is the secret information that the prover claims she has knowledge of,

• The value “x” is a value that is generated based on “w” but is obfuscated such that anyone can access “x” without figuring out “w.”

to generate a zk proof, you will need to provide the hidden info and the proxy public info

Verify

The verify algorithm is responsible for taking the proof created by the proving algorithm and asserting true or false, depending on whether the proof is correct or incorrect. It takes as inputs the verification key (“vk”), the public value “x,” and the “proof”.

$$Verify(vk,x,proof)=bool$$

Overview of ZK Dapp

• circom builds the proving circuit to generate proofs on specific inputs (?)