ZK Proofs 201: SNARK, STARK & the top use cases
Going deeper on ZK criteria, SNARK vs. STARK, and other use cases.
In this article, we’ll look deeper into zero-knowledge technology and its uses in crypto. If you didn’t catch our Zero Knowledge 101 article, read it first! This is a complex topic, and it will be extra challenging if you don’t have the basics.
What is zero-knowledge?
First, let’s refresh ourselves on what a zero-knowledge proof is:
A zero-knowledge proof is a method of convincing someone that you know a secret, without telling them the secret.
This idea was first conceived in the 1980s, but an actual method for developing zero-knowledge proofs was not discovered until 1991, using the tricolor problem.
In this scenario, we have a graph of connected nodes. The nodes can be colored in three colors, but two adjacent nodes must be colored differently.
It is possible to prove that you know a solution while giving zero knowledge of that solution to a Verifier. Simply reveal two nodes (without showing any other nodes) until the Verifier reaches extremely high confidence. This can be repeated with very large arrays and numerous reveals computationally to create zero-knowledge for complex problems.
This solution proved that zero-knowledge proofs are possible and formed the backbone for the innovation and development which has occurred since.
Criteria for ZK proofs
Let’s take a closer look at what actually defines a zk-proof (also spelled ZK proof). In order to pass the test, a ZK-proof must meet three criteria:
- Completeness: If the statement is true, the Verifier will be convinced by the proof, without any extra information.
- Soundness: If the statement is false, the Prover will not be able to convince the Verifier that it is true with the proof.
- Zero-knowledge: The Verifier does not learn any additional information about the statement beyond the fact that it is true.
Interactive vs. Non-Interactive Proofs
Within the category of zk-proofs, we can sort them into two general types based on the degree of communication required.
Interactive proofs convince the Verifier through back-and-forth communication. Think back to our tricolor example. In that case, the Verifier has to ask to see more nodes (colored circles) and the Prover has to reveal them over and over and over. The Prover and Verifier had to interact with each other multiple times. This method is simple but not ideal for complex or computerized tasks, like blockchain transactions. Consider if a zk-rollup needed to communicate thousands of times with a Layer 1 just to execute one batch of transactions; the fees and lag would be unbearable.
Non-interactive proofs reduce the degree of communication required between the Prover and Verifier to just one message. The computation behind this is too complex for this short article, but it can be summarized like this: the Verifier is replaced by an algorithm, who poses random questions or tests to the Prover. The proof is generated and sent to the Verifier, who uses another algorithm to confirm that the Prover had no prior knowledge of the tests, and that the proof meets the criteria of completeness, soundness, and zero knowledge. The development of non-interactive zk-proofs allowed them to be used for more practical applications. Almost all zero-knowledge crypto tools use non-interactive proofs.
Non-interactive proof types: SNARKs and STARKs
As if “zero-knowledge” wasn’t a strange enough term, we now get into the really weird words: SNARKs and STARKs.
Succinct Non-Interactive Arguments of Knowledge (SNARKs) and Scalable Transparent Arguments of Knowledge (STARKs) are the two most common types of ZK proofs (though not the only ones).
SNARKs have “non-interactive” in the name, and their main characteristic lies in how they generate the verification method that allows the Verifier and Prover to communicate non-interactively. This is achieved by creating a Common Reference String (CRS), a public parameter which both parties use to create/validate the proof.
But there’s a downside to creating the CRS: someone has to do it! This introduces a security risk, as there are now other entities involved in the process. (To some, this defeats the purpose of using ZK proofs in the first place: trustlessness.) In creating the CRS, the parties involved have access to sensitive information, which could be used to create false proofs. This information is charmingly called “toxic waste”, and it must be deleted as soon as the CRS is made.
To limit the security risks involved, the CRS is often created using a multi-party computation (MPC) setup ceremony. In this method, multiple parties input some of the toxic waste required to create the CRS and keep it hidden from each other. That way, as long as just one party deletes their toxic waste at the end, the CRS is secured. However, the risk still exists that they won’t.
STARKs (developed by Starknet) provide a solution to this problem by eliminating the CRS. Instead of toxic waste, parameters are generated randomly, using methods that are publicly verifiable. In addition to this security advantage, STARKs are also faster to prove and verify than SNARKs, particularly for complex proofs. The chief downside lies in their use of data: STARK proofs are much larger than SNARKs, making them more expensive to use.
SNARKs are used by many zero-knowledge tools for their lower costs and relative simplicity. The best-known Layer 2 Ethereum rollup, zkSync, uses a trusted setup ceremony. However, it includes over 200 participants (even Vitalik Buterin himself!), and as long as just one of them is honest, the whole system is secure. We’ll cover zkSync in great detail in our next article.
At the same time, STARKs are being employed more and more, particularly in situations with high security needs.
ZK use cases beyond rollups
That brings us to the fun part: how can we actually use this zero-knowledge stuff?
Layer 2 rollups are the most developed use case, with several prominent examples including zkSync, Loopring, ZKSpace, and Aztec. But, zero-knowledge is an area of rapid, ongoing development, and new applications arise all the time. In this article, we’ll look at two of them: private cryptocurrencies and ZK identity. (And stay tuned for our ZK 301 article, where we’ll look at the newest use case: zkEVMs.)
One of the most intriguing implementations for zero-knowledge is in identity verification. In the crypto space, it is not uncommon for people to stay anonymous and use pseudonyms; surely you’ve seen major influencers on Twitter who are known only by an ENS domain and an NFT.
This can extend even to the founders of large projects who remain “undoxxed” for their entire career. An example is 0xMaki, the former Head Chef of SushiSwap and now a member of the LayerZero team.
This poses a challenging question: how can we trust an anonymous person with our hard-earned cash? While crypto-natives might be undaunted by this prospect, it’s a tough pill to swallow for people with a traditional finance background.
But, consider the scenarios that ZK identity tools can unlock:
- To apply for a loan, an anonymous debtor could prove that they have taken out loans before and paid them back on time, without revealing their identity, the size of the loans, or their purpose.
- When weighing in on a DAO proposal or community decision, someone could prove the size of their stake, time with the project, or reputation in the broader space, without revealing their identity or the exact details of these qualifications.
- To qualify for an airdrop, an NFT minting whitelist, early access to a dApp, or other exclusive opportunity, someone could prove the size of their holdings, collection of exclusive NFTs, extensive transaction history, or similar without revealing the exact nature of this sensitive information.
And the list goes on and on. Several projects have already begun implementing zero-knowledge identity solutions, and the most prominent is Polygon ID.
Polygon ID is a zero-knowledge identity platform developed by the Polygon blockchain team. The platform offers privacy for end users and on-chain verification for dApps and protocols, creating an environment that is both more private and more secure. Mihailo Bjelic, Polygon’s co-founder, has said that Polygon ID is the first in “the digital identity space” that is “private by default, offers on-chain verification and permissionless attestation.”
Private blockchains and cryptocurrencies
Zero-knowledge is a powerful way to transact and communicate without revealing excess information. This has made it a popular technology to advance one of crypto’s key aims: privacy.
Numerous projects have employed ZK proofs to anonymize transactions, protect user privacy, and encrypt data.
The most famous of these is Zcash, which was the “first widespread application of zk-SNARKs” when it launched in 2016. Zcash “shielded transactions” fully encrypt the sender, recipient and amount of a transaction. Zcash claims its technology exceeds that of other private cryptocurrencies like Monero because it also hides the transaction graph, making it extremely difficult to trace Zcash transactions. The Zcash market cap is currently $495 million with 24-hour volumes of $33 million.
An intriguing part of Zcash history is “The Ceremony,” the most well-known trusted setup in history. To launch Zcash in 2016, private keys were generated in a two-day process across six locations around the world. Afterwards, the toxic waste was destroyed -- physically, with electric saws and bonfires! And it united some strange bedfellows: both JPMorgan and Edward Snowden participated.
Another prominent example of ZK adoption for privacy is the TRON blockchain and cryptocurrency. In July 2020, Tron upgraded to Tron 4.0 and introduced the TRONZ privacy protocol, based on SNARKs. This added three types of transactions to the network: minting shielded TRC-20 tokens, burning them back to the unshielded form, and shielded transfers between addresses.
While Zcash and Tron are Layer 1s, Aztec is an encryption-oriented Ethereum Layer 2. It uses zk-SNARKs to rollup transactions for lower fees, while also fully encrypting them. Its Aztec Connect SDK allows developers to build encrypted dApps and DAOs on Ethereum as well. The zk.money protocol, built on Aztec, is an Ethereum DeFi tool with encryption and reduced fees.
Zero-knowledge is a rapidly developing technology, and new features and applications are being developed every day. Look out for our next article in this series: Zero-Knowledge 301, about the expanding field of zkEVMs. And of course connect with Pontem on Twitter and Telegram for more updates!
Pontem Network is a product studio building foundational dApps for Aptos. Our products include: Pontem Wallet, Liquidswap (the first DEX/AMM for Aptos), Move Playground, a Move browser code editor, the Move IntelliJ IDE plugin for developers; and the ByteBabel Solidity-Move code translator -- the first implementation of the Ethereum Virtual Machine for Aptos.