commonware_cryptography/bls12381/primitives/
poly.rs

1//! Polynomial operations over the BLS12-381 scalar field.
2//!
3//! # Warning
4//!
5//! The security of the polynomial operations is critical for the overall
6//! security of the threshold schemes. Ensure that the scalar field operations
7//! are performed over the correct field and that all elements are valid.
8
9use crate::bls12381::primitives::{
10    group::{self, Element, Scalar},
11    Error,
12};
13use bytes::BufMut;
14use commonware_utils::SizedSerialize;
15use rand::{rngs::OsRng, RngCore};
16use std::collections::BTreeMap;
17
18/// Private polynomials are used to generate secret shares.
19pub type Private = Poly<group::Private>;
20
21/// Public polynomials represent commitments to secrets on a private polynomial.
22pub type Public = Poly<group::Public>;
23
24/// Signature polynomials are used in threshold signing (where a signature
25/// is interpolated using at least `threshold` evaluations).
26pub type Signature = Poly<group::Signature>;
27
28/// The default partial signature type (G2).
29pub type PartialSignature = Eval<group::Signature>;
30
31/// The default partial signature length (G2).
32pub const PARTIAL_SIGNATURE_LENGTH: usize = u32::SERIALIZED_LEN + group::SIGNATURE_LENGTH;
33
34/// A polynomial evaluation at a specific index.
35#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
36pub struct Eval<C: Element> {
37    pub index: u32,
38    pub value: C,
39}
40
41impl<C: Element> Eval<C> {
42    /// Canonically serializes the evaluation.
43    pub fn serialize(&self) -> Vec<u8> {
44        let value_serialized = self.value.serialize();
45        let mut bytes = Vec::with_capacity(u32::SERIALIZED_LEN + value_serialized.len());
46        bytes.put_u32(self.index);
47        bytes.extend_from_slice(&value_serialized);
48        bytes
49    }
50
51    /// Deserializes a canonically encoded evaluation.
52    pub fn deserialize(bytes: &[u8]) -> Option<Self> {
53        let index = u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]);
54        let value = C::deserialize(&bytes[u32::SERIALIZED_LEN..])?;
55        Some(Self { index, value })
56    }
57}
58
59/// A polynomial that is using a scalar for the variable x and a generic
60/// element for the coefficients.
61///
62/// The coefficients must be able to multiply the type of the variable,
63/// which is always a scalar.
64#[derive(Debug, Clone, PartialEq, Eq)]
65// Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L24-L28
66pub struct Poly<C>(Vec<C>);
67
68/// Returns a new scalar polynomial of the given degree where each coefficients is
69/// sampled at random using kernel randomness.
70///
71/// In the context of secret sharing, the threshold is the degree + 1.
72pub fn new(degree: u32) -> Poly<Scalar> {
73    // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L46-L52
74    new_from(degree, &mut OsRng)
75}
76
77// Returns a new scalar polynomial of the given degree where each coefficient is
78// sampled at random from the provided RNG.
79///
80/// In the context of secret sharing, the threshold is the degree + 1.
81pub fn new_from<R: RngCore>(degree: u32, rng: &mut R) -> Poly<Scalar> {
82    // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L46-L52
83    let coeffs = (0..=degree).map(|_| Scalar::rand(rng)).collect::<Vec<_>>();
84    Poly::<Scalar>(coeffs)
85}
86
87impl<C> Poly<C> {
88    /// Creates a new polynomial from the given coefficients.
89    pub fn from(c: Vec<C>) -> Self {
90        Self(c)
91    }
92
93    /// Returns the constant term of the polynomial.
94    pub fn constant(&self) -> &C {
95        &self.0[0]
96    }
97
98    /// Returns the degree of the polynomial
99    pub fn degree(&self) -> u32 {
100        (self.0.len() - 1) as u32 // check size in deserialize, safe to cast
101    }
102
103    /// Returns the number of required shares to reconstruct the polynomial.
104    ///
105    /// This will be the threshold
106    pub fn required(&self) -> u32 {
107        self.0.len() as u32 // check size in deserialize, safe to cast
108    }
109}
110
111impl<C: Element> Poly<C> {
112    /// Commits the scalar polynomial to the group and returns a polynomial over
113    /// the group.
114    ///
115    /// This is done by multiplying each coefficient of the polynomial with the
116    /// group's generator.
117    pub fn commit(commits: Poly<Scalar>) -> Self {
118        // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L322-L340
119        let commits = commits
120            .0
121            .iter()
122            .map(|c| {
123                let mut commitment = C::one();
124                commitment.mul(c);
125                commitment
126            })
127            .collect::<Vec<C>>();
128
129        Poly::<C>::from(commits)
130    }
131
132    /// Returns a zero polynomial.
133    pub fn zero() -> Self {
134        Self::from(vec![C::zero()])
135    }
136
137    /// Returns the given coefficient at the requested index.
138    ///
139    /// It panics if the index is out of range.
140    pub fn get(&self, i: u32) -> C {
141        self.0[i as usize].clone()
142    }
143
144    /// Set the given element at the specified index.
145    ///
146    /// It panics if the index is out of range.
147    pub fn set(&mut self, index: u32, value: C) {
148        self.0[index as usize] = value;
149    }
150
151    /// Performs polynomial addition in place
152    pub fn add(&mut self, other: &Self) {
153        // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L87-L95
154
155        // if we have a smaller degree we should pad with zeros
156        if self.0.len() < other.0.len() {
157            self.0.resize(other.0.len(), C::zero())
158        }
159
160        self.0.iter_mut().zip(&other.0).for_each(|(a, b)| a.add(b))
161    }
162
163    /// Canonically serializes the polynomial.
164    pub fn serialize(&self) -> Vec<u8> {
165        let mut bytes = Vec::new();
166        for c in &self.0 {
167            bytes.extend_from_slice(&c.serialize());
168        }
169        bytes
170    }
171
172    /// Deserializes a canonically encoded polynomial.
173    pub fn deserialize(bytes: &[u8], expected: u32) -> Option<Self> {
174        let expected = expected as usize;
175        let mut coeffs = Vec::with_capacity(expected);
176        for chunk in bytes.chunks_exact(C::size()) {
177            if coeffs.len() >= expected {
178                return None;
179            }
180            let c = C::deserialize(chunk)?;
181            coeffs.push(c);
182        }
183        if coeffs.len() != expected {
184            return None;
185        }
186        Some(Self(coeffs))
187    }
188
189    /// Evaluates the polynomial at the specified value.
190    pub fn evaluate(&self, i: u32) -> Eval<C> {
191        // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L111-L129
192
193        // We add +1 because we must never evaluate the polynomial at its first point
194        // otherwise it reveals the "secret" value after a reshare (where the constant
195        // term is set to be the secret of the previous dealing).
196        let mut xi = Scalar::zero();
197        xi.set_int(i + 1);
198
199        // Use Horner's method to evaluate the polynomial
200        let res = self.0.iter().rev().fold(C::zero(), |mut sum, coeff| {
201            sum.mul(&xi);
202            sum.add(coeff);
203            sum
204        });
205        Eval {
206            value: res,
207            index: i,
208        }
209    }
210
211    /// Recover the polynomial's constant term given at least `t` polynomial evaluations.
212    pub fn recover(t: u32, mut evals: Vec<Eval<C>>) -> Result<C, Error> {
213        // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/a714310be76620e10e8797d6637df64011926430/crates/threshold-bls/src/poly.rs#L131-L165
214
215        // Ensure there are enough shares
216        let t = t as usize;
217        if evals.len() < t {
218            return Err(Error::InvalidRecovery);
219        }
220
221        // Convert the first `t` sorted shares into scalars
222        let mut err = None;
223        evals.sort_by(|a, b| a.index.cmp(&b.index));
224        let xs = evals
225            .into_iter()
226            .take(t)
227            .fold(BTreeMap::new(), |mut m, sh| {
228                let mut xi = Scalar::zero();
229                xi.set_int(sh.index + 1);
230                if m.insert(sh.index, (xi, sh.value)).is_some() {
231                    err = Some(Error::DuplicateEval);
232                }
233                m
234            });
235        if let Some(e) = err {
236            return Err(e);
237        }
238
239        // Iterate over all indices and for each multiply the lagrange basis
240        // with the value of the share
241        let mut acc = C::zero();
242        for (i, xi) in &xs {
243            let mut yi = xi.1.clone();
244            let mut num = Scalar::one();
245            let mut den = Scalar::one();
246
247            for (j, xj) in &xs {
248                if i == j {
249                    continue;
250                }
251
252                // xj - 0
253                num.mul(&xj.0);
254
255                // 1 / (xj - xi)
256                let mut tmp = xj.0;
257                tmp.sub(&xi.0);
258                den.mul(&tmp);
259            }
260
261            let inv = den.inverse().ok_or(Error::NoInverse)?;
262            num.mul(&inv);
263            yi.mul(&num);
264            acc.add(&yi);
265        }
266        Ok(acc)
267    }
268}
269
270/// Returns the public key of the polynomial (constant term).
271pub fn public(public: &Public) -> group::Public {
272    *public.constant()
273}
274
275#[cfg(test)]
276pub mod tests {
277    // Reference: https://github.com/celo-org/celo-threshold-bls-rs/blob/b0ef82ff79769d085a5a7d3f4fe690b1c8fe6dc9/crates/threshold-bls/src/poly.rs#L355-L604
278    use super::*;
279    use crate::bls12381::primitives::group::{Scalar, G2};
280
281    #[test]
282    fn poly_degree() {
283        let s = 5;
284        let p = new(s);
285        assert_eq!(p.degree(), s);
286    }
287
288    #[test]
289    fn add_zero() {
290        let p1 = new(3);
291        let p2 = Poly::<Scalar>::zero();
292        let mut res = p1.clone();
293        res.add(&p2);
294        assert_eq!(res, p1);
295
296        let p1 = Poly::<Scalar>::zero();
297        let p2 = new(3);
298        let mut res = p1;
299        res.add(&p2);
300        assert_eq!(res, p2);
301    }
302
303    #[test]
304    fn interpolation_insufficient_shares() {
305        let degree = 4;
306        let threshold = degree + 1;
307        let poly = new(degree);
308        let shares = (0..threshold - 1)
309            .map(|i| poly.evaluate(i))
310            .collect::<Vec<_>>();
311        Poly::recover(threshold, shares).unwrap_err();
312    }
313
314    #[test]
315    fn commit() {
316        let secret = new(5);
317        let coeffs = secret.0.clone();
318        let commitment = coeffs
319            .iter()
320            .map(|coeff| {
321                let mut p = G2::one();
322                p.mul(coeff);
323                p
324            })
325            .collect::<Vec<_>>();
326        let commitment = Poly::from(commitment);
327        assert_eq!(commitment, Poly::commit(secret));
328    }
329
330    fn pow(base: Scalar, pow: usize) -> Scalar {
331        let mut res = Scalar::one();
332        for _ in 0..pow {
333            res.mul(&base)
334        }
335        res
336    }
337
338    #[test]
339    fn addition() {
340        for deg1 in 0..100u32 {
341            for deg2 in 0..100u32 {
342                let p1 = new(deg1);
343                let p2 = new(deg2);
344                let mut res = p1.clone();
345                res.add(&p2);
346
347                let (larger, smaller) = if p1.degree() > p2.degree() {
348                    (&p1, &p2)
349                } else {
350                    (&p2, &p1)
351                };
352
353                for i in 0..larger.degree() + 1 {
354                    let i = i as usize;
355                    if i < (smaller.degree() + 1) as usize {
356                        let mut coeff_sum = p1.0[i];
357                        coeff_sum.add(&p2.0[i]);
358                        assert_eq!(res.0[i], coeff_sum);
359                    } else {
360                        assert_eq!(res.0[i], larger.0[i]);
361                    }
362                }
363                assert_eq!(
364                    res.degree(),
365                    larger.degree(),
366                    "deg1={}, deg2={}",
367                    deg1,
368                    deg2
369                );
370            }
371        }
372    }
373
374    #[test]
375    fn interpolation() {
376        for degree in 0..100u32 {
377            for num_evals in 0..100u32 {
378                let poly = new(degree);
379                let expected = poly.0[0];
380
381                let shares = (0..num_evals).map(|i| poly.evaluate(i)).collect::<Vec<_>>();
382                let recovered_constant = Poly::recover(num_evals, shares).unwrap();
383
384                if num_evals > degree {
385                    assert_eq!(
386                        expected, recovered_constant,
387                        "degree={}, num_evals={}",
388                        degree, num_evals
389                    );
390                } else {
391                    assert_ne!(
392                        expected, recovered_constant,
393                        "degree={}, num_evals={}",
394                        degree, num_evals
395                    );
396                }
397            }
398        }
399    }
400
401    #[test]
402    fn evaluate() {
403        for d in 0..100u32 {
404            for idx in 0..100_u32 {
405                let mut x = Scalar::zero();
406                x.set_int(idx + 1);
407
408                let p1 = new(d);
409                let evaluation = p1.evaluate(idx).value;
410
411                let coeffs = p1.0;
412                let mut sum = coeffs[0];
413                for (i, coeff) in coeffs
414                    .into_iter()
415                    .enumerate()
416                    .take((d + 1) as usize)
417                    .skip(1)
418                {
419                    let xi = pow(x, i);
420                    let mut var = coeff;
421                    var.mul(&xi);
422                    sum.add(&var);
423                }
424
425                assert_eq!(sum, evaluation, "degree={}, idx={}", d, idx);
426            }
427        }
428    }
429}
commonware_cryptography/bls12381/primitives/poly.rs

commonware_cryptography/bls12381/primitives/
poly.rs
