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