1use crate::Error;
  2use rand::Rng;
  3use rayon::prelude::*;
  4use std::{
  5    fmt::{Debug, Formatter, Result as FmtResult},
  6    marker::PhantomData,
  7};
  8
  9use crate::crh::FixedLengthCRH;
 10use algebra::{groups::Group, Field, ToConstraintField};
 11
 12#[cfg(feature = "r1cs")]
 13pub mod constraints;
 14
 15pub trait PedersenWindow: Clone {
 16    const WINDOW_SIZE: usize;
 17    const NUM_WINDOWS: usize;
 18}
 19
 20#[derive(Clone, Default)]
 21pub struct PedersenParameters<G: Group> {
 22    pub generators: Vec<Vec<G>>,
 23}
 24
 25pub struct PedersenCRH<G: Group, W: PedersenWindow> {
 26    group:  PhantomData<G>,
 27    window: PhantomData<W>,
 28}
 29
 30impl<G: Group, W: PedersenWindow> PedersenCRH<G, W> {
 31    pub fn create_generators<R: Rng>(rng: &mut R) -> Vec<Vec<G>> {
 32        let mut generators_powers = Vec::new();
 33        for _ in 0..W::NUM_WINDOWS {
 34            generators_powers.push(Self::generator_powers(W::WINDOW_SIZE, rng));
 35        }
 36        generators_powers
 37    }
 38
 39    pub fn generator_powers<R: Rng>(num_powers: usize, rng: &mut R) -> Vec<G> {
 40        let mut cur_gen_powers = Vec::with_capacity(num_powers);
 41        let mut base = G::rand(rng);
 42        for _ in 0..num_powers {
 43            cur_gen_powers.push(base);
 44            base.double_in_place();
 45        }
 46        cur_gen_powers
 47    }
 48}
 49
 50impl<G: Group, W: PedersenWindow> FixedLengthCRH for PedersenCRH<G, W> {
 51    const INPUT_SIZE_BITS: usize = W::WINDOW_SIZE * W::NUM_WINDOWS;
 52    type Output = G;
 53    type Parameters = PedersenParameters<G>;
 54
 55    fn setup<R: Rng>(rng: &mut R) -> Result<Self::Parameters, Error> {
 56        let time = start_timer!(|| format!(
 57            "PedersenCRH::Setup: {} {}-bit windows; {{0,1}}^{{{}}} -> G",
 58            W::NUM_WINDOWS,
 59            W::WINDOW_SIZE,
 60            W::NUM_WINDOWS * W::WINDOW_SIZE
 61        ));
 62        let generators = Self::create_generators(rng);
 63        end_timer!(time);
 64        Ok(Self::Parameters { generators })
 65    }
 66
 67    fn evaluate(parameters: &Self::Parameters, input: &[u8]) -> Result<Self::Output, Error> {
 68        let eval_time = start_timer!(|| "PedersenCRH::Eval");
 69
 70        if (input.len() * 8) > W::WINDOW_SIZE * W::NUM_WINDOWS {
 71            panic!(
 72                "incorrect input length {:?} for window params {:?}x{:?}",
 73                input.len(),
 74                W::WINDOW_SIZE,
 75                W::NUM_WINDOWS
 76            );
 77        }
 78
 79        let mut padded_input = Vec::with_capacity(input.len());
 80        let mut input = input;
 81        // Pad the input if it is not the current length.
 82        if (input.len() * 8) < W::WINDOW_SIZE * W::NUM_WINDOWS {
 83            let current_length = input.len();
 84            padded_input.extend_from_slice(input);
 85            for _ in current_length..((W::WINDOW_SIZE * W::NUM_WINDOWS) / 8) {
 86                padded_input.push(0u8);
 87            }
 88            input = padded_input.as_slice();
 89        }
 90
 91        assert_eq!(
 92            parameters.generators.len(),
 93            W::NUM_WINDOWS,
 94            "Incorrect pp of size {:?}x{:?} for window params {:?}x{:?}",
 95            parameters.generators[0].len(),
 96            parameters.generators.len(),
 97            W::WINDOW_SIZE,
 98            W::NUM_WINDOWS
 99        );
100
101        // Compute sum of h_i^{m_i} for all i.
102        let result = bytes_to_bits(input)
103            .par_chunks(W::WINDOW_SIZE)
104            .zip(&parameters.generators)
105            .map(|(bits, generator_powers)| {
106                let mut encoded = G::zero();
107                for (bit, base) in bits.iter().zip(generator_powers.iter()) {
108                    if *bit {
109                        encoded = encoded + base;
110                    }
111                }
112                encoded
113            })
114            .reduce(G::zero, |a, b| a + &b);
115        end_timer!(eval_time);
116
117        Ok(result)
118    }
119}
120
121pub fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
122    let mut bits = Vec::with_capacity(bytes.len() * 8);
123    for byte in bytes {
124        for i in 0..8 {
125            let bit = (*byte >> i) & 1;
126            bits.push(bit == 1)
127        }
128    }
129    bits
130}
131
132impl<G: Group> Debug for PedersenParameters<G> {
133    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
134        write!(f, "Pedersen Hash Parameters {{\n")?;
135        for (i, g) in self.generators.iter().enumerate() {
136            write!(f, "\t  Generator {}: {:?}\n", i, g)?;
137        }
138        write!(f, "}}\n")
139    }
140}
141
142impl<ConstraintF: Field, G: Group + ToConstraintField<ConstraintF>> ToConstraintField<ConstraintF>
143    for PedersenParameters<G>
144{
145    #[inline]
146    fn to_field_elements(&self) -> Result<Vec<ConstraintF>, Error> {
147        Ok(Vec::new())
148    }
149}