SNARKs vs. STARKS vs. Recursive SNARKs

Written by Alchemy

Reviewed by Brady Werkheiser

Published on May 27, 20229 min read

---

Zero-knowledge proofs are mechanisms that allow one party to reveal knowledge of information to another party without revealing the information itself. Also called validity proofs, ZK proofs were originally used to hide transaction details in privacy-focused blockchains. 

But ZK proofs also have another exciting use case: scaling general-purpose blockchains. With validity proofs, blockchain nodes can verify transactions without storing the details or replaying the computation. This reduces confirmation times and boosts network throughput.  

Due to their scalability benefits, ZK proofs have become a core infrastructure for blockchain scaling projects, especially zero-knowledge rollups. In this guide, we cover the major classifications of ZK proofs used in blockchains: ZK-SNARKs, ZK-STARKs, and recursive ZK-SNARKs. 

What is a ZK-SNARK?

ZK-SNARK is a protocol for generating zero-knowledge proofs to verify the authenticity of information without exposing the underlying data. The acronym means Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.  

A ZK-SNARK protocol involves two parties: the prover (Alice) and the verifier (Bob). The prover (Alice) is the party making a claim, while the verifier (Bob) is the party responsible for verifying the claim. 

The information referenced in the claim is called a witness or secret. A prover (Alice) uses the ZK-SNARK mechanism to produce a proof to show a verifier (Bob) that the claim is true…without revealing the referenced information.

A hypothetical example involving ZK-SNARKs is authenticating user identities. An individual could prove a statement ("I am a US citizen") without revealing personal information (e.g., a passport or Social Security Number). 

ZK-SNARKs are so-called because they possess the following qualities:

1. Zero-knowledge: This means that the verifier knows nothing about a statement except for its validity or falsity. 

2. Succinct: The proof is small enough for the verifier to verify in a short timeframe. 

3. Non-interactive: SNARKs are non-interactive because provers and verifiers don't need to exchange information beyond the initial proof submitted. Early zero-knowledge proving systems required provers and verifiers to exchange multiple messages to verify statements. 

 4. Argument: A SNARK is a "computationally sound" statement that satisfies rigorous requirements, making it difficult to cheat (i.e., generate false proofs). 

5. Knowledge: SNARK-based proofs cannot be created with access to the underlying information or the witness.  

ZK-SNARKs in blockchains 

Distributed computing systems, like public blockchains, need to solve the so-called "computational integrity problem". Computational integrity (CI) refers to the correctness of the output gained from a specific computation. 

In public blockchains, computational integrity refers to the correctness of transactions executed on a network. Most blockchains achieve it by making other computers (nodes) rerun each transaction. 

However, this approach is problematic. Forcing every node to replay each transaction slows down the network and limits scalability. Nodes also have to store transaction data (or they cannot replay computations), causing exponential increases in the blockchain's size. 

But what if nodes could check the validity of a computation without replaying it? This would improve network throughput and remove the need for nodes to store excess transaction data.

Enter ZK-SNARKs. 

Validity proofs generated using ZK-SNARK can prove the validity of a transaction without revealing the inputs. This is why privacy-focused cryptocurrencies like Zcash and Monero use SNARKs to obfuscate information about transactions. 

A SNARK can also prove the correctness of a computation performed off-chain without nodes replaying every step of the computation. This is where ZK-SNARK becomes useful for scaling blockchains. 

Verifying off-chain computations with SNARKs is a complex process that starts with encoding the computation into a mathematical expression. This mathematical statement forms the basis of the validity proof. 

The verifier then performs an operation on the proof to check its correctness. If the proof passes all checks, the underlying computation is considered valid. This is why SNARKs are succinct—the size of a validity proof is many times smaller than the computation it verifies. 

ZK-SNARKs and ZK rollups 

A rollup is a Layer 2 scaling solution for Ethereum that improves throughput on the Layer 1 (L1) blockchain through off-chain execution. Rollups process transactions on an L2 chain, aggregate multiple off-chain transactions into blocks, and submit them to the L1 chain. 

By moving computation away from the base layer, rollups decrease network congestion and scale transactions. 

However, the L1 chain needs to know if transactions executed off-chain are valid or not (i.e., the computational integrity problem). Otherwise, a malicious actor can hijack the rollup and submit bad transactions to the main chain. 

A type of rollup (zero-knowledge rollup) uses ZK-SNARKs to prove the authenticity of off-chain transactions to the L1 chain. SNARK proofs can be verified by anyone, which assures the L1 chain of transaction validity. 

Most ZK rollups that use ZK-SNARKs follow the same structure:

1. Users on the L2 chain sign transactions and submit them to validators. 

2. Validators compress transactions into a block and generate a corresponding validity proof (SNARK). This provides cryptographic guarantees that the new state resulted from the addition of valid transactions. 

3. A smart contract on the L1 chain performs an operation on the validity proof. The results of this operation determine if batched transactions are validated and posted to the main chain. 

What are the benefits of ZK-SNARKs?

There are three main benefits of using ZK-SNARKs: high throughput, small validity proof sizes, and security.

1. High throughput 

ZK-SNARKs scale throughput by shrinking computation on Ethereum's base layer. With ZK-SNARKs, rollups can increase TPS rates into the thousands. 

A ZK-SNARK is usually many times smaller than the transaction data it verifies. This reduces congestion on the base blockchains and enables cheaper gas fees and faster transactions. 

2. Small proof sizes 

The small size of SNARK proofs makes them easy to verify on the main chain. On Ethereum, this means lower gas fees for verifying off-chain transactions, reducing rollup costs for end-users. 

3. Security 

ZK rollups are considered more secure than other scaling projects mainly because of the cutting-edge cryptographic security mechanisms used in ZK-SNARKs. 

ZK-SNARK proof is computationally sound, making it difficult to deceive verifiers and act maliciously. The non-interactiveness of ZK-SNARKs also means proofs can be trustlessly verified by anyone. 

What are the downsides of ZK-SNARKs?

There are three main downsides of using ZK-SNARKs: it requires a trusted setup, they are susceptible to quantum computing attacks, and they rely on special hardware.

1. Trusted setup 

Setting up the ZK-SNARK protocol requires the creation of a Universal Common Reference String (CRS). Also described as public parameters, the CRS enables secure communication between provers and verifiers. 

If a malicious actor gained knowledge of the public parameters, they could generate false validity proofs. Some projects attempt to solve this problem by using multi-party computation (MPC), which involves different individuals, to generate the public parameters. 

Nevertheless, this approach requires users to trust the integrity of those involved. This is quite problematic since the purpose of blockchains is to reduce the need to trust authorities. 

2. Susceptibility to quantum-computing attacks

ZK-SNARK uses Elliptic Curve Cryptography (ECC) to encrypt information used in producing validity proofs. ECC is relatively secure for now, but advancements in quantum computing could break its security model. 

3. Reliance on special hardware 

Generating validity proofs with ZK-SNARKs is a computationally-intensive process, which means provers must invest in specialized hardware. Because very few people can buy these machines, many think the ZK-SNARK proving process is highly centralized.  

What projects use ZK-SNARKs?

Five notable projects that use ZK-SNARKs are ZKSync, Loopring, Aztec, Polygon Hermez, and ZKSpace.

ZKSync

EVM-compatible ZK rollup living on Ethereum Mainnet created by Matter Labs. ZKSync supports smart contracts, token swaps, payments, and NFT minting. 

Loopring

Ethereum Layer 2 (L2) project powered by SNARK-based ZK rollup technology. Loopring also serves as a decentralized exchange for trading ETH and other ERC-20 tokens, for a fraction of the costs charged on DEXs on Ethereum Mainnet. 

Aztec

Open-source L2 network built on the Ethereum network. Aztec leverages ZK-SNARKs to scale transactions and increase the financial privacy of users. 

Polygon Hermez 

ZK rollup operating atop the Ethereum blockchain. Polygon Hermez uses ZK-SNARKs to power secure and low-cost token transfers and payments. 

ZKSpace

ZK rollup project based on ZK-SNARKs. ZKSpace offers Ethereum users lower gas fees and faster transactions and comprises an AMM-style DEX (ZKSwap v3), payments network (ZKSquare), and NFT marketplace (ZKSea).

What is a ZK-STARK?

ZK-STARK is an acronym for Zero-Knowledge Scalable Transparent Argument of Knowledge. Just like ZK-SNARKs, ZK-STARKs show a statement is valid without revealing anything about the statement itself. 

Save for a few differences, a STARK has the same properties as a SNARK. STARK-based validity proofs are generated using a piece of information, which is hidden from the verifier. A STARK can also verify the correctness of transactions without revealing the inputs.

ZK-STARKs vs. ZK-SNARKs

The major difference with ZK-STARKs comes from their scalable and transparent properties: 

ZK-STARK is considered transparent because it can work without a trusted setup of a Common Reference String (CRS). Instead, STARK protocols use publicly verifiable randomness to set up interactions between provers and verifiers. 

ZK-STARKs are scalable because proving and verifying complexity scale quasilinearly in relation to computation complexity. With ZK-SNARKs, proving and verification complexity scale linearly in relation to the underlying computation. 

This simply means ZK-SNARK protocols require more time to produce and verify proofs than ZK-STARKs when the computation we need to verify is larger. This is why STARKs are better suited to applications that handle large volumes of transactions. 

What are the benefits of ZK-STARKs?

There are four main benefits of using ZK-STARKs: there is no need for a trusted setup, they’re scalable, they afford users with maximum throughput, and they have high-security guarantees.

1. No need for a trusted setup

ZK-STARKs don't require a trusted setup to function and instead rely on public randomness. This reduces trust assumptions on the part of users and improves the security of STARK-based protocols. 

2. Scalable properties 

STARKs can be computed and verified faster at scale compared to SNARKs. More importantly, ZK-STARKs keep proving and verifying times low even as the complexity of the underlying computation grows exponentially. 

3. Maximum throughput 

Like SNARKs, STARKs can scale blockchains by enabling secure and verifiable off-chain computation. 

A single STARK proof submitted to the L1 chain can verify thousands of transactions conducted off the main chain. Hence, several high-profile ZK rollup projects use ZK-SNARKs to prove the integrity of off-chain computation. 

4. Higher security guarantees 

ZK-STARKs use collision-resistant hashes for encryption instead of the elliptic curve schemes used in ZK-SNARKs. This is considered resistant to quantum computing attacks, making it more secure than the elliptic curves used in SNARKs.

What are the downsides of ZK-STARKs?

The two main downsides of using ZK-STARKs are that they use larger proof sizes and there is less adoption of the technology in the blockchain space.

1. Larger proof sizes 

While STARKs provide faster proofs, the drawback is that these proofs are larger compared to SNARK-based proofs. This makes STARK proofs costlier to verify on Ethereum since computing bigger proofs incurs higher gas fees. 

2. Lower adoption 

SNARKs were the first practical application of zero-knowledge technology in blockchains, which is why they have more market share than STARKs. Most ZK rollups use ZK-SNARKs and the developer ecosystem and tooling for SNARK-based ZK proofs is larger. 

Although ZK-STARKs also has high-profile supporters, including the Ethereum Foundation, they have lower adoption. Developers may, therefore, find less support and tooling for building ZK projects with STARKs. 

What projects use ZK-STARKs?

StarkNet

General-purpose ZK rollup operating as an L2 network on Ethereum. StarkNet allows decentralized applications (dApps) to achieve unlimited scalability without compromising Ethereum's decentralization and security. 

dYdX

Ethereum-based ZK rollup project (which doubles as a decentralized exchange) offering crypto users and traders fast and low-cost trading, borrowing, and lending. dYdX uses STARK proofs as part of its security mechanism, guaranteeing users safety of funds. 

Polygon Miden

STARK-based ZK rollup with EVM compatibility. Although still in production, Polygon Miden will be the first EVM-compatible ZK-STARK protocol at launch and allow developers to migrate Ethereum-native dApps to enjoy scalability on the L2 network. 

What is a recursive ZK-SNARK?

A recursive SNARK system generates proofs in parallel for different transaction blocks and aggregates them into one single block proof that gets submitted to the main blockchain, which means one SNARK can verify other SNARKs.

The L2 rollup still submits one validity proof on Ethereum. However, this "recursive proof" verifies transactions in multiple L2 blocks, all of which become valid once the on-chain contract accepts the submitted proof. 

What problem do recursive ZK-SNARKs solve?

Recursive ZK-SNARKs dramatically increase the number of transactions that can be finalized with a ZK proof by including multiple L2 proofs in a single proof submitted to the L1 chain, which is currently limited by Ethereum’s 12-14 second block time.

Block time refers to how long it takes to mine a new block of transactions on Ethereum. ZK rollups can only submit one on-chain transaction (and the corresponding validity proof) per block, limiting how many transactions they can process. 

How is a recursive ZK-SNARK different from a regular ZK-SNARK?

A recursive ZK-SNARK is different from a normal ZK-SNARK because recursive ZK-SNARKs can verify more than one transaction block by combining SNARKs generated for different L2 blocks into a single validity proof that is submitted to the L1 chain. 

ZK rollups create a SNARK proof for each batch of transactions before posting to the main blockchain, and a single SNARK proof can only verify one block of transactions conducted on the L2 rollup. 

ZK-SNARKs can verify transactions that have been verified by regular ZK-SNARKs without using the original inputs. Ergo, the on-chain smart contract can verify a larger set of off-chain computations without running multiple SNARKs as inputs. 

What is Plonky2?

Plonky2 is a novel proving mechanism used in Polygon Zero, a proposed Polygon ZK rollup that uses recursive ZK-SNARKs to increase transactions.

Recursive SNARKs scale the proof-generation process by aggregating several proofs into a recursive proof, and Plonky2 uses the same technique to decrease the time it takes to generate new block proofs. 

The Plonky2 proving mechanism generates proofs for thousands of transactions in parallel before recursively aggregating them into one block proof. This is more efficient than traditional proving mechanisms that try to generate the entire block proof at once. 

The benefits of this approach are obvious.

Plonky2 can generate a recursive proof in 0.17 seconds, making it the fastest proving mechanism available. Moreover, Plonky2 produces proofs on a consumer-grade device, solving the hardware centralization issues with regular SNARK-based prover systems. 

Conclusion

Zero-knowledge proofs have gone from privacy-protecting technologies to becoming the next frontier of scaling technology. With the explosion of ZK rollups, it’s safe to say ZK-SNARKs, ZK-STARKs, and recursive SNARKs will feature heavily in the drive to scale Ethereum. 

Web3 developers can harness zero-knowledge technology by building on StarkNet, a STARK-powered Ethereum ZK rollup supported by Alchemy. Start building dApps that scale today without trade-offs today!