position” 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:
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 vote system example:
import jsonfrom 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')https://www.cairo-lang.org/docs/hello_cairo/voting.html
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.
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.
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.