sapling_crypto/
pedersen_hash.rs

1//! Implementation of the Pedersen hash function used in Sapling.
2
3#[cfg(test)]
4pub(crate) mod test_vectors;
5
6use alloc::vec::Vec;
7use core::ops::{AddAssign, Neg};
8use ff::PrimeField;
9use group::Group;
10
11use super::constants::{PEDERSEN_HASH_CHUNKS_PER_GENERATOR, PEDERSEN_HASH_EXP_WINDOW_SIZE};
12
13#[derive(Copy, Clone)]
14pub enum Personalization {
15    NoteCommitment,
16    MerkleTree(usize),
17}
18
19impl Personalization {
20    pub fn get_bits(&self) -> Vec<bool> {
21        match *self {
22            Personalization::NoteCommitment => vec![true, true, true, true, true, true],
23            Personalization::MerkleTree(num) => {
24                assert!(num < 63);
25
26                (0..6).map(|i| (num >> i) & 1 == 1).collect()
27            }
28        }
29    }
30}
31
32pub fn pedersen_hash<I>(personalization: Personalization, bits: I) -> jubjub::SubgroupPoint
33where
34    I: IntoIterator<Item = bool>,
35{
36    let mut bits = personalization.get_bits().into_iter().chain(bits);
37
38    let mut result = jubjub::SubgroupPoint::identity();
39    let mut generators = crate::constants::pedersen_hash_exp_table().iter();
40
41    loop {
42        let mut acc = jubjub::Fr::zero();
43        let mut cur = jubjub::Fr::one();
44        let mut chunks_remaining = PEDERSEN_HASH_CHUNKS_PER_GENERATOR;
45        let mut encountered_bits = false;
46
47        // Grab three bits from the input
48        while let Some(a) = bits.next() {
49            encountered_bits = true;
50
51            let b = bits.next().unwrap_or(false);
52            let c = bits.next().unwrap_or(false);
53
54            // Start computing this portion of the scalar
55            let mut tmp = cur;
56            if a {
57                tmp.add_assign(&cur);
58            }
59            cur = cur.double(); // 2^1 * cur
60            if b {
61                tmp.add_assign(&cur);
62            }
63
64            // conditionally negate
65            if c {
66                tmp = tmp.neg();
67            }
68
69            acc.add_assign(&tmp);
70
71            chunks_remaining -= 1;
72
73            if chunks_remaining == 0 {
74                break;
75            } else {
76                cur = cur.double().double().double(); // 2^4 * cur
77            }
78        }
79
80        if !encountered_bits {
81            break;
82        }
83
84        let mut table: &[Vec<jubjub::SubgroupPoint>] =
85            generators.next().expect("we don't have enough generators");
86        let window = PEDERSEN_HASH_EXP_WINDOW_SIZE as usize;
87        let window_mask = (1u64 << window) - 1;
88
89        let acc = acc.to_repr();
90        let num_limbs: usize = acc.as_ref().len() / 8;
91        let mut limbs = vec![0u64; num_limbs + 1];
92        for (src, dst) in acc
93            .as_chunks::<8>()
94            .0
95            .iter()
96            .zip(limbs[..num_limbs].iter_mut())
97        {
98            *dst = u64::from_le_bytes(*src);
99        }
100
101        let mut tmp = jubjub::SubgroupPoint::identity();
102
103        let mut pos = 0;
104        while pos < jubjub::Fr::NUM_BITS as usize {
105            let u64_idx = pos / 64;
106            let bit_idx = pos % 64;
107            let i = (if bit_idx + window < 64 {
108                // This window's bits are contained in a single u64.
109                limbs[u64_idx] >> bit_idx
110            } else {
111                // Combine the current u64's bits with the bits from the next u64.
112                (limbs[u64_idx] >> bit_idx) | (limbs[u64_idx + 1] << (64 - bit_idx))
113            } & window_mask) as usize;
114
115            tmp += table[0][i];
116
117            pos += window;
118            table = &table[1..];
119        }
120
121        result += tmp;
122    }
123
124    result
125}
126
127#[cfg(test)]
128pub mod test {
129    use alloc::string::ToString;
130    use group::Curve;
131
132    use super::*;
133
134    pub struct TestVector<'a> {
135        pub personalization: Personalization,
136        pub input_bits: Vec<u8>,
137        pub hash_u: &'a str,
138        pub hash_v: &'a str,
139    }
140
141    #[test]
142    fn test_pedersen_hash_points() {
143        let test_vectors = test_vectors::get_vectors();
144
145        assert!(!test_vectors.is_empty());
146
147        for v in test_vectors.iter() {
148            let input_bools: Vec<bool> = v.input_bits.iter().map(|&i| i == 1).collect();
149
150            // The 6 bits prefix is handled separately
151            assert_eq!(v.personalization.get_bits(), &input_bools[..6]);
152
153            let p = jubjub::ExtendedPoint::from(pedersen_hash(
154                v.personalization,
155                input_bools.into_iter().skip(6),
156            ))
157            .to_affine();
158
159            assert_eq!(p.get_u().to_string(), v.hash_u);
160            assert_eq!(p.get_v().to_string(), v.hash_v);
161        }
162    }
163}
sapling_crypto/pedersen_hash.rs

sapling_crypto/
pedersen_hash.rs
