eth 2.0 layer-2 scalability zero knowledge proof zk-rollups zk-snarks

Breaking Down ETH 2.0 - zk-SNARKS and zk-Rollups

Image Source: Przemysław Thomann

Ethereum 2.0 will trigger a seismic shift in the crypto space. Some of the changes that this upgrade is going to trigger are:

• The transition to Casper protocol
• Sharding
• Raiden state channels
• Plasma

Raiden and Plasma are layer-2 protocols that allow Ethereum to conduct thousands of transactions off-chain in the form of state channels and side chains. Plasma, in particular, can theoretically allow a side chain to process thousands of transactions and commit just one single hash to the main Ethereum blockchain. While this sounds pretty amazing on paper, there is a significant problem here. If there is some dispute in one of these side plasma chains, there isn’t a proper mechanism that the users can use to exit the protocol efficiently.

Achieving layer-2 scalability and availability with zk-Rollups

This is where a technique called “ZK-Rollups” comes in. With the smart integration of zk-SNARKS, a privacy protocol, it will be possible for ETH 2.0 to create an immensely scalable layer-2, which still has the security and data availability that’s expected of Ethereum.

However, before we get into that, let’s first understand what is zk-SNARKS and zero-knowledge proofs..

NOTE: We highly recommend that you read our article on Raiden and Plasma before continuing on here.

Zk-SNARKS: What are Zero-Knowledge Proofs?

zk-SNARKS is the privacy cryptography protocol made famous by Zcash - a privacy coin. At its core lies the concept of zero-knowledge proofs or ZKPs. To understand how it works, let’s at the two parties involved in a proof – Prover and Verifier.

• Prover: Wants to prove a hypothesis.
• Verifier: Wants to judge the Prover’s honesty.

The core idea behind ZKP is this - Prove that you own a specific piece of knowledge without actually revealing what it is. Eg. Proving that you are above a certain age limit by just showing the last two digits of your birth year. In its essence, the ZKP asks the two following questions:

• Question the morality of the Verifier instead of the Prover.
• How can the Prover maintain the confidentiality of their knowledge without exposing it to the Verifier?

Zk-SNARKS Explained - Examples of Zero-Knowledge Proofs

A ZKP has the following properties:

• Completeness: A statement is true if an honest prover can convince an honest verifier.
• Soundness: If the prover is dishonest, they can’t fool the verifier.
• Zero-knowledge: The verifier will not know what the statement actually is.   

Let’s look at some examples.

#1 Color blindness and Apples

Look at the following diagram to understand how normal vision works and how color blind vision.

In our hypothetical scenario, the prover has normal vision and the verifier has color blindness. The former has two apples - red and green. The verifier thinks that both the apples are of the same color and the prover wants to disprove this without explicitly telling them what the colors are.

This is how it works:

• The verifier shows the apples to the prover.
• He then hides his hands behind the prover and switches the apples or keeps them as is.
• Now he reveals the prover his hands again.
• If the verifier has made the switch, the prover will be able to point it out instantly. This proves that the apples are of different colors.

The verifier can repeat the test multiple times to make sure that the result wasn’t a fluke. Let’s look at how this verifies the ZKP properties.

• Completeness: Since the prover was honest, they were able to give the correct answer multiple times.
• Soundness: The verifier conducted the test multiple times to make sure that the results were fluke-free.
• Zero-Knowledge: The prover never revealed the apples’ colors.

#2 Alibaba’s Cave

Up next, we have one of the most famous ZKP examples in theoretical cryptography.

In this case, we have a prover (P), a verifier (V), and a cave with a magical door at the back. P says that he knows the secret password that opens up this magical door. So, how does P prove to V that they know the password without disclosing what it is?

•  P goes down path A or B and reaches the secret door.
• At this point, P calls out to V, who enters the cave.
• V tells P to come down path B. If P really does know the passphrase, he won’t have any problem coming down any of the paths.
• V repeats the experiment multiple times to make sure that they are not getting duped.
• If P is honest, they shouldn’t have a problem coming down any of the paths.

How are the three properties of zero-knowledge satisfied?

• Completeness: Since the prover was honest, they were able to give the correct answer multiple times.
• Soundness: The verifier conducted the test multiple times to make sure that the results were fluke-free.

 

• Zero-Knowledge: P didn’t have to reveal what the passphrase actually was.

 

What is Zk-SNARKS – Making ZKP non-interactive

One of the main problems with the traditional ZKP is that it's a highly interactive system. In both the examples that we have shown you above (Alibaba’s Cave and Apples), you require both the prover and verifier to be present simultaneously. As you can imagine, this isn’t a scalable technique. In 1986, the Fiat-Shamir heuristic showed how this could work with discrete logarithms. We will see both the interactive and the non-interactive version.

Interactive

• Prover P wants to show Verifier V that she knows x, such that y= g^x to the base g.
• P takes a value v from set Z and computes t such that, t = g^v. She then sends over t to V.
• V then takes up a random value c from the same set Z and sends it over to P.
• P calculates a value r = v-c^x and sends it over to V.
• Now, since r= v-c*x, y= g^x and by simple substitution, g^(v-c*x)* g ^ c*x = g^v = t.
• So, V will check g^r * y^c and see if it’s “t” or not.
• Hence, without explicitly knowing the value of “x,” V can still check if t = g^r * y^c, or not.
• As such, V will be able to tell if P is being truthful about owning the secret information or not.

The above exchange satisfies the ZKP properties, but it still requires both Alice and Bob to be present simultaneously.

Non-Interactive

So, how do we make ZKPs non-interactive? With cryptographic hash functions!

• Prover P wants to show Verifier V that she knows x, such that y= g^x to the base g.
• P takes a value v from set Z and computes t such that, t = g^v. She then sends over t to V.
• P computes a value c = H(g,y,t) where H() is a hash function.
• Finally, P calculates r = v - c*x and sends this to V.
• Whenever V comes online, they can check if t = g^r * y^c, or not. 

This interaction is also completely zero-knowledge, but it didn’t require both the Prover and the Verifier to be present at the same time. This innovation was fundamental in the creation of zk-SNARKS.

Speaking of which….

What is zk-SNARKs?

Zk-SNARKS stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.” Now that we know how the theory works with ZKPs let’s get it all into an algorithmic formation.

In our typical zk-SNARK, we have three unique algorithms:

• Prover (P): This algorithm takes in three terms as inputs – proving key (pk), a random input (x), and the statement (w) that they want to prove. This algorithm takes in these inputs and gives a proof of statement prf.
• Verifier (V): Takes in the prf from the P algorithm and returns TRUE if valid or FALSE if not. Along with the prf, this algorithm takes in two more values - the random input “x” and verifying key “vk.”
• Key Generator (G): Taken in a secret “Lambda” value and a program “C” to generate pk and vk. The lambda value has to be kept private and confidential. If someone gets their hands on this value, they can use it to generate proving and verifying keys. They can use this to build counterfeit proofs, at will. 

Zk-SNARKs explained - Bringing the algorithms together

The program C takes in the prover’s secret statement “w” and the value x and does the following function:

So, let’s see how we can bring in all this together along with the algorithms and values we have declared in the section above.

• The verifier uses generator G to create the proving and verifying keys.
• The verifier puts in a secret lambda value to generate these keys such that G(C, lambda) = (pk, vk).
• The prover must now take the pk and prove the validity of their statement by creating a proof-of-statement prf, such that prf = P(pk, x, w). Over here, x is the SHA-256 hash of w.
• Prover sends over prf to the Verifier, who validates the claim by running their verifying algorithm, such as V(vk, x, prf).
• V returns TRUE if Prover is honest. Otherwise, it returns FALSE.

Alright, so now with zk-SNARKS explained, let’s get started with zk-Rollups.

ZK-Rollups - An Introduction

Before we proceed, let’s understand what a rollup actually means. Quite similar to Plasma, a Rollup is a layer-2 scaling solution where every single contract holds a succinct cryptographic commitment of a larger sidechain state. Users maintain these states without putting additional stress to the layer-1, aka, the base blockchain layer. Ethereum co-founder believes that rollups will be the best way to bring in layer-2 functionality to Ethereum 2.0 since it mitigates Plasma’s most significant problem - data availability.

Plasma and data availability

To give you a brief overview, plasma restructures the Ethereum blockchain like this:

The idea is to use Ethereum as the primary root chain, while several plasma chains are sprouting out of it. The root chain remains devoid of activity, while it delegates complex calculations and functions to these plasma chains.

While it's a good idea on paper, it has one huge flaw – data availability.

Imagine this situation.

Alice has 1 ETH in Plasma block 3, but she doesn’t see it anymore in block 4. This obviously means that plasma block 4’s validator is working maliciously. She immediately raises a dispute and sends a fraud-proof to the root chain, which checks if there is any validity to her claim or not. If yes, it rolls back the data in plasma block 4 and makes it invalid.

Do you see the problem here?

There is a considerable availability problem here. The system is held hostage for a brief period by the malicious owner of plasma block 4. In a zk-Rollup system, the plasma block will only contain the ZK proofs of the data and not the actual data itself.

Apart from this, zk-Rollups increases scalability by bundling hundreds of transfers into one single transaction. Its smart contract can disintegrate these transfers and verify all of them in one transaction.

Zk-Rollups Overview

A zk-Rollup scheme has two users - Transactors and Relayers.

Transactors

They create and broadcast transfers to the whole network. This transferred data includes – an indexed “to” and “from” address, a transaction value, the network fees, and nonce. 

• The addresses are stored in a shortened 3 bytes indexed version. This reduces the processing power required to handle these addresses.
• The transaction is either greater or less than zero, signifying whether it is a deposit or a withdrawal.
• The zk-Rollup smart contract has two Merkle Trees – one for addresses and the other for transfer amounts.

Relayers

While the transactors are in charge of transacting and broadcasting, the relayers have two major roles:

• Collecting a large amount of transfers and creating a rollup.
• Generate the SNARK proof, which represents the blockchain state. This proof compares a snapshot of the blockchain before and after the transfers. It only reports back something if there have been any changes in the underlying state.

Anyone can become a relayer as long as they have a stake locked up in the Rollup contract. This makes sure that they have enough incentive to work in the interest of the network.

Zk-Rollups – The numbers involved

Matter Labs have been working on and documenting various zk-Rollups implementations. As per their tests, this is what they discovered.

• Currently, the cost of public data per transfer transaction in the Matter testnet is 16 bytes.
• In the post-Istanbul Ethereum, this will cost around 272 gas.
• In the worst-case scenario where the overall proof cost can go up to 1M, zk-rollups can still do over 2000 transactions per second. For comparison’s sake, Ethereum currently can only do 25 transactions per second at more, while Visa does around 1667 transactions per second.
• Zk-Rollups can offer more efficient calculations when dealing with large data sets. The reason being, users will just need to deal with the SNARKs and not the data itself.

Pros and Cons of zk-Rollups

Pros

• Significantly faster than Plasma.
• Gas cost per data transfer is significantly low.
• It allows for the parallel computation of the blocks, which helps in scalability and decentralization.
• Each transaction only contains the SNARK proofs instead of the whole data itself, which again boosts scalability.

Cons

• Zero-knowledge proof computation is a very resource-intensive process.
• The initial setup of Zk-Rollups can be a little centralized in nature.
• The overall security of the system is dependent on a certain level of trust.

NOTE: Matter Labs noted that the resources required to build smart contracts on ZKPs had reduced considerably. Rollups contracts follow the same principles and models as EVM (Ethereum Virtual Machine).

ZK-Rollups Alternative: Optimistic Rollup

Optimistic Rollup (OR) is an alternative to the standard ZK-Rollup that removes the need for zero-knowledge proofs altogether. Instead of verifying and checking each transaction, the network assumes that they are all correct and allows user-intervention only if someone reports an incorrect transaction by submitting a fraud-proof. While the initial overhead for OR maybe lesser than zk-Rollups, it requires the users to publish the complete transaction input set every single time. On the other hand, zk-Rollups is a lot more flexible.

Ethereum co-founder, Vitalik Buterin, is extremely intrigued with both of the solutions, calling them “amazing.” He noted that both the Rollups could allow Ethereum 2.0 to scale up payments while providing the security and availability that’s expected of Ethereum.

Zk-Rollups and zk-SNARKS Explained: Conclusion

The best thing about zk-Rollups is that it's not just a theoretical concept. Loopring recently launched a zk-Rollup exchange has already managed to do 2,500 transactions per second. The Ethereum developers are pretty confident that they can reach a throughput of up to 2,500-10,000 if they combine rollups with sharding.

However, this still requires a lot of work before complete implementation. As of now, the team is making steady progress. 
We hope that you now have a better idea of what is zk-SNARKS and zk-Rollups. Do you want to know more about Ethereum and smart contract coding? Want to prepare yourself before Ethereum 2.0 launches? Check out our blockchain courses to find a repository of highly valuable educational blockchain material that will give you a significant edge in the job market.