Skip to main content

pathfinder_crypto/hash/pedersen/
chain.rs

1use crate::algebra::field::Felt;
2use crate::hash::pedersen_hash;
3
4/// HashChain is the structure used over at cairo side to represent the hash
5/// construction needed for computing the class hash.
6///
7/// Empty hash chained value equals `H(0, 0)` where `H` is the
8/// [`pedersen_hash()`] function, and the second value is the number of values
9/// hashed together in this chain. For other values, the accumulator is on each
10/// update replaced with the `H(hash, value)` and the number of count
11/// incremented by one.
12#[derive(Default)]
13pub struct HashChain {
14    hash: Felt,
15    count: usize,
16}
17
18impl HashChain {
19    pub fn update(&mut self, value: Felt) {
20        self.hash = pedersen_hash(self.hash, value);
21        self.count = self
22            .count
23            .checked_add(1)
24            .expect("could not have deserialized larger than usize Vecs");
25    }
26
27    pub fn chain_update(mut self, value: Felt) -> Self {
28        self.update(value);
29        self
30    }
31
32    pub fn finalize(self) -> Felt {
33        let count =
34            Felt::from_be_slice(&self.count.to_be_bytes()).expect("usize is smaller than 251-bits");
35        pedersen_hash(self.hash, count)
36    }
37
38    pub fn single(value: Felt) -> Felt {
39        Self::default().chain_update(value).finalize()
40    }
41}
42
43#[cfg(test)]
44mod tests {
45    use super::{Felt, HashChain};
46
47    #[test]
48    fn test_non_empty_chain() {
49        let mut chain = HashChain::default();
50
51        chain.update(Felt::from_hex_str("0x1").unwrap());
52        chain.update(Felt::from_hex_str("0x2").unwrap());
53        chain.update(Felt::from_hex_str("0x3").unwrap());
54        chain.update(Felt::from_hex_str("0x4").unwrap());
55
56        let computed_hash = chain.finalize();
57
58        // produced by the cairo-lang Python implementation:
59        // `hex(compute_hash_on_elements([1, 2, 3, 4]))`
60        let expected_hash =
61            Felt::from_hex_str("0x66bd4335902683054d08a0572747ea78ebd9e531536fb43125424ca9f902084")
62                .unwrap();
63
64        assert_eq!(expected_hash, computed_hash);
65    }
66}