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: Like 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 the protocol's focus on enhancing the scalability of blockchain. ZK-STARK can perform off-chain computations and store data, 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 ZK-SNARK in meaning, 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 a founding scientist of Zcash. He is also one of the seven board members of the StarkNet Foundation.
STARK is similar to STNARK and is a proof and verification protocol. It allows for the processing of 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 computations 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 the 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 parameter lambda generated during this phase is leaked, anyone who knows this parameter 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 because 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.
The proofs generated by SNARK are smaller in size, usually only a few hundred bytes, while STARK proofs are typically 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 and faster proof generation, 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, with zero-knowledge proofs submitted 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 used an analogy to describe StarkEx and StarkNet as a computer and a cloud, respectively. Purchasing StarkEx is like having a customized computer, with each client having their own scaling computer. StarkNet, on the other hand, provides a network as a general service that anyone can pay for and use.
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 allows a prover to perform large-scale computations off-chain and generate a STARK proof of their correctness, which is then verified on-chain.
StarkNet is an effective aggregation of validity without permission. 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 STARK, which is then verified on Ethereum. Due to the exponentially smaller computational cost of verifying the proof 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 that supports proving general computations. Cairo first appeared on the Ethereum mainnet in the summer of 2020. 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 computational 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 takes 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 faster. 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 Statements 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 large Statement is ultimately limited by available computational resources such as memory. This effectively limits the scalability of STARK proofs before recursive proving.
Recursive Proving#
Using STARK proofs, the time required to prove a statement is roughly linear with 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 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 call recursive proving.
Recursive proving can further reduce the cost of on-chain verification and verification computation time. The development of a recursive verifier 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 computational applications that were previously infeasible on Ethereum, such as AI, machine learning, 3D art, and game physics engines. These features make STARKs improve user experience and reduce gas costs while maintaining the security of the Ethereum settlement layer.