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