cairo_vm/
program_hash.rs

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

cairo_vm/
program_hash.rs
