What’s Starknet: a diffirent zkVM tech stack

March 14th, 2023

Summary

How Starknet Works: Compares to Ethereum, Starknet only needs a sequencer to executes calculations off-chain. Then, in order to reduce the amount of data, the prover generates a ZK-STARK proof for the transaction. Finally, verifier verifies the correctness of the proof on-chain, and finally bundles multiple L2 transactions into a single transaction on Ethereum (known as Rollup). Therefore, Starknet reduces the execution and storage cost on the chain, resulting in lower gas fees and higher TPS.
EVM-equivalent: Starknet has a ZK-friendly Cairo VM which is different from EVM, which means Starknet does not support EVM and Solidity. But with the introduction of the Solidity compiler Warp and the Cairo zkEVM Kakarot, Starknet can achieve type 3 EVM-equivalent.
STARK Proof System: Compared with other ZK proof systems, STARK is safer and more scalable. Its proof generation speed linearly scalable, and verification time and proof size are logarithmically scalable($O(polylog(N))$). The larger the proof, the lower the total cost and verification time. Additionally, STARK relies purely on hashing and information theory, so it has simpler cryptography assumptions, making it resistant to quantum attacks. But it’s disadvantage is that the size of the initial proof generation is large.
Cairo VM and Language: The Cairo VM is a STARK-friendly, Turing-complete von-Neumann CPU architecture. It can perform infinitely close to ASIC through software programming. And it has a programming language called Cairo, which is based on Cairo assembly AIR and Sierra. This makes it highly efficient and safe to compile. It is similar to Rust, have a certain learning difficulty. Cairo supports verifiers to verify programs through bytecode hashes, improves on-chain scalability and privacy. But Cairo is still updating.

In another article, we’d show the progress of decentralization of prover, sequencer, full node, client, Cairo, protocol and other Starknet network components.

🛒 How Starknet Works

First of all, let's see how Ethereum works. In Ethereum, verifying the correctness of transactions requires all nodes to check, validate, and execute each transaction. This process ensures the accuracy of the computation and broadcasts the resulting state changes across the network.

https://ethereum.org/en/developers/docs/evm/

But Starknet only executes calculations off-chain and generates a proof, then verifies the correctness of the proof on-chain, and finally bundles multiple L2 transactions into a single transaction on Ethereum. Accurately ZKR will write transactions to Ethereum as calldata, where data that is included in external calls to smart contract functions gets stored(similar to memory).

So Starknet can greatly improve network operation speed, reduce on-chain communication, increase network throughput, and therefore has higher TPS and lower gas compared to Ethereum.

In short, verifying the correctness of a calculation can be compared to a teacher needing to check whether the class has mastered a certain topic.

The Ethereum method is to check that each student (node) if has memorized the entire textbook (state history), while the Starknet method is to administering a paper test. The latter being more efficient and less costly, but still guaranteed to be safe.

As with most ZKRs such as Validity Rollup, Scroll, Polygon zkEVM and zkSync, Starknet has a class of roles called provers to generate proofs. And the verifiers verify the proofs as a contract on L1 (Ethereum).

Specifically, Starknet consists of five components: Prover, Sequencer, and Full Node on Starknet, as well as Verifier and Starknet Core (they are all deployed on Ethereum).

The following figure shows the architecture of Starknet, thanks to David for his great work!

The workflow of Starknet is as follows:

When we initiate a transaction on Starknet, an off-chain server—the sequencer—receives, sequences, validates, and bundles them into blocks. Execute the transaction, and then send the state transition to the Starknet Core contract.
The prover generates a proof for every transaction and send it to the verifier contract deployed on Ethereum.
The verifier sends the result of the validation to the StarkNet Core contract on Ethereum, and triggers a new set of Ethereum transactions from StarkNet Core contract to update the global state on-chain for record keeping. State transition is sent as "calldata" (Blob after EIP-4844) to save L1 transaction gas. These "metadata" can be decrypted by Starknet full nodes.

A full node stores state changes, metadata, proofs, and records all transactions performed in Rollup. It tracks the current global state of the system. Decrypting the "metadata" allows for the reconstruction of Starknet's history when necessary.

🚄EVM-equivalent

The Starknet network itself is not EVM-equivalent and has designed a ZK-friendly Cairo VM.

Instead of making circuits for the Ethernet opcode, Starknet has made its own set of assembly language, AIR (Algebraic Intermediate Representation), and high-level language Cairo that are more ZK-friendly.

https://drive.google.com/file/d/1dhZ5GtSK4sHCNcklGzNHfR-lSzplpD8J/view

The disadvantage of not being equivalent with EVM is that it cannot inherit the Ethereum’s Solidity code and toolchain, so there is no basis for large-scale migration of the Ethereum application ecosystem to Starknet. The Cairo language has a certain learning threshold for developers, and the Cairo toolchain and libraries are in their infancy.

However, designing independent VM has its benefits. For instance, Starknet's Cairo VM is more ZK-friendly and executes circuits more efficiently, resulting in higher TPS and lower gas usage in the future (more details to follow). Additionally, abandoning EVM design opens up many possibilities for application innovations that are not possible on Ethereum.

Starknet belongs to the type 4 level EVM-equivalent defined by Vitalik (strictly speaking, Starknet is a zkVM).

https://vitalik.eth.limo/general/2022/08/04/zkevm.html

Although Starknet “itself” is not EVM-equivalence, Starknet is still equivalent with Ethereum in other ways.

Warp is a Solidity-Cairo translator, now complete, developed by Nethermind. It possible for Warp to transpile Ethereum smart contracts to Starknet Cairo Contracts.

However, there are several features of Solidity that are not yet supported or do not have analogs in Starknet. While some of these features may be introduced in the future, others may not be possible due to fundamental differences between the platforms.

Kakarot is a zkEVM written in Cairo(so it’s a contract), bytecode-equivalent EVM and allow developers run any EVM bytecode program. Ethereum applications can be deployed on Starknet by deploying to Kakarot.

Kakarot is a work in progress and is not yet ready for production.

Starknet's ZK-friendly Cairo VM does not support EVM and Solidity. However, by introducing the Solidity compiler Warp and the Cairo zkEVM Kakarot, it will be possible for Starknet to achieve a type 3 EVM-equivalent.

🧬 STARK Proof System

Currently, there are many different proof systems available for generating and verifying proofs, such as Halo, PLONK, Groth16, Groth09, Marlin, and Plonky2, etc., which all belong to the SNARK proof system. Every proof system has a prover who generates proofs and a verifier who verifies the proofs. Different ZK projects almost use different proof systems. The main proof systems are SNARK and STARK. And Starknet uses STARK.

https://medium.com/alliancedao/zkps-in-web-3-now-and-the-future-21b459348f29

SNARK stands for Succinct Non-interactive Argument of Knowledge, while STARK stands for Scalable Transparent Argument of Knowledge. STARK is a special and innovative type of SNARK, with "S" changing from Succinct to Scalable and "T" standing for transparent, replacing the non-interactive feature.

https://www.altoros.com/blog/zero-knowledge-proof-improving-privacy-for-a-blockchain/

STARK has more innovations than SNARK. It does not need to rely on "trusted settings" like SNARKs. It also comes with simpler cryptography assumptions, avoids the need for elliptic curve, pairing, and exponential knowledge assumptions, relies purely on hashing and information theory, and is therefore resistant to quantum attacks. Generally speaking, STARK is more secure than SNARK.

https://research.thetie.io/zero-knowledge-starks-snarks/

And STARK is more scalable. Proof generation speed is linearly scalable, and verification time and proof size are logarithmically scalable. However, the disadvantage is that the generated proof size is larger. As the size of the proof increases, the cost of verification decreases marginally, meaning that the larger the proof, the lower the average cost.

Proof time scales linearly

Let's take a look at the doc for STARKs. The amount of time spent by the prover scales nearly linearly with the number of hash invocations.

At 80-bit security, STARK takes 1 second to execute for every 12,288 hash invocations, yielding 12,288 invocations per second; while it takes 10 seconds for every 98,304 hash invocations, yielding 9,830 invocations per second. Therefore, we can know the amount of time spent by the prover scales nearly-linearly in the number of hash invocations, as shown in the following figure:

Verifier time and proof size scales logarithmically

As you can see on the left, when the hash invocations is increased from 3,072 to 49,152, the verification time increases from 40 ms to 60 ms. And when the hash invocations increases from 49,152 to 786,432, the verification time only increases from 60 ms to 80 ms. The proof size is the same. Therefore, we can conclude that the more hash invocations, the shorter the average verification time and the smaller the average proof size.

As an example: Verification of the proofs of two programs of 1 million steps

● Total verification cost of each verified separately: $2 log2(T) \approx 794$

● Total verification cost of both verified together: $log2(2T) \approx 438$

Cost reduction of factor 1.8 (or almost 2)

All the experiments, for both the prover and the verifier, were run on the same machine with the following specifications:

Operating-System: Linux 5.3.0-51-generic x86 64.
CPU: Intel(R) Core(TM) i7-7700K @ 4.20GHz (4 cores, 2 threads per core).
RAM: 16GB DDR4 (8GB × 2, Speed: 2667 MHz)
While the prover uses multi-threading, in all of the experiments the verifier was restricted to utilize only a single thread.

Recursive Proving

A universal and succinct proof/argument of knowledge system, such as STARKs, can be used to incrementally verify computation. This means that a computation can generate a proof that attests to the correctness of a previous instance of that computation. This concept is known informally as "recursive proof composition" or "recursive STARKs.”

In other words, a recursive STARK prover would generate a proof for a statement saying the state of a system can be moved from a to a+1 because the prover has verified a (recursive) proof attesting to the computational integrity of a and has faithfully executed the computation on the state a, reaching the new state a+1.

In short, you can understand that the recursive proving combines two proofs, a and a+1, into a single proof. As the following figure shows:

https://medium.com/starkware/recursive-starks-78f8dd401025

In this example, four statements are sent to SHARP (a Verifier) and each statement is proven in parallel. Then, each pair of proofs is validated by a Recursive Verifier statement, which is a Cairo program that verifies a STARK proof, and a proof is generated for each validation. This Recursive Verifier statement confirms that two proofs have been verified to be correct. Next, the two proofs are merged again by another Recursive Verifier statement. This results in one proof that attests to all four original statements. Finally, this proof can be submitted on-chain and verified by a Solidity verifier smart contract.

According to Eli Ben-Sasson, co-founder of StarkWare, the new recursive validity proofs have the potential to rollup to 60 million transactions into a single one on the Ethereum blockchain.

⭐Cairo VM and Cairo Language

The Cairo VM is a STARK-friendly, Turing-complete von-Neumann CPU architecture. It includes a programming language called Cairo, which is based on Cairo assembly and AIR (Algebraic Intermediate Representations), making it highly efficient to compile.

Let's first take a look at Cairo VM. Cairo VM is a parallel state machine that allows transactions to be executed concurrently, significantly increasing TPS. In contrast, EVM is a serial state machine.

Cairo is a smart contract language that can be deployed on or off Starknet. Any Cairo program can generate STARK proofs. Its syntax is similar to Rust.

This a Cairo voting system example:

import json

from starkware.crypto.signature.signature import (
    pedersen_hash, private_to_stark_key, sign)

# Set an identifier that will represent what we're voting for.
# This will appear in the user's signature to distinguish
# between different polls.
POLL_ID = 10018

# Generate key pairs.
priv_keys = []
pub_keys = []

for i in range(10):
    priv_key = 123456 * i + 654321  # See "Safety note" below.
    priv_keys.append(priv_key)

    pub_key = private_to_stark_key(priv_key)
    pub_keys.append(pub_key)

# Generate 3 votes of voters 3, 5, and 8.
votes = []
for (voter_id, vote) in [(3, 0), (5, 1), (8, 0)]:
    r, s = sign(
        msg_hash=pedersen_hash(POLL_ID, vote),
        priv_key=priv_keys[voter_id])
    votes.append({
        'voter_id': voter_id,
        'vote': vote,
        'r': hex(r),
        's': hex(s),
    })

# Write the data (public keys and votes) to a JSON file.
input_data = {
    'public_keys': list(map(hex, pub_keys)),
    'votes': votes,
}

with open('voting_input.json', 'w') as f:
    json.dump(input_data, f, indent=4)
    f.write('\n')

Cairo programs are collections of assembly code, and Cairo developers will write smart contracts in the high-level language Cairo rather than Cairo assembly. When we write a Cairo program, the Cairo compiler will compile the Cairo code into Cairo assembly, and the Cairo assembler will take the assembly code and generate Cairo bytecode (which runs on the Cairo CPU) to be executed in the Cairo VM.

Here are some Cairo's features.

Bootloading: Loading programs from their hash

A program may write the bytecode of another program to memory and then set the Program Counter to point to that memory segment, thus starting the execution of the other program.

One specific use of this idea is “Bootloading from hash”: A program, called “the bootloader” computes and outputs the hash of the bytecode of another program and then starts executing it as above. This way, the verifier only needs to know the hash of the program being executed and not its full bytecode.

This improves both privacy and scalability:

Privacy: the verifier can verify the execution of a program without knowing what the computation does.
Scalability: assuming the program hash is known to the verifier, the verification time does not depend linearly on the program size, as would be the case if the program – rather than its hash – were given as input to the verifier. Verification time and program size have a logarithmic relationship, as mentioned in the STARK section.

CPU Architecture

Cairo VM is flexible. It can be infinitely close to the performance of AISC through software programming.

Builtins

Developers can debug and use the internal setting function directly to reduce the amount of calculation development needed without converting any code.

https://medium.com/@pban/demystifying-cairo-white-paper-part-i-b71976ad0108

The circuit represented by the ASIC chip or the experiment described in the developer's mathematics is equivalent to Cairo's circuit. However, Cairo is still being updated, and the latest version is called Cairo 1.0.

https://medium.com/starkware/cairo-1-0-aa96eefb19a0

The main addition in Cairo 1.0 is Sierra (Safe Intermediate Representation). It serves as a new intermediate representation layer between Cairo 1.0 and Cairo bytecode. Sierra’s goal is to ensure that every Cairo run — i.e. a Cairo program and its input — can be proven.

Acknowledgement

Special thanks to Cyberight Capital for supporting this article.

Cyberight Capital is an alternative investment institution. We discover the valid potential points of the industry by changing roles and respect for people and technology. Focusing on Humanist, Technology Driven, Independent Thinking.