mmr_crypto_primitives/crh/pedersen/
mod.rs

1use crate::{Error, Vec};
2use ark_std::rand::Rng;
3use ark_std::{
4    fmt::{Debug, Formatter, Result as FmtResult},
5    marker::PhantomData,
6};
7#[cfg(feature = "parallel")]
8use rayon::prelude::*;
9
10use crate::crh::{CRHScheme, TwoToOneCRHScheme};
11use ark_ec::ProjectiveCurve;
12use ark_ff::{Field, ToConstraintField};
13use ark_serialize::CanonicalSerialize;
14use ark_std::borrow::Borrow;
15use ark_std::cfg_chunks;
16
17use super::MMRTwoToOneCRHScheme;
18
19#[cfg(feature = "r1cs")]
20pub mod constraints;
21
22pub trait Window: Clone {
23    const WINDOW_SIZE: usize;
24    const NUM_WINDOWS: usize;
25}
26
27#[derive(Clone, Default)]
28pub struct Parameters<C: ProjectiveCurve> {
29    pub generators: Vec<Vec<C>>,
30}
31
32pub struct CRH<C: ProjectiveCurve, W: Window> {
33    group: PhantomData<C>,
34    window: PhantomData<W>,
35}
36
37impl<C: ProjectiveCurve, W: Window> CRH<C, W> {
38    pub(crate) const INPUT_SIZE_BITS: usize = W::WINDOW_SIZE * W::NUM_WINDOWS;
39    pub fn create_generators<R: Rng>(rng: &mut R) -> Vec<Vec<C>> {
40        let mut generators_powers = Vec::new();
41        for _ in 0..W::NUM_WINDOWS {
42            generators_powers.push(Self::generator_powers(W::WINDOW_SIZE, rng));
43        }
44        generators_powers
45    }
46
47    pub fn generator_powers<R: Rng>(num_powers: usize, rng: &mut R) -> Vec<C> {
48        let mut cur_gen_powers = Vec::with_capacity(num_powers);
49        let mut base = C::rand(rng);
50        for _ in 0..num_powers {
51            cur_gen_powers.push(base);
52            base.double_in_place();
53        }
54        cur_gen_powers
55    }
56}
57
58impl<C: ProjectiveCurve, W: Window> CRHScheme for CRH<C, W> {
59    type Input = [u8];
60    type Output = C::Affine;
61    type Parameters = Parameters<C>;
62
63    fn setup<R: Rng>(rng: &mut R) -> Result<Self::Parameters, Error> {
64        let time = start_timer!(|| format!(
65            "PedersenCRH::Setup: {} {}-bit windows; {{0,1}}^{{{}}} -> C",
66            W::NUM_WINDOWS,
67            W::WINDOW_SIZE,
68            W::NUM_WINDOWS * W::WINDOW_SIZE
69        ));
70        let generators = Self::create_generators(rng);
71        end_timer!(time);
72        Ok(Self::Parameters { generators })
73    }
74
75    fn evaluate<T: Borrow<Self::Input>>(
76        parameters: &Self::Parameters,
77        input: T,
78    ) -> Result<Self::Output, Error> {
79        let eval_time = start_timer!(|| "PedersenCRH::Eval");
80        let input = input.borrow();
81        if (input.len() * 8) > W::WINDOW_SIZE * W::NUM_WINDOWS {
82            panic!(
83                "incorrect input length {:?} for window params {:?}✕{:?}",
84                input.len(),
85                W::WINDOW_SIZE,
86                W::NUM_WINDOWS
87            );
88        }
89
90        let mut padded_input = Vec::with_capacity(input.len());
91        let mut input = input;
92        // Pad the input if it is not the current length.
93        if (input.len() * 8) < W::WINDOW_SIZE * W::NUM_WINDOWS {
94            padded_input.extend_from_slice(input);
95            let padded_length = (W::WINDOW_SIZE * W::NUM_WINDOWS) / 8;
96            padded_input.resize(padded_length, 0u8);
97            input = padded_input.as_slice();
98        }
99
100        assert_eq!(
101            parameters.generators.len(),
102            W::NUM_WINDOWS,
103            "Incorrect pp of size {:?}✕{:?} for window params {:?}✕{:?}",
104            parameters.generators[0].len(),
105            parameters.generators.len(),
106            W::WINDOW_SIZE,
107            W::NUM_WINDOWS
108        );
109
110        // Compute sum of h_i^{m_i} for all i.
111        let bits = bytes_to_bits(input);
112        let result = cfg_chunks!(bits, W::WINDOW_SIZE)
113            .zip(&parameters.generators)
114            .map(|(bits, generator_powers)| {
115                let mut encoded = C::zero();
116                for (bit, base) in bits.iter().zip(generator_powers.iter()) {
117                    if *bit {
118                        encoded += base;
119                    }
120                }
121                encoded
122            })
123            .sum::<C>();
124
125        end_timer!(eval_time);
126
127        Ok(result.into())
128    }
129}
130
131pub struct TwoToOneCRH<C: ProjectiveCurve, W: Window> {
132    group: PhantomData<C>,
133    window: PhantomData<W>,
134}
135
136impl<C: ProjectiveCurve, W: Window> TwoToOneCRH<C, W> {
137    pub(crate) const INPUT_SIZE_BITS: usize = W::WINDOW_SIZE * W::NUM_WINDOWS;
138    const HALF_INPUT_SIZE_BITS: usize = Self::INPUT_SIZE_BITS / 2;
139    pub fn create_generators<R: Rng>(rng: &mut R) -> Vec<Vec<C>> {
140        CRH::<C, W>::create_generators(rng)
141    }
142
143    pub fn generator_powers<R: Rng>(num_powers: usize, rng: &mut R) -> Vec<C> {
144        CRH::<C, W>::generator_powers(num_powers, rng)
145    }
146}
147
148impl<C: ProjectiveCurve, W: Window> TwoToOneCRHScheme for TwoToOneCRH<C, W> {
149    type Input = [u8];
150    type Output = C::Affine;
151    type Parameters = Parameters<C>;
152
153    fn setup<R: Rng>(r: &mut R) -> Result<Self::Parameters, Error> {
154        CRH::<C, W>::setup(r)
155    }
156
157    fn evaluate<T: Borrow<Self::Input>>(
158        parameters: &Self::Parameters,
159        left_input: T,
160        right_input: T,
161    ) -> Result<Self::Output, Error> {
162        let left_input = left_input.borrow();
163        let right_input = right_input.borrow();
164        assert_eq!(
165            left_input.len(),
166            right_input.len(),
167            "left and right input should be of equal length"
168        );
169        // check overflow
170
171        debug_assert!(left_input.len() * 8 <= Self::HALF_INPUT_SIZE_BITS);
172
173        let mut buffer = vec![0u8; (Self::HALF_INPUT_SIZE_BITS + Self::HALF_INPUT_SIZE_BITS) / 8];
174
175        buffer
176            .iter_mut()
177            .zip(left_input.iter().chain(right_input.iter()))
178            .for_each(|(b, l_b)| *b = *l_b);
179
180        CRH::<C, W>::evaluate(parameters, buffer.as_slice())
181    }
182
183    /// A simple implementation method: just concat the left input and right input together
184    ///
185    /// `evaluate` requires that `left_input` and `right_input` are of equal length.
186    fn compress<T: Borrow<Self::Output>>(
187        parameters: &Self::Parameters,
188        left_input: T,
189        right_input: T,
190    ) -> Result<Self::Output, Error> {
191        <Self as TwoToOneCRHScheme>::evaluate(
192            parameters,
193            crate::to_unchecked_bytes!(left_input)?,
194            crate::to_unchecked_bytes!(right_input)?,
195        )
196    }
197}
198
199pub fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
200    let mut bits = Vec::with_capacity(bytes.len() * 8);
201    for byte in bytes {
202        for i in 0..8 {
203            let bit = (*byte >> i) & 1;
204            bits.push(bit == 1)
205        }
206    }
207    bits
208}
209
210
211impl<C: ProjectiveCurve, W: Window> MMRTwoToOneCRHScheme for TwoToOneCRH<C, W> {
212    type Input = [u8];
213    type Output = C::Affine;
214    type Parameters = Parameters<C>;
215
216    fn setup<R: Rng>(r: &mut R) -> Result<Self::Parameters, Error> {
217        CRH::<C, W>::setup(r)
218    }
219
220    fn evaluate<T: Borrow<Self::Input>>(
221        parameters: &Self::Parameters,
222        left_input: T,
223        right_input: T,
224    ) -> Result<Self::Output, Error> {
225        let left_input = left_input.borrow();
226        let right_input = right_input.borrow();
227        assert_eq!(
228            left_input.len(),
229            right_input.len(),
230            "left and right input should be of equal length"
231        );
232        // check overflow
233
234        debug_assert!(left_input.len() * 8 <= Self::HALF_INPUT_SIZE_BITS);
235
236        let mut buffer = vec![0u8; (Self::HALF_INPUT_SIZE_BITS + Self::HALF_INPUT_SIZE_BITS) / 8];
237
238        buffer
239            .iter_mut()
240            .zip(left_input.iter().chain(right_input.iter()))
241            .for_each(|(b, l_b)| *b = *l_b);
242
243        CRH::<C, W>::evaluate(parameters, buffer.as_slice())
244    }
245
246    /// A simple implementation method: just concat the left input and right input together
247    ///
248    /// `evaluate` requires that `left_input` and `right_input` are of equal length.
249    fn compress<T: Borrow<Self::Output>>(
250        parameters: &Self::Parameters,
251        left_input: T,
252        right_input: T,
253    ) -> Result<Self::Output, Error> {
254        <Self as MMRTwoToOneCRHScheme>::evaluate(
255            parameters,
256            crate::to_unchecked_bytes!(left_input)?,
257            crate::to_unchecked_bytes!(right_input)?,
258        )
259    }
260
261    fn left_compress( 
262        parameters: &Self::Parameters,
263        left_input: &Self::Output,
264        right_input:&Self::Input,
265    ) -> Result<Self::Output, Error> {
266        <Self as MMRTwoToOneCRHScheme>::evaluate(
267            parameters,
268            crate::to_unchecked_bytes!(left_input)?,
269            right_input.to_vec(),
270        )
271    }
272
273    fn right_compress(
274        parameters: &Self::Parameters,
275        left_input: &Self::Input,
276        right_input: &Self::Output
277    ) -> Result<Self::Output, Error> {
278        <Self as MMRTwoToOneCRHScheme>::evaluate(
279            parameters,
280            left_input,
281            &crate::to_unchecked_bytes!(right_input)?,
282        )
283    }
284}
285
286
287impl<C: ProjectiveCurve> Debug for Parameters<C> {
288    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
289        writeln!(f, "Pedersen Hash Parameters {{")?;
290        for (i, g) in self.generators.iter().enumerate() {
291            writeln!(f, "\t  Generator {}: {:?}", i, g)?;
292        }
293        writeln!(f, "}}")
294    }
295}
296
297impl<ConstraintF: Field, C: ProjectiveCurve + ToConstraintField<ConstraintF>>
298    ToConstraintField<ConstraintF> for Parameters<C>
299{
300    #[inline]
301    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
302        Some(Vec::new())
303    }
304}
mmr_crypto_primitives/crh/pedersen/mod.rs

mmr_crypto_primitives/crh/pedersen/
mod.rs
