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 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, 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 as a proof and verification protocol. It allows for processing large computations, generating a proof of correctness for the computation, and then verifying the proof with minimal computation. STARKs can play a crucial role in blockchain scalability by 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 "trusted setups". 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 with knowledge of these parameters can generate fake proofs.

ZK-SNARK relies on elliptic curve cryptography (ECC), which is a cryptographic technique that uses the properties of elliptic curves to generate secure cryptographic keys. This 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.

The proofs generated by SNARK are smaller in size, typically only a few hundred bytes, while STARK proofs are usually several hundred kilobytes. This makes SNARK faster and consumes less gas for on-chain proof verification. However, due to the off-chain computation and faster proof generation of STARK, 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 and importance of 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, where purchasing StarkEx is like having a customized computer, and each client has 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 and 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 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 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 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 computation statements, and faster, more secure encoding proofs. Cairo programs can prove the execution of individual application logic. However, a Cairo program can also be a concatenation of multiple such applications, called 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 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 once all individual Statements have been received. 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 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 verifying a statement 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 recursive verifier developed by 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, game physics engines, etc. These features improve user experience and reduce gas costs while maintaining the security of the Ethereum settlement layer.