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
126        // (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}
127        // for all i. Described in section 5.4.1.7 in the Zcash protocol
128        // specification.
129        let result = padded_input
130            .par_chunks(W::WINDOW_SIZE * CHUNK_SIZE)
131            .zip(&parameters.generators)
132            .map(|(segment_bits, segment_generators)| {
133                segment_bits
134                    .par_chunks(CHUNK_SIZE)
135                    .zip(segment_generators)
136                    .map(|(chunk_bits, generator)| {
137                        let mut encoded = generator.clone();
138                        if chunk_bits[0] {
139                            encoded = encoded + generator;
140                        }
141                        if chunk_bits[1] {
142                            encoded += &generator.double();
143                        }
144                        if chunk_bits[2] {
145                            encoded = encoded.neg();
146                        }
147                        encoded
148                    })
149                    .reduce(G::zero, |a, b| a + &b)
150            })
151            .reduce(G::zero, |a, b| a + &b);
152        end_timer!(eval_time);
153
154        Ok(result)
155    }
156}
157
158impl<G: Group> Debug for BoweHopwoodPedersenParameters<G> {
159    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
160        write!(f, "Bowe-Hopwood Pedersen Hash Parameters {{\n")?;
161        for (i, g) in self.generators.iter().enumerate() {
162            write!(f, "\t  Generator {}: {:?}\n", i, g)?;
163        }
164        write!(f, "}}\n")
165    }
166}
167
168#[cfg(test)]
169mod test {
170    use crate::{
171        crh::{bowe_hopwood::BoweHopwoodPedersenCRH, pedersen::PedersenWindow},
172        FixedLengthCRH,
173    };
174    use algebra::curves::edwards_sw6::EdwardsProjective;
175    use rand::thread_rng;
176
177    #[test]
178    fn test_simple_bh() {
179        #[derive(Clone)]
180        struct TestWindow {}
181        impl PedersenWindow for TestWindow {
182            const WINDOW_SIZE: usize = 90;
183            const NUM_WINDOWS: usize = 8;
184        }
185
186        let rng = &mut thread_rng();
187        let params =
188            <BoweHopwoodPedersenCRH<EdwardsProjective, TestWindow> as FixedLengthCRH>::setup(rng)
189                .unwrap();
190        <BoweHopwoodPedersenCRH<EdwardsProjective, TestWindow> as FixedLengthCRH>::evaluate(
191            &params,
192            &[1, 2, 3],
193        )
194        .unwrap();
195    }
196}