omahs/cairo-rs

cairo-rs is a Rust implementation of the Cairo VM. Cairo (CPU Algebraic Intermediate Representation) is a programming language for writing provable programs, where one party can prove to another that a certain computation was executed correctly. Cairo and similar proof systems can be used to provide scalability to blockchains.

cairo-rs

Table of Contents

• About
• Getting Started
  • Dependencies
• Usage
  • Running cairo-rs
  • Running a function in a Cairo program with arguments
  • WebAssembly Demo
  • Testing
• Code Coverage
• Benchmarks
• Related Projects
• Documentation
  • Cairo
  • Original Cairo VM Internals
  • Compilers and Interpreters
  • Computational Integrity and Zero Knowledge Proofs
• Possible changes for the future
• Changelog
• License

About

cairo-rs is a Rust implementation of the Cairo VM.

The code of the original Cairo VM can be found here.

Getting Started

Dependencies

• Rust
• Cargo
• PyEnv for running the original VM and compiling cairo programs
• cairo-lang (optional)

Usage

Running cairo-rs

Compile with cargo build --release, once the binary is built, it can be found in target/release/ under the name cairo-rs-run. To run a compiled json program through the VM, call the executable giving it the path and name of the file to be executed.

Full compilation and execution example:

git clone https://github.com/lambdaclass/cairo-rs.git

cd cairo-rs

cargo build --release

cairo-compile cairo_programs/abs_value_array.cairo --output cairo_programs/abs_value_array_compiled.json

target/release/cairo-rs-run cairo_programs/abs_value_array_compiled.json --layout all

Running a function in a Cairo program with arguments

When running a Cairo program directly using the Cairo-rs repository you would first need to prepare a couple of things.

1. Specify the cairo program and the function you want to run

let program =
        Program::from_file(Path::new(&file_path), Some(&func_name));

2. Instantiate the VM, the cairo_runner, the hint processor, and the entrypoint

let mut vm = VirtualMachine::new(
            BigInt::new(Sign::Plus, vec![1, 0, 0, 0, 0, 0, 17, 134217728]),
            false,
        );

let mut cairo_runner = CairoRunner::new(&program, "all", false);

let mut hint_processor = BuiltinHintProcessor::new_empty();

let entrypoint = program
        .identifiers
        .get(&format!("__main__.{}", &func_name))?
        .pc;

3. Lastly, initialize the builtins and segments.

cairo_runner.initialize_builtins(&mut vm)?;
cairo_runner.initialize_segments(&mut vm, None);

When using cairo-rs with the starknet devnet there are additional parameters that are part of the OS context passed on to the run_from_entrypoint function that we do not have here when using it directly. These parameters are, for example, initial stacks of the builtins, which are the base of each of them and are needed as they are the implicit arguments of the function.

 let _var = cairo_runner.run_from_entrypoint(
            entrypoint,
            vec![
                &mayberelocatable!(2),  //this is the entry point selector
                &MaybeRelocatable::from((2,0)) //this would be the output_ptr for example if our cairo function uses it
                ],
            false,
            true,
            true,
            &mut vm,
            &mut hint_processor,
        );

WebAssembly Demo

A demo on how to use cairo-rs with WebAssembly can be found here.

Testing

Run the test suite:

make test

Code Coverage

Track of the project's code coverage: Codecov.

Benchmarks

Running a Cairo program that gets the 1000th Fibonacci number we got the following benchmarks:

• Execution time with Criterion
• Flamegraph
• Github action results

Run the benchmark suite with cargo:

cargo bench

Related Projects

• starknet_in_rust: implementation of Starknet in Rust, powered by the cairo-rs VM.
• cairo-rs-py: Bindings for using cairo-rs from Python code.

Documentation

Cairo

• From Cairo Documentation: How Cairo Works
• Cairo – a Turing-complete STARK-friendly CPU architecturer
• A Verified Algebraic Representation of Cairo Program Execution
• Cairo Verifier in Rust

Original Cairo VM Internals

We wrote a document explaining how the Cairo VM works. It can be found here.

Compilers and Interpreters

This is a list of recommended books to learn how to implement a compiler or an interpreter.

• How I wrote my own "proper" programming language - Mukul Rathi
• Introduction to Compilers and Language Design - Douglas Thain
• Beautiful Racket - Matthew Flatt
• Crafting interpreters - Robert Nystrom
• Engineering a Compiler - Keith D. Cooper, Linda Torczon

StarkNet

• StarkNet's Architecture Review

Computational Integrity and Zero Knowledge Proofs

Basics

• Intro to zero knowledge proofs
• Security and Privacy for Crypto with Zero-Knowledge Proofs
• A Hands-On Tutorial for Zero-Knowledge Proofs Series

ZK SNARKs

• What are zk-SNARKs?
• Vitalik's introduction to how zk-SNARKs are possible
• Vitalik's post on quadratic arithmetic programs
• Why and How zk-SNARK Works - Maksym Petkus
• Comparing General Purpose zk-SNARKs
• Dark forest's intro + circuits PART 1
• Dark forest's intro + circuits PART 2

STARKs

Introduction:

• Cryptography Stack Exchange Answer
• Hasu gets STARK-pilled - with Eli Ben-Sasson
• Cairo for Blockchain Developers
• Why STARKs are the key to unlocking blockchain scalability
• STARKs whitepaper: Scalable, transparent, and post-quantum secure computational integrity
• STARKs vs. SNARKs: A Cambrian Explosion of Crypto Proofs

Vitalik Buterin's blog series on zk-STARKs:

• STARKs, part 1: Proofs with Polynomials
• STARKs, part 2: Thank Goodness it's FRI-day
• STARKs, part 3: Into the Weeds

Alan Szepieniec's STARK tutorial:

• Anatomy of a STARK

StarkWare's STARK Math blog series:

• STARK Math: The Journey Begins
• Arithmetization I
• Arithmetization II
• Low Degree Testing
• A Framework for Efficient STARKs

Possible changes for the future

• Make the alloc functionality an internal feature of the VM rather than a hint.

Changelog

Keep track of the latest changes here.

License

MIT