Full Integrity documentation

​
Cairo memory sections

Cairo memory consists of 3 main sections - program, execution and output. That’s a simplification, but for understanding hashes calculated by Integrity, it will be enough. The program section contains your Cairo code compiled to Cairo VM instructions. Execution and output depend on program and input data. They are both calculated when running the program, but only output is exposed in public memory.

​
Fact and Verification Hash

After verifying the proof, Integrity calculates two hashes: program_hash and output_hash. They are Poseidon hashes of corresponding memory sections. Then, those two hashes are hashed together to get fact_hash.

If your contract needs to check whether certain proof was verified, you have to calculate those hashes in your contract and pass a fact_hash (or better verification_hash) to Integrity’s function. Usually you would verify proofs for some constant set of programs with arbitrary input and output, which means that you can hardcode program_hash while calculating output_hash and fact_hash dynamically.

However, as is usually the case, the reality is more complicated. To reduce public memory size, Cairo programs are often bootloaded, which means that your program isn’t run directly, but rather a special program called “bootloader” is placed in program segment, which is responsible for loading your program (called child program) to memory, executing it and calculating program_hash of the child program. This means that every bootloaded program will have the same program_hash and the program_hash of child program will only be present in bootloader’s output. This flow and hash calculation is represented in the following diagram:

Fortunately, you don’t need to implement above logic yourself, because Integrity provides a Scarb package with many useful utility functions, namely calculate_fact_hash and calculate_bootloaded_fact_hash. For more details, see “Calls from Starknet contracts” section in Integrity documentation.

If you have fact_hash calculated, you can call integrity’s get_all_verifications_for_fact_hash function to check whether given fact_hash has been verified. However, because Integrity accepts proofs with many settings and any number of security bits, you need to check if the proof has been verified with enough number of security bits. For that you can use is_fact_hash_valid_with_security utility function.

Here is an example of how to use those functions:

use integrity::{
    Integrity, calculate_bootloaded_fact_hash,
    SHARP_BOOTLOADER_PROGRAM_HASH,
};

const SECURITY_BITS: u32 = 70;
const FIBONACCI_PROGRAM_HASH: felt252 = 0x59874649ccc5a0a15ee77538f1eb760acb88cab027a2d48f4246bf17b7b7694;

fn is_fibonacci_verified(fib_index: felt252, fib_value: felt252) -> bool {
    let fact_hash = calculate_bootloaded_fact_hash(
        SHARP_BOOTLOADER_PROGRAM_HASH,
        FIBONACCI_PROGRAM_HASH,
        [fib_index, fib_value].span()
    );

    let integrity = Integrity::new(); // automatically uses current FactRegistry address
    integrity.is_fact_hash_valid_with_security(fact_hash, SECURITY_BITS)
}

An alternative way is using verification_hash, which is composed from fact_hash, configuration and security bits. That means that no additional checks are needed.

And here is how you would check verification of multiple proofs with the same configuration using verification_hash:

use integrity::{
    Integrity, IntegrityWithConfig,
    calculate_bootloaded_fact_hash,
    SHARP_BOOTLOADER_PROGRAM_HASH,
    VerifierConfiguration,
};

fn is_multi_fibonacci_verified(fib: Span<(felt252, felt252)>) -> bool {
    let config = VerifierConfiguration {
        layout: 'recursive_with_poseidon',
        hasher: 'keccak_160_lsb',
        stone_version: 'stone6',
        memory_verification: 'relaxed',
    };

    let integrity = Integrity::new().with_config(config, SECURITY_BITS);

    let mut result = true;
    for f in fib {
        let (fib_index, fib_value) = *f;

        let fact_hash = calculate_bootloaded_fact_hash(
            SHARP_BOOTLOADER_PROGRAM_HASH, FIBONACCI_PROGRAM_HASH, [fib_index, fib_value].span()
        );

        if !integrity.is_fact_hash_valid(fact_hash) {
            result = false;
        }
    };
    result
}

If you are having trouble calculating any of those hashes, check out Integrity Hashes Calculator. Not only does it automatically calculate hashes for provided program_hash and output array, but also supports proof uploading, so you can get data directly from it.

​
Scripts for fact_hash calculation

​
Python

import sys
import json
from starkware.cairo.lang.vm.cairo_pie import CairoPie
from starkware.cairo.bootloaders.generate_fact import get_program_output, get_cairo_pie_fact_info
from starkware.cairo.bootloaders.hash_program import compute_program_hash_chain
from starkware.cairo.lang.vm.crypto import poseidon_hash_many

def calculate_fact_hash(file_path: str) -> str:
    """
    Calculates and returns the fact hash for a given CairoPie file.
    """
    cairo_pie = CairoPie.from_file(file_path)
    
    child_program_hash = compute_program_hash_chain(program=cairo_pie.program, use_poseidon=False)
    
    child_output = get_program_output(cairo_pie)
    
    bootloader_output = [
        1,
        len(child_output) + 2,
        child_program_hash,
        *child_output
    ]
    
    bootloader_output_hash = poseidon_hash_many(bootloader_output)
    # 0x40519557c48b25e7e7d27cb27297300b94909028c327b385990f0b649920cc3 - custom bootloader
    # 0x5ab580b04e3532b6b18f81cfa654a05e29dd8e2352d88df1e765a84072db07 - sharp
    bootloader_program_hash = 0x5ab580b04e3532b6b18f81cfa654a05e29dd8e2352d88df1e765a84072db07

    fact_hash = poseidon_hash_many([
        bootloader_program_hash,
        bootloader_output_hash
    ])
    
    return json.dumps({
        "child_program_hash": hex(child_program_hash),
        "child_output": [hex(x) for x in child_output],
        "bootloader_output": [hex(x) for x in bootloader_output],
        "bootloader_output_hash": hex(bootloader_output_hash),
        "bootloader_program_hash": hex(bootloader_program_hash),
        "fact_hash": hex(fact_hash),
    })
    

if __name__ == "__main__":
    path = sys.argv[1]
    print(calculate_fact_hash(path))

​
Rust

use cairo_vm::program_hash::compute_program_hash_chain;
use cairo_vm::vm::runners::cairo_pie::CairoPie;
use starknet::core::types::Felt;
use starknet_os::crypto::poseidon::poseidon_hash_many_bytes;
use alloy::primitives::B256;
use cairo_vm::Felt252;

/// Default bootloader program version.
///
/// https://github.com/starkware-libs/cairo-lang/blob/efa9648f57568aad8f8a13fbf027d2de7c63c2c0/src/starkware/cairo/bootloaders/hash_program.py#L11
pub const BOOTLOADER_VERSION: usize = 0;

pub struct BootLoaderOutput {
    pub one_felt: Felt,
    pub program_output_len_add_2: Felt,
    pub program_hash: Felt,
    pub program_output: Vec<Felt>,
}

impl BootLoaderOutput {
    pub fn to_byte_nested_vec(&self) -> Vec<Vec<u8>> {
        let mut result = Vec::new();
        result.push(self.one_felt.to_bytes_be().to_vec());
        result.push(self.program_output_len_add_2.to_bytes_be().to_vec());
        result.push(self.program_hash.to_bytes_be().to_vec());
        for felt in &self.program_output {
            result.push(felt.to_bytes_be().to_vec());
        }
        result
    }
}

pub fn get_fact_l2(cairo_pie: &CairoPie, program_hash: Option<Felt>) -> color_eyre::Result<B256> {
    let program_hash = match program_hash {
        Some(hash) => hash,
        None => Felt::from_bytes_be(
            &compute_program_hash_chain(&cairo_pie.metadata.program, BOOTLOADER_VERSION)
                .map_err(|e| {
                    tracing::error!(
                        log_type = "FactInfo",
                        category = "fact_info",
                        function_type = "get_fact_info",
                        "Failed to compute program hash: {}",
                        e
                    );
                    FactError::ProgramHashCompute(e.to_string())
                })?
                .to_bytes_be(),
        ),
    };
    let program_output = get_program_output(cairo_pie)?;
    let boot_loader_output: BootLoaderOutput = BootLoaderOutput {
        one_felt: Felt::ONE,
        program_output_len_add_2: Felt::from(program_output.len()).add(2),
        program_hash,
        program_output,
    };
    let boot_loader_output_slice_vec = boot_loader_output.to_byte_nested_vec();
    let boot_loader_output_hash_vec =
        poseidon_hash_many_bytes(&*boot_loader_output_slice_vec.iter().map(|v| v.as_slice()).collect::<Vec<_>>())?
            .to_vec();
    let boot_loader_output_hash = boot_loader_output_hash_vec.as_slice();

    // Bootloader Program Hash : 0x5ab580b04e3532b6b18f81cfa654a05e29dd8e2352d88df1e765a84072db07
    // taken from the code sent by integrity team.
    let boot_loader_program_hash_bytes = Felt::from_str("0x5ab580b04e3532b6b18f81cfa654a05e29dd8e2352d88df1e765a84072db07")?.to_bytes_be();
    let boot_loader_program_hash = boot_loader_program_hash_bytes.as_slice();

    let fact_hash = poseidon_hash_many_bytes(vec![boot_loader_program_hash, boot_loader_output_hash].as_slice())?;

    Ok(B256::from_slice(fact_hash.to_vec().as_slice()))
}

pub fn get_program_output(cairo_pie: &CairoPie) -> Result<Vec<Felt252>, FactError> {
    let segment_info =
        cairo_pie.metadata.builtin_segments.get(&BuiltinName::output).ok_or(FactError::OutputBuiltinNoSegmentInfo)?;

    let mut output = vec![Felt252::from(0); segment_info.size];
    let mut insertion_count = 0;
    let cairo_program_memory = &cairo_pie.memory.0;

    for ((index, offset), value) in cairo_program_memory.iter() {
        if *index == segment_info.index as usize {
            match value {
                MaybeRelocatable::Int(felt) => {
                    output[*offset] = *felt;
                    insertion_count += 1;
                }
                MaybeRelocatable::RelocatableValue(_) => {
                    return Err(FactError::OutputSegmentUnexpectedRelocatable(*offset));
                }
            }
        }
    }

    if insertion_count != segment_info.size {
        return Err(FactError::InvalidSegment);
    }

    Ok(output)
}