Cleaopatra is a Rust implementation of the Cairo VM

Last update: Jun 19, 2022

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:

Cairo

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:

StarkWare's STARK Math blog series:

GitHub

https://github.com/lambdaclass/cleopatra_cairo
Comments
  • 1. Refactor memory into HashMap

    Motivation: Change memory structure from matrix to HashMap in order to improve performance for larger programs. Issue: #109

    What was changed in this PR:

    • Change Memory structure to Hashmap
    • Change segment size calculation and relocation to not be dependent of the memory structure
    • Change initialize_segments method to not use Memory
    • Removed Error handling associated with the previous implementation of memory
    • Add function relocate_address (in relocatable.rs) + tests
    • Remove unused function from_relocatable_to_indexes

    Checklist

    • [x] Linked to Github Issue
    • [x] Unit tests added
    • [x] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by fmoletta at 2022-06-13 17:42
  • 2. Refactor Memory into matrix + Relocatable into usize

    Motivation: Improve current work by using more appropriate data structures

    What was changed:

    • Change Memory storage from HashMap to Matrix
    • Change Relocatable struct members from BigInt to usize
    • Change main in Program to optional usize
    • Add necessary function from_relocatable_to_segment_indexes
    • Adapt every method and tests accordingly
    • MemorySegmentManager now adds a new Vec to Memory when add() is called
    • Add the following checks when inserting into memory:
      • The memory segment dictated by the segment index must have been previously allocated (this happens during initialize_segements)
      • Elements can only be inserted contiguous to the previous one (enforcing continuous memory)(should be checked)
    • Change Memory::from to public method (used to be Trait)
    • Improve tests (Unified criteria for creating MaybeRelocatables to from)

    Checklist

    • [ ] Linked to Github Issue
    • [x] Unit tests added
    • [x] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by fmoletta at 2022-06-02 18:29
  • 3. [CU-#2t8y6yg] Add Codecov

    Add Codecov

    Add Codecov to keep track of the project coverage. Issue #41

    Checklist

    • [x] Linked to Github Issue
    • [ ] Unit tests added
    • [ ] Integration tests added.
    • [ ] This change requires new documentation.
    • [ ] Documentation has been added/updated.
    Reviewed by pefontana at 2022-05-26 15:07
  • 4. Add to_field_element conversion to write_output

    Motivation: The Cairo VM applies a conversion to numbers before printing them as program output, which affects larger numbers. This PR aims to add this missing conversion to the write_output method

    What was changed in this PR:

    • Add the function to_field_element, which converts a BigInt to another BigInt, changing its range from [0, prime] to [-prime/2, prime/2]
    • This function is now applied to each number before it is written in write_output
    • Add tests for the new function and for write_output
    • Remove panics from write_output

    Checklist

    • [ ] Linked to Github Issue
    • [x] Unit tests added
    • [x] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by fmoletta at 2022-06-16 16:54
  • 5. Struct integration test

    Struct integration test

    Description

    Add an integration test that checks if structs work correctly

    Checklist

    • [ ] Linked to Github Issue
    • [ ] Unit tests added
    • [x] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by Juan-M-V at 2022-06-16 12:32
  • 6. cleopatra vm fail to run my cairo program

    Here is my code:

    %builtins output pedersen
    
    from starkware.cairo.common.cairo_builtins import HashBuiltin
    from starkware.cairo.common.hash import hash2
    
    func main{output_ptr, pedersen_ptr: HashBuiltin*}():
        let (res) = hash2{hash_ptr=pedersen_ptr}(1, 2)
    
        res = [output_ptr]
    
        let output_ptr = output_ptr + 1
        return()
    end
    

    cairo-compile && cairo-run works

    cairo-compile check_hash.cairo --output check_hash_compiled.json
    cairo-run --program=check_hash_compiled.json --layout=small --print_output 
    Program output:
      -1025514936890165471153863463586721648332140962090141185746964417035414175707
    

    But cleaopatra doesn't

    cargo run -- ~/Documents/rusty-crew/cairo_test/check_hash_compiled.json  
        Finished dev [unoptimized + debuginfo] target(s) in 0.01s
         Running `target/debug/cleopatra-run /Users/tdelabro/Documents/rusty-crew/cairo_test/check_hash_compiled.json`
    thread 'main' panicked at 'Couldn't compute or deduce op1', src/vm/vm_core.rs:441:9
    note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
    

    Why is that ?

    Reviewed by tdelabro at 2022-06-16 10:28
  • 7. Fix range-check validation

    Motivation: Currently, range-check is applied to elements inserted during initialization in the range-check segment, and not to those inserted afterwards. This PR aims to validate the range of each element when they are inserted into the range-check builtin segment.

    What was changed in this PR:

    • Replace method validate_existing_memory for add_validation_rule in BuiltinRunner
    • Move validated_addresses to Memory
    • Add validation_rules to Memory (A HashMap containing validation_rules and their corresponding segment)
    • Add methods add_validation_rule, validate_memory_cell and validate_existing_memory to Memory
    • Initialize vm now adds the validation rules of each builtin before calling validate_existing_memory
    • Inserting an element into memory now runs validate_memory_cell on it after inserting

    Checklist

    • [ ] Linked to Github Issue
    • [x] Unit tests added
    • [x] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by fmoletta at 2022-06-15 18:50
  • 8. Remove todos

    Remove TODOs

    Description

    Remove TODO comments from code. resolves: #131

    Checklist

    • [x] Linked to Github Issue
    • [ ] Unit tests added
    • [ ] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by Juan-M-V at 2022-06-15 13:06
  • 9. Verify auto deductions

    Motivation: Add the method verify_auto_deductions, used to verify that each memory cell was deduced correctly.

    What was changed in this PR:

    • Add method verify_auto_deductions
    • Add tests for verify_auto_deductions for each builtin with a non-trivial deduce_memory_cell method

    Checklist

    • [ ] Linked to Github Issue
    • [ ] Unit tests added
    • [ ] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by fmoletta at 2022-06-14 20:23
  • 10. [CU-2x6r1cw] update documentation

    Update documentation

    Description

    • Rename folder docs/cleopatra_cairo_vm -> docs/python_vm
    • Move folder docs/diagram -> docs/python_vm/diagram

    Checklist

    • [ ] Linked to Github Issue
    • [ ] Unit tests added
    • [ ] Integration tests added.
    • [x] This change requires new documentation.
      • [x] Documentation has been added/updated.
    Reviewed by pefontana at 2022-06-14 16:37
  • 11. [CU-2xckwme] update criterion benchmarks

    Update criterion benchmarks

    Description

    • Update criterion benchmark and flamegraph
    • Change folder name ./benches -> ./bench

    Checklist

    • [ ] Linked to Github Issue
    • [ ] Unit tests added
    • [ ] Integration tests added.
    • [x] This change requires new documentation.
      • [x] Documentation has been added/updated.
    Reviewed by pefontana at 2022-06-14 16:14
  • 12. Trace encoding

    Trace Encoding

    Description

    Add a function to write the relocated trace to a file

    Checklist

    • [ ] Linked to Github Issue
    • [ ] Unit tests added
    • [ ] Integration tests added.
    • [ ] This change requires new documentation.
      • [ ] Documentation has been added/updated.
    Reviewed by Juan-M-V at 2022-06-16 14:44
  • 13. Implement Functionality for add method on MemorySegmentManagement

    Current documentation of add(&mut self, memory: &mut Memory, size: Option<usize>):

    If size is not None the segment is finalized with the given size

    is not implemented

    Reviewed by Juan-M-V at 2022-06-15 13:20
A Rust implementation of BIP-0039

bip39-rs A Rust implementation of BIP0039 Changes See the changelog file, or the Github releases for specific tags. Documentation Add bip39 to your Ca

Apr 4, 2022
Official Rust implementation of the Nimiq protocol
Official Rust implementation of the Nimiq protocol

Nimiq Core implementation in Rust (core-rs) Rust implementation of the Nimiq Blockchain Core Nimiq is a frictionless payment protocol for the web. Thi

Mar 2, 2022
Rust implementation of Zcash protocol

The Parity Zcash client. Gitter Blog: Parity teams up with Zcash Foundation for Parity Zcash client Installing from source Installing the snap Running

Jun 6, 2022
A (mostly) pure-Rust implementation of various cryptographic algorithms.

Rust-Crypto A (mostly) pure-Rust implementation of various common cryptographic algorithms. Rust-Crypto seeks to create practical, auditable, pure-Rus

Jun 19, 2022
A pure-Rust implementation of group operations on Ristretto and Curve25519
A pure-Rust implementation of group operations on Ristretto and Curve25519

curve25519-dalek A pure-Rust implementation of group operations on Ristretto and Curve25519. curve25519-dalek is a library providing group operations

Jun 15, 2022
[INACTIVE] TLS 1.2 implementation in Rust

suruga is Rust implementation of TLS 1.2. It currently implements some core parts of TLS 1.2, NIST P-256 ECDHE and chacha20-poly1305. Usage extern cra

Mar 10, 2022
A prototype implementation of the Host Identity Protocol v2 for bare-metal systems, written in pure-rust.
A prototype implementation of the Host Identity Protocol v2 for bare-metal systems, written in pure-rust.

Host Identity Protocol for bare-metal systems, using Rust I've been evaluating TLS replacements in constrained environments for a while now. Embedded

Jun 4, 2022
An implementation of the FP-Growth algorithm in pure Rust.

fp-growth-rs An implementation of the FP-Growth algorithm in pure Rust, which is inspired by enaeseth/python-fp-growth. Usage Add this to your Cargo.t

Feb 27, 2022
A pure-Rust implementation of various threshold secret sharing schemes

Threshold Secret Sharing Efficient pure-Rust library for secret sharing, offering efficient share generation and reconstruction for both traditional S

Jun 12, 2022
A Rust implementation of the Message Layer Security group messaging protocol

Molasses An extremely early implementation of the Message Layer Security group messaging protocol. This repo is based on draft 4 of the MLS protocol s

Apr 11, 2022
Pure Rust implementation of the RNCryptor cryptographic format by Rob Napier

rncryptor Rust Implementation of the RNCryptor spec This library implements the specification for the RNCryptor encrypted file format by Rob Napier. d

Apr 2, 2022
Implementation of the Web Cryptography specification in Rust.

[wip] webcrypto Implementation of the Web Cryptography specification in Rust. This crate hopes to ease interoperability between WASM and native target

Mar 7, 2022
Implementation of Plonk by Hand in rust

plonk-by-fingers This is a toy implementation of the excellent Joshua Fitzgerald Plonk by hand (part2) (part3) tutorial all written from scratch, do n

May 2, 2022
A Rust implementation of Trojan with QUIC tunnel, Lite-TLS and more.

Trojan-Oxide A Rust implementation of Trojan with QUIC tunnel, Lite-TLS and more. Overview Full support for the original Trojan Protocol, including TC

Jun 12, 2022
Pure Rust implementation of the Leighton Micali Signature scheme.

Leighton-Micali Hash-Based Signatures LMS implementation in Rust according to the IETF RFC 8554. This implementation is binary compatible with the ref

Jun 2, 2022
Rust implementation of Shamir's Secret Sharing

Horcrux - Rust implementation of Shamir's Secret Sharing This program is an example implementation of Shamir's Secret Sharing in Rust. You can find mo

Apr 13, 2022
Rust implementation of CAIP standards

Rust CAIP Standard Utilities Chain Agnostic Improvement Proposals (CAIP) is a set of standards for multi-chain interoperability. CAIP-2: Chain ID use

Nov 15, 2021
Implementation of Yao's Millionare problem in Rust
Implementation of Yao's Millionare problem in Rust

Yao's Millionaire Problem Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information

Dec 20, 2021
Ecoball Node is the Official Rust implementation of the Ecoball protocol.

Ecoball Node is the Official Rust implementation of the Ecoball protocol. It is a fork of OpenEthereum - https://github.com/openethereum/

Jun 9, 2022