This is a in-depth theoretical analysis on zero-knowledge proofs.

Zero knowledge proofs are a very important field of cryptography, zero-knowledge is achieved when there are two parties involved. What do I mean about that? even before I explain that, what are zero knowledge proofs?

Zero-knowledge proofs is where a prover makes a claim or an assertion to a verifier that his or her proof is valid, which must be approved by the verifier, without the prover leaking any knowledge other than the assertion or the claim itself. So now you understand why I said zero-knowledge is achieved when there are two parties involved right?

Now lets take a quick look at who those parties are. These parties are the prover and the verifier. Who then is a prover?

A prover is the one that makes the claim or the assertion that his or her proof is valid without giving any knowledge about his claim. Now that we know the prover it is important for us to know the verifier.

A verifier is simply the one that approves the prover's claim provided it is true. You realize how this makes zero-knowledge interesting and critically important in cryptography. Zero-knowledge proofs have tons of applications but we'll cover them in later sections.

Every strong algorithm has strong fundamentals or structure. If so how are zero-knowledge proofs structured and how do you think they work?

Essentially there are two structures involved in zero-knowledge proofs. They are the proving structure and, the verifying structure.

As mentioned earlier, there is a “prover” and “verifier”. The “prover” wants to prove the knowledge of a solution to a specific problem (or truth of a statement), without leaking any knowledge of the solution itself to the “verifier”, who wants to be reassured that the prover actually does know the solution (or that the statement is true).

1. Zero-Knowledge: This is the situation where the verifier does not know any knowledge (zero knowledge) of the prover’s statement or solution that, other than the truth of the statement.

2. Completeness: This is in the case where if the statement is true, the verifier would be convinced of the truth of statement by the prover.

3. Soundness: The prover can only convince the verifier of the truth of the statement if that statement itself is actually true, except with some very small probability.

In the class of non-interactive proofs, a particularly interesting concept for proving integrity of results for large computations is that of SNARK, i.e., succinct non-interactive argument of knowledge. By this term, we denote a proof system which is:

succinct: the size of the proof is very small compared to the size of the statement or the witness, i.e., the size of the computation itself,

non-interactive: it does not require rounds of interaction between the prover and the verifier,

argument: we consider it secure only for provers that have bounded computational resources, which means that provers with enough computational power can convince the verifier of a wrong statement,

knowledge-sound: it is not possible for the prover to construct a proof without knowing a certain so-called witness for the statement; formally, for any prover able to produce a valid proof, there is an extractor capable of extracting a witness (”the knowledge”) for the statement.

SNARK systems can be further equipped with a zero-knowledge property that enables the proof to be done without revealing anything about the intermediate steps (the witness). We will call these schemes zk-SNARKs.

A (zk-)SNARK protocol (as any other non-interactive proof system) is described by three algorithms that work as follows:

1. Gen is the setup algorithm, generating a necessary string crs used later in the proving process and some verification key vrs, sometimes assumed to be secret to the verifier only. It is typically run by a trusted party.

2. Prove is the proving algorithm that takes as input the crs, the statement u and a corresponding witness w and outputs the proof π.

3. Verify is the algorithm that takes as input the verification key vrs, the statement u and the proof π, and returns 1 ”accept” the proof or 0, ”reject”.

SNARK schemes can be used for delegating computation in the following way: a server can run a computation for a client and non-interactively prove the accuracy of the result.

The client can verify the result’s correctness in nearly-linear time in the size of the input (instead of running the entire computation itself ).

Proof systems can be interactive where the prover and verifier exchange many messages, or non-interactive where the prover sends a single convincing proof to the verifier.

A proof system in cryptography, is an interactive protocol by which one party (called the prover) wishes to convince another party (called the verifier) that a given statement is true. In zero-knowledge proof, we require further that the proof does not reveal anything more than the truth of the statement. At a first glimpse, it sounds counter-intuitive, being able to prove something is correct, without revealing any extra detail.

Zero-knowledge proofs are useful when the prover has private data that should not be leaked but needs to demonstrate a certain fact about this data. The prover may for instance want want to show it is following a protocol correctly but does not want to reveal its own input.

Researches in zero-knowledge proofs have been prompted by authentication systems where one party wants to prove its identity to a second party via some secret information such as a password but does not want to disclose anything about its secret password to the second party. This is called a zero-knowledge proof of knowledge.

A proof of knowledge is an interactive protocol in which the prover succeeds in ”convincing” a verifier that it knows something (a password, the steps of a computation, etc.) associated with the statement. For example, if the statement is ”I am Alice.”, the prover should show knowledge of the secret password of Alice; if the statement is ”I computed the function f(x) and obtained y.”, then the prover must convince its verifier that it knows all the steps of this computation that lead to the result y.

1. zk-SNARKs: A Gentle Introduction by Anca Nitulescu

2. Efficient Zero-Knowledge Proof Systems by Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth

3. An Exploration of Zero-Knowledge Proofs and zk-SNARKs by Terrence Jo