1use crate::{Error, Vec};
  2use core::{
  3    fmt::{Debug, Formatter, Result as FmtResult},
  4    marker::PhantomData,
  5};
  6use rand::Rng;
  7#[cfg(feature = "parallel")]
  8use rayon::prelude::*;
  9
 10use super::pedersen::{bytes_to_bits, PedersenCRH, PedersenWindow};
 11use crate::crh::FixedLengthCRH;
 12use algebra_core::{biginteger::BigInteger, fields::PrimeField, groups::Group};
 13use ff_fft::cfg_chunks;
 14
 15#[cfg(feature = "r1cs")]
 16pub mod constraints;
 17
 18pub const CHUNK_SIZE: usize = 3;
 19
 20#[derive(Clone, Default)]
 21pub struct BoweHopwoodPedersenParameters<G: Group> {
 22    pub generators: Vec<Vec<G>>,
 23}
 24
 25pub struct BoweHopwoodPedersenCRH<G: Group, W: PedersenWindow> {
 26    group: PhantomData<G>,
 27    window: PhantomData<W>,
 28}
 29
 30impl<G: Group, W: PedersenWindow> BoweHopwoodPedersenCRH<G, W> {
 31    pub fn create_generators<R: Rng>(rng: &mut R) -> Vec<Vec<G>> {
 32        let mut generators = Vec::new();
 33        for _ in 0..W::NUM_WINDOWS {
 34            let mut generators_for_segment = Vec::new();
 35            let mut base = G::rand(rng);
 36            for _ in 0..W::WINDOW_SIZE {
 37                generators_for_segment.push(base);
 38                for _ in 0..4 {
 39                    base.double_in_place();
 40                }
 41            }
 42            generators.push(generators_for_segment);
 43        }
 44        generators
 45    }
 46}
 47
 48impl<G: Group, W: PedersenWindow> FixedLengthCRH for BoweHopwoodPedersenCRH<G, W> {
 49    const INPUT_SIZE_BITS: usize = PedersenCRH::<G, W>::INPUT_SIZE_BITS;
 50    type Output = G;
 51    type Parameters = BoweHopwoodPedersenParameters<G>;
 52
 53    fn setup<R: Rng>(rng: &mut R) -> Result<Self::Parameters, Error> {
 54        fn calculate_num_chunks_in_segment<F: PrimeField>() -> usize {
 55            let upper_limit = F::modulus_minus_one_div_two();
 56            let mut c = 0;
 57            let mut range = F::BigInt::from(2_u64);
 58            while range < upper_limit {
 59                range.muln(4);
 60                c += 1;
 61            }
 62
 63            c
 64        }
 65
 66        let maximum_num_chunks_in_segment = calculate_num_chunks_in_segment::<G::ScalarField>();
 67        if W::WINDOW_SIZE > maximum_num_chunks_in_segment {
 68            return Err(format!(
 69                "Bowe-Hopwood hash must have a window size resulting in scalars < (p-1)/2, \
 70                 maximum segment size is {}",
 71                maximum_num_chunks_in_segment
 72            )
 73            .into());
 74        }
 75
 76        let time = start_timer!(|| format!(
 77            "BoweHopwoodPedersenCRH::Setup: {} segments of {} 3-bit chunks; {{0,1}}^{{{}}} -> G",
 78            W::NUM_WINDOWS,
 79            W::WINDOW_SIZE,
 80            W::WINDOW_SIZE * W::NUM_WINDOWS * CHUNK_SIZE
 81        ));
 82        let generators = Self::create_generators(rng);
 83        end_timer!(time);
 84        Ok(Self::Parameters { generators })
 85    }
 86
 87    fn evaluate(parameters: &Self::Parameters, input: &[u8]) -> Result<Self::Output, Error> {
 88        let eval_time = start_timer!(|| "BoweHopwoodPedersenCRH::Eval");
 89
 90        if (input.len() * 8) > W::WINDOW_SIZE * W::NUM_WINDOWS * CHUNK_SIZE {
 91            panic!(
 92                "incorrect input length {:?} for window params {:?}x{:?}x{}",
 93                input.len(),
 94                W::WINDOW_SIZE,
 95                W::NUM_WINDOWS,
 96                CHUNK_SIZE,
 97            );
 98        }
 99
100        let mut padded_input = Vec::with_capacity(input.len());
101        let input = bytes_to_bits(input);
102        // Pad the input if it is not the current length.
103        padded_input.extend_from_slice(&input);
104        if input.len() % CHUNK_SIZE != 0 {
105            let current_length = input.len();
106            for _ in 0..(CHUNK_SIZE - current_length % CHUNK_SIZE) {
107                padded_input.push(false);
108            }
109        }
110
111        assert_eq!(padded_input.len() % CHUNK_SIZE, 0);
112
113        assert_eq!(
114            parameters.generators.len(),
115            W::NUM_WINDOWS,
116            "Incorrect pp of size {:?} for window params {:?}x{:?}x{}",
117            parameters.generators.len(),
118            W::WINDOW_SIZE,
119            W::NUM_WINDOWS,
120            CHUNK_SIZE,
121        );
122        for generators in parameters.generators.iter() {
123            assert_eq!(generators.len(), W::WINDOW_SIZE);
124        }
125        assert_eq!(CHUNK_SIZE, 3);
126
127        // Compute sum of h_i^{sum of
128        // (1-2*c_{i,j,2})*(1+c_{i,j,0}+2*c_{i,j,1})*2^{4*(j-1)} for all j in segment}
129        // for all i. Described in section 5.4.1.7 in the Zcash protocol
130        // specification.
131
132        let result = cfg_chunks!(padded_input, W::WINDOW_SIZE * CHUNK_SIZE)
133            .zip(&parameters.generators)
134            .map(|(segment_bits, segment_generators)| {
135                cfg_chunks!(segment_bits, CHUNK_SIZE)
136                    .zip(segment_generators)
137                    .map(|(chunk_bits, generator)| {
138                        let mut encoded = generator.clone();
139                        if chunk_bits[0] {
140                            encoded = encoded + generator;
141                        }
142                        if chunk_bits[1] {
143                            encoded += &generator.double();
144                        }
145                        if chunk_bits[2] {
146                            encoded = encoded.neg();
147                        }
148                        encoded
149                    })
150                    .sum::<G>()
151            })
152            .sum::<G>();
153
154        end_timer!(eval_time);
155
156        Ok(result)
157    }
158}
159
160impl<G: Group> Debug for BoweHopwoodPedersenParameters<G> {
161    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
162        write!(f, "Bowe-Hopwood Pedersen Hash Parameters {{\n")?;
163        for (i, g) in self.generators.iter().enumerate() {
164            write!(f, "\t  Generator {}: {:?}\n", i, g)?;
165        }
166        write!(f, "}}\n")
167    }
168}
169
170#[cfg(test)]
171mod test {
172    use crate::{
173        crh::{bowe_hopwood::BoweHopwoodPedersenCRH, pedersen::PedersenWindow},
174        FixedLengthCRH,
175    };
176    use algebra::{edwards_on_bls12_381::EdwardsProjective, test_rng};
177
178    #[test]
179    fn test_simple_bh() {
180        #[derive(Clone)]
181        struct TestWindow {}
182        impl PedersenWindow for TestWindow {
183            const WINDOW_SIZE: usize = 63;
184            const NUM_WINDOWS: usize = 8;
185        }
186
187        let rng = &mut test_rng();
188        let params =
189            <BoweHopwoodPedersenCRH<EdwardsProjective, TestWindow> as FixedLengthCRH>::setup(rng)
190                .unwrap();
191        <BoweHopwoodPedersenCRH<EdwardsProjective, TestWindow> as FixedLengthCRH>::evaluate(
192            &params,
193            &[1, 2, 3],
194        )
195        .unwrap();
196    }
197}