Unlocking Zero Knowledge Proofs: From Beginner to Advanced
Tags: security, blockchain, algorithms, computerscience
Published: 2023-04-09 11:40:36

> Zero Knowledge Proof(zkp): Where Proof Meets Privacy, and Trust Meets Efficiency.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rk0x1m3u5wkfm2i2es2s.png)

Imagine There is a lock, and you want to prove to a verifier that you have the keys to that lock. You ask the verifier to give you the lock and then you go into a dark room where the verifier cannot see what you're doing. Inside the dark room, you use the keys to open the lock, put a ring inside, and then lock it back. Finally, you send the locked lock with the ring inside back to the verifier. This way, the verifier can be sure that you have the keys to that lock, as you were able to open and lock it in the dark room without revealing the keys or the ring to the verifier. This is a simple analogy that illustrates the concept of Zero Knowledge Proofs, where you can prove ownership or knowledge of something without revealing the actual information.

**Mathematics behind Interactive zk proof.**

The discrete logarithm problem (DLP) is a commonly used mathematical problem in interactive zero-knowledge proofs (ZKPs). Here's a simplified description of how DLP is used in an interactive ZKP:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lo2rlnagpyt2vgj74k58.png)

**Statement:** The prover wants to prove possession of a secret value x, such that

> y = g^x mod p

where g is a known generator of a cyclic group of order p, and y is a known value.

**Challenge-Response Phase:**

The verifier challenges the prover with a randomly chosen value, typically represented as c.
The prover responds with a new value, typically represented as r, computed using the initial statement, the challenge c, and some random values. The response is computed as

>z = (x + cr) mod (p-1).

**Verification Phase:**

The verifier checks if the response z satisfies the equation
 
> y^c * g^r mod p = g^z mod p.

If the equation is satisfied, the verifier is convinced that the prover possesses the knowledge of the secret value x as claimed in the statement.
Iterative Process: If the verifier is not satisfied, the challenge-response phase can be repeated multiple times to increase the security of the proof.

The DLP is used in the challenge-response phase to create a response value that is computationally difficult for anyone else, including the verifier, to compute without knowing the secret value x. The verification phase then checks if the response value satisfies the equation based on the initial statement, challenge, and response. This ensures that the prover possesses the knowledge of the secret value x without revealing it to the verifier, making it a powerful technique for constructing interactive zero-knowledge proofs.

However, this method can be inefficient as it requires multiple interactions between the verifier and the prover. Fortunately, there are more efficient ZKP techniques, such as non-interactive Zero Knowledge Proofs (NIZKPs), where the prover can generate a proof without needing additional interactions with the verifier. This allows for more streamlined and efficient proofs of knowledge while maintaining the confidentiality of sensitive information.

## Introduction to zkSNARK(zero knowledge Succinct Non-Interactive Arguments of Knowledge

> Interactive ZK proofs are like a conversation, where the prover and verifier exchange information and interact multiple times. Non-interactive ZK proofs are like a monologue, where the prover shares a single proof that the verifier can verify without further interaction.

Asymmetric key cryptography underpins zkSNARK by providing the foundation for generating and verifying proofs. It involves a pair of keys - public and private - used by the prover and verifier to generate and verify SNARK proofs, similar to how digital signatures are used in asymmetric key cryptography for authenticity verification of messages.

Now here is a breakdown of SNARK.

**Succinct:** The proof generated by SNARK is short and concise, requiring minimal computational resources to verify.

**Non-Interactive:** The proof can be verified without further interaction with the prover, making it efficient and suitable for various applications.

**Argument:** The proof is a mathematical argument that attests to the validity of a statement, without revealing any underlying data.

**Knowledge:** The proof demonstrates that the prover possesses certain information or knowledge, without disclosing the details of that information.

## Let's understand the workflow of SNARKS

It consists of 3 algorithms:

**1)Generate the proving and verifying keys (Setup)**

The Setup algorithm generates two keys: the proving key (“pk”) and verification key (“vk”).

> (pk,vk) = setup(circuit(C), secret(λ))

In the context of zkSNARKs, a "circuit" refers to a specific computation that is represented in a formalized way using logical gates, similar to how a digital circuit is represented using gates like AND, OR, and NOT. The circuit defines the behavior of the computation that we want to prove knowledge of without revealing any secrets.

A trusted ceremony is a process in which a group of trusted individuals or entities collaboratively generate the initial parameters for a zkSNARK system in a secure and controlled environment. The parameters generated ("Secret")i n the trusted ceremony are used to create the proving key and verification key, which are used for generating and verifying proofs in zkSNARKs.

**2)Proof Generation (π) **
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.

Witness "w" is the secret you as a prover know and not reveal it to the verifier and public value "x" is used to verify the proof(π) generated with the witness.

proof = Prove(pk,x,w)

**3)verify **
The verify algorithm takes in the proof, the public value "x" and the verification key(vk) and return true or false.

> V(vk, x, π) = true

If the equation is true, then the proof is valid, and the verifier is convinced that the prover possesses the knowledge of the secret witness "w" without revealing it.

This is a very high level overview of zkSNARK.

## There are several real-world applications that utilize zkSNARK

**Cryptocurrencies:** zkSNARKs are used in some blockchain protocols, such as Zcash and Horizen, to provide private and anonymous transactions without revealing the sender, receiver, or transaction amount.

**Identity and Access Management:** zkSNARKs can be used for secure and privacy-preserving identity verification, authentication, and access control, allowing users to prove their identity without revealing any personal information.

_In conclusion, zkSNARKs unlock the power of zero-knowledge proofs, allowing for secure and private interactions in various fields, from cryptocurrencies to supply chain management, healthcare to voting systems, and beyond. With zkSNARKs, secrets can be proven without revealing them, unlocking new possibilities for privacy-enhancing technologies. So, let's embrace the magic of zero-knowledge proofs and step into a world where trust is preserved, privacy is respected, and security is paramount. It's time to unlock the secrets with zkSNARKs and pave the way for a more secure and private future!_