Zero-Knowledge Proofs 🔒 for dummies

Before we delve into how ZKP works, let's first understand what it is through an example:

Example

Consider a cave similar to Alibaba cave, containing a magic door that requires a secret word to open it. The cave has two entrances A and B, both leading to the magic door.

Consider two persons, Alice (prover) and Bob (verifier) in the situation that Alice knows the secret words to open the magic door and Bob does not. Bob is curious to find out whether Alice knows the secret words or not.

Hence, a scheme is devised which allows Alice to prove that she knows the secret words without actually revealing them to Bob.

Bob waits outside the cave as Alice goes into the cave. Alice takes either path A or B. Bob is not allowed to see which path she takes. Then, Bob enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random.

Now two cases arise,

Case 1. Alice knows the secret words: She can return via the path specified even if it requires her to cross the gate, no problem.

Case 2. Alice doesn’t know the secret words: In this case, she can only return via the path she came in, if this is the path Bob chose earlier, then it is good, if not she is caught lying. So there is a 50% chance that she still can successfully claim that she knows the secret words, even though she doesn’t due to sheer luck.

50% is not good enough, so Alice and Bob repeat this exercise. With each iteration the chances of Alice not knowing the secret words and being able to claim that she does, decrease. After 20 iterations they become very low (one in a million)

At this point, Alice has successfully proved to Bob that she does possess the knowledge of secret words.

Definition

A Zero-Knowledge Proof is a form of cryptography/algorithm that enables one party in a transaction, the prover, to prove that they have knowledge of information that confirms a statement to be true to another party, the verifier, without revealing what that information is.

A zero-knowledge proof algorithm must contain the following 3 properties:

• Completeness - If a statement is correct, and the prover and verifier both follow the correct protocol, then the verifier should accept the proof as true.

• Soundness - If the statement is false, then the verifier will not be convinced by the proof even if they follow the protocol.

• Zero-Knowledge - If the protocol is followed by the prover and the statement is deemed to be correct, then the verifier should be convinced of the prover’s statement being true, even though they do not know any other information besides the provided proof.

Below is a cartoon, which was inspired by an excellent article by Christian Lundkvist and shows a particular type of ZKP called a zk-SNARK:

Applications of Zero Knowledge Proofs

Zero Knowledge proofs have a wide range of applications, but amongst them, here are a few popular ones.

1. Privacy in Blockchains: The transparency of Blockchains, though has a lot of advantages, as we could publicly verify transactions, but it also implies little privacy. With zero-knowledge proofs we could shield transactions on the blockchain, thereby making it possible to carry out private transactions, messaging etc. Examples of private blockchains or protocols are Zcash, Mina and Monero.

2. Blockchain Scalability: The Ethereum Blockchain, uses a Proof of Work model which although increases security in decentralized protocols, is very resource-intensive, and requires a great deal of computational power to function. With the advent of Zk-rollups, rather than process or compute each transaction that is made directly to the blockchain, we can now batch hundreds and thousands of transactions into one, with validity proof to verify the correctness of transactions and get them recorded on Ethereum in one go.

3. Authentication: Zero-knowledge proofs, are seeing massive adoptions in authentication protocols, as it provides a medium of authenticating users without the need for private information such as passwords, IDs etc.

4. Machine Learning: Zero-knowledge proofs are also seeing a lot of adoptions in machine learning, as it can allow the owner of an algorithm, to convince others about the results of their models, without revealing any information about the machine learning model itself.

Now before we even talk about what zkEVM is, let's first try to understand what EVM is.

EVM

A Zero-Knowledge Ethereum Virtual Machine is, as the name suggests, a virtual machine that generates zero-knowledge proofs to verify the correctness of the data, and by extension, the programs. They’re a layer on top of Ethereum; a ZK-rollup submits transaction data to Ethereum along with Zero-Knowledge Proofs verifying the validity of off-chain transaction batches.

What are ZK-rollups?

Very briefly, a roll-up performs transaction computations off-chain, but stores transaction data on-chain; creating two layers within the data. This is handled through smart contracts whose primary function is to bundle transaction data and transfer it off-chain for processing. This is then handled by the participants on the network, known as ‘validators’ or ‘sequencers’, who then submit batches of data containing the minimum information required to validate the transactions.

Here’s where ZK-rollups are different from their optimistic counterparts. ZK-rollups generate cryptographic proofs that are used to verify the validity of the transactions. Optimistic rollups, on the other hand, assume that all transactions are valid and perform no validity checks whatsoever.

zkEVM

To oversimplify, Ethereum Virtual Machine (EVM) is the mechanism through which Ethereum executes its transactions. The idea is that every blockchain needs a mechanism to ensure the transactions are valid because every transaction in every block means there’s a state change to the machine.

The idea with Ethereum was to have a global computer connected through individual nodes. EVM is that network. EVM is an environment where various activities happen within the ecosystem.

For a developer or user used to working within the Ethereum environment, improper state changes could, at the very least, cause headaches. It very well has the potential to make the application completely unusable.

The idea here is to scale the functionalities of Ethereum while retaining all of its functionalities, in a way that doesn’t harm the integrity of the environment. It’s a complicated problem, to say the very least.

Ideally, this means that the environment for the rollups should be as close to EVM as possible, however, there is a significantly positive correlation between incremental closeness to EVM and costs. This has been pointed out by Vitalik Buterin as well (summarized by Polygon) “‘The closer a zkEVM is to the EVM in its every detail, the more costly it will be to generate ZK proofs”

A zkEVM replicates the Ethereum environment as a rollup and allows the developers to build as though they were building on Ethereum. The idea is that the developers would not need to change their code or abandon their EVM tools while moving toward a rollup.

Vitalik Buterin has divided rollups into five types, in decreasing closeness to Ethereum:

Type 1 — zkEVMs: Fully Equivalent to Ethereum
zk-EVM Type 1s are to be fully equivalent to Ethereum, with practically no changes made to their state or transaction trees within their consensus. Type-1 zkEVMs are fully compatible with EVM, but require more time as no re-working is done to make proof generation faster.

Type 2 zkEVMs: EVM Equivalent
zkEVMs Type 2 aims to be ‘like’ Ethereum, in terms of having a native environment that is equivalent to EVM and not Ethereum. They look like Ethereum on the outside but their EVM has modifications to make the proof generation process faster.

Type 3 zkEVMs — Departure from Ethereum
Type 3 zkEVMs focus on the creation of EVM-like systems within zk-rollups. This means making specific changes to the EVM to make building applications easier and the proof generation process much faster. However, some applications built with native EVM chains might need some rewiring.

Type 4 zkEVMs — Derivative EVM
zkEVM Type — 4 would be functional with high-level languages, but not EVM itself. There are several layers to the process here, which is made efficient by skipping the process of providing zero-knowledge proofs for each stage of EVM execution.

Conclusion

zkEVMs are the latest in what is going to be a long line of blockchain complementary products. As mentioned before, one of the greatest problems that space faces as a whole is the fact that despite being decentralized, blockchain technology is not scalable.

Major investment firms have already started to realize the value of products like this. Scroll, Polygon and zkSync are currently in competition for launching their products.

What's Next!

Congratulations! Now you have all the fundamentals to help you get started with learning more about zkp and zkEVM. I'm super proud of you!

If you liked this article, make sure to check out my other articles on Hashnode. You're gonna love it, if you're a budding web3 developer, just like me!

Hi there, I'm Biswarghya Biswas! If you enjoyed this post, feel free to share. And make sure to follow me on Twitter and also connect on LinkedIn👋