ark_bulletproofs/
generators.rs

1//! The `generators` module contains API for producing a
2//! set of generators for a rangeproof.
3
4#![allow(non_snake_case)]
5#![deny(missing_docs)]
6
7extern crate alloc;
8
9use ark_ec::{AffineRepr, CurveGroup};
10use ark_ff::PrimeField;
11use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
12use ark_std::marker::PhantomData;
13use ark_std::{ops::Add, rand::SeedableRng, vec::Vec};
14use digest::Digest;
15use rand_chacha::ChaChaRng;
16use sha3::Sha3_512;
17
18/// Represents a pair of base points for Pedersen commitments.
19///
20/// The Bulletproofs implementation and API is designed to support
21/// pluggable bases for Pedersen commitments, so that the choice of
22/// bases is not hard-coded.
23///
24/// The default generators are:
25///
26/// * `B`: the `ristretto255` basepoint;
27/// * `B_blinding`: the result of `ristretto255` SHA3-512
28/// hash-to-group on input `B_bytes`.
29#[derive(Copy, Clone)]
30pub struct PedersenGens<G: AffineRepr> {
31    /// Base for the committed value
32    pub B: G,
33    /// Base for the blinding factor
34    pub B_blinding: G,
35}
36
37impl<G: AffineRepr> PedersenGens<G> {
38    /// Creates a Pedersen commitment using the value scalar and a blinding factor.
39    pub fn commit(&self, value: G::ScalarField, blinding: G::ScalarField) -> G {
40        self.B
41            .mul_bigint(value.into_bigint())
42            .add(self.B_blinding.mul_bigint(blinding.into_bigint()))
43            .into_affine()
44    }
45}
46
47impl<G: AffineRepr> Default for PedersenGens<G> {
48    fn default() -> Self {
49        let mut bytes = Vec::new();
50        (G::generator()).serialize_uncompressed(&mut bytes).unwrap();
51
52        let mut hash = Sha3_512::new();
53        Digest::update(&mut hash, &bytes);
54        let h = hash.finalize();
55
56        let mut res = [0u8; 32];
57        res.copy_from_slice(&h[..32]);
58
59        let mut prng = ChaChaRng::from_seed(res);
60
61        PedersenGens {
62            B: G::generator(),
63            B_blinding: G::rand(&mut prng),
64        }
65    }
66}
67
68/// The `GeneratorsChain` creates an arbitrary-long sequence of
69/// orthogonal generators.  The sequence can be deterministically
70/// produced starting with an arbitrary point.
71struct GeneratorsChain<G: AffineRepr> {
72    prng: ChaChaRng,
73    affine_curve_phantom: PhantomData<G>,
74}
75
76impl<G: AffineRepr> GeneratorsChain<G> {
77    /// Creates a chain of generators, determined by the hash of `label`.
78    fn new(label: &[u8]) -> Self {
79        let mut hash = Sha3_512::new();
80        Digest::update(&mut hash, b"GeneratorsChain");
81        Digest::update(&mut hash, label);
82        let h = hash.finalize();
83
84        let mut res = [0u8; 32];
85        res.copy_from_slice(&h[..32]);
86
87        let prng = ChaChaRng::from_seed(res);
88
89        GeneratorsChain {
90            prng,
91            affine_curve_phantom: PhantomData,
92        }
93    }
94
95    /// Advances the reader n times, squeezing and discarding
96    /// the result.
97    fn fast_forward(mut self, n: usize) -> Self {
98        for _ in 0..n {
99            let _ = G::rand(&mut self.prng);
100        }
101        self
102    }
103}
104
105impl<G: AffineRepr> Default for GeneratorsChain<G> {
106    fn default() -> Self {
107        Self::new(&[])
108    }
109}
110
111impl<G: AffineRepr> Iterator for GeneratorsChain<G> {
112    type Item = G;
113
114    fn next(&mut self) -> Option<Self::Item> {
115        Some(G::rand(&mut self.prng))
116    }
117
118    fn size_hint(&self) -> (usize, Option<usize>) {
119        (usize::MAX, None)
120    }
121}
122
123/// The `BulletproofGens` struct contains all the generators needed
124/// for aggregating up to `m` range proofs of up to `n` bits each.
125///
126/// # Extensible Generator Generation
127///
128/// Instead of constructing a single vector of size `m*n`, as
129/// described in the Bulletproofs paper, we construct each party's
130/// generators separately.
131///
132/// To construct an arbitrary-length chain of generators, we apply
133/// SHAKE256 to a domain separator label, and feed each 64 bytes of
134/// XOF output into the `ristretto255` hash-to-group function.
135/// Each of the `m` parties' generators are constructed using a
136/// different domain separation label, and proving and verification
137/// uses the first `n` elements of the arbitrary-length chain.
138///
139/// This means that the aggregation size (number of
140/// parties) is orthogonal to the rangeproof size (number of bits),
141/// and allows using the same `BulletproofGens` object for different
142/// proving parameters.
143///
144/// This construction is also forward-compatible with constraint
145/// system proofs, which use a much larger slice of the generator
146/// chain, and even forward-compatible to multiparty aggregation of
147/// constraint system proofs, since the generators are namespaced by
148/// their party index.
149#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
150pub struct BulletproofGens<G: AffineRepr> {
151    /// The maximum number of usable generators for each party.
152    pub gens_capacity: usize,
153    /// Number of values or parties
154    pub party_capacity: usize,
155    /// Precomputed \\(\mathbf G\\) generators for each party.
156    G_vec: Vec<Vec<G>>,
157    /// Precomputed \\(\mathbf H\\) generators for each party.
158    H_vec: Vec<Vec<G>>,
159}
160
161impl<G: AffineRepr> BulletproofGens<G> {
162    /// Create a new `BulletproofGens` object.
163    ///
164    /// # Inputs
165    ///
166    /// * `gens_capacity` is the number of generators to precompute
167    ///    for each party.  For rangeproofs, it is sufficient to pass
168    ///    `64`, the maximum bitsize of the rangeproofs.  For circuit
169    ///    proofs, the capacity must be greater than the number of
170    ///    multipliers, rounded up to the next power of two.
171    ///
172    /// * `party_capacity` is the maximum number of parties that can
173    ///    produce an aggregated proof.
174    pub fn new(gens_capacity: usize, party_capacity: usize) -> Self {
175        let mut gens = BulletproofGens {
176            gens_capacity: 0,
177            party_capacity,
178            G_vec: (0..party_capacity).map(|_| Vec::new()).collect(),
179            H_vec: (0..party_capacity).map(|_| Vec::new()).collect(),
180        };
181        gens.increase_capacity(gens_capacity);
182        gens
183    }
184
185    /// Returns j-th share of generators, with an appropriate
186    /// slice of vectors G and H for the j-th range proof.
187    pub fn share(&self, j: usize) -> BulletproofGensShare<'_, G> {
188        BulletproofGensShare {
189            gens: &self,
190            share: j,
191        }
192    }
193
194    /// Increases the generators' capacity to the amount specified.
195    /// If less than or equal to the current capacity, does nothing.
196    pub fn increase_capacity(&mut self, new_capacity: usize) {
197        use byteorder::{ByteOrder, LittleEndian};
198
199        if self.gens_capacity >= new_capacity {
200            return;
201        }
202
203        for i in 0..self.party_capacity {
204            let party_index = i as u32;
205            let mut label = [b'G', 0, 0, 0, 0];
206            LittleEndian::write_u32(&mut label[1..5], party_index);
207            self.G_vec[i].extend(
208                &mut GeneratorsChain::<G>::new(&label)
209                    .fast_forward(self.gens_capacity)
210                    .take(new_capacity - self.gens_capacity),
211            );
212
213            label[0] = b'H';
214            self.H_vec[i].extend(
215                &mut GeneratorsChain::<G>::new(&label)
216                    .fast_forward(self.gens_capacity)
217                    .take(new_capacity - self.gens_capacity),
218            );
219        }
220        self.gens_capacity = new_capacity;
221    }
222
223    /// Return an iterator over the aggregation of the parties' G generators with given size `n`.
224    pub fn G(&self, n: usize, m: usize) -> impl Iterator<Item = &G> {
225        AggregatedGensIter {
226            n,
227            m,
228            array: &self.G_vec,
229            party_idx: 0,
230            gen_idx: 0,
231        }
232    }
233
234    /// Return an iterator over the aggregation of the parties' H generators with given size `n`.
235    pub fn H(&self, n: usize, m: usize) -> impl Iterator<Item = &G> {
236        AggregatedGensIter {
237            n,
238            m,
239            array: &self.H_vec,
240            party_idx: 0,
241            gen_idx: 0,
242        }
243    }
244}
245
246struct AggregatedGensIter<'a, G: AffineRepr> {
247    array: &'a Vec<Vec<G>>,
248    n: usize,
249    m: usize,
250    party_idx: usize,
251    gen_idx: usize,
252}
253
254impl<'a, G: AffineRepr> Iterator for AggregatedGensIter<'a, G> {
255    type Item = &'a G;
256
257    fn next(&mut self) -> Option<Self::Item> {
258        if self.gen_idx >= self.n {
259            self.gen_idx = 0;
260            self.party_idx += 1;
261        }
262
263        if self.party_idx >= self.m {
264            None
265        } else {
266            let cur_gen = self.gen_idx;
267            self.gen_idx += 1;
268            Some(&self.array[self.party_idx][cur_gen])
269        }
270    }
271
272    fn size_hint(&self) -> (usize, Option<usize>) {
273        let size = self.n * (self.m - self.party_idx) - self.gen_idx;
274        (size, Some(size))
275    }
276}
277
278/// Represents a view of the generators used by a specific party in an
279/// aggregated proof.
280///
281/// The `BulletproofGens` struct represents generators for an aggregated
282/// range proof `m` proofs of `n` bits each; the `BulletproofGensShare`
283/// provides a view of the generators for one of the `m` parties' shares.
284///
285/// The `BulletproofGensShare` is produced by [`BulletproofGens::share()`].
286#[derive(Copy, Clone)]
287pub struct BulletproofGensShare<'a, G: AffineRepr> {
288    /// The parent object that this is a view into
289    gens: &'a BulletproofGens<G>,
290    /// Which share we are
291    share: usize,
292}
293
294impl<'a, G: AffineRepr> BulletproofGensShare<'a, G> {
295    /// Return an iterator over this party's G generators with given size `n`.
296    pub(crate) fn G(&self, n: usize) -> impl Iterator<Item = &'a G> {
297        self.gens.G_vec[self.share].iter().take(n)
298    }
299
300    /// Return an iterator over this party's H generators with given size `n`.
301    pub(crate) fn H(&self, n: usize) -> impl Iterator<Item = &'a G> {
302        self.gens.H_vec[self.share].iter().take(n)
303    }
304}
305
306#[cfg(test)]
307mod tests {
308    use super::*;
309
310    #[test]
311    fn aggregated_gens_iter_matches_flat_map() {
312        type G = ark_secq256k1::Affine;
313
314        let gens = BulletproofGens::<G>::new(64, 8);
315
316        let helper = |n: usize, m: usize| {
317            let agg_G: Vec<G> = gens.G(n, m).cloned().collect();
318            let flat_G: Vec<G> = gens
319                .G_vec
320                .iter()
321                .take(m)
322                .flat_map(move |G_j| G_j.iter().take(n))
323                .cloned()
324                .collect();
325
326            let agg_H: Vec<G> = gens.H(n, m).cloned().collect();
327            let flat_H: Vec<G> = gens
328                .H_vec
329                .iter()
330                .take(m)
331                .flat_map(move |H_j| H_j.iter().take(n))
332                .cloned()
333                .collect();
334
335            assert_eq!(agg_G, flat_G);
336            assert_eq!(agg_H, flat_H);
337        };
338
339        helper(64, 8);
340        helper(64, 4);
341        helper(64, 2);
342        helper(64, 1);
343        helper(32, 8);
344        helper(32, 4);
345        helper(32, 2);
346        helper(32, 1);
347        helper(16, 8);
348        helper(16, 4);
349        helper(16, 2);
350        helper(16, 1);
351    }
352
353    #[test]
354    fn resizing_small_gens_matches_creating_bigger_gens() {
355        type G = ark_secq256k1::Affine;
356
357        let gens = BulletproofGens::<G>::new(64, 8);
358
359        let mut gen_resized = BulletproofGens::<G>::new(32, 8);
360        gen_resized.increase_capacity(64);
361
362        let helper = |n: usize, m: usize| {
363            let gens_G: Vec<G> = gens.G(n, m).cloned().collect();
364            let gens_H: Vec<G> = gens.H(n, m).cloned().collect();
365
366            let resized_G: Vec<G> = gen_resized.G(n, m).cloned().collect();
367            let resized_H: Vec<G> = gen_resized.H(n, m).cloned().collect();
368
369            assert_eq!(gens_G, resized_G);
370            assert_eq!(gens_H, resized_H);
371        };
372
373        helper(64, 8);
374        helper(32, 8);
375        helper(16, 8);
376    }
377}
ark_bulletproofs/generators.rs

ark_bulletproofs/
generators.rs
