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

noah_bulletproofs/
generators.rs
