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

cairo_vm/
program_hash.rs
