Zero Knowledge, Zero Problems: A zkOverview

Don’t ‘know’ anything about zero-knowledge proofs? After reading this post, you'll know how they work and what they're good for. But you'll also realize there's even more we do not know yet. 

Nothing to worry about; as the Greek philosopher Socrates put it, "The more I learn, the less I realize I know." 

When you spend time on CT (Crypto Twitter) these days, you will come across people who have an equally strong faith in the power of Zero Knowledge Proofs (ZKPs), as Socrates had in his ideas (he was sentenced to death for corrupting the youths - if we still dealt this way with people, Andrew Tate be long gone). 

Whenever a technology gets everyone across ecosystems excited, it's well worth investigating where that shared conviction comes from. So, let's start with when it all began. 

A little timeline 

Zero-Knowledge-Proofs are a cryptographic technology first introduced in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their paper "The Knowledge Complexity of Interactive Proof-Systems," making them older than 90% of crypto conference attendees. 

Their paper introduced a hierarchy of interactive proof systems and articulated how a proof could look like that allowed someone to prove something without revealing it. From then onwards, ZKPs remained in the realm of academia, where in the early 90s, researchers came up with the idea of succinct proofs. 

Without going into too much detail on succinct proofs yet, what's important about them is that they drastically reduce the proving time/ 

Or, as David Boneh, a Stanford professor of Computer Science, put it, "Succinctness is magic. There’s no good physical explanation for why it’s possible.”

In the 2010s, thanks to the broad availability of computers and increased funding for cryptographic research, ZKPs found their first applications in reality, most prominently in the crypto industry. 

In 2014, Zcash launched using zk-SNARKs, a type of ZKP,  to enable private transactions, and in 2020, filecoin went live on the mainnet with the largest deployed zk-SNARK to date. The network produces 6-7 million proofs daily to verify that nodes in its network store files as they claim. 

What exactly are ZKPs? 

In short, ZKPs are protocols between 2 parties: the verifier and the prover. The prover proves to the verifier that they own a piece of information without revealing it. 

There are a variety of scenarios researchers have thought of to bring this concept to real life. One famous example is that of a colorblind friend.

Imagine you have a colorblind friend, and you want to convince them that you can see colors. How would you go about that? The ZK researchers suggest that you need two balls, green and red. Then, you hand them to your friend, who switches them behind their back. 

They then show you the balls and ask if they switched them or not. You repeat this process until there is a proven high probability that you can see colors. Way to spend your time with friends. 

All Zero-Knowledge Proofs need to fulfill the following three criteria: 

• Zero Knowledge: the verifier can't access the original content. The only thing the verifier will learn about is the statement's validity. 
• Soundness: means that the protocol cannot validate any invalid input as accurate.
• Completeness: as long as the input is valid, the protocol will always validate it. 

Going back to the example of the colorblind friend, zero-knowledge would require that only you can find out, and your friend can't convince others that you can see colors. For example, even if you were to film the process, viewers would never know if they'd watch an honest display of your experiment or if it was scripted. 

Interactive vs. non-interactive proofs

The colorblind friend example is a so-called interactive proof, requiring interaction between the verifier and the prover. The verifier in such a proof sends random queries or challenges to the prover (in the example, asking if the balls had been shuffled) and repeats until they are convinced of the correctness (you not being color blind). 

Due to the back and forth between the verifier and prover, interactive proofs can be inefficient, especially if many verifiers are involved. In contrast, non-interactive proofs require no interaction at all and consist only of a prover providing a proving object. 

Most of the zero-knowledge proofs in use are non-interactive. 

Types of ZK-Proofs 

Currently, four different types of zero-knowledge proofs find application in crypto. 

zk-SNARKS
Is short for Zero-Knowledge Succinct Non-Interactive Argument and contains magic, according to Professor Boneh. It's the first non-interactive proving algorithm. This is enabled by the use of a shared key that establishes public parameters used to verify claims. The downside of this algorithm is that it requires a trusted setup ceremony during which the key is created. It's like a frathouse initiation ritual but by nerds who use things like pictures or lava lamps to generate random inputs. 

ZCash was the first to introduce zk-SNARKS to enable fully encrypted transactions, 

Bulletproofs 

La Roux once sang: 

I'm having fun; don't put me down
I'll never let you sweep me off my feet
This time, baby, I'll be bulletproof

Cryptographers, too, like to have fun. And when doing so, they sometimes develop new algorithms that avoid the trusted setup ceremony altogether. Because if we've learned anything from all the recent multi-sig exploits, people in crypto can't be trusted. 

Bulletproofs were introduced as non-interactive zero-knowledge proofs that are "Short like bullets, yet offering bulletproof security assumption." by a team or researchers. 

Designed with crypto in mind, their only issue is that verification takes longer than with SNARKs. And if there's one thing degens do not have, then it's patience. 

PLONK 
PLONKs were a breakthrough in creating efficient SNARKs. The acronym is short for permutations over Lagrange bases for oecumenical non-interactive arguments of knowledge, in other words, technical gibberish for Giga brains. 

Unlike zk-SNARKs, they do not require a shared string for each new use case but rely on one shared proof system that can be used for any type of computation. Aztec Network and Matter Labs are already relying on PLONKs. 

zk-STARKs
Just like Tony Stark in Iron Man, zk-STARKs are pretty powerful. Short for Zero-Knowledge Scalable Transparent Argument of Knowledge, this algorithm represents an updated version of previous zk algorithms, removing the need for trusted setups. On top of that, zk-STARKs are highly scalable thanks to requiring minimal interaction between the two parties. They are also the only current algorithm that is considered quantum secure and live in deployment on Starknet. 

What are all these ZKPs good for? 

Outside of crypto, there are various use cases for zero-knowledge proofs, such as allowing voters to prove they voted without revealing their choice or enabling companies to prove not being bankrupt without sharing all their balance sheets. ING even used zero-knowledge proofs to allow prospective borrowers to prove that they fall into a certain income bracket without sharing details of their salary. Nevertheless, ZKPs haven't taken off there yet. 

In crypto, however, we love to talk about three-letter acronyms. Existing Web3 use cases of ZKPs are centered around privacy, data validation, and scalability. 

Privacy

Currently, most public blockchains are pseudonymous, meaning that all data is publicly available, and even though it's not directly tied to your person, savvy researchers or spies like Arkham can still often tie the two together. ZKPs introduce a way to enable users to transact without any of the transactions being publicly available. In practice, this means no third party can see who you transferred to and what amount. For a taste of that, try Zcash or any other of the privacy coins.

And even though privacy is very high up the cypherpunk manifesto, it's not necessarily the aspect that has everyone so excited about ZKPs these days. Just look at Zcash's price performance... 

Data Validation

The second use case for ZKPs in crypto, and the one most tested, we'd like to argue, is data validation. While ZKPs can be used for privacy, they also serve as a verification for honest computation. This is quite useful in the context of projects that have to store data but do not want to re-compute it in its entirety. 

Take Filecoin; in the context of the storage network, clients that store files become provers who send ZKPs to the full nodes (verifiers) to ensure that data is stored, maintained and secured without any corruption. The bad news for filecoin hodlers is that few consider that a big deal, except for Arthur Hayes and Matti,

Similar to how Filecoin uses ZKPs, in Subsquid's architecture, ZKPs allow us to ensure that all on-chain data (for direct queries or indexing) is saved efficiently by nodes in our data lake. For more on our architecture, check out the whitepaper. 

And even though data validation is lit, it's not what makes a crypto degen's heart go faster. That's L2s with points zk attached for scale.  

Making batches of transactions small 

Blockchains themselves are pretty inefficient. Verification happens on multiple nodes, meaning the more traffic goes through a chain, the more computation takes place. Maintaining decentralization requires keeping hardware requirements low, but that is impossible with the current state of affairs: high demand for some chains driving high fees. 

To remedy expensive transaction costs and still enable scale, Layer-2s and rollups use sequencers that batch transactions off-chain (on the Layer-2) and then create a proof that verifies the validity of all transactions on the Layer-1. 

They circumvent the need to verify each individual transaction and only post compressed proof. Since the proofs aren't really about privacy but just to confirm the correct chain state, they are also often called validity proofs. 

zkEVMs

zkEVMs are a type of Layer Two that uses zero-knowledge proofs to create a proof of execution of Ethereum-like transactions. There are different types of zkEVMs, all making trade-offs between EVM compatibility and performance. For a trip down the zkEVM lane, check out this blog post by Vitalik. Anything that has zkEVM in their network name is an example of such an L2, in addition to Taiko and Scroll, who were more creative in their brand names. 

zkRollups 

zk Rollups follow a similar principle to zkEVMs, except they aren't all that fuzzed about achieving EVM compatibility, but they are more interested in simply enabling fast and cheap transactions. By moving computation off-chain, they increase scale and use zk Proofs to submit their state to Layer-1. Aztec Network is an example of a privacy-focused L2 using zkps, while Immutable X uses ZKPs simply to make it possible to build on-chain games without bankrupting the devs (and players). 

Yet, privacy and scalability are just one aspect of how ZKPs are expected to be used. An area still under-explored yet full of potential is interoperability. 

Interoperability 

There's probably no need to reiterate how much interoperability still s*cks these days. Try going from Astar Substrate to NEAR native coins, and you get the full package of high fees, going through multiple hoops, installing different wallets, and waiting times. 

A major challenge in interoperability between blockchains has been that all offer different security guarantees. Current solutions rely heavily on trusted systems like CEXs or, worse, 1/12 multisigs. By removing bridges, we'd not only remove the stress that comes with bridging but also rid North Korea of a big income source. 

ZKPs could aid in replacing the current trust assumptions with cryptographic guarantees by allowing different chains to verify their state easily, and the rights of users to spend funds on different chains.

Despite the potential, this remains the most nascent application of ZKPs. But as Polygon's AggLayer and the zkWASM research project suggest, there's first progress. Cosmos already boasts Interachain accounts where users can interact across chains with just one account, offering a glimpse into the future. 

We're still early 

All of this sounds great, but it's worth stating the obvious: even though zero-knowledge proofs have been around for 30 years, their application in crypto is still in its incipient stages. 

Challenges include: 

• Complexity makes it hard for devs to integrate them into existing systems 
• Scalability: even though one can aggregate proofs when millions or more proofs are required, computation needs increase significantly. And people already cry over the computational requirements of a Solana node. They should try running a ZK prover. Fortunately, with Hardware/acc, chances are that this will partly be solved by simple technological progress. 
• Need for trusted setups 
• Lack of interoperability between different zk systems. 

These are hard problems, but not impossible to overcome with some dedication and collaboration. 

"Nothing in the world is worth having or worth doing unless it means effort, pain, difficulty…" - Theodore Roosevelt 

The future is bright 

ZKPs can greatly contribute to easing user experience and enable seamless communication between protocols, similar to how SSL ensures people stay safe on the internet. They'll dissolve boundaries between web2 and Web3 to allow a greater share of humans and devices to benefit from Web3. As hardware accelerates and proofs become more efficient, they'll likely find their way into IoT devices. 

Statista estimates we'll use 30 billion IoT devices by 2030. Take note everyone wanting to bring Web3 to billions. You never specified you meant humans; it's not too late to change course. 

Web3 projects like Filecoin have already demonstrated the reliable use of ZKPs for verification of data storage. Similarly, at Subsquid, we're using ZKPs to verify that on-chain data is stored in our decentralized data lake for ease of access. 

In summary, the future of ZKPs x Web3 is bright. 


Subsquid docs | GitHub | Twitter | Developer Chat

Article by @Naomi_fromhh