0.9 ZKP and zkSNARK

Up until here in the course, all the blockchain we presented relied on the whole data of the ledger being public and accessible to anyone. It allows enforcing integrity of the data, enabling anyone to audit the blockchain and double check that every transaction is correct.

Modern cryptographic technologies allow to envision a different way, using methods allowing users to prove statements about their data without revealing the data itself. This need for privacy-preserving proofs is where Zero-Knowledge Proofs (ZKPs) come into play.

Zero-Knowledge Proofs allow one party, the prover, to convince another party, the verifier, that a certain statement is true without revealing any additional information beyond the validity of the statement. The theoretical foundation of ZKPs relies on three core properties:

1. Completeness: If the statement is true and both parties follow the protocol honestly, the verifier will be convinced.

2. Soundness: If the statement is false, no dishonest prover can convince the verifier that it is true, except with some small probability.

3. Zero-Knowledge: If the statement is true, the verifier learns nothing other than the fact that the statement is true.

Interactive proofs

To understand how these proofs operate in practice, let's look at Interactive Proofs (IP). An interactive proof system involves multiple rounds of communication between the prover and verifier. In each round, the verifier sends a challenge to the prover, who responds with evidence supporting the claim. The process continues until the verifier is satisfied with the provided evidence.

Example:

Let's see how a prover can show to a verifier he knows a $x\in \mathbb{N}$ such that: $y=x^2\ (\text{mod }n)$

Protocol

Proof protocol would consist of multiple rounds. Here is how a single round of proving would go:

1. Prover chooses a random $r\in [1,n]$ such that $gcd(r,n)=1$.

2. Prover sends $s=r^2\ (\text{mod }n)$ to V.

3. Verifier flips a coin, choosing a random $b\in \{0,1\}$, and sends $b$ to Prover.

4. Prover computes $z=rx^b\ (\text{mod }n)$, (which he can because he knows $x$ ) and sends it to Verifier. Meaning that, depending on the coin flip: $z=rx$ or $z=r\ (\text{mod }n)$.

5. Verifier then computes $sy^b\ (\text{mod }n)$ and checks if it is equal to $z^2$.

This protocol is repeated for K consecutive rounds, if for every round the verifier's equality check is valid, then the verifiers accepts the proof.

Completeness

If both parties are honest, and execute the protocol correctly, then for every round: $y=x^2\ (\text{mod }n) \implies sy^b = r^2x^{2b}=(rx^b)^2=z^2\ (\text{mod }n)$.

Therefore, if both parties are honest, execute the protocol correctly and the statement is true, then the verifier will accept all K rounds, hence the final proof. And this is exaclty how completeness is defined above.

Soundness

If a malicious prover doesn't have a valid $x$ satisfying the statement, let's find out what would be his possibilities to try to cheat the protocol.

During a single round, instead of generating a random $r\in [1,n]$, the malicious prover could dishonestly send a specific value as $s$, then depending on $b$, a malicious $z$, that would enable him to pass verifier's ultimate check: $sy^b = z^2\ (\text{mod }n)$.

• Case $b=0$: The final check would then be $s = z^2\ (\text{mod }n)$. Hence, to cheat the verifier in case he knows $b$ will be 0, the prover would have to chose any $r\in [1,n]$, send at step 1 $s=r^2$, and at step 4 $z=r$.

• Case $b=1$: The final check would then be $sy = z^2\ (\text{mod }n)$. Hence, to cheat the verifier in case he knows $b$ will be 1, the prover would have to chose any $r\in [1,n]$, send at step 1 $s=r^2y^{-1}$, and at step 4 $z=r$.

But since the prover doesn't know in advance $b$, in particular before sending a value for $s$ at step 2, he can only prepare cheating for one of those two cases. He can either chose to:

• Send $s=r^2$

  • Then if $b=0$, the prover can cheat the verifier by sending $z=r$.

  • But if $b=1$, the verifier will compute for final check $sy^b = sy=r^2y\ (\text{mod }n)$ and compare it to $z^2$. So to cheat him, the prover would have to send $z$ such that $z^2=r^2y=r^2x^2=(rx)^2$. Hence necessarily, $z=rx\ (\text{mod }n)$, which the prover could only compute by knowing $x$ itself.

• Send $s=r^2y^{-1}$

  • Then if $b=1$, the prover can cheat the verifier by sending $z=r$.

  • But if $b=0$, the verifier will compute for final check $sy^b = s=r^2y^{-1}\ (\text{mod }n)$ and compare it to $z^2$. So to cheat him, the prover would have to send $z$ such that $z^2=r^2y^{-1}=r^2(x^2)^{-1}=(rx^{-1})^2$. Hence necessarily, $z=rx^{-1}\ (\text{mod }n)$, which the prover could only compute by knowing $x^{-1}$, and therefore $x$ itself.

Hence, in any case, if the verifiers draws $b\in\{0,1\}$ uniformly, after sending one of these two $s$ value, the prover would only have a probability $p=\frac{1}{2}$ of successfully cheating the verifier during a single round.

Therefore the probability of cheating the verifier for K consecutive rounds would be $\frac{1}{2^k}$. This means that by choosing a high enough amount of rounds K, the verifier can ensure with a probability as closed to 1 as he wants that the prover is not cheating, since $\lim_k (1-\frac{1}{2^k})=1$.

Zero knowledge

By choosing a uniformly random value $r\in[1,n]$, a prover does not disclose any information about $x$ by sending, $r^2$, $rx$ nor $r$ which are the only values disclosed if the protocol is correctly executed by the prover.

Non-Interactive proofs

The problem with non-interactive proof is there lack practicality, in particular in a blockchain environment, where constant back-and-forth communication is infeasible as we cannot expect every users to remain live during proofs. It also causes a communication overhead which can be a bottleneck for scaling. Fortunately, a prominent class of zero-knowledge proofs, known as zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge), transforms the interactive process into a non-interactive one.

Usually turning an interactive proof protocol into a non-interactive one is done using a technique called Fiat-Shamir transform. The idea behind it is to make the prover to simulate the behavior of the verifier by generating challenges that are proven to be random, for instance by using a hash function to generate the challenges, with the data of the statement along with other data generated during a

A zk-SNARK consists of three key phases:

1. Setup: A trusted setup phase generates public parameters used for both proving and verification. This phase often involves complex cryptographic operations, including elliptic curve pairings.

2. Proving: The prover uses these public parameters and a private witness (the secret data) to generate a proof. This proof convinces the verifier of the statement's validity without revealing the witness.

3. Verification: The verifier, using the proof and the public parameters, checks the proof's validity in a computationally efficient manner.

The mathematical backbone of zk-SNARKs relies on quadratic arithmetic programs (QAPs), which encode the computation as a set of polynomial equations. These equations are then transformed into cryptographic commitments using homomorphic properties, ensuring that operations on encrypted data correspond to operations on the plaintext.

Consider a function f that we want to prove has a certain output y without revealing x. The prover constructs a polynomial that represents the computation of f(x)=y. Through a series of cryptographic transformations, this polynomial is committed to in a way that the verifier can check the correctness of y without gaining any information about x.

The succinctness of zk-SNARKs is another important feature. The proof size and verification time are both significantly smaller compared to traditional proof systems, making them ideal for applications with resource constraints, such as smart contracts on blockchains.

The implementation of zk-SNARKs also involves elliptic curve cryptography, particularly pairing-friendly curves like BN254. These curves support efficient bilinear pairings, which are critical for the construction of zk-SNARK proofs.

One real-world application of zk-SNARKs is in privacy-focused cryptocurrencies like Zcash. In Zcash, zk-SNARKs enable shielded transactions where the sender, receiver, and transaction amount remain confidential while still ensuring the transaction's validity and preventing double-spending.