The Zero Knowledge Frontier: On SNARKs, STARKs, and Future Applications

“I know one thing, and that is that I know nothing” – Socrates 

There has been a lot of palpable fervor lately surrounding L2 scaling solutions, and rightfully so. With Optimism releasing a governance token, demand for lower gas fees on ETH mainnet, and a litany of new ideas being produced at back-to-back hackathons, it’s safe to say that L2 2022 is in full swing. 

In today’s piece, I’ll be dissecting one of the most powerful, yet often misunderstood, cryptographic tools ever created: zero–knowledge proofs. In addition, I’ll be highlighting use cases and proposals for future implementation, as well as demonstrating why zk proofs hold a key to crypto’s future. 
This is a continuation of an ongoing series analyzing how blockchains can best scale to meet the needs of billions. If you are unfamiliar with rollups, I suggest this primer.

Simply put, a zk proof is a way for a prover to convince a verifier that something is true without actually revealing any information about it. Let’s illustrate this with an analogy: suppose we have two people, Alice and Bob. Alice has a sealed deck of 52 playing cards. Alice picks a red card in secret and wants to prove to Bob that she has a red card, without actually showing the red card. In order to do this, Alice will need to separate all the black cards from the deck and show them to Bob. Bob counts all 26 black cards, verifying their presence, and determines that the card Alice has must be red. Therefore, Alice was able to prove to Bob that she had the red card, without actually showing it. This analogy is extremely simplified and does not paint the full picture, but the core idea behind the tech remains the same. 

Zk proofs are not novel to this decade, or even to this millennia. In fact, the idea was first introduced in the 1980s by abstract mathematics researchers. This solution was developed to solve the problems relating to, at the time, theoretical systems between Provers and Verifiers – interactive proofs. 

But what if the Verifier turns out to be malicious? How much extra information is the Prover revealing, besides verifying the truthfulness of a statement? Let’s look at how hashed versions of passwords on centralized servers are stored. Traditionally, upon interacting with the server, the server would learn the cleartext password. This is an awful way to conduct ‘proof of identity’, so researchers turned to a system that proves a statement while revealing no extraneous information. 

More concretely, suppose we have some function C, with two inputs C(x,y). Let x be the public input, y be a secret witness, and let the output of the function be either true or false. Given a specific public input x, the prover must show that they know a secret witness y such that C(x,y) == true. From the prover’s perspective, randomness is necessary to realize zero knowledge. On the verifier side, randomness is needed to produce queries to the prover. The first application widely demonstrated was in the NP – complete class of complexities called the graph three – coloring problem. This was a huge breakthrough, as this application can be applied to any problem in the NP class. That’s like hitting 20 birds with one stone. 

In the blockchain space, there are many implementations of zk proofs because of its ability to provide scalability, as well as utility in privacy models. Specifically, the verifier performs exponentially less computational work than without a zk proof system. The prover, on the other hand, requires quite a bit of computational overhead needed to perform the proof. I’ll discuss this in detail later.

While there are a multitude of zk protocols that currently exist, for this piece I’m focusing on SNARKs and STARKs, with deep dives on other protocols to follow in later pieces.

Succinct Non-Interactive Arguments of Knowledge, or SNARK, is a popular proving mechanism that incorporates zero-knowledge proofs that was first introduced in 2011. Under the hood, zk-SNARKs use elliptic curves for security and rely on a trusted setup. Initially, keys are created to develop the proofs required for transactions and for verification of said proofs. These keys contain a reference string linking the verification key and the key sending private information. For this to work, it is vital that the method of creation of the key is deleted, and that the creator of the key is trustworthy (hence the term trusted setup). This reliance on trust in the creation stage remains a big point of criticism in zk-SNARKs. In addition, the reference string is non-upgradable, meaning that if the program needs to be updated, the trusted setup phase needs to be re-run.

In actual practice, however, zk-SNARKs are hard to implement on their own. There are a multitude of steps that need to be checked in a computation, but doing the work to check each step individually takes an unfeasible amount of time. The solution comes in the form of polynomials. Encoding the computation into polynomials saves a tremendous amount of information and time. Instead of having a boundless number of equations between numbers, we can substitute them with polynomial expressions that “stand in” for them.

But wait, there’s more! Typically, equations are verified with polynomials by checking each coefficient, but this again takes too long. Polynomial commitments come into play here. A Polynomial commitment can be viewed as a unique method of “hashing” a polynomial. This allows for verification in a much shorter time, regardless of how large the polynomial is. In addition, polynomial commitments are inherently privacy preserving, as the proof is much smaller than the polynomial itself. The polynomial commitment will not reveal more than a modicum of information from the polynomial, though randomness can be added. For a more mathematical dive into polynomial commitments and verification, check this out. 

Polynomial commitments use one of three major protocols: bulletproof, KZG, and FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Comparing and contrasting each will get a bit dense and beyond the scope of this current piece, as they each deserve their own deep dives.

Tired with the status quo, in 2018 a group of researchers sought to include transparency in zk systems. Transparency meant not having to rely on a trusted party for initial setup, which eliminated the threat of an open backdoor. This led to the creation of scalable transparent arguments of knowledge, or STARKs. STARKs use hash functions as their source of security, which differs from the bilinear implementation used by SNARKs. The scalable aspect of the name refers to two things: 

Though zk-SNARK pioneers like Zcash have been around for a while, the creation of zk STARKs ushered in an explosion of development in space. The work in zk protocols is not limited to rollups. In fact, some L1s have been built based on zk proofs, as well as budding gaming projects. 
StarkWare is a pioneer in zk-STARK, developing two core products: StarkNet, a permissionless decentralized zk rollup, and StarkEx, a standalone zk rollup SaaS. Additionally, StarkWare was the first producer of a production-grade zk virtual machine (zkVM) called Cairo. Cairo claims to have done this through implementation of a Turing complete Von Neumann architecture. Each program resides in the VM’s memory, alongside the data processed by it. Cairo can be accessed by anyone today, and is currently being used by prominent StarkEx clients like dydx, Immutable, and DeversiFi. Other novel applications using their own version of zkVM include Polygon Miden and RiscZero, the latter of which is attempting to build a general purpose zkVM.

Contrary to the bootstrapping zkVM ideology, are zkEVMs. zkVMs start from scratch as a new blockchain VM optimized for zk, or simply adapt Solidity tooling and compatibility. On the other hand, zkEVMs implement the full set of EVM opcodes. The usage of the EVM opcodes offers a few benefits:

Unsurprisingly, there seems to be a hard divide between the zkVM and zkEVM camps.

The biggest advantage zkEVMs have over zkVMs is the EVM equivalence. Targeting the massive existing dApp community through low gas fee incentives and an easy on-boarding experience for developers has historically proven fruitful, which is exactly what zkEVM builders are counting on. 
The most popular zkEVM project currently is zkSync, which uses zk-SNARKs to validate and scale as a layer 2 solution. In addition, zkSync has chosen to put data availability off-chain, and is secured using proof of stake (zkPorter) by zkSync token stakers (implying an airdrop might be imminent). The design of this implementation falls under a solution developed by StarkWare called Volition.

Finally, a rather newer player to the scene, Scroll is developing a general purpose L2 zkEVM. Scroll takes a new approach to generating zk proofs off-chain using GPU power. Recent breakthroughs in zk proofs like Poseidon hash, Plookup, and PLONK have brought the cost down enough to make zkEVM a reality. Additionally, advancements in GPU and ASIC/FPGA accelerators are improving hardware conditions, bringing the cost further down. Scroll is still in its development phase, with plans on debuting their zkEVM testnet within the coming months.

Zk proofs were initially developed with the idea of maintaining privacy. Though popular media may focus current use cases on ‘greater allowance of TPS’, the fact remains that zk proofs have a much wider range of applications. 
One such application is a tool that verifies the identity of users by checking assets in wallet or on-chain transactions anonymously via zk circuitry.

Zk identities have the potential to be extremely powerful, and use cases are immediately available in the real world. For instance, suppose I am a debtor who is trying to prove his creditworthiness while still keeping banking information and activity private. I would show that I’ve paid off large loans from multiple trusted banks, but will not reveal the banks or the specifications of those loans.

Another big development in the zk area is efficient private delegation of zk-SNARK provers. As stated earlier, time to prove is quite slow. Hashing 10kb with SHA2 takes 140 seconds, instead of the desired few milliseconds. A solution to this would be to outsource the proving. Unfortunately, this brings up another dilemma: secrets are invariably leaked to the workers. What is needed: outsourcing proving with privacy. Through careful implementation, it is possible to delegate proving to a device like a mobile phone with 26x faster speeds than computing locally. This novel framework was first presented at the zkSummit in April 2022 by Pratyush Mishra. 

We are very early in the development of application based zk proofs. Nevertheless, the pace of progress has been rapid. Stages that expert researchers thought would not be reached in 5 years have already come to fruition. That said, there’s still a lot to accomplish. There is still a lot of strife between development communities, as camps are being formed and opinions are being politicized. Only time will tell which party is right. What is certain is that, when historians look back, they will see this period of zk implementations as the seminal part in the spectacular history of cryptocurrency. 

This report is for informational purposes only and is not investment or trading advice. The views and opinions expressed in this report are exclusively those of the author, and do not necessarily reflect the views or positions of The TIE Inc. The Author may be holding the cryptocurrencies or using the strategies mentioned in this report. You are fully responsible for any decisions you make; the TIE Inc. is not liable for any loss or damage caused by reliance on information provided. For investment advice, please consult a registered investment advisor.