Cleaopatra is a Rust implementation of the Cairo VM

Last update: Dec 28, 2022

Overview

Cleopatra Cairo VM

Cleaopatra is a Rust implementation of the Cairo VM. The VM is fully functional but we don't support builtins or hints yet. We are working on it.

Running Cleopatra

Compile with cargo build --release, once the binary is built, it can be found in target/release/ under the name cleopatra-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/cleopatra_cairo.git
cd cleopatra_cairo

cargo build --release
./target/release/cleopatra-run tests/support/fibonacci_compiled.json

Testing

Run the test suite with cargo:

cargo test

Code Coverage

Track of the project's code coverage: Codecov.

Cleopatra benchmarks:

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

Execution time with Criterion
Flamegraph

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.

Computational integrity and Zero Knowledge Proofs

Basics

ZK SNARKs

ZK STARKs

Introduction:

Vitalik Buterin's blog series on zk-STARKs:

Alan Szepieniec's STARK tutorial:

Anatomy of a STARK

StarkWare's STARK Math blog series:

Comments

Add CLI option to specify entrypoint
Configurable entrypoint

Description

As described in #180, it might be useful to be able to run another function than the main function as an entrypoint.

Checklist

[x] Linked to Github Issue

[x] Unit tests added

[x] Integration tests added.
opened by Bernardstanislas 15
ci: add gh-pages docs workflow
Description

Partially addresses #75, providing rendered documentation on github pages.

This pull adds a CI task and makefile target to build and deploy rustdocs.

The current benchmark CI task should be unaffected, though its template is being updated in PR#201 to link to the generated html docs.

Checklist

[x] Linked to Github Issue

[ ] Unit tests added

[ ] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by PartyLich 11
feat(CairoRunner): add a get_output function

Expose the raw output

Description

Atm, you can only print the execution output. I need a way to get it directly from the lib, without printing it. write_output now wrap the new get_output

opened by tdelabro 8
Chore: Separate each builtin into a different file
Separate each builtin into a different file

Description

Issue #195

Moves the implementation of each builtin runner into its own file.

Export paths remain unchanged.

No additional tests have been added. Functionality should not be affected, it's just a reorganization chore

Checklist

[x] Linked to Github Issue

[ ] Unit tests added

[ ] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by PartyLich 6
Implement `get_memory_segment_addresses` for builtins
Implement get_memory_segment_addresses for builtins

Description

Implementation of get_memory_segment_addresses for builtins.

Checklist

[ ] Linked to Github Issue

[x] Unit tests added

[ ] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by azteca1998 5
Add implementation for hint on assert_not_zero (math.cairo)
Add implementation for hint on assert_not_zero (math.cairo)

Add implementation of assert_not_zero cairo hint (math.cairo) https://github.com/starkware-libs/cairo-lang/blob/167b28bcd940fd25ea3816204fa882a0b0a49603/src/starkware/cairo/common/math.cairo#L4

Checklist

[ ] Linked to Github Issue

[x] Unit tests added

[x] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by pefontana 5
Finish `CairoRunner::end_run()`'s `proof_mode` section.
Finish CairoRunner::end_run()'s proof_mode section

Description

Finish CairoRunner::end_run()'s proof_mode section.

Checklist

[ ] Linked to Github Issue

[ ] Unit tests added

[ ] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by azteca1998 4
Extract constants from program and pass them to `HintProcessor::execute_hint`
Extract constants from program and pass them to HintProcessor::execute_hint

Description

Allow hint processors to use constants defined in the program specification. Following issue #423.

Checklist

[x] Linked to Github Issue

[x] Unit tests added

[ ] Integration tests added.

[x] This change requires new documentation.

[x] Documentation has been added/updated.
opened by azteca1998 4
pow and math_cmp integration test
pow and math_cmp integration test

Description

The cairo_programs/math_cmp_is_le_felt.cairo was really short, so it was replaced with cairo_programs/math_cmp.cairo that tests all the math_cmp functions.

Add integration test: cairo_programs/math_cmp_and_pow_integration_test.cairo that the all the pow and math_cmp functions

Checklist

[ ] Linked to Github Issue

[ ] Unit tests added

[x] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by pefontana 4
Redesign hints processing
Our current hint handling has a few issues:

It exposes the whole VM state, limiting how much of the inner workings of the VM we can change further down the road;

It forces all the processing to happen during program execution, without the ability to validate/preprocess beforehand;

Relies too much in &mut vm, which forces a lot of cloning to make the borrow checker happy;

It's, thus, too unfriendly towards custom hint processors.

This ticket is not about directly solving the issues, as that will probably take several iterations that may be done independently. This is about discussing how to solve them. Any feedback is welcome.

My current proposal is the following:

Determine what hints actually need. At first sight, they seem to need the following:

Mutable access to AP;

Immutable access to FP and PC;

Mutable access to the VM memory (but in a proxy, as we shouldn't include accesses made by hints into the accessed addresses tracking, according to the Python VM);

Mutable access to the current hint execution scope;

The ability to add and remove one level from the scope;

A way to map referenced IDs to VM memory;

Access to AP tracking;

Refactor the current (WIP) trait to only receive what's needed;

Split the process into compilation (ran during program loading) and execution (ran during VM steps). The trait would now need to implement two or maybe three methods, as the executor is bound to the compiler.

The compiling step would need to store relevant data in a new custom structure, which represents the hint in some compiled form (maybe Python bytecode for Python executors, an enumerated value for our hardcoded hints or even the plain string as we use it now, lambdas, etc) and its auxiliary data, such as resolved references, PC (as it's already known), AP tracking information, etc.;

The processing step would receive the object previously created as well as the scope, the FP and AP, etc., and would then appropriately execute the compiled hint.

enhancement help wanted question hints
opened by Oppen 4
Add offsets as primitive

Offsets in instructions are specified to be signed 16 bits integers. We were keeping them as BigInts and operating with those, heavily slowing down execution. By converting them to isize we save about 30% of execution time, up to 50% in some cases.

opened by Oppen 3
Optimize accessed address tracking
This commit does a few things:

It uses chained iterators to avoid creating too many intermediary containers.

It specializes relocation for addresses for ad-hoc use when computing memory holes. This saves lot's of back and forth conversions and makes the code more readable, at the cost of a little bit of duplication.

Removes the accessed_addresses HashMap from CairoRunner. Filling it consumed almost half of the runtime in several programs.

Replaces CairoRunner::mark_as_accessed with VirtualMachine::mark_address_range_as_accessed to keep up with the previous change.

TODO:

Maybe go back with relocate_address or completely exploit the difference somehow.

Update cairo-rs-py to use the new VirtualMachine method.

Fix the new function to actually figure out if the run ended.

TITLE

Description

Description of the pull request changes and motivation.

Checklist

[ ] Linked to Github Issue

[ ] Unit tests added

[ ] Integration tests added.

[ ] This change requires new documentation.

[ ] Documentation has been added/updated.
opened by Oppen 1
Wrong builtins being passed to a test function
This issue relates to the testing of the get_allocated_memory_units function.

There's one test for each builtin runner, starting here.

Inside each test, there's a call to the program macro, and a string is passed to the builtins parameter. In some of the tests, this string seems to be incorrect

bitwise → “output”, “bitwise”

Problem: it calls two builtin runners, it should just call bitwise

ec_op → “ec_op”

hash → “pedersen”

range_check → “pedersen”

problem: it should call range_check

keccak → “keccak”
opened by martinacantaro 0
Increase code coverage even more
Adding tests for Keccak

Description

Add test to get_allocated_memory_units() to check if it returns the keccak builtin's allocated memory units correctly. Rename fn get_allocated_memory_units_bitwise_with_values() to fn get_allocated_memory_units_bitwise_with_items() to match the other tests naming convention

Checklist

[x] Linked to Github Issue https://github.com/lambdaclass/cairo-rs/issues/667

[x] Unit tests added

[-] Integration tests added.

[-] This change requires new documentation.

[-] Documentation has been added/updated.
opened by martinacantaro 1

Owner

Lambdaclass

A software company from another dimension

GitHub

STARK Cairo prover using lambdaworks

STARK Cairo prover using lambdaworks. 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.