shared_types/
pedersen.rs

1// can optimize `vector_commit` to use a MSM (pippenger's) instead of the for loop
2
3use std::cmp::max;
4use std::ops::{Add, Mul};
5
6use crate::curves::PrimeOrderCurve;
7use crate::curves::Sha3XofReaderWrapper;
8use crate::ff_field;
9use crate::utils::pippengers::scalar_mult_pippenger;
10use ark_std::log2;
11use itertools::Itertools;
12use num::traits::ToBytes;
13use num::PrimInt;
14use num::Unsigned;
15use num::Zero;
16use serde::{Deserialize, Serialize};
17use sha3::digest::ExtendableOutput;
18use sha3::digest::Update;
19use sha3::Shake256;
20
21#[cfg(test)]
22/// The tests for pedersen commitments.
23pub mod tests;
24
25/// For committing to vectors of integers and scalars using the Pedersen commitment scheme.
26#[derive(Debug, Serialize, Deserialize, Clone)]
27#[serde(bound = "C: PrimeOrderCurve")]
28pub struct PedersenCommitter<C: PrimeOrderCurve> {
29    /// vector of "g" generators, i.e. the generators that are exponentiated by the message elements themselves (length > 0)
30    /// The first N generators are used to commit to a vector of N values. The last generator is used for scalar commitments.
31    pub generators: Vec<C>,
32    /// the "h" generator which is exponentiated by the blinding factor
33    pub blinding_generator: C,
34    /// The bitwidth of the absolute values of the integers that can be committed to using integral vector commit methods (has no bearing on scalar_commit and vector_commit).
35    pub int_abs_val_bitwidth: usize,
36    generator_doublings: Vec<Vec<C>>,
37}
38
39impl<C: PrimeOrderCurve> PedersenCommitter<C> {
40    const DEFAULT_INT_ABS_VAL_BITWIDTH: usize = 8;
41    /// Creates a new PedersenCommitter with random generators.  See also [PedersenCommitter].
42    /// Generators are sampled using the public string and the Shake256 hash function.
43    /// Post: self.generators.len() == num_generators
44    pub fn new(
45        num_generators: usize,
46        public_string: &str,
47        int_abs_val_bitwidth: Option<usize>,
48    ) -> Self {
49        let all_generators = Self::sample_generators(num_generators + 1, public_string);
50        let blinding_generator_h = all_generators[0];
51        let generators_g_i = all_generators[1..].to_vec();
52        let int_abs_val_bitwidth =
53            int_abs_val_bitwidth.unwrap_or(Self::DEFAULT_INT_ABS_VAL_BITWIDTH);
54
55        let generator_doublings: Vec<Vec<C>> = generators_g_i
56            .clone()
57            .into_iter()
58            .map(|gen| precompute_doublings(gen, int_abs_val_bitwidth))
59            .collect();
60
61        Self {
62            generators: generators_g_i,
63            blinding_generator: blinding_generator_h,
64            int_abs_val_bitwidth,
65            generator_doublings,
66        }
67    }
68
69    /// Return the generator used for scalar commitments.
70    pub fn scalar_commit_generator(&self) -> C {
71        self.generators[self.generators.len() - 1]
72    }
73
74    /// Sample generators using the public string and the Shake256 hash function.
75    /// Pre: public_string.len() >= 32
76    /// Post: result.len() == num_generators
77    /// TODO: make seekable (block cipher)
78    fn sample_generators(num_generators: usize, public_string: &str) -> Vec<C> {
79        assert!(public_string.len() >= 32);
80        let mut public_string_array: [u8; 32] = [0; 32];
81        public_string_array.copy_from_slice(&public_string.as_bytes()[..32]);
82        let mut shake = Shake256::default();
83        shake.update(&public_string_array);
84        let reader = shake.finalize_xof();
85        let mut reader_wrapper = Sha3XofReaderWrapper::new(reader);
86        let generators: Vec<_> = (0..num_generators)
87            .map(|_| C::random(&mut reader_wrapper))
88            .collect();
89        generators
90    }
91
92    /// Create a new PedersenCommitter with the provided generators.
93    /// See [PedersenCommitter].
94    /// DEFAULT_INT_ABS_VAL_BITWIDTH is used for `int_abs_val_bitwidth` if None is provided.
95    pub fn new_with_generators(
96        generators: Vec<C>,
97        blinding_generator: C,
98        int_abs_val_bitwidth: Option<usize>,
99    ) -> Self {
100        let int_abs_val_bitwidth =
101            int_abs_val_bitwidth.unwrap_or(Self::DEFAULT_INT_ABS_VAL_BITWIDTH);
102        let generator_doublings: Vec<Vec<C>> = generators
103            .clone()
104            .into_iter()
105            .map(|gen| precompute_doublings(gen, int_abs_val_bitwidth))
106            .collect();
107        Self {
108            generators,
109            blinding_generator,
110            int_abs_val_bitwidth,
111            generator_doublings,
112        }
113    }
114
115    /// An optimized version of Pedersen vector commit when the message is
116    /// comprised of values that fit within 128 bits.
117    pub fn unsigned_integer_vector_commit<T: Unsigned + Zero + ToBytes>(
118        &self,
119        message: &[T],
120        blinding: &C::Scalar,
121    ) -> C {
122        assert!(message.len() <= self.generators.len());
123        let unblinded_commit = self
124            .generators
125            .iter()
126            .zip(message.iter())
127            .fold(C::zero(), |acc, (gen, input)| {
128                acc + gen.scalar_mult_unsigned_integer(input)
129            });
130        unblinded_commit + self.blinding_generator * *blinding
131    }
132
133    /// Commits to the vector of u8s using the specified blinding factor.
134    /// Uses the precomputed generator powers and the binary decomposition.
135    /// Convient wrapper of integer_vector_commit.
136    /// Pre: self.int_abs_val_bitwidth >= 8.
137    /// Post: same result as vector_commit, assuming uints are smaller than scalar field order.
138    pub fn u8_vector_commit(&self, message: &[u8], blinding: &C::Scalar) -> C {
139        debug_assert!(self.int_abs_val_bitwidth >= 8);
140        let message_is_negative_bits = vec![false; message.len()];
141        self.integer_vector_commit(message, &message_is_negative_bits, blinding)
142    }
143
144    /// Commits to the vector of i8s using the specified blinding factor.
145    /// Uses the precomputed generator powers and the binary decomposition.
146    /// Convient wrapper of integer_vector_commit.
147    /// Pre: self.int_abs_val_bitwidth >= 8.
148    /// Post: same result as vector_commit, assuming ints are smaller than scalar field order.
149    pub fn i8_vector_commit(&self, message: &[i8], blinding: &C::Scalar) -> C {
150        debug_assert!(self.int_abs_val_bitwidth >= 8);
151        let message_is_negative_bits = message.iter().map(|x| *x < 0i8).collect_vec();
152        let message: Vec<u8> = message
153            .iter()
154            .map(|x| (*x as i16).unsigned_abs() as u8)
155            .collect(); // convert i8 to i16 first so that .abs() doesn't fail for i8::MIN
156        self.integer_vector_commit(&message, &message_is_negative_bits, blinding)
157    }
158
159    /// Commits to the vector of integers using the specified blinding factor.
160    /// Integers are provided as a vector of UNSIGNED ints and a vector of bits indicating whether the integer is negative.
161    /// Pre: values in message are non-negative.
162    /// Pre: values have unsigned binary expressions using at most (self.highest_generator_power + 1) bits.
163    /// Pre: message.len() <= self.message_generators.len()
164    pub fn integer_vector_commit<T: PrimInt>(
165        &self,
166        message: &[T],
167        message_is_negative_bits: &[bool],
168        blinding: &C::Scalar,
169    ) -> C {
170        assert!(message.len() <= self.generators.len());
171        let unblinded_commit = message
172            .iter()
173            .zip(self.generator_doublings.iter())
174            .map(|(input, generator_doublings)| {
175                debug_assert!(*input >= T::zero());
176                let bits = binary_decomposition_le(*input);
177                let mut acc = C::zero();
178                bits.into_iter().enumerate().for_each(|(i, bit)| {
179                    if bit {
180                        debug_assert!(i < self.int_abs_val_bitwidth); // ensure bit decomp is not longer than our precomputed generator powers
181                        acc += generator_doublings[i];
182                    }
183                });
184                acc
185            })
186            .zip(message_is_negative_bits.iter())
187            .map(
188                |(gen_power, is_negative)| {
189                    if *is_negative {
190                        -gen_power
191                    } else {
192                        gen_power
193                    }
194                },
195            )
196            .fold(C::zero(), |acc, value| acc + value);
197
198        unblinded_commit + self.blinding_generator * *blinding
199    }
200
201    /// Commit to the provided vector using the specified blinding factor.
202    /// The first message.len() generators are used to commit to the message.
203    /// Note that self.int_abs_val_bitwidth is not relevant here.
204    /// Pre: message.len() <= self.message_generators.len()
205    pub fn vector_commit(&self, message: &[C::Scalar], blinding: &C::Scalar) -> C {
206        assert!(message.len() <= self.generators.len());
207        let bucket_size = max(1, log2(message.len()));
208        let unblinded_commit = scalar_mult_pippenger(
209            bucket_size as usize,
210            &self.generators[0..message.len()],
211            message,
212        );
213        unblinded_commit + self.blinding_generator * *blinding
214    }
215
216    /// Convenience wrapper of [self.vector_commit] that returns the commitment wrapped in a
217    /// CommittedVector.
218    pub fn committed_vector(
219        &self,
220        message: &[C::Scalar],
221        blinding: &C::Scalar,
222    ) -> CommittedVector<C> {
223        CommittedVector {
224            value: message.to_vec(),
225            blinding: *blinding,
226            commitment: self.vector_commit(message, blinding),
227        }
228    }
229
230    /// Commit to the provided scalar using the specified blinding factor.
231    /// Note that self.int_abs_val_bitwidth is not relevant here.
232    /// Pre: self.message_generators.len() >= 1
233    pub fn scalar_commit(&self, message: &C::Scalar, blinding: &C::Scalar) -> C {
234        self.generators[self.generators.len() - 1] * *message + self.blinding_generator * *blinding
235    }
236
237    /// Convenience wrapper of [self.scalar_commit] that returns the commitment wrapped in a
238    /// CommittedScalar.
239    pub fn committed_scalar(
240        &self,
241        message: &C::Scalar,
242        blinding: &C::Scalar,
243    ) -> CommittedScalar<C> {
244        CommittedScalar {
245            value: *message,
246            blinding: *blinding,
247            commitment: self.scalar_commit(message, blinding),
248        }
249    }
250}
251
252// Compute the little endian binary decomposition of the provided integer value.
253// Pre: value is non-negative.
254// Post: result.len() is std::mem::size_of::<T>() * 8;
255fn binary_decomposition_le<T: PrimInt>(value: T) -> Vec<bool> {
256    debug_assert!(value >= T::zero());
257    let bit_size = std::mem::size_of::<T>() * 8;
258    (0..bit_size)
259        .map(|i| value & (T::one() << i) != T::zero())
260        .collect()
261}
262
263// Returns the vector [2^i * base for i in 0..bitwidth]
264// Post: powers.len() == bitwidth
265fn precompute_doublings<G: PrimeOrderCurve>(base: G, bitwidth: usize) -> Vec<G> {
266    let mut powers = vec![];
267    let mut last = base;
268    for _exponent in 0..bitwidth {
269        powers.push(last);
270        last = last.double();
271    }
272    powers
273}
274
275#[derive(Serialize, Deserialize, Clone, PartialEq, Debug)]
276#[serde(bound = "C: PrimeOrderCurve")]
277/// The committer's view of a scalar commitment, i.e. not just the commitment itself but also the
278/// underlying value and the blinding factor.
279pub struct CommittedScalar<C: PrimeOrderCurve> {
280    /// The value committed to
281    pub value: C::Scalar,
282    /// The blinding factor
283    pub blinding: C::Scalar,
284    /// The commitment
285    pub commitment: C,
286}
287
288impl<C: PrimeOrderCurve> CommittedScalar<C> {
289    pub fn zero() -> Self {
290        Self {
291            value: C::Scalar::ZERO,
292            blinding: C::Scalar::ZERO,
293            commitment: C::zero(),
294        }
295    }
296
297    /// Panic if the commitment does not match the value and blinding factor when using the provided
298    /// PedersenCommitter.
299    pub fn verify(&self, committer: &PedersenCommitter<C>) {
300        let recomputed_commitment = committer.scalar_commit(&self.value, &self.blinding);
301        assert!(recomputed_commitment == self.commitment)
302    }
303}
304
305impl<C: PrimeOrderCurve> Mul<C::Scalar> for CommittedScalar<C> {
306    type Output = CommittedScalar<C>;
307    /// Multiply the committed scalar by a scalar.
308    fn mul(self, scalar: C::Scalar) -> Self::Output {
309        Self::Output {
310            value: self.value * scalar,
311            blinding: self.blinding * scalar,
312            commitment: self.commitment * scalar,
313        }
314    }
315}
316
317impl<C: PrimeOrderCurve> Mul<C::Scalar> for &CommittedScalar<C> {
318    type Output = CommittedScalar<C>;
319    /// Multiply the committed scalar by a scalar.
320    fn mul(self, scalar: C::Scalar) -> Self::Output {
321        Self::Output {
322            value: self.value * scalar,
323            blinding: self.blinding * scalar,
324            commitment: self.commitment * scalar,
325        }
326    }
327}
328
329impl<C: PrimeOrderCurve> Add<CommittedScalar<C>> for CommittedScalar<C> {
330    type Output = CommittedScalar<C>;
331    /// Add two committed scalars.
332    fn add(self, other: CommittedScalar<C>) -> Self::Output {
333        Self::Output {
334            value: self.value + other.value,
335            blinding: self.blinding + other.blinding,
336            commitment: self.commitment + other.commitment,
337        }
338    }
339}
340
341#[derive(Clone, Debug)]
342/// The committer's view of a vector commitment, i.e. not just the commitment itself but also the
343/// underlying value and the blinding factor.
344pub struct CommittedVector<C: PrimeOrderCurve> {
345    /// The vector of values committed to
346    pub value: Vec<C::Scalar>,
347    /// The blinding factor
348    pub blinding: C::Scalar,
349    /// The commitment
350    pub commitment: C,
351}
352
353impl<C: PrimeOrderCurve> CommittedVector<C> {
354    pub fn zero(length: usize) -> Self {
355        Self {
356            value: (0..length).map(|_| C::Scalar::ZERO).collect(),
357            blinding: C::Scalar::ZERO,
358            commitment: C::zero(),
359        }
360    }
361}
362
363impl<C: PrimeOrderCurve> Mul<C::Scalar> for CommittedVector<C> {
364    type Output = CommittedVector<C>;
365    /// Multiply the committed vector by a scalar.
366    fn mul(self, scalar: C::Scalar) -> Self::Output {
367        Self::Output {
368            value: self.value.iter().map(|val| *val * scalar).collect(),
369            blinding: self.blinding * scalar,
370            commitment: self.commitment * scalar,
371        }
372    }
373}
374
375impl<C: PrimeOrderCurve> Add<CommittedVector<C>> for CommittedVector<C> {
376    type Output = CommittedVector<C>;
377    /// Add two committed vectors.
378    fn add(self, other: CommittedVector<C>) -> Self::Output {
379        Self::Output {
380            value: self
381                .value
382                .iter()
383                .zip(other.value.iter())
384                .map(|(a, b)| *a + *b)
385                .collect(),
386            blinding: self.blinding + other.blinding,
387            commitment: self.commitment + other.commitment,
388        }
389    }
390}
shared_types/pedersen.rs

shared_types/
pedersen.rs
