lambdaworks_crypto/hash/pedersen/
mod.rs

1use lambdaworks_math::{
2    elliptic_curve::short_weierstrass::point::ShortWeierstrassProjectivePoint as Point,
3    field::{
4        element::FieldElement as FE,
5        fields::fft_friendly::stark_252_prime_field::Stark252PrimeField,
6    },
7};
8
9mod constants;
10mod parameters;
11use parameters::PedersenParameters;
12pub use parameters::PedersenStarkCurve;
13
14mod private {
15    use super::*;
16
17    pub trait Sealed {}
18
19    impl<P: PedersenParameters> Sealed for P {}
20}
21
22pub trait Pedersen: PedersenParameters + self::private::Sealed {
23    /// Implements Starkware version of Pedersen hash of x and y.
24    /// Divides each of x and y into 4-bit chunks, and uses lookup tables to accumulate pre-calculated
25    /// points corresponding to a given chunk.
26    /// Accumulation starts from a "shift_point" whose points are derived from digits of pi.
27    /// Pre-calculated points are multiples by powers of 2 of the "shift_point".
28    ///
29    /// Find specification at https://docs.starkware.co/starkex/crypto/pedersen-hash-function.html
30    fn hash(x: &FE<Self::F>, y: &FE<Self::F>) -> FE<Self::F>;
31
32    /// Performs lookup to find the constant point corresponding to 4-bit chunks of given input.
33    /// Keeps adding up those points to the given accumulation point.
34    fn lookup_and_accumulate(acc: &mut Point<Self::EC>, bits: &[bool], prep: &[Point<Self::EC>]);
35}
36
37// FIXME: currently we make some assumptions that apply to `Stark252PrimeField`, so only mark the
38// implementation when that's the field.
39impl<P: PedersenParameters<F = Stark252PrimeField>> Pedersen for P {
40    // Taken from Jonathan Lei's starknet-rs
41    // https://github.com/xJonathanLEI/starknet-rs/blob/4ab2f36872435ce57b1d8f55856702a6a30f270a/starknet-crypto/src/pedersen_hash.rs
42
43    fn hash(x: &FE<Self::F>, y: &FE<Self::F>) -> FE<Self::F> {
44        let x = x.to_bits_le();
45        let y = y.to_bits_le();
46        let mut acc = P::SHIFT_POINT.clone();
47
48        Self::lookup_and_accumulate(&mut acc, &x[..248], &P::POINTS_P1); // Add a_low * P1
49        Self::lookup_and_accumulate(&mut acc, &x[248..252], &P::POINTS_P2); // Add a_high * P2
50        Self::lookup_and_accumulate(&mut acc, &y[..248], &P::POINTS_P3); // Add b_low * P3
51        Self::lookup_and_accumulate(&mut acc, &y[248..252], &P::POINTS_P4); // Add b_high * P4
52
53        *acc.to_affine().x()
54    }
55
56    fn lookup_and_accumulate(acc: &mut Point<Self::EC>, bits: &[bool], prep: &[Point<Self::EC>]) {
57        bits.chunks(P::CURVE_CONST_BITS)
58            .enumerate()
59            .for_each(|(i, v)| {
60                let offset = bools_to_usize_le(v);
61                if offset > 0 {
62                    // Table lookup at 'offset-1' in table for chunk 'i'
63                    *acc = acc.operate_with_affine(&prep[i * P::TABLE_SIZE + offset - 1]);
64                }
65            })
66    }
67}
68
69#[inline]
70fn bools_to_usize_le(bools: &[bool]) -> usize {
71    let mut result: usize = 0;
72    for (ind, bit) in bools.iter().enumerate() {
73        if *bit {
74            result += 1 << ind;
75        }
76    }
77    result
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use crate::hash::pedersen::parameters::PedersenStarkCurve;
84
85    // Test case ported from:
86    // https://github.com/starkware-libs/crypto-cpp/blob/95864fbe11d5287e345432dbe1e80dea3c35fc58/src/starkware/crypto/ffi/crypto_lib_test.go
87
88    #[test]
89    fn test_stark_curve() {
90        let x = FE::from_hex_unchecked(
91            "03d937c035c878245caf64531a5756109c53068da139362728feb561405371cb",
92        );
93        let y = FE::from_hex_unchecked(
94            "0208a0a10250e382e1e4bbe2880906c2791bf6275695e02fbbc6aeff9cd8b31a",
95        );
96        let hash = PedersenStarkCurve::hash(&x, &y);
97        assert_eq!(
98            hash,
99            FE::from_hex_unchecked(
100                "030e480bed5fe53fa909cc0f8c4d99b8f9f2c016be4c41e13a4848797979c662"
101            )
102        );
103    }
104}
lambdaworks_crypto/hash/pedersen/mod.rs

lambdaworks_crypto/hash/pedersen/
mod.rs
