Throne of ZK: SNARK vs STARK

Kido Kim

Published in

nonce Classic

7 min readMar 23, 2023

Author: Kido Kim

Summary

SNARK and STARK each have distinct advantages.
Looking back on past cases, it is likely the two technologies will secure their own dominant sector
Recently, attempts to optimize only the advantages of both methods have been attracting attention.

Intro

Looking at the history of technological development, it was common to see similar technologies emerge at a similar time and compete for market hegemony. These phenomena have also been found in our small Web3 market, specifically the zero-knowledge market; namely between zk-snark (hereon SNARK) and zk-stark (hereon STARK). We will examine and compare the distinct characteristics of SNARK and STARK respectively, then predict how this competition will develop in the future based on past examples.

SNARK and STARK

WHAT IS zk-SNARK?

zk-SNARK = zero-knowledge Succint Non-interactive Argument of Knowledge

zk-SNARK was birthed in January 2012 by Professor Alessandro Chiesa (co-inventor of Zerocash, co-founder of Zcash, and co-founder of StarkWare Industries) of UC Berkeley and his team. It was through their paper the world first discovered the concept of zk-SNARK. Of the four words making up SNARK, our focus should be on “Succint” and “Non-interactive”.

Succint: This refers to quick and easy verification that has been made possible with its smaller size of proof. “Quick and easy” here translates to minimal computation requirements, making SNARK advantageous for reduced gas consumption and faster transactions on the blockchain.
Non-interactive: Non-Interactive zkp overcomes the limitations of interactive zkp in that a prover can prove through cryptography that they know specific information without any interaction. Most of what we call zero-knowledge proof tech today are non-interactive zkp.
(Limitation of interactive zkp: Proofs rely on probability and require multiple interactions, making them partly inefficient in terms of speed and computation.)

(Note: For clear contrast between the two technologies, comparisons have been made based on early SNARKs)

WHAT IS zk-STARK?

zk-STARK = zero-knowledge Scalable Transparent ARgument of Knowledge

zk-STARK was birthed in 2018 by Eli Ben-Sasson and his team. Among the four words that make up STARK, the focus should be put on “Scalable” and “Transparent”.

Scalable: zk-STARK is clearly technology focused on improving the scalability of blockchain. zk-stark does not require drastically higher computational power compared to SNARK even when resolving complex proofs and thus it is expected to have better scalability.
The graph below, based on data from the STARK whitepaper, visualizes the change in time required for SNARK and STARK as computational complexity increases. STARK shows relatively modest fluctuations despite the increasing complexity of proof.

As the computational complexity increases, the time required for Snark increases significantly compared to Stark (Source)

Transparent: STARK does not require a trusted setup. This implies that the parameters used for the proof are transparently disclosed.

SNARK ↔ STARK

Proof size

Zero-knowledge proof is a method by which one party(prover) can prove to another party(the verifier) that a given statement is true without disclosing all the information it holds. Proof size refers to the amount of data needed for this proof.

Proof size is decisive in zero-knowledge proofs, because the larger the proof size, the more computation and interaction is needed to generate and send proof.

The proof size of a SNARK that has finished trusted set-up is significantly smaller than that of STARKs. As a result, gas consumption and the time required for SNARK is significantly lower than STARK. This is one of the reasons why many projects choose to implement SNARK.

Resources to refer to

Noteworthy references include the no. of projects, no. of developers, no. of published codes and libraries, and the size of the community in which various discussions arise. The dominant opinion is that SNARK has more resources than STARK. However, according to the 2022 Developer Report recently published by Electric Capital, the number of developers entering StarkNet is increasing noticeably, meaning the tables could be turned at any time.

Among the emerging ecosystems Aptos, Sui, and Starknet, Starknet has the highest number of full-time developers at around 120 (Source: Electric Capital)

Among ecosystems with 100+ full-time developers, Starknet has the fastest year-over-year change in developers at +243% (Source: Electric Capital)

Below is a compilation of headlines mentioning Starknet from Electric Capital’s 2022 Developer Report, which shows that developers are onboarding into Starknet ecosystem quickly.

ecosystems with 100+ full-time developers: starknet +243%, Internet computer +94%, & Cardano +14% grew yoy while tezos stayed flat
ecosystems with 300+ total devs: starknet +134%, i̵c̵p̵ ̵+̵4̵8̵%̵,̵ ̵n̵e̵a̵r̵ ̵+̵4̵1̵%̵,̵ ̵t̵h̵e̵ ̵g̵r̵a̵p̵h̵ ̵+̵2̵1̵%̵,̵ ̵K̵u̵s̵a̵m̵a̵ ̵+̵9̵%̵,̵ ̵B̵i̵t̵c̵o̵i̵n̵ ̵+̵2̵%̵,̵ ̵c̵a̵r̵d̵a̵n̵o̵ ̵+̵2̵%̵,̵ ̵&̵ ̵C̵e̵l̵o̵ ̵f̵l̵a̵t̵
since 2018: Polygon, NEar, Tezos, BNB, internet computer, & starknet grew 20x+ to 120+ full-time devs
Internet computer, starknet, tezos, the graph, avalanche, & celo had <50 devs and now have 300+ devs
ecosystems under 2 years old: starknet, aptos, & sui have 60+ Full-Time developers; starknet has the most at almost 120 Full-Time developers
Starknet, BNB, avalanche, Cardano, tezos, & icp took different paths to grow to 100+ full-time developers
ecosystems under 2 years old: starknet, aptos, & sui have 100+ total developers; starknet has the most at almost 400 total devs

Trusted setup

A trusted setup is a process in which multiple parties participate to create standard parameters for a proof system. Participants in this process must be credible, thus the term “trusted” is used. It is possible for a single party to set it up as opposed to multiple parties but therein would lie the risk of assigning a large portion of the proof system to one party.

Although the introduction of trusted setups into the proof system has brought ground-breaking effects (speed, etc.), it has the disadvantage that a third party other than the Prover and Verifier must be trusted, meaning this may lead to a potential trust risk.

*Note in this article, for comparison between SNARK and STARK, early SNARK models were the standard hence trusted setups were mentioned as necessary. But recently discussions on transparent structures (without trusted setups) have been actively underway(e.g. Halo, Halo2, etc).

Quantum Resistance

SNARK uses elliptic curve cryptography, which is vulnerable to quantum computer attacks. STARK, on the other hand, uses cryptographic hash functions known to be resistant to quantum computer attacks. A more detailed explanation can be found here.

SNARK vs. STARK predictions based on past cases

“History doesn’t repeat itself, but it often rhymes.” — Mark Twain

Throughout history, there have been many cases in which similar technologies appeared at a similar time and competed. Most times the technology that won this competition dominated the market but in some cases, in which the technologies had distinct advantages, both survived.

The table below summarizes 15 competitions between similar technologies from 1970 to 2010 by the winners, winning factors, and keywords. Most had a single winner and after its victory, completely dominated the market. However, there have also been cases in which both survived, which was when the advantages of the two competing technologies were clear and mutually exclusive (e.g., Wi-Fi vs. Bluetooth, MP3 vs. AAC).

Likewise, SNARKs and STARKs also have clear distinguishable advantages. Since the zero-knowledge proof market is still in its early stages, the two are often compared for belonging to the same category. But as the market matures, and the number and nature of applications that use zero-knowledge proofs will diversify, and SNARK with STARK will be able to secure a respective sector they can dominate. (I.e. For consumer apps with low computational complexity → SNARKs, for building projects with high computational complexity → STARKs)

So, what’s NEXT?

Competition between the two may end with just one winner (e.g., HD DVD vs. Blu-ray), or both surviving in their own way (e.g., Wi-Fi vs. Bluetooth), or even both becoming obsolete as new technologies emerge (e.g., 3G vs. 4G then 5G).

Nonetheless, the research done for both methods have, and will become foundational for the development of zero-knowledge proofs and therefore are of tremendous significance. For those curious about the next step for zero-knowledge proofs, let me conclude by recommending a few topics worth keeping an eye on.

SNARK + STARK → SPARK!! 💥💥

As the respective strengths of SNARKs and STARKs are clear, attempts to take maximum advantage of both technologies have actively been underway. The papers below are materials that have had a great impact on academia, the industry, or have recently attracted a lot of attention.

Labs focusing on zk

The following labs conduct research or invest focused on zero-knowledge technology. Staying up to date with their posts can also be a good way to quickly grasp the latest issues in the industry.

: Personae Labs, Delendum, 0xPARC, Geometry Research

Developing and Diversifying zkp Systems

The table below categorizes zkp systems developed from 2013 to 2021 in terms of; protocol, transparency, universality, post-quantum security, and programming paradigms.