Golden Outpost | Zero Knowledge Frontier: About SNARK, STARK and Future Applications

Source: Vaish Puri @TheTieLabs

"I know only one thing, and that is that I know nothing" - Socrates

There's been a lot of palpable enthusiasm around L2 scaling solutions lately, and rightfully so. With the release of Optimism's governance token, the need for lower gas fees on the ETH mainnet, and a flurry of new ideas being generated in back-to-back hackathons, it's safe to say that L2 is in full swing in 2022.

In today's post, I'll dissect one of the most powerful yet often misunderstood encryption tools ever created: zero-knowledge proofs. Additionally, I will highlight use cases and recommendations for future implementations and show why zero-knowledge proofs are key to the future of crypto.

Why Zero-Knowledge Proofs Are Important

Simply put, a zero-knowledge proof is a way for a prover to convince a verifier that something is true without actually revealing any information. 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 sneaks a red card, trying to prove to Bob that she has a red card, but doesn't actually show it. In order to do this, Alice needs to separate all the black cards from the pile and show them to Bob. Bob counts all 26 black cards, verifies their existence, and determines that the card owned by Alice must be red. Therefore, Alice is able to prove to Bob that she has a red card without actually showing it. This metaphor is very simplified and doesn't paint the full picture, but the core idea behind the technology remains the same.

Zero-knowledge proofs are not new for this decade or even millennia. In fact, the idea was first proposed by abstract mathematics researchers in the 1980s. The solution was to solve a problem at the time associated with theoretical systems between provers and verifiers - interactive proofs.

But what if the verifier turns out to be malicious? How much additional information did Prover reveal beyond verifying the truth of the statement? Let's see how hashes of passwords are stored on centralized servers. Traditionally, when interacting with a server, the server gets the password in clear text. That's a poor way to do "proof of identity," so the researchers turned to a system that can prove claims without revealing any extraneous information.

More specifically, suppose we have some function C with two inputs C(x,y). Let x be the public input, y be the secret witness, and let the output of the function be true or false. Given a particular public input x, the prover must prove that they know a secret witness y such that C(x,y) == true. From the perspective of the prover, achieving zero knowledge requires randomness. On the verifier side, randomness is needed to generate queries to the prover. The first widely demonstrated application was in NP - completing a class of complexity called three-coloring problems of graphs. This was a huge breakthrough because this application can be applied to any problem in the NP class. This can serve multiple purposes.

In the blockchain space, there are many implementations of zero-knowledge proofs due to their ability to provide scalability as well as their utility in privacy models. Specifically, verifiers perform exponentially less computational work than would be the case without a zero-knowledge proof system. On the other hand, the prover requires considerable computational overhead to perform the proof. I'll discuss this in more detail later.

ZK protocol

While a plethora of zk protocols currently exist, for this post I will focus on SNARKs and STARKs, and dig into other protocols in later posts.

Succinct Non-Interactive Argument of Knowledge (SNARK) is a popular proof mechanism that incorporates zero-knowledge proofs first introduced in 2011. Under the hood, zk-SNARKs use elliptic curves for security and rely on trusted settings. Initially, keys are created to develop the proofs needed for transactions and to verify said proofs. These keys contain a reference string linking the authentication key and the key for sending private messages. To do this, the method of creating the key must be removed, and the creator of the key is trusted (hence the name trusted setup). This reliance on trust during the creation phase remains a major criticism of zk-SNARKs. Also, reference strings are not upgradable, which means that if the program needs to be updated, the trusted setup phase needs to be re-run.

However, in real practice, zk-SNARKs are difficult to implement on their own. There are many steps to examine in a calculation, but it is not feasible to examine the time spent on the work of each step individually. The solution comes in the form of a polynomial. Coding calculations as polynomials can save a lot of information and time. Instead of having an infinite number of equations between the numbers, we can replace them with polynomial expressions that "replace" them.

But wait, there's more! Usually, polynomials are used to verify equations by checking each coefficient, but again this takes too long. Polynomial commitments come into play here. Polynomial commitments can be thought of as a unique way to "hash" polynomials. This allows verification in less time, no matter how large the polynomial is. Furthermore, polynomial commitments are inherently privacy-preserving because the proof is much smaller than the polynomial itself. Although randomness can be added, polynomial promises do not reveal a small amount of information about polynomials.

Polynomial commitments use one of three main protocols: bulletproof, KZG, and FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Comparing and contrasting them is beyond the scope of this article, as each deserves an in-depth study on its own.

In 2018, a group of researchers attempted to add transparency to zk systems. Transparency means not having to rely on trusted parties for initial setup, eliminating the threat of opening backdoors. This leads to the creation of scalable transparent arguments of knowledge, or STARKs. STARK uses a hash function as its source of security, which is different from the bilinear implementation used by SNARK. The scalability aspect refers to two things:

1. Compared with SNARK, the running time of the prover is much smaller in complexity.

2. The size of the verification time is multi-logarithmic. STARKs use FRI to improve information storage capacity and performance.

current application

While zk-SNARK pioneers like Zcash have been around for a while, the creation of zk-STARKs has exploded. Work in the zk protocol is not limited to Rollup. In fact, some L1s are already built on top of zk proofs, as well as budding gaming projects.

StarkWare is the pioneer of zk-STARK, developing two core products: StarkNet, a permissionless decentralized zk rollup, and StarkEx, an independent zk rollup SaaS. Additionally, StarkWare developed a production-grade zk virtual machine (zkVM) called Cairo. Cairo claims to implement Turing-complete von Neumann structures. Each program resides in the VM's memory along with the data it processes. Anyone can access Cairo today and is currently being used by prominent StarkEx clients such as dydx, Immutable, and DeversiFi. Other new applications using their own versions of zkVM include Polygon Miden and RiscZero, which is trying to build a general zkVM.

The opposite of zkVM ideology is zkEVM. zkVMs start from scratch as new blockchain VMs optimized for zk, or simply adapted for Solidity tooling and compatibility. On the other hand, zkEVM implements the complete set of EVM opcodes. There are several benefits to using EVM opcodes:

• Achieve full compatibility with the EVM ecosystem and tools

• Inheriting the Ethereum Security Model

• Efficiency may be similar to compiler-based approaches

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

The biggest advantage of zkEVM over zkVM is EVM equivalence. Targeting the large existing dApp community with low gas fee incentives and an easy development experience for developers has proven fruitful, which is what the zkEVM builders are counting on.

The most popular zkEVM project right now is zkSync, which uses zk-SNARKs as a layer-2 solution for verification and scaling. Additionally, zkSync has chosen to keep data availability off-chain, secured by zkSync token stakers using Proof of Stake (zkPorter) (meaning an airdrop could be imminent). The design of this implementation is based on a solution developed by StarkWare called Volition.

Finally, a fairly new player, Scroll is developing a general-purpose L2 zkEVM. Scroll takes a new approach to using GPU power to generate zk proofs off-chain. Recent breakthroughs in zk proofs like Poseidon hashing, Plookup, and PLONK have brought the cost down enough to make zkEVM a reality. In addition, advances in GPUs and ASIC/FPGA accelerators are improving hardware conditions and further reducing costs. Scroll is still in development and plans to launch their zkEVM testnet in the coming months.

future application

Zk Proof was originally developed to maintain privacy. While popular media may focus current use cases on "greater TPS permitting", the fact remains that zk Proof has a wider range of applications.

One such application is the tool zk-ID, which verifies the identity of users by anonymously checking assets in wallets or on-chain transactions through zk circuits.

Zk identities have extremely powerful potential and immediate real-world use cases. For example, let's say I'm a debtor trying to prove my creditworthiness while still keeping my banking information and activities private. I will certify that I have repaid large loans from various trusted banks, but will not disclose the banks or the specifications of these loans.

Four key components to support future zk-identity

Another major development in the zk space is the efficient private delegation of zk-SNARK provers. As mentioned earlier, the proof times are rather slow. Using SHA2 to hash 10kb takes 140 seconds, not the required milliseconds. The solution to this problem is to outsource proofs. Unfortunately, this brings up another dilemma: secrets are always revealed. What is needed: proof of outsourced privacy. With careful implementation, proofs can be delegated to devices such as mobile phones up to 26 times faster than local computation. This novel framework was first presented by Pratyush Mishra at zkSummit in April 2022.

epilogue

We are in the very early stages of developing application-based zk proofs. Still, the pace of progress is fast. There is still a lot of conflict between communities as camps are forming and opinions are being politicized. Only time will tell which side is right. To be sure, when historians look back, they will see this period of zk implementations as a seminal part of the spectacular history of cryptocurrencies.