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