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