Frontiers of Zero Knowledge: About SNARKs, STARKs and Future Applications

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

There’s been a lot of apparent enthusiasm around L2 scaling solutions lately, and rightfully so. With Optimism releasing governance tokens, demand for lower gas fees on the ETH mainnet, and a flurry of new ideas spawned in back-to-back hackathons, it’s safe to say that L2 is in full swing in 2022. 

In today’s article, I’ll dissect one of the most powerful yet often misunderstood cryptographic 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. 

bsNQYC7TtmYx29JDTsYLSJE3K8vFs5a1wrKmMFdL.png

Why zero-knowledge proofs matter

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 steals a red card, trying to prove to Bob that she has a red card, but doesn’t actually show a red card. In order to do this, Alice needs to separate all the black cards from the deck and show them to Bob. Bob counts all 26 black cards, verifies their existence, and determines that the card Alice has must be red. Thus, Alice is able to prove to Bob that she has a red card without actually showing it. The 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 to this decade or even millennia. In fact, the idea was first proposed by abstract mathematics researchers in the 1980s. The solution was designed to solve a problem at the time associated with theoretical systems between provers and verifiers – interactive proofs. 

But what if the validator turns out to be malicious? How much additional information did Prover reveal beyond verifying the veracity of the statement? Let’s see how the hash of the password is stored on the centralized server. Traditionally, when interacting with a server, the server gets the password in clear text. This is a poor way of doing “proof of identity”, so the researchers turned to a system that could prove a claim without revealing any irrelevant 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 point of view of the prover, achieving zero-knowledge requires randomness. On the verifier’s side, randomness is required to generate queries on the prover. The first widely demonstrated application was in NP – solving a class of complexities called tricoloring problems for graphs. This is a huge breakthrough as this application can be applied to any problem in NP class. This can be done in one fell swoop. 

In the blockchain space, there are many implementations of zero-knowledge proofs due to their ability to provide scalability and utility in privacy models. Specifically, the computational work performed by the validator is exponentially reduced compared to without the zero-knowledge proof system. On the other hand, the prover requires considerable computational overhead to perform the proof. I will discuss this in detail later.

ZK protocol

While a large number of zk protocols currently exist, for this article I will focus on SNARKs and STARKs and dive into other protocols in later articles.

Succinct Non-Interactive Arguments of Knowledge (SNARKs) are a popular proof mechanism that incorporates zero-knowledge proofs, which were 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 proofs required for transactions and to verify said proofs. These keys contain a reference string linking the authentication key and the key to send the private message. 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 at the creation stage remains a major point of criticism for 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 rerun.

However, in practical practice, zk-SNARKs are difficult to implement by themselves. There are many steps that need to be checked in a calculation, but it is not feasible to check the time taken for the work of each step individually. The solution comes in the form of a polynomial. Coding computations as polynomials can save a lot of information and time. Instead of having an infinite number of equations between numbers, we can replace them with polynomial expressions that “replace” them.

But wait, there’s more! Typically, the equation is validated using polynomials 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 little information about polynomials.

Polynomial promises 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 is worth digging into 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 open backdoors. This has led to the creation of scalable transparent arguments of knowledge, or STARKs. STARKs use a hash function as their source of security, unlike the bilinear implementation used by SNARKs. The scalability aspect refers to two things: 

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

2. The size of the verification time is logarithmic. STARKs utilize FRI to improve information storage and performance.

cHOqK2UXUGxmXXUxZ0neaXfqGTGXVkh4A247CKXp.png

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 zk proofs, as well as budding game projects. 

StarkWare is a pioneer of zk-STARK, developing two core products: StarkNet, a permissionless decentralized zk rollup, and StarkEx, a standalone zk rollup SaaS. Additionally, StarkWare has developed a production-grade zk virtual machine (zkVM) called Cairo. Cairo claims that Turing-complete von Neumann structures can be achieved. 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 version of zkVM include Polygon Miden and RiscZero, which is trying to build a generic zkVM.

68906fe7f983b93602b4f34c07aecf22The ideological opposite of zkVM is zkEVM. zkVMs started from scratch as new blockchain VMs optimized for zk, or just adapted to Solidity tooling and compatibility. On the other hand, zkEVM implements the full 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 approach

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 incentives and an easy development experience for developers has historically proven fruitful, which is exactly what zkEVM builders are counting on. 

The most popular zkEVM project at the moment is zkSync, which uses zk-SNARKs as a 2-layer solution for verification and scaling. Additionally, zkSync opted to place data availability off-chain and 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.

ui8nSakqv7Bt4EIF7mEZXDg4BH80wC0GnclDu14C.png

yD2SUUYIxoJnVTjMlTwSmPjP8xQhnaZvKGFdqufg.jpegFinally, a fairly new player, 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 such as 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, further reducing costs. Scroll is still in development and plans to launch their zkEVM testnet in the coming months.

future applications

Zk Proof was originally developed to maintain privacy. While the mass media may focus current use cases on “greater TPS allows”, 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.

DFW6yk4Zo7CoHWp6igZyTANl47GwYDjbGZK3bSkW.png

Zk identities have extremely strong potential and have 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 multiple trusted banks, but will not disclose the banks or the specifications of these loans.

bsudlqLnN1znlxhjokb8qRwZF9ESGu1j543IJbXB.jpegFour 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 time to proof is rather slow. It takes 140 seconds to hash 10kb with SHA2, not the milliseconds required. The solution to this problem is to outsource proofs. Unfortunately, this presents another dilemma: secrets are always leaked. What is needed: Outsourced Privacy Proof. With careful implementation, proofs can be delegated to devices such as mobile phones 26 times faster than local computation. This novel framework was first proposed by Pratyush Mishra at zkSummit in April 2022. 

Q5Wk5rJunmPOzIUQWumHb3zzXnCUyKKWx5ckzW9g.png

Epilogue

We are in the very early stages of developing an application based zk Proof. Still, the pace of progress has been rapid. There is still a lot of conflict between communities as camps are being formed 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 cryptocurrency’s spectacular history. 

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/frontiers-of-zero-knowledge-about-snarks-starks-and-future-applications/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2022-05-07 10:22
Next 2022-05-08 01:29

Related articles