From Zero to Hero in Zero Knowledge Proofs [Part 6]
This is the sixth 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!
Until now, we have been going through the fundamental concepts necessary to understand ZKPs. From this lesson onwards, we will change gears and get into the meat of it. We will discuss the properties and features of ZKPs. So, let’s get started.
Properties of zero-knowledge proofs (ZKPs)
Zero-knowledge proof is a mathematical concept initially proposed by MIT researchers Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the 1980s. A clear definition of the concept is:
Zero-knowledge Proof (ZKP) is a technique to define whether the provided data is true without revealing it.
Simply put, it is a method by which one party can prove to another party that something is true. And they do so without revealing any information apart from the fact that this specific statement is true.
For any proof to be considered zero-knowledge proof, it needs to fulfill three criteria which are explained below:
Completeness
The protocol returns “true” if the input is valid.
If the input is valid, we want the zero-knowledge protocol to return the value “true”. This allows us to make the assumption that the proof can be accepted by the verifier (assuming the prover and verifier act honestly).
Soundness
The verifier is able to reject invalid statements.
Assuming that a prover would act dishonestly, we want the verifier to be able to reject an invalid statement rather than accept it as true (with high probability).
Zero-knowledge
The verifier only knows whether a statement is valid.
The underlying assumption of zk-proofs is “zero-knowledge”. This means that the verifier learns nothing about a statement beyond its validity or falsity. This requirement also prevents the verifier from deriving the original input from the proof.
Features of ZKPs
All zero-knowledge proofs are not the same. They can differentiate based on the features they have. Different features are suitable for different kinds of problems. For each unique problem, we need to figure out which features would fit best, and then we can choose the ZKP which offers those features.
Let’s discuss these features in detail:
Interactive vs non-interactive proofs
Interactive proofs mean that for a prover to prove something to the verifier, multiple rounds of interaction or communication are required. The verifier can challenge the prover with certain “questions” that the prover can only answer if she indeed has access to the secret (witness). To ensure the prover isn’t guessing blindly and getting the correct answers by chance, the verifier and the prover repeat this interaction many times to lower the possibility of the prover faking knowledge of the witness.
Interactive proof:
Prover and Verifier go through n rounds of communication
Remember the Alibaba cave example from the previous chapter? That was interactive proof since Victor repeatedly challenged Peggy to take a certain path in the cave.
In non-interactive proofs, only one round of communication is needed. The prover has some secret information using which he or she computes a zero-knowledge proof. He or she then publishes this proof in a place accessible to the verifier e.g., on a distributed ledger/blockchain. The verifier(s) can later at any point check the validity of the proof with the help of another algorithm. No active communication between the two parties is required and the proof can be communicated asynchronously.
Non-interactive proof:
The Prover stores the proof on the blockchain, and verifier(s) verify by fetching proof from the blockchain
Interactive proofs were more popular in the early days. However, now the trend is shifting towards non-interactive proofs since they can be used to prove a single proof to multiple independent verifiers.
Succinct vs non-succinct proofs
Succinctness means that the created proof is smaller than the input (secret) data, also known as the witness. In contrast, non-succinct means that the proof is larger than the input data.
Succinctness results in fewer storage requirements and faster verification times. Therefore, if the storage medium for the proofs is expensive, then the succinctness property is desirable.
Zero-knowledge proof vs proof of knowledge
We already know what a zero-knowledge proof is. A prover proves something to a verifier without giving away any information about the secret witness.
In a proof of knowledge, a prover must prove that it knows something to a verifier. A proof of knowledge is stronger and more useful than just proving the statement is true. For instance, it allows me to prove that I know a secret key, rather than just that it exists.
Argument vs proof
In a proof, the “soundness” property holds against a computationally unbounded prover, and in an argument, the “soundness” only holds against a polynomially bounded prover. Arguments are thus often called “computationally sound proofs”.
By computationally unbounded, we mean that the prover has unlimited computational resources and can create any kind of proof using any inputs.
By polynomially bounded, we mean that the prover can only create proofs that can be created in a polynomial time i.e., it does not have unlimited resources. This means that in arguments, the Prover and the Verifier must agree on what they’re proving i.e., both must know the statement that is to be proven and what the inputs to this statement represent.
A practical application of Arguments is in the SNARK and STARK protocols.
That’s it for today. If you want to test your knowledge, try this quiz!
In the next post, we will start with the actual ZK protocols, the first of them being ZK-Snarks. Stay tuned for some hands-on on ZKPs as well. 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.
