ben2077 / cairo-rs

cairo-rs is a Rust implementation of the Cairo VM. Cairo 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

cairo-rs is a Rust implementation of the Cairo VM. The project used to be called cleopatra-cairo but after being feature complete we decided it was clearer to call the vm cairo-rs.

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

Dependencies

• Rust
• Cargo
• PyEnv for running the original VM and compiling cairo programs

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 to 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
./target/release/cairo-rs-run tests/support/fibonacci_compiled.json

WebAssembly

While cairo-rs is compatible with WebAssembly, it doesn't implement any bindings to it. Instead, create a new WebAssembly crate with cairo-rs as a dependency and implement the required functionality there.

Since mimalloc is not automatically compilable to WebAssembly, the cairo-rs dependency should disable the default features, which will in turn disable mimalloc.

WebAssembly doesn't support filesystem access unless building with WASI support, therefore cairo_run may not work as is. Running programs may require manual program, vm and runner initialization.

Testing

Run the test suite:

make test

Code Coverage

Track of the project's code coverage: Codecov.

cairo-rs 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

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

These 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

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.