zkSTARK¶

Overview¶

zkSTARK stands for Zero-Knowledge Scalable Transparent Argument of Knowledge. It is a zero-knowledge proof technology proposed in 2018 by Eli Ben-Sasson and the StarkWare team. Compared to zkSNARK, zkSTARK's core advantages lie in transparency (no trusted setup required), scalability, and resistance to quantum computing attacks, at the cost of larger proof sizes.

The name zkSTARK reveals its key properties: zero-knowledge protects private information, scalability supports processing large-scale computations, transparency eliminates the need for a trusted setup, and argument of knowledge ensures the prover truly possesses the relevant knowledge. Transparency is one of zkSTARK's most notable advantages, making its security assumptions purer and more auditable than zkSNARK schemes that require a trusted setup.

Core Properties¶

Transparency (Transparent)

zkSTARK does not require a Trusted Setup; all public parameters can be generated openly without relying on secret random numbers. This eliminates the risk of "toxic waste," making the system more transparent and auditable. Transparency is zkSTARK's most prominent advantage, avoiding the complexity and potential risks of multi-party computation ceremonies in zkSNARK.

Scalability (Scalable)

zkSTARK's proof generation and verification times grow quasi-linearly, meaning that even for large-scale computations, performance degradation is relatively modest. Compared to Replay Computation verification time, zkSTARK's proof and verification times are quasi-linear and logarithmic, respectively. Proof generation time is approximately O(log^2 n), and verification time complexity is logarithmic, where n is the computation scale. This scalability makes zkSTARK suitable for handling complex computational tasks.

Post-Quantum Security

zkSTARK is based on hash functions and information-theoretic security, and does not rely on elliptic curve cryptography or pairing operations. The only cryptographic element in STARK is a collision-resistant hash function. Therefore, with an ideal hash function, STARK is resistant to quantum attacks. This makes zkSTARK capable of resisting quantum computer attacks. As quantum computing technology develops, this quantum-resistant property becomes increasingly important.

Proof Size

zkSTARK's proof size is larger than zkSNARK's, typically tens to hundreds of KB. Although much larger than zkSNARK (a few hundred bytes), considering the advantages of no trusted setup and quantum resistance, this size increase is acceptable in many application scenarios, particularly where bandwidth is not the primary bottleneck.

Technical Principles¶

zkSTARK uses the FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) protocol as its core. This technology uses polynomial commitments and Merkle tree structures to verify the low-degree property of polynomials through repeated low-degree testing. The entire process is based on FRI's recursive folding mechanism, with each step halving the polynomial degree until it reaches a sufficiently small degree for direct verification.

The computation is first encoded as an AIR (Algebraic Intermediate Representation). The prover converts the execution trace into polynomials and commits to these polynomials using a Merkle tree. The verifier checks constraint satisfaction through random sampling. The entire protocol is made non-interactive through the Fiat-Shamir heuristic transformation; in a blockchain environment, only the proof and Merkle root need to be submitted.

Comparison with zkSNARK¶

Feature	zkSNARK	zkSTARK
Trusted Setup	Required	Not required (Transparent)
Proof Size	Very small (~200 bytes)	Larger (~100 KB)
Verification Time	Constant time	Logarithmic time
Quantum Resistance	No	Yes
Gas Cost	Lower	Higher
Cryptographic Basis	Elliptic curve pairing	Hash functions

Use Cases¶

Layer2 Scaling Solutions

StarkNet and StarkEx are Ethereum Layer2 solutions based on zkSTARK. Projects such as dYdX, Immutable X, and Sorare use StarkEx to achieve high-throughput and low-cost decentralized trading. StarkNet further provides a general-purpose smart contract platform, supporting complex decentralized application development using the Cairo language.

Verifiable Computation

zkSTARK can be used to prove the correctness of complex computations without revealing computational details. This is particularly important in privacy computing, outsourced computation, and institutional applications. Enterprises can verify computation results without trusting the executing party, protecting trade secrets.

Privacy Protection and Compliance

zkSTARK enables privacy transactions, identity authentication, and compliance proofs. Users can prove they satisfy certain conditions (such as proof of wealth, age verification) without disclosing specific information. Regulators can verify compliance without infringing on privacy.

Data Integrity Verification

Although zkSTARK is commonly used for computation verification, its transparency also makes it suitable for data integrity and storage proof scenarios. Decentralized storage systems can use zkSTARK to prove data availability and integrity.

Development History¶

In 2018, Eli Ben-Sasson and others published the zkSTARK paper, proposing a transparent zero-knowledge proof scheme. That same year, StarkWare was founded, focusing on commercial applications of zkSTARK.

In 2019, StarkWare released the Cairo programming language for writing programs that can generate STARK proofs. That same year, StarkEx began providing scaling services for DeFi projects such as dYdX.

In 2021, the StarkNet Alpha testnet launched, providing a general-purpose Layer2 network supporting complex smart contracts. dYdX's perpetual contract exchange based on StarkEx became a leading project in decentralized derivatives trading.

In 2022-2023, the StarkNet mainnet gradually opened and matured, launching the STRK token. An increasing number of projects chose to build on zkSTARK technology, spanning DeFi, NFTs, gaming, and other domains.