What Is a zk-STARK and How Does It Work?

What Is a zk-STARK?

A zk-STARK is a cryptographic way to prove that a computation is correct, without the person checking the proof having to run the full computation again. Thanks to the zero-knowledge property, certain data used in the computation can also stay hidden.

The acronym stands for Zero-Knowledge Scalable Transparent ARgument of Knowledge. That sounds technical, but the parts are pretty easy to explain:

• Zero-Knowledge: you can prove that something is true without revealing the underlying secret information.
• Scalable: even with large computations, the proof can still be checked relatively efficiently.
• Transparent: no trusted setup is needed. That means there does not have to be a special setup beforehand where secret information is created and then safely destroyed.
• Argument of Knowledge: a valid proof shows that the creator has the information needed to carry out the computation correctly. That makes it extremely hard to fake a valid proof.

In crypto, this is especially useful when large computations are done outside the blockchain. For example, a system can process many transactions off-chain and then send one proof to the blockchain. The blockchain does not have to run every computation again, but only checks whether the submitted proof is valid.

Example: Suppose thousands of transactions are processed outside Ethereum. Instead of redoing all those transactions on Ethereum, a system can generate one zk-STARK that proves the whole batch was processed according to the rules. Ethereum then only has to check that proof.

The foundation for STARKs was described in 2018 by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. The system was designed to make large computations efficiently verifiable without a trusted setup.

Key Takeaways

• A zk-STARK proves that a computation was carried out correctly without doing the whole thing again.
• Zero knowledge can keep private input hidden, but it is not automatically present in every STARK application.
• STARKs do not need a trusted setup with secret parameters.
• In rollups, many off-chain transactions can be checked on a blockchain with one validity proof.
• The technique can be used for both blockchain scaling and verifiable computations outside crypto.

How Does a zk-STARK Work?

A zk-STARK turns a large computation into a form that is much easier to verify. The party doing the computation, the prover, then creates a cryptographic proof. The verifier checks that proof without redoing the full original computation.

Simply put: the prover does the heavy computing work, and the verifier uses a set of cryptographic and mathematical checks to confirm that the result is correct.

At a high level, it works like this:

1. The computation is turned into mathematical rules: First, the rules that every step of the computation must follow are defined. With STARKs, this often happens through something called Algebraic Intermediate Representation (AIR). You can think of this as a mathematical description of what is and is not allowed during the computation.

2. The prover records all computation steps: The prover runs the computation and creates what is called an execution trace. You can think of this as a large table that keeps track of the different steps in the computation.

3. The data is recorded cryptographically: The prover processes this data mathematically and records it with cryptographic commitments, for example using a Merkle tree. That way, the prover cannot just change the data afterward.

4. The verifier checks a selection of the data: Next, checks are performed at unpredictable points. The verifier checks, among other things, whether the data matches the earlier commitments and whether the mathematical rules of the computation were followed. STARKs use a technique called FRI for this. It makes it possible to efficiently check whether the mathematical functions used have the right form, without checking every piece of data individually.

5. The proof is verified If all checks pass, the verifier has strong cryptographic assurance that the computation was carried out correctly. The full computation does not have to be run again for that. When used on a blockchain, the prover can send the final proof to a smart contract. That contract checks the proof and only accepts the new result if it is valid. StarkWare, for example, uses on-chain verifiers on Ethereum to check STARK proofs.

Example: Suppose a rollup processes 1,000 transactions outside Ethereum. The rollup performs all the computations and then creates one proof showing that the transactions were processed according to the rules. Ethereum does not have to run all 1,000 transactions again. Instead, a smart contract checks the proof. If it is valid, the rollup’s new state can be accepted.

This makes zk-STARKs especially interesting for scalability: a lot of computation can happen outside the blockchain, while the blockchain can still cryptographically check whether the result is correct.

What Are Zero-Knowledge Proofs?

A zero-knowledge proof makes it possible to prove that a statement is true without revealing the secret information behind that statement.

Simply put: the prover shows the verifier that something is correct without having to share all the underlying data.

A zero-knowledge proof has three important properties:

• Completeness: if the statement is true and the prover does everything correctly, the verifier can accept the proof.
• Soundness: someone trying to prove a false statement has only a negligible chance of getting away with it.
• Zero knowledge: the verifier does not learn any extra secret information, beyond the fact that the statement is true.

Example: A system can prove that a batch of transactions was processed according to all the rules, without making certain private details from those transactions public.

In a rollup, the public statement might be that a new state root comes from a valid sequence of transactions. Which data stays hidden depends on how the proof system and the application are designed.

Important to know: a validity proof does not automatically provide privacy. A system can cryptographically prove that transactions were processed correctly while the transaction data itself is still public. For privacy, the zero-knowledge property has to be intentionally built into the system.

What Is the Role of STARKs?

STARKs are the proof system that makes it possible to prove and verify large computations efficiently without a trusted setup.

The zero-knowledge property determines which information can stay hidden. The STARK technique makes sure the verifier can efficiently check whether the computation was carried out according to the rules.

An important feature of STARKs is that they are transparent. There is no trusted setup where secret cryptographic parameters are created in advance and then have to be safely destroyed. Instead, the system relies in part on public randomness and cryptographic hash functions.

STARKs also use techniques like FRI, which makes it possible to efficiently check whether the mathematical structure behind the proof is correct.

The term Argument of Knowledge means that a prover cannot just make a valid proof out of nowhere. Under the system’s security assumptions, the prover must have the information needed to carry out the computation correctly.

What Are zk-STARKs Used For?

zk-STARKs are mainly used to run large computations outside a blockchain and then prove with one cryptographic proof that the result is correct. One major use case for this is validity rollups.

In such a rollup, many transactions are processed outside the base layer. Then a proof is sent to the blockchain showing that the new state was created from the old state according to the rules.

That is useful because the base layer does not have to run all the computations again. The cost of one proof can be spread across a large group of transactions.

A well-known example is StarkEx. This system uses STARK proofs to process large numbers of transactions for applications like trading, payments, gaming, and NFTs. The transactions are bundled, after which a proof is created and checked by a smart contract on Ethereum.

STARK technology can also be used outside crypto. In principle, the technique works for situations where you want to prove that a large computation was carried out correctly without the verifier having to redo all the work. With zero knowledge, certain underlying data can also stay hidden.

A proof does not solve everything on its own. In rollups, for example, it is still important where the transaction data is available. A valid proof shows that the computation follows the recorded rules, but it does not automatically guarantee that all data is available.

Which Blockchains Use STARKs?

The best-known example of a blockchain network that uses STARK proofs is Starknet. Starknet is a Layer 2 on top of Ethereum that processes many transactions outside Ethereum and then sends a STARK proof to Ethereum.

Ethereum checks this proof to confirm that Starknet’s new state was calculated correctly. That means Ethereum does not have to re-execute every transaction that happens on Starknet individually.

StarkEx also uses STARK proofs, but StarkEx is not a standalone blockchain. It is a scaling solution that lets different crypto applications process large numbers of transactions outside Ethereum and then cryptographically prove that the computations were carried out correctly.

So Ethereum itself does not use STARKs as its own consensus or transaction mechanism. The network can, however, verify STARK proofs submitted by applications and Layer 2 networks like Starknet.

Important to know: using STARK proofs does not automatically mean transactions are private. Starknet uses STARK validity proofs to prove that computations were carried out correctly, while zero-knowledge privacy is a separate property.

What Are the Benefits of zk-STARKs?

zk-STARKs make it possible to verify large computations much more efficiently than if every participant had to run all the computations again.

The main benefits are:

• No trusted setup: STARKs do not need a prior ceremony where secret cryptographic information is created and then safely destroyed.
• Efficient verification: the verifier can check a large computation without redoing every single step.
• Good for scalability: one proof can show the correct execution of a large batch of transactions, allowing blockchains to process more transactions outside the base layer.
• Potential for privacy: when zero knowledge is built into the system, certain private data can stay hidden while the computation is still verifiable.
• Hash-based security: for their proving layer, STARKs rely on cryptographic hash functions instead of the elliptic-curve pairings used in many classic SNARK systems.

Because of that hash-based approach, STARKs are also often seen as better prepared for a future with powerful quantum computers. Well-known quantum algorithms are a bigger problem for many elliptic-curve constructions than for well-chosen cryptographic hash functions.

That does not mean every application using STARKs is automatically fully quantum-safe. The hash functions used, the parameters, the implementation, and other cryptographic parts of the system still matter.

What Are the Limitations of zk-STARKs?

zk-STARKs also have downsides. In particular, creating a proof can take a lot of computing power and memory. So the heavy work does not disappear, but is mostly shifted to the prover.

In addition, STARK proofs are usually larger than proofs in many classic zk-SNARK systems. That can mean more data has to be processed when a proof is verified on a blockchain.

Other limitations include:

• Technical complexity: developers have to correctly convert computations into a form that the proof system can verify.
• Proof generation costs: creating proofs can require a lot of computing power and therefore come with costs.
• The proof only checks the recorded rules: if the application logic itself contains a bug, a valid proof only proves that those faulty rules were followed correctly.
• Privacy is not automatic: a STARK-based system can use validity proofs without keeping transaction data secret.

In short: a STARK proof can strongly prove that a certain computation was carried out according to the recorded rules, but it cannot decide whether those rules themselves were designed well.

What Is the Difference Between zk-STARKs and zk-SNARKs?

zk-STARKs and zk-SNARKs have the same general goal: to efficiently prove that a computation was carried out correctly without the verifier having to run the full computation again.

The main difference is the cryptographic technique used to do that.

One major advantage of zk-SNARKs is that proofs can be very small in many systems. That makes them attractive when the amount of data that has to be verified on-chain needs to stay as small as possible.

zk-STARKs usually have larger proofs, but they do not need a trusted setup and use different cryptographic assumptions. That makes them especially attractive for large computations and applications where transparency of the setup matters.

It is also important not to lump all zk-SNARKs together. zk-SNARK is a broad term for multiple proof systems. Not every SNARK uses the same cryptography, and not every variant requires the same kind of trusted setup.

For both techniques, a validity proof does not automatically mean privacy. Zero knowledge has to be part of the specific proof system and application.

Conclusion

A zk-STARK is a cryptographic technique that lets you prove a large computation was carried out correctly without the verifier having to run the full computation again.

That makes zk-STARKs especially interesting for blockchain scalability. Rollups can process large numbers of transactions outside the base layer and then use one proof to show that the result is correct.

Key advantages are the transparent design without a trusted setup and the efficient verification of large computations. The tradeoff is larger proofs, a lot of work for the prover, and technical complexity.

So zk-STARKs are mainly a way to make large computations efficiently and cryptographically verifiable. Privacy can be part of that, but it is not automatic.