Function lagrange_coefficient

pub fn lagrange_coefficient<E: Curve>(
    x: Scalar<E>,
    j: usize,
    xs: &[impl AsRef<Scalar<E>>],
) -> Option<NonZero<Scalar<E>>>

Calculates lagrange coefficient $\lambda_j$ to interpolate a polynomial at point $x$

Lagrange coefficient are often used to turn polynomial key shares into additive key shares.

Inputs

xs denotes the points with known values that define the polynomial. j is a index of element in xs for which lagrange coefficient is calculated. x is a point at which the polynomial is interpolated.

Returns

Returns None if j >= xs.len() or if there’s m such that xs[j] == xs[m] or x == xs[m]. Note that, generally, lagrange interpolation is only defined when elements in xs are pairwise distinct.

Example

use generic_ec::{Scalar, SecretScalar, NonZero, curves::Secp256k1};
use generic_ec_zkp::polynomial::{Polynomial, lagrange_coefficient};

let secret = SecretScalar::<Secp256k1>::random(&mut OsRng);
// polynomial `f(x)` shares `f(0) = secret`
let f = Polynomial::sample_with_const_term(&mut OsRng, 2, secret.clone());

// Publicly-known shares indexes
let I = [Scalar::from(1), Scalar::from(2), Scalar::from(3)];
// Secret shares
let shares: [Scalar<_>; 3] = I.map(|i| f.value(&i));

// Reconstruct a `secret = f(0)`
let lambdas = [0, 1, 2].map(|j| lagrange_coefficient(Scalar::zero(), j, &I).unwrap());
let reconstructed_secret = lambdas
    .into_iter()
    .zip(shares)
    .map(|(lambda_i, x_i)| lambda_i * x_i)
    .sum::<Scalar<_>>();
assert_eq!(secret.as_ref(), &reconstructed_secret);