cairo_vm/
program_hash.rs

1use starknet_crypto::pedersen_hash;
2
3use crate::Felt252;
4
5use crate::stdlib::vec::Vec;
6use crate::types::builtin_name::BuiltinName;
7use crate::types::relocatable::MaybeRelocatable;
8use crate::vm::runners::cairo_pie::StrippedProgram;
9
10type HashFunction = fn(&Felt252, &Felt252) -> Felt252;
11
12#[derive(thiserror_no_std::Error, Debug)]
13pub enum HashChainError {
14    #[error("Data array must contain at least one element.")]
15    EmptyData,
16}
17
18#[derive(thiserror_no_std::Error, Debug)]
19pub enum ProgramHashError {
20    #[error(transparent)]
21    HashChain(#[from] HashChainError),
22
23    #[error(
24        "Invalid program builtin: builtin name too long to be converted to field element: {0}"
25    )]
26    InvalidProgramBuiltin(&'static str),
27
28    #[error("Invalid program data: data contains relocatable(s)")]
29    InvalidProgramData,
30}
31
32/// Computes a hash chain over the data, in the following order:
33///     h(data[0], h(data[1], h(..., h(data[n-2], data[n-1])))).
34/// [cairo_lang reference](https://github.com/starkware-libs/cairo-lang/blob/efa9648f57568aad8f8a13fbf027d2de7c63c2c0/src/starkware/cairo/common/hash_chain.py#L6)
35
36fn compute_hash_chain<'a, I>(data: I, hash_func: HashFunction) -> Result<Felt252, HashChainError>
37where
38    I: Iterator<Item = &'a Felt252> + DoubleEndedIterator,
39{
40    match data.copied().rev().reduce(|x, y| hash_func(&y, &x)) {
41        Some(result) => Ok(result),
42        None => Err(HashChainError::EmptyData),
43    }
44}
45
46/// Creates an instance of `Felt252` from a builtin name.
47///
48/// Converts the builtin name to bytes then attempts to create a field element from
49/// these bytes. This function will fail if the builtin name is over 31 characters.
50fn builtin_name_to_field_element(builtin_name: &BuiltinName) -> Result<Felt252, ProgramHashError> {
51    // The Python implementation uses the builtin name without suffix
52    Ok(Felt252::from_bytes_be_slice(
53        builtin_name.to_str().as_bytes(),
54    ))
55}
56
57/// Converts a `MaybeRelocatable` into a `Felt252` value.
58///
59/// Returns `InvalidProgramData` if `maybe_relocatable` is not an integer
60fn maybe_relocatable_to_field_element(
61    maybe_relocatable: &MaybeRelocatable,
62) -> Result<Felt252, ProgramHashError> {
63    maybe_relocatable
64        .get_int_ref()
65        .copied()
66        .ok_or(ProgramHashError::InvalidProgramData)
67}
68
69/// Computes the Pedersen hash of a program.
70/// [(cairo_lang reference)](https://github.com/starkware-libs/cairo-lang/blob/efa9648f57568aad8f8a13fbf027d2de7c63c2c0/src/starkware/cairo/bootloaders/hash_program.py#L11)
71pub fn compute_program_hash_chain(
72    program: &StrippedProgram,
73    bootloader_version: usize,
74) -> Result<Felt252, ProgramHashError> {
75    let program_main = program.main;
76    let program_main = Felt252::from(program_main);
77
78    // Convert builtin names to field elements
79    let builtin_list: Result<Vec<Felt252>, _> = program
80        .builtins
81        .iter()
82        .map(builtin_name_to_field_element)
83        .collect();
84    let builtin_list = builtin_list?;
85
86    let program_header = vec![
87        Felt252::from(bootloader_version),
88        program_main,
89        Felt252::from(program.builtins.len()),
90    ];
91
92    let program_data: Result<Vec<_>, _> = program
93        .data
94        .iter()
95        .map(maybe_relocatable_to_field_element)
96        .collect();
97    let program_data = program_data?;
98
99    let data_chain_len = program_header.len() + builtin_list.len() + program_data.len();
100    let data_chain_len_vec = vec![Felt252::from(data_chain_len)];
101
102    // Prepare a chain of iterators to feed to the hash function
103    let data_chain = [
104        &data_chain_len_vec,
105        &program_header,
106        &builtin_list,
107        &program_data,
108    ];
109
110    let hash = compute_hash_chain(data_chain.iter().flat_map(|&v| v.iter()), pedersen_hash)?;
111    Ok(hash)
112}
113
114#[cfg(test)]
115mod tests {
116    #[cfg(feature = "std")]
117    use {crate::types::program::Program, rstest::rstest, std::path::PathBuf};
118
119    use starknet_crypto::pedersen_hash;
120
121    use super::*;
122
123    #[test]
124    fn test_compute_hash_chain() {
125        let data: Vec<Felt252> = vec![
126            Felt252::from(1u64),
127            Felt252::from(2u64),
128            Felt252::from(3u64),
129        ];
130        let expected_hash = pedersen_hash(
131            &Felt252::from(1u64),
132            &pedersen_hash(&Felt252::from(2u64), &Felt252::from(3u64)),
133        );
134        let computed_hash = compute_hash_chain(data.iter(), pedersen_hash)
135            .expect("Hash computation failed unexpectedly");
136
137        assert_eq!(computed_hash, expected_hash);
138    }
139
140    #[cfg(feature = "std")]
141    #[rstest]
142    // Expected hashes generated with `cairo-hash-program`
143    #[case::fibonacci(
144        "../cairo_programs/fibonacci.json",
145        "0x43b17e9592f33142246af4c06cd2b574b460dd1f718d76b51341175a62b220f"
146    )]
147    #[case::field_arithmetic(
148        "../cairo_programs/field_arithmetic.json",
149        "0x1031772ca86e618b058101af9c9a3277bac90712b750bcea1cc69d6c7cad8a7"
150    )]
151    #[case::keccak_copy_inputs(
152        "../cairo_programs/keccak_copy_inputs.json",
153        "0x49484fdc8e7a85061f9f21b7e21fe276d8a88c8e96681101a2518809e686c6c"
154    )]
155    fn test_compute_program_hash_chain(
156        #[case] program_path: PathBuf,
157        #[case] expected_program_hash: String,
158    ) {
159        let program =
160            Program::from_file(program_path.as_path(), Some("main"))
161                .expect("Could not load program. Did you compile the sample programs? Run `make test` in the root directory.");
162        let stripped_program = program.get_stripped_program().unwrap();
163        let bootloader_version = 0;
164
165        let program_hash = compute_program_hash_chain(&stripped_program, bootloader_version)
166            .expect("Failed to compute program hash.");
167
168        let program_hash_hex = format!("{:#x}", program_hash);
169
170        assert_eq!(program_hash_hex, expected_program_hash);
171    }
172}
cairo_vm/program_hash.rs

cairo_vm/
program_hash.rs
