Understanding Zero-Knowledge Proofs and SNARK Basics.#
The term "ZK-STARK" is an acronym that stands for "Zero-Knowledge Scalable Transparent Argument of Knowledge". Each part of the name refers to a feature of ZK-STARK:
Zero-Knowledge: Similar to ZK-SNARK, this also represents "zero-knowledge", where the prover can prove to the verifier that they possess certain information without revealing the information itself.
Scalable: Emphasizes that the protocol focuses on enhancing the scalability of blockchain. ZK-STARK is able to compute and store data off-chain, exponentially improving scalability.
Transparent: Marks one of the most significant differences between ZK-STARK and ZK-SNARK. It uses publicly-available randomness to generate parameters, eliminating the need for trusted setups.
Argument of Knowledge: Similar to its meaning in ZK-SNARK, but using a different computational approach. It effectively eliminates the need for trusted setups by using collision-resistant hash functions.
The first detailed paper on STARK was published in 2018 by Eli Ben-Sasson, Iddo Bentov, Yinon Horeshy, and Michael Riabzev. Eli Ben-Sasson is a mathematician and computer scientist, the President and Co-founder of StarkWare, a co-inventor of STARK, FRI, and Zerocash protocols, and one of the seven board members of the StarkNet Foundation.
STARK is similar to STNARK as a proof and verification protocol. It allows for processing large-scale computations, generating a proof of correctness for the computation, and then verifying the proof with minimal computation. STARKs can play a crucial role in the scalability of blockchain, enabling off-chain computation and storage, with only a small fraction of the computation being verified on-chain. By performing minimal computation on-chain, verifiers can prove the integrity of a large amount of off-chain computation.
Comparison between ZK-STARK and ZK-SNARK#
ZK-STARKs address one of the main weaknesses of ZK-SNARKs, which is its reliance on a "trusted setup". ZK-SNARK requires an initial trusted setup phase to generate the randomness needed for generating zero-knowledge proofs. If the secret parameters generated during this phase are leaked, anyone who knows these parameters can generate fake proofs.
ZK-SNARK relies on elliptic curve cryptography (ECC), which is an encryption technique that uses the properties of elliptic curves to generate secure cryptographic keys. It is a popular choice for online security as these keys can be used to encode and decode data. ZK-STARK purely uses collision-resistant hash algorithms, making the parameters publicly transparent and eliminating the threat of quantum computing.
Proofs generated by SNARK are smaller in size, typically only a few hundred bytes, while proofs generated by STARK are usually several hundred kilobytes, making SNARK faster and consuming less gas for on-chain proof verification. However, due to STARK's off-chain computation and storage capabilities, as well as its faster proof generation speed, it is more scalable.
Applications of STARK#
STARK has been adopted by blockchain scalability solutions such as ZK-rollups and Layer-2. These protocols allow for off-chain computation and storage of data, and then submit zero-knowledge proofs on-chain to update the network's state.
StarkWare received a $12 million grant from the Ethereum Foundation, demonstrating Ethereum's support for and importance placed on STARK technology.
StarkWare has built two solutions, StarkEx and StarkNet, based on STARK. Co-founder Eli Sabasson has made an analogy, comparing StarkEx to a computer and StarkNet to the cloud. Purchasing StarkEx is like having your own customized computer, where each client has their own scaling computer. StarkNet, on the other hand, provides a network that is a general service, accessible to everyone who pays the fees.
StarkEx Provides Customized ToB Services for Applications#
StarkNet is a permissionless, decentralized, and censorship-resistant general layer 2 network.
In June 2020, the first STARK-based scaling solution, StarkEx, was deployed on the Ethereum mainnet. StarkEx has a prover that can perform large-scale computations off-chain and generate a STARK proof of their correctness, along with a verifier on-chain that verifies the proof.
StarkNet is a decentralized validity aggregator. It operates as a layer 2 network on Ethereum, extending Ethereum's computational capabilities without compromising its composability and security. All StarkNet transactions are batched and their validity is proven by STARKs and verified on Ethereum. Due to the exponentially smaller computational cost of verifying proofs compared to off-chain computation, StarkNet scales Ethereum's computational capacity by several orders of magnitude.
Core Components of StarkNet#
Prover: A separate process that generates STARK proofs for verification. The prover submits the STARK proofs to the registered verifiers on Ethereum.
StarkNet Operating System: Updates the system's state based on received transactions. Supports the execution of StarkNet contracts.
StarkNet State: The state consists of contract code and contract storage.
StarkNet Contracts on Ethereum: Verify the proofs submitted by L2 and update the state, facilitating L1 ↔ L2 interactions.
StarkNet External Infrastructure
Full-State Nodes: Nodes in the StarkNet network used solely for querying the current StarkNet state. They can independently answer queries about the current state of the StarkNet network, including L1 state. They do not execute batch transactions or proof batches.
Sequencer Nodes: The main nodes of the StarkNet network. They implement the core functionality of sorting the transactions submitted to them. They execute StarkNet contract programs and ultimately update the state of StarkNet contracts.
Cairo#
A programming language developed by StarkWare engineers to support proving general computations. In the summer of 2020, Cairo first appeared on the Ethereum mainnet. Cairo stands for CPU Algebraic Intermediate Representation (AIR) and includes a single AIR for verifying the instruction set of this "CPU". It opens the door for more complex business logic, arbitrary computation statements, and faster, more secure encoding of proofs. Cairo programs can prove the execution of individual application logic. However, a Cairo program can also be a concatenation of multiple such applications, known as SHARP.
SHARP
Shared Prover: Gathers transactions from several independent applications and proves them in a single STARK proof. Applications combine their transaction batches to fill the capacity of the STARK proof more quickly. Transactions are processed at a higher rate and with lower latency.
Here, statements arrive one by one over time. When a certain capacity (or time) threshold is reached, a large combined statement (Train) is generated. The proof of this merged statement can only be proven after receiving all individual statements. This proof takes a long time to prove (approximately the sum of the time required to prove each individual statement).
The proof of a significantly large statement is ultimately limited by available computational resources such as memory. This practically limits the scalability of STARK proofs before recursive proving.
Recursive Proving#
Using STARK proofs, the time required to prove a statement is roughly linear to the time required to execute the statement. Additionally, if proving a statement takes T time, verifying the proof takes approximately log(T) time, which is often referred to as "logarithmic compression". In other words, with STARK, the time spent on verifying statements is much less than the time spent on computation.
Cairo allows for general computational expressions to be proven by STARK provers and verified by verifiers. So, we can also write a Cairo program to verify multiple STARK proofs. We can generate a single proof to verify the validity of multiple "upstream" proofs. This is what we refer to as recursive proving.
Recursive proving can further reduce the cost of on-chain verification and verification computation time. The development of recursive verifiers in Cairo also opens up the possibility of submitting proofs to StarkNet. This would allow for the construction of L3 on top of the public StarkNet (L2 network).
The low cost of on-chain verification will enable a new class of complex computations that were previously infeasible on Ethereum, such as AI, machine learning, 3D art, game physics engines, and more. These features make STARKs improve user experience and reduce gas costs while maintaining the security of the Ethereum settlement layer.