confium_tc/reshare/
lagrange.rs

1//! Lagrange interpolation helpers for share re-sharing.
2//!
3//! Re-sharing works by computing Lagrange interpolation of existing
4//! shares at new party indices. The result is a new share that is
5//! consistent with the same aggregate secret.
6
7use serde::{Deserialize, Serialize};
8
9/// A field element for Lagrange interpolation. Stored as raw bytes;
10/// the algorithm-specific crate (FROST, CMP20, etc.) interprets them
11/// per the underlying curve/group.
12#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
13pub struct FieldElement(pub Vec<u8>);
14
15impl FieldElement {
16    /// Construct a new field element.
17    pub fn new(bytes: Vec<u8>) -> Self {
18        Self(bytes)
19    }
20}
21
22/// Compute the Lagrange coefficient λ_i(x) evaluated at point `x`,
23/// given the set of x-coordinates `xs` and the index `i`.
24///
25/// For threshold schemes, this is typically computed modulo a prime
26/// that depends on the curve/group. This crate provides the algorithmic
27/// skeleton; concrete modprime arithmetic lives in the algorithm crates.
28pub fn lagrange_basis_at(
29    xs: &[u64],
30    i: usize,
31    x: u64,
32    op_eval: &impl Fn(i128) -> i128,
33    op_mul: &impl Fn(i128, i128) -> i128,
34    op_div: &impl Fn(i128, i128) -> i128,
35) -> i128 {
36    let xi = xs[i] as i128;
37    let mut result = 1i128;
38    for (j, &xj) in xs.iter().enumerate() {
39        if j == i {
40            continue;
41        }
42        let xj_i128 = xj as i128;
43        let x_i128 = x as i128;
44        let numerator = op_eval(x_i128 - xj_i128);
45        let denominator = op_eval(xi - xj_i128);
46        result = op_mul(result, op_div(numerator, denominator));
47    }
48    result
49}
50
51/// Compute the new share for party at index `target_x` given existing
52/// (x, y) pairs and arithmetic ops. This is the core of re-sharing.
53pub fn interpolate_at(
54    points: &[(u64, FieldElement)],
55    target_x: u64,
56    op_eval: &impl Fn(i128) -> i128,
57    op_mul: &impl Fn(i128, i128) -> i128,
58    op_add: &impl Fn(i128, i128) -> i128,
59    op_div: &impl Fn(i128, i128) -> i128,
60) -> FieldElement {
61    let xs: Vec<u64> = points.iter().map(|(x, _)| *x).collect();
62    let mut result = 0i128;
63    for (i, (_, y)) in points.iter().enumerate() {
64        let lambda = lagrange_basis_at(&xs, i, target_x, op_eval, op_mul, op_div);
65        let y_val = i128::from_be_bytes(y.0[..16].try_into().unwrap_or([0u8; 16]));
66        result = op_add(result, op_mul(lambda, y_val));
67    }
68    FieldElement::new(result.to_be_bytes().to_vec())
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    // Integer arithmetic helpers for testing.
76    fn id(x: i128) -> i128 {
77        x
78    }
79    fn mul(a: i128, b: i128) -> i128 {
80        a * b
81    }
82    fn add(a: i128, b: i128) -> i128 {
83        a + b
84    }
85    fn div(a: i128, b: i128) -> i128 {
86        if b == 0 {
87            panic!("division by zero");
88        }
89        a / b
90    }
91
92    #[test]
93    fn lagrange_basis_two_points() {
94        // Two points: (1, 5), (2, 7). Linear interpolation: y = 2x + 3
95        // λ_0 at x=0 = (0-2)/(1-2) = 2
96        let xs = vec![1, 2];
97        let result = lagrange_basis_at(&xs, 0, 0, &id, &mul, &div);
98        assert_eq!(result, 2);
99    }
100
101    #[test]
102    fn interpolate_recovers_secret() {
103        // y = 2x + 3, so secret at x=0 is 3
104        // Points: (1, 5), (2, 7)
105        // Encode as FieldElements with 16-byte big-endian.
106        let points = vec![
107            (1u64, FieldElement::new(5i128.to_be_bytes().to_vec())),
108            (2u64, FieldElement::new(7i128.to_be_bytes().to_vec())),
109        ];
110        let result = interpolate_at(&points, 0, &id, &mul, &add, &div);
111        let recovered = i128::from_be_bytes(result.0[..16].try_into().unwrap());
112        assert_eq!(recovered, 3);
113    }
114}
confium_tc/reshare/lagrange.rs

confium_tc/reshare/
lagrange.rs
