generic_ec_zkp/
polynomial.rs

1//! Provides [polynomial](Polynomial) primitive, typically used in secret sharing and threshold DKG
2
3#[cfg(feature = "alloc")]
4#[doc(inline)]
5pub use requires_alloc::*;
6
7#[cfg(feature = "alloc")]
8#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
9mod requires_alloc {
10    use alloc::{vec, vec::Vec};
11    use core::{iter, ops};
12
13    use generic_ec::traits::{IsZero, Samplable, Zero};
14    use rand_core::RngCore;
15
16    /// Polynomial $f(x) = \sum_i a_i x^i$ defined as a list of coefficients $[a_0, \dots, a_{\text{degree}}]$
17    ///
18    /// Polynomial is generic over type of coefficients `C`, it can be `Scalar<E>`, `NonZero<Scalar<E>>`, `SecretScalar<E>`, `Point<E>`,
19    /// or any other type that implements necessary traits.
20    #[derive(Debug, Clone)]
21    #[cfg_attr(feature = "udigest", derive(udigest::Digestable))]
22    pub struct Polynomial<C> {
23        /// `coefs[i]` is coefficient of `x^i` term
24        ///
25        /// Last element of `coefs` must be non-zero
26        coefs: Vec<C>,
27    }
28
29    impl<C: IsZero> Polynomial<C> {
30        /// Constructs a polynomial from its coefficients
31        ///
32        /// `coefs[i]` is coefficient of `x^i` term. Resulting polynomial will be
33        /// $f(x) = \sum_i \\text{coefs}_i \cdot x^i$
34        ///
35        /// ## Example
36        /// ```rust
37        /// # use rand_core::OsRng;
38        /// use generic_ec::{Scalar, curves::Secp256k1};
39        /// use generic_ec_zkp::polynomial::Polynomial;
40        ///
41        /// let coefs: [Scalar<Secp256k1>; 3] = [
42        ///     Scalar::random(&mut OsRng),
43        ///     Scalar::random(&mut OsRng),
44        ///     Scalar::random(&mut OsRng),    
45        /// ];
46        /// let polynomial = Polynomial::from_coefs(coefs.to_vec());
47        ///
48        /// let x = Scalar::random(&mut OsRng);
49        /// assert_eq!(
50        ///     coefs[0] + x * coefs[1] + x * x * coefs[2],
51        ///     polynomial.value::<_, Scalar<_>>(&x),
52        /// );
53        /// ```
54        pub fn from_coefs(mut coefs: Vec<C>) -> Self {
55            // Truncate trailing zeroes
56            let zeroes_count = coefs
57                .iter()
58                .rev()
59                .take_while(|coef_i| coef_i.is_zero())
60                .count();
61            let coefs_len = coefs.len();
62            coefs.truncate(coefs_len - zeroes_count);
63
64            Self { coefs }
65        }
66    }
67
68    impl<C> Polynomial<C> {
69        /// Returns polynomial degree
70        ///
71        /// Polynomial degree is index of most significant non-zero coefficient. Polynomial $f(x) = 0$
72        /// considered to have degree $deg(f) = 0$.
73        ///
74        /// $$
75        /// \begin{dcases}
76        /// deg(f(x) = \sum_i a_i \cdot x^i) &= n \\text{, where } a_n \ne 0 \land n \to max \\\\
77        /// deg(f(x) = 0) &= 0
78        /// \end{dcases}
79        /// $$
80        pub fn degree(&self) -> usize {
81            #[allow(clippy::expect_used)]
82            match self.coefs.len() {
83                0 => 0,
84                len => len - 1,
85            }
86        }
87
88        /// Returns polynomial coefficients
89        pub fn coefs(&self) -> &[C] {
90            &self.coefs
91        }
92
93        /// Destructs polynomial, returns its coefficients
94        pub fn into_coefs(self) -> Vec<C> {
95            self.coefs
96        }
97    }
98
99    impl<C: Samplable> Polynomial<C> {
100        /// Samples a random polynomial with specified degree
101        pub fn sample(rng: &mut impl RngCore, degree: usize) -> Self {
102            Self {
103                coefs: iter::repeat_with(|| C::random(rng))
104                    .take(degree + 1)
105                    .collect(),
106            }
107        }
108
109        /// Samples a random polynomial with specified degree and constant term
110        ///
111        /// Constant term determines value of polynomial at point zero: $f(0) = \\text{const\\_term}$
112        ///
113        /// ## Example
114        /// ```rust
115        /// use generic_ec::{Scalar, curves::Secp256k1};
116        /// use generic_ec_zkp::polynomial::Polynomial;
117        /// # use rand_core::OsRng;
118        ///
119        /// let const_term = Scalar::<Secp256k1>::from(1234);
120        /// let polynomial = Polynomial::sample_with_const_term(&mut OsRng, 3, const_term);
121        /// assert_eq!(const_term, polynomial.value::<_, Scalar<_>>(&Scalar::zero()));
122        /// ```
123        pub fn sample_with_const_term(
124            rng: &mut impl RngCore,
125            degree: usize,
126            const_term: C,
127        ) -> Self {
128            Self {
129                coefs: iter::once(const_term)
130                    .chain(iter::repeat_with(|| C::random(rng)).take(degree))
131                    .collect(),
132            }
133        }
134    }
135
136    impl<C> Polynomial<C> {
137        /// Evaluates polynomial value at given point: $f(\\text{point})$
138        ///
139        /// Polynomial coefficients, point, and output can all be differently typed.
140        ///
141        /// ## Example: polynomial with coefficients typed as non-zero scalars vs elliptic points
142        /// Let $f(x) = a_1 \cdot x + a_0$ and $F(x) = G \cdot f(x)$. Coefficients
143        /// of $f(x)$ are typed as `NonZero<Scalar<E>>`, and $F(x)$ has coefficients typed as `NonZero<Point<E>>`.
144        ///
145        /// When we evaluate $f(x)$, we have coefficients `C` of type `NonZero<Scalar<E>>`, and both point `P`
146        /// and output `O` of type `Scalar<E>`.
147        ///
148        /// On other hand, when $F(x)$ is evaluated, coefficients `C` have type `NonZero<Point<E>>`, point `P` has
149        /// type `Scalar<E>`, and output `O` is of type `Point<E>`.
150        ///
151        /// ```rust
152        /// use generic_ec::{Point, Scalar, NonZero, curves::Secp256k1};
153        /// use generic_ec_zkp::polynomial::Polynomial;
154        /// # use rand_core::OsRng;
155        ///
156        /// let f: Polynomial<NonZero<Scalar<Secp256k1>>> = Polynomial::sample(&mut OsRng, 1);
157        /// let F: Polynomial<NonZero<Point<_>>> = &f * &Point::generator();
158        ///
159        /// let x = Scalar::random(&mut OsRng);
160        /// assert_eq!(
161        ///     f.value::<_, Scalar<_>>(&x) * Point::generator(),    
162        ///     F.value::<_, Point<_>>(&x)
163        /// );
164        /// ```
165        pub fn value<P, O>(&self, point: &P) -> O
166        where
167            O: Zero,
168            for<'a> O: ops::Mul<&'a P, Output = O> + ops::Add<&'a C, Output = O>,
169        {
170            self.coefs
171                .iter()
172                .rev()
173                .fold(O::zero(), |acc, coef_i| acc * point + coef_i)
174        }
175    }
176
177    /// Multiplies polyinomial $F(x)$ at $k$ returning resulting polyinomial
178    /// $F'(x) = k \cdot F(x)$ without allocations
179    ///
180    /// $k$ needs to be of type `C`.
181    impl<C> ops::Mul<&C> for Polynomial<C>
182    where
183        for<'a> &'a C: ops::Mul<&'a C, Output = C>,
184    {
185        type Output = Polynomial<C>;
186
187        fn mul(mut self, rhs: &C) -> Self::Output {
188            self.coefs
189                .iter_mut()
190                .for_each(|coef_i| *coef_i = &*coef_i * rhs);
191            self
192        }
193    }
194
195    /// Multiplies polynomial $F(x)$ at $k$ returning resulting polynomial
196    /// $F'(x) = k \cdot F(x)$, resulting polynomial is allocated at heap
197    ///
198    /// $k$ can be any type as long as it can be multiplied at `C`
199    impl<B, C, O> ops::Mul<&B> for &Polynomial<C>
200    where
201        for<'a> &'a C: ops::Mul<&'a B, Output = O>,
202    {
203        type Output = Polynomial<O>;
204
205        fn mul(self, rhs: &B) -> Self::Output {
206            Polynomial {
207                coefs: self.coefs.iter().map(|coef_i| coef_i * rhs).collect(),
208            }
209        }
210    }
211
212    impl<C> ops::AddAssign<&Polynomial<C>> for Polynomial<C>
213    where
214        C: Clone + for<'a> ops::AddAssign<&'a C>,
215    {
216        fn add_assign(&mut self, rhs: &Polynomial<C>) {
217            self.coefs
218                .iter_mut()
219                .zip(&rhs.coefs)
220                .for_each(|(f1_coef_i, f2_coef_i)| *f1_coef_i += f2_coef_i);
221            if self.coefs.len() < rhs.coefs.len() {
222                let self_len = self.coefs.len();
223                self.coefs.extend_from_slice(&rhs.coefs[self_len..])
224            }
225        }
226    }
227
228    impl<C> ops::Add<&Polynomial<C>> for Polynomial<C>
229    where
230        C: Clone + for<'a> ops::AddAssign<&'a C>,
231    {
232        type Output = Polynomial<C>;
233
234        fn add(mut self, rhs: &Polynomial<C>) -> Self::Output {
235            self += rhs;
236            self
237        }
238    }
239
240    impl<'a, C> iter::Sum<&'a Polynomial<C>> for Polynomial<C>
241    where
242        C: Clone + 'a,
243        C: for<'c> ops::AddAssign<&'c C>,
244    {
245        fn sum<I: Iterator<Item = &'a Polynomial<C>>>(mut iter: I) -> Self {
246            let Some(mut sum) = iter.next().cloned() else {
247                return Self { coefs: vec![] };
248            };
249            for polynomial in iter {
250                sum += polynomial;
251            }
252            sum
253        }
254    }
255
256    impl<C> iter::Sum<Polynomial<C>> for Polynomial<C>
257    where
258        C: for<'a> ops::AddAssign<&'a C> + Clone,
259    {
260        fn sum<I: Iterator<Item = Polynomial<C>>>(mut iter: I) -> Self {
261            let Some(mut sum) = iter.next() else {
262                return Self { coefs: vec![] };
263            };
264            for polynomial in iter {
265                sum += &polynomial
266            }
267            sum
268        }
269    }
270
271    #[cfg(feature = "serde")]
272    impl<C> serde::Serialize for Polynomial<C>
273    where
274        C: serde::Serialize,
275    {
276        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
277        where
278            S: serde::Serializer,
279        {
280            self.coefs.serialize(serializer)
281        }
282    }
283
284    #[cfg(feature = "serde")]
285    impl<'de, C: IsZero> serde::Deserialize<'de> for Polynomial<C>
286    where
287        C: serde::Deserialize<'de>,
288    {
289        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
290        where
291            D: serde::Deserializer<'de>,
292        {
293            let coefs = Vec::<C>::deserialize(deserializer)?;
294            Ok(Self::from_coefs(coefs))
295        }
296    }
297}
298
299use generic_ec::{Curve, NonZero, Scalar};
300
301/// Calculates lagrange coefficient $\lambda_j$ to interpolate a polynomial at point $x$
302///
303/// Lagrange coefficient are often used to turn polynomial key shares into additive
304/// key shares.
305///
306/// ## Inputs
307///
308/// `xs` denotes the points with known values that define the polynomial. `j` is a index
309/// of element in `xs` for which lagrange coefficient is calculated. `x` is a point at
310/// which the polynomial is interpolated.
311///
312/// ## Returns
313/// Returns `None` if `j >= xs.len()` or if there's `m` such that `xs[j] == xs[m]` or
314/// `x == xs[m]`. Note that, generally, lagrange interpolation is only defined when
315/// elements in `xs` are pairwise distinct.
316///
317/// ## Example
318/// ```rust
319/// use generic_ec::{Scalar, SecretScalar, NonZero, curves::Secp256k1};
320/// use generic_ec_zkp::polynomial::{Polynomial, lagrange_coefficient};
321/// # use rand_core::OsRng;
322///
323/// let secret = SecretScalar::<Secp256k1>::random(&mut OsRng);
324/// // polynomial `f(x)` shares `f(0) = secret`
325/// let f = Polynomial::sample_with_const_term(&mut OsRng, 2, secret.clone());
326///
327/// // Publicly-known shares indexes
328/// let I = [Scalar::from(1), Scalar::from(2), Scalar::from(3)];
329/// // Secret shares
330/// let shares: [Scalar<_>; 3] = I.map(|i| f.value(&i));
331///
332/// // Reconstruct a `secret = f(0)`
333/// let lambdas = [0, 1, 2].map(|j| lagrange_coefficient(Scalar::zero(), j, &I).unwrap());
334/// let reconstructed_secret = lambdas
335///     .into_iter()
336///     .zip(shares)
337///     .map(|(lambda_i, x_i)| lambda_i * x_i)
338///     .sum::<Scalar<_>>();
339/// assert_eq!(secret.as_ref(), &reconstructed_secret);
340/// ```
341pub fn lagrange_coefficient<E: Curve>(
342    x: Scalar<E>,
343    j: usize,
344    xs: &[impl AsRef<Scalar<E>>],
345) -> Option<NonZero<Scalar<E>>> {
346    let xs_without_j = xs
347        .iter()
348        .enumerate()
349        .filter(|(i, _x_i)| *i != j)
350        .map(|(_, x_i)| x_i);
351    let nom = xs_without_j
352        .clone()
353        .map(|x_m| x - x_m.as_ref())
354        .product::<Scalar<E>>();
355
356    let x_j = xs.get(j)?.as_ref();
357    let denom = xs_without_j
358        .map(|x_m| x_j - x_m.as_ref())
359        .product::<Scalar<E>>();
360    let denom_inv = denom.invert()?;
361
362    NonZero::from_scalar(nom * denom_inv)
363}
364
365/// Calculates lagrange coefficient $\lambda_j$ to interpolate a polynomial at point $0$
366///
367/// Functionally the same as calling [`lagrange_coefficient(Scalar::zero(), j, xs)`](lagrange_coefficient),
368/// but a bit faster.
369pub fn lagrange_coefficient_at_zero<E: Curve>(
370    j: usize,
371    xs: &[impl AsRef<Scalar<E>>],
372) -> Option<NonZero<Scalar<E>>> {
373    let xs_without_j = xs
374        .iter()
375        .enumerate()
376        .filter(|(i, _x_i)| *i != j)
377        .map(|(_, x_i)| x_i.as_ref());
378    let nom = xs_without_j.clone().product::<Scalar<E>>();
379
380    let x_j = xs.get(j)?.as_ref();
381    let denom = xs_without_j.map(|x_m| x_m - x_j).product::<Scalar<E>>();
382    let denom_inv = denom.invert()?;
383
384    NonZero::from_scalar(nom * denom_inv)
385}
386
387#[cfg(all(test, feature = "alloc"))]
388#[generic_tests::define]
389#[allow(non_snake_case)]
390mod tests {
391    use alloc::vec::Vec;
392    use core::iter;
393
394    use generic_ec::{Curve, Point, Scalar, SecretScalar};
395    use rand::Rng;
396    use rand_dev::DevRng;
397
398    use crate::polynomial::lagrange_coefficient;
399
400    use super::Polynomial;
401
402    #[test]
403    fn secret_sharing<E: Curve>() {
404        let mut rng = DevRng::new();
405
406        // 1. Sample secret
407        let secret = SecretScalar::<E>::random(&mut rng);
408        let f = Polynomial::sample_with_const_term(&mut rng, 3, secret.clone());
409
410        // Chech that `f(0) = secret`
411        {
412            let f_0: Scalar<_> = f.value(&Scalar::zero());
413            assert_eq!(secret.as_ref(), &f_0);
414        }
415
416        // 2. Commit to the secret
417        // F(x) = G * f(x)
418        let F = &f * &Point::generator();
419        assert_eq!(
420            &secret * Point::generator(),
421            F.value::<_, Point<_>>(&Scalar::zero())
422        );
423
424        // 3. Derive 4 secret and public shares
425        let shares_indexes: [Scalar<E>; 4] = [
426            Scalar::from(1),
427            Scalar::from(2),
428            Scalar::from(3),
429            Scalar::from(4),
430        ];
431        let shares: [Scalar<_>; 4] = shares_indexes.map(|i| f.value(&i));
432        let public_shares = shares.map(|secret_share| Point::generator() * secret_share);
433
434        // Chech that `public_shares[i] = F(i)`
435        {
436            for (i, public_share) in (1..).zip(&public_shares) {
437                assert_eq!(public_share, &F.value::<_, Point<E>>(&Scalar::from(i)));
438            }
439        }
440
441        // 4. Reconstruct the secret
442        let lambdas =
443            [0, 1, 2, 3].map(|j| lagrange_coefficient(Scalar::zero(), j, &shares_indexes).unwrap());
444        let reconstructed_secret: Scalar<E> = lambdas
445            .into_iter()
446            .zip(shares)
447            .map(|(lambda_i, x_i)| lambda_i * x_i)
448            .sum();
449        assert_eq!(secret.as_ref(), &reconstructed_secret);
450
451        assert_eq!(
452            lambdas,
453            [0, 1, 2, 3].map(|j| super::lagrange_coefficient_at_zero(j, &shares_indexes).unwrap())
454        );
455    }
456
457    #[test]
458    fn polynomial_sum<E: Curve>() {
459        let mut rng = DevRng::new();
460
461        // Sample 10 polynomials of different degree
462        let polynomials: Vec<Polynomial<Scalar<E>>> = iter::repeat_with(|| {
463            let degree = rng.gen_range(5..15);
464            Polynomial::sample(&mut rng, degree)
465        })
466        .take(10)
467        .collect();
468
469        let polynomials_sum1: Polynomial<Scalar<E>> = polynomials.iter().sum();
470        let polynomials_sum2: Polynomial<Scalar<E>> = polynomials.iter().cloned().sum();
471
472        let point = Scalar::random(&mut rng);
473
474        let value_actual1 = polynomials_sum1.value::<_, Scalar<E>>(&point);
475        let value_actual2 = polynomials_sum2.value::<_, Scalar<E>>(&point);
476
477        let value_expected: Scalar<E> = polynomials
478            .iter()
479            .map(|f_i| f_i.value::<_, Scalar<E>>(&point))
480            .sum();
481
482        assert_eq!(value_expected, value_actual1);
483        assert_eq!(value_expected, value_actual2);
484    }
485
486    #[test]
487    fn polynomial_from_coefs<E: Curve>() {
488        let mut rng = DevRng::new();
489
490        let coefs = [
491            Scalar::<E>::random(&mut rng),
492            Scalar::random(&mut rng),
493            Scalar::random(&mut rng),
494        ];
495        let f = Polynomial::from_coefs(coefs.to_vec());
496
497        assert_eq!(f.degree(), 2);
498
499        for _ in 0..100 {
500            let x = Scalar::random(&mut rng);
501
502            let f_x: Scalar<E> = f.value(&x);
503            let expected = coefs[0] + x * coefs[1] + x * x * coefs[2];
504
505            assert_eq!(f_x, expected);
506        }
507    }
508
509    #[instantiate_tests(<generic_ec::curves::Secp256k1>)]
510    mod secp256k1 {}
511    #[instantiate_tests(<generic_ec::curves::Secp256r1>)]
512    mod secp256r1 {}
513    #[instantiate_tests(<generic_ec::curves::Stark>)]
514    mod stark {}
515}
generic_ec_zkp/polynomial.rs

generic_ec_zkp/
polynomial.rs
