Walkthroughs of Examples

This chapter will contain detailed walkthroughs of selected examples from the examples/ directory.

Fibonacci

The fibonacci example computes the n-th Fibonacci number, where n is a power of 2. The purpose of this example is to show how to perform a simple computation within the zkVM.

Guest Code

The guest program for the fibonacci example is located at examples/examples/fibonacci.rs.

extern crate ceno_rt;

fn main() {
    // Compute the (1 << log_n) 'th fibonacci number, using normal Rust code.
    let log_n: u32 = ceno_rt::read();
    let mut a = 0_u32;
    let mut b = 1_u32;
    let n = 1 << log_n;
    for _ in 0..n {
        let mut c = a + b;
        c %= 7919; // Modulus to prevent overflow.
        a = b;
        b = c;
    }
    // Constrain with public io
    ceno_rt::commit(&b);
}

The guest program reads a private input log_n from the host. This input determines the number of iterations to perform. The program then calculates n = 1 << log_n and computes the n-th Fibonacci number using a standard iterative approach. To prevent the numbers from growing too large, the computation is performed modulo 7919. Finally, the program commits the result back to the host as a public output.

This example demonstrates the basic workflow of a Ceno zkVM program: reading private inputs, performing computations, and committing public outputs. It shows that you can write standard Rust code for the guest, and the zkVM will execute it.

Is Prime

The is_prime example counts the number of prime numbers up to a given integer n. This example showcases a slightly more complex algorithm and control flow.

Guest Code

The guest program for the is_prime example is located at examples/examples/is_prime.rs.

extern crate ceno_rt;

fn is_prime(n: u32) -> bool {
    if n < 2 {
        return false;
    }
    let mut i = 2;
    while i * i <= n {
        if n.is_multiple_of(i) {
            return false;
        }
        i += 1;
    }

    true
}

fn main() {
    let n: u32 = ceno_rt::read();
    let mut cnt_primes = 0;

    for i in 0..=n {
        cnt_primes += is_prime(i) as u32;
    }

    if cnt_primes > 1000 * 1000 {
        panic!();
    }
}

The guest program reads an integer n from the host. It then iterates from 0 to n, checking if each number is prime using a helper function is_prime. The is_prime function implements the trial division method. The total count of prime numbers is accumulated in cnt_primes. If the count of primes exceeds a certain threshold, the program will panic. This demonstrates how to handle exceptional cases in the guest. The program does not commit any public output, but the proof generated by the zkVM still guarantees that the computation was performed correctly.

This example highlights the ability to define and use helper functions within the guest code, as well as the use of control flow constructs like loops and conditional statements.

BN254 Curve Syscalls

The bn254_curve_syscalls example demonstrates the use of syscalls for elliptic curve operations on the BN254 curve. This is useful for cryptographic applications that require curve arithmetic.

Guest Code

The guest program for the bn254_curve_syscalls example is located at examples/examples/bn254_curve_syscalls.rs.

// Test addition of two curve points. Assert result inside the guest
extern crate ceno_rt;
use ceno_syscall::{syscall_bn254_add, syscall_bn254_double};

use substrate_bn::{AffineG1, Fr, G1, Group};
fn bytes_to_words(bytes: [u8; 64]) -> [u32; 16] {
    let mut bytes = bytes;
    // Reverse the order of bytes for each coordinate
    bytes[0..32].reverse();
    bytes[32..].reverse();
    std::array::from_fn(|i| u32::from_le_bytes(bytes[4 * i..4 * (i + 1)].try_into().unwrap()))
}

fn g1_to_words(elem: G1) -> [u32; 16] {
    let elem = AffineG1::from_jacobian(elem).unwrap();
    let mut x_bytes = [0u8; 32];
    elem.x().to_big_endian(&mut x_bytes).unwrap();
    let mut y_bytes = [0u8; 32];
    elem.y().to_big_endian(&mut y_bytes).unwrap();

    let mut bytes = [0u8; 64];
    bytes[..32].copy_from_slice(&x_bytes);
    bytes[32..].copy_from_slice(&y_bytes);

    bytes_to_words(bytes)
}

fn main() {
    let a = G1::one() * Fr::from_str("237").unwrap();
    let b = G1::one() * Fr::from_str("450").unwrap();
    let mut a = g1_to_words(a);
    let b = g1_to_words(b);

    log_state(&a);
    log_state(&b);

    syscall_bn254_add(&mut a, &b);

    assert_eq!(
        a,
        [
            3533671058, 384027398, 1667527989, 405931240, 1244739547, 3008185164, 3438692308,
            533547881, 4111479971, 1966599592, 1118334819, 3045025257, 3188923637, 1210932908,
            947531184, 656119894
        ]
    );
    log_state(&a);

    let c = G1::one() * Fr::from_str("343").unwrap();
    let mut c = g1_to_words(c);
    log_state(&c);

    syscall_bn254_double(&mut c);
    log_state(&c);

    let one = g1_to_words(G1::one());
    log_state(&one);

    syscall_bn254_add(&mut c, &one);
    log_state(&c);

    // 2 * 343 + 1 == 237 + 450, one hopes
    assert_eq!(a, c);
}

#[cfg(debug_assertions)]
fn log_state(state: &[u32]) {
    use ceno_rt::info_out;
    info_out().write_frame(unsafe {
        core::slice::from_raw_parts(state.as_ptr() as *const u8, size_of_val(state))
    });
}

#[cfg(not(debug_assertions))]
fn log_state(_state: &[u32]) {}

The guest program initializes two points on the BN254 curve. It then uses the syscall_bn254_add syscall to add the two points and asserts that the result is correct by comparing it with a pre-computed value. It also demonstrates the use of the syscall_bn254_double syscall to double a point. The program includes helper functions to convert between different representations of curve points.

This example showcases how to leverage syscalls to perform complex and computationally expensive operations. By using syscalls, the guest can delegate these operations to the host, which can often execute them more efficiently. The guest can still verify the results of the syscalls to ensure the integrity of the computation.

Ceno RT Alloc

The ceno_rt_alloc example shows how to use the allocator in the Ceno runtime to allocate memory on the heap.

Guest Code

The guest program for the ceno_rt_alloc example is located at examples/examples/ceno_rt_alloc.rs.

use core::ptr::{addr_of, read_volatile};

extern crate ceno_rt;

extern crate alloc;
use alloc::{vec, vec::Vec};

static mut OUTPUT: u32 = 0;

fn main() {
    // Test writing to a global variable.
    unsafe {
        OUTPUT = 0xf00d;
        black_box(addr_of!(OUTPUT));
    }

    // Test writing to the heap.
    let v: Vec<u32> = vec![0xbeef];
    black_box(&v[0]);

    // Test writing to a larger vector on the heap
    let mut v: Vec<u32> = vec![0; 128 * 1024];
    ceno_syscall::syscall_phantom_log_pc_cycle("finish allocation");
    v[999] = 0xdead_beef;
    black_box(&v[0]);

    ceno_syscall::syscall_phantom_log_pc_cycle("start fibonacci");
    let log_n: u32 = 12;
    let mut a = 0_u32;
    let mut b = 1_u32;
    let n = 1 << log_n;
    for _ in 0..n {
        let mut c = a + b;
        c %= 7919; // Modulus to prevent overflow.
        a = b;
        b = c;
    }
    ceno_syscall::syscall_phantom_log_pc_cycle("end fibonacci");

    // write to heap which allocated earlier shard
    v[999] = 0xbeef_dead;
    let mut v: Vec<u32> = vec![0; 128 * 1024];
    // write to heap allocate in current non-first shard
    v[0] = 0xdead_beef;
}

/// Prevent compiler optimizations.
fn black_box<T>(x: *const T) -> T {
    unsafe { read_volatile(x) }
}

The guest program demonstrates three different memory operations. First, it writes to a global static variable. Second, it allocates a small Vec on the heap. Third, it allocates a much larger Vec on the heap and writes a value to an element in it. The black_box function is used to ensure that the compiler does not optimize away these memory operations.

This example is important for understanding how memory management works in the Ceno zkVM. It shows that the guest has access to both static memory and heap memory, and can perform dynamic memory allocation.

Keccak Syscall

The keccak_syscall example demonstrates how to use a syscall to perform the Keccak permutation, which is the core of the Keccak hash function (used in SHA-3).

Guest Code

The guest program for the keccak_syscall example is located at examples/examples/keccak_syscall.rs.

//! Compute the Keccak permutation using a syscall.
//!
//! Iterate multiple times and log the state after each iteration.

extern crate ceno_rt;
use ceno_syscall::syscall_keccak_permute;

const ITERATIONS: usize = 100;

fn main() {
    let mut state = [0_u64; 25];

    for i in 0..ITERATIONS {
        syscall_keccak_permute(&mut state);
        if i == 0 {
            log_state(&state);
        }
    }
}

#[cfg(debug_assertions)]
fn log_state(state: &[u64; 25]) {
    use ceno_rt::info_out;
    info_out().write_frame(unsafe {
        core::slice::from_raw_parts(state.as_ptr() as *const u8, state.len() * size_of::<u64>())
    });
}

#[cfg(not(debug_assertions))]
fn log_state(_state: &[u64; 25]) {}

The guest program initializes a 25-word state and then enters a loop where it repeatedly applies the Keccak permutation to the state using the syscall_keccak_permute syscall. The log_state function is used to log the state after the first permutation, which can be useful for debugging.

This example further illustrates the power of syscalls. The Keccak permutation is a complex operation, and implementing it efficiently in the guest would be challenging. By providing it as a syscall, the Ceno platform makes it easy for guest programs to use this important cryptographic primitive.

Median

The median example shows how to find the median of a list of numbers. It demonstrates a common pattern where the host provides a candidate answer, and the guest verifies it.

Guest Code

The guest program for the median example is located at examples/examples/median.rs.

//! Find the median of a collection of numbers.
//!
//! Of course, we are asking our good friend, the host, for help, but we still need to verify the answer.
extern crate ceno_rt;
use ceno_rt::debug_println;
#[cfg(debug_assertions)]
use core::fmt::Write;

fn main() {
    let numbers: Vec<u32> = ceno_rt::read();
    let median_candidate: u32 = ceno_rt::read();
    let smaller = numbers.iter().filter(|x| **x < median_candidate).count();
    assert_eq!(smaller, numbers.len() / 2);
    debug_println!("{}", median_candidate);
}

The guest program reads a list of numbers and a median candidate from the host. It then verifies that the candidate is indeed the median by counting the number of elements in the list that are smaller than the candidate. If the count is equal to half the length of the list, the assertion passes, and the program successfully completes.

This example showcases a powerful pattern for zkVM programming: verifiable computation. The host, which is not constrained by the limitations of the zkVM, can perform a complex computation (like finding the median of a large list) and then provide the answer to the guest. The guest’s task is then to perform a much simpler computation to verify that the host’s answer is correct. This allows for the verification of complex computations that would be too expensive to perform directly in the zkVM.

Sorting

The sorting example demonstrates how to sort a list of numbers inside the guest.

Guest Code

The guest program for the sorting example is located at examples/examples/sorting.rs.

extern crate ceno_rt;
use ceno_rt::debug_println;
#[cfg(debug_assertions)]
use core::fmt::Write;

fn main() {
    let mut scratch: Vec<u32> = ceno_rt::read();
    scratch.sort();
    // Print any output you feel like, eg the first element of the sorted vector:
    debug_println!("{}", scratch[0]);
}

The guest program reads a list of numbers from the host, creates a mutable copy of it, and then sorts the copy using the standard sort method from the Rust standard library. The debug_println! macro is used to print the first element of the sorted vector, which can be useful for debugging.

This example demonstrates that the Ceno zkVM supports a significant portion of the Rust standard library, including common data structures and algorithms. This makes it easy to write complex programs for the guest, as you can leverage the power and convenience of the standard library.