bsv/primitives/
polynomial.rs

1//! Polynomial operations for threshold cryptography (Shamir's Secret Sharing).
2//!
3//! Implements polynomial representation using (x, y) points in GF(p) where p
4//! is the secp256k1 field prime, and Lagrange interpolation for secret recovery.
5//! Follows the TS SDK Polynomial.ts implementation exactly.
6
7use crate::primitives::big_number::{BigNumber, Endian};
8use crate::primitives::curve::Curve;
9use crate::primitives::error::PrimitivesError;
10use crate::primitives::utils::{base58_decode, base58_encode};
11
12/// A point in GF(p) representing (x, y) coordinates for polynomial evaluation.
13///
14/// All arithmetic is performed mod p (the secp256k1 field prime).
15/// This matches the TS SDK's PointInFiniteField class.
16#[derive(Clone, Debug)]
17pub struct PointInFiniteField {
18    pub x: BigNumber,
19    pub y: BigNumber,
20}
21
22impl PointInFiniteField {
23    /// Create a new point, reducing coordinates mod p.
24    pub fn new(x: BigNumber, y: BigNumber) -> Self {
25        let curve = Curve::secp256k1();
26        let x_mod = x.umod(&curve.p).unwrap_or(x);
27        let y_mod = y.umod(&curve.p).unwrap_or(y);
28        PointInFiniteField { x: x_mod, y: y_mod }
29    }
30
31    /// Serialize this point as "base58(x).base58(y)".
32    pub fn to_string_repr(&self) -> String {
33        let x_bytes = self.x.to_array(Endian::Big, None);
34        let y_bytes = self.y.to_array(Endian::Big, None);
35        format!("{}.{}", base58_encode(&x_bytes), base58_encode(&y_bytes))
36    }
37
38    /// Parse a point from "base58(x).base58(y)" format.
39    pub fn from_string_repr(s: &str) -> Result<Self, PrimitivesError> {
40        let parts: Vec<&str> = s.split('.').collect();
41        if parts.len() != 2 {
42            return Err(PrimitivesError::InvalidFormat(format!(
43                "Expected 'x.y' format, got: {s}"
44            )));
45        }
46        let x_bytes = base58_decode(parts[0])?;
47        let y_bytes = base58_decode(parts[1])?;
48        let x = BigNumber::from_bytes(&x_bytes, Endian::Big);
49        let y = BigNumber::from_bytes(&y_bytes, Endian::Big);
50        Ok(PointInFiniteField::new(x, y))
51    }
52}
53
54/// Polynomial over GF(p) represented by its evaluation points.
55///
56/// Used for Lagrange interpolation in Shamir's Secret Sharing.
57/// The polynomial passes through the stored points and can be evaluated
58/// at any x value using Lagrange interpolation.
59pub struct Polynomial {
60    pub points: Vec<PointInFiniteField>,
61    pub threshold: usize,
62}
63
64impl Polynomial {
65    /// Create a new polynomial from points with optional threshold.
66    ///
67    /// If threshold is not specified, it defaults to the number of points.
68    pub fn new(points: Vec<PointInFiniteField>, threshold: Option<usize>) -> Self {
69        let t = threshold.unwrap_or(points.len());
70        Polynomial {
71            points,
72            threshold: t,
73        }
74    }
75
76    /// Create a polynomial from a private key for Shamir's Secret Sharing.
77    ///
78    /// The private key value is the y-intercept (x=0, y=key).
79    /// Additional (threshold - 1) random points are generated.
80    pub fn from_private_key(key_bytes: &[u8], threshold: usize) -> Self {
81        let curve = Curve::secp256k1();
82        let key_bn = BigNumber::from_bytes(key_bytes, Endian::Big);
83
84        // The key is the y-intercept: point at x=0
85        let mut points = vec![PointInFiniteField::new(BigNumber::zero(), key_bn)];
86
87        // Generate (threshold - 1) random points
88        for _ in 1..threshold {
89            let random_x_bytes = crate::primitives::random::random_bytes(32);
90            let random_y_bytes = crate::primitives::random::random_bytes(32);
91            let random_x = BigNumber::from_bytes(&random_x_bytes, Endian::Big)
92                .umod(&curve.p)
93                .unwrap_or(BigNumber::one());
94            let random_y = BigNumber::from_bytes(&random_y_bytes, Endian::Big)
95                .umod(&curve.p)
96                .unwrap_or(BigNumber::one());
97            points.push(PointInFiniteField::new(random_x, random_y));
98        }
99
100        Polynomial::new(points, Some(threshold))
101    }
102
103    /// Evaluate the polynomial at x using Lagrange interpolation.
104    ///
105    /// Uses the stored points and Lagrange basis polynomials to compute
106    /// the polynomial's value at the given x coordinate. All arithmetic
107    /// is performed mod p (secp256k1 field prime).
108    pub fn value_at(&self, x: &BigNumber) -> BigNumber {
109        let curve = Curve::secp256k1();
110        let p = &curve.p;
111
112        let mut y = BigNumber::zero();
113
114        for i in 0..self.threshold {
115            let mut term = self.points[i].y.clone();
116
117            for j in 0..self.threshold {
118                if i != j {
119                    let xj = &self.points[j].x;
120                    let xi = &self.points[i].x;
121
122                    // numerator = (x - xj) mod p
123                    let numerator = x.sub(xj).umod(p).unwrap_or(BigNumber::zero());
124
125                    // denominator = (xi - xj) mod p
126                    let denominator = xi.sub(xj).umod(p).unwrap_or(BigNumber::zero());
127
128                    // denominator_inverse = denominator^(-1) mod p
129                    let denominator_inverse = denominator.invm(p).unwrap_or(BigNumber::zero());
130
131                    // fraction = numerator * denominator_inverse mod p
132                    let fraction = numerator
133                        .mul(&denominator_inverse)
134                        .umod(p)
135                        .unwrap_or(BigNumber::zero());
136
137                    // term = term * fraction mod p
138                    term = term.mul(&fraction).umod(p).unwrap_or(BigNumber::zero());
139                }
140            }
141
142            y = y.add(&term).umod(p).unwrap_or(BigNumber::zero());
143        }
144
145        y
146    }
147}
148
149// ---------------------------------------------------------------------------
150// Tests
151// ---------------------------------------------------------------------------
152
153#[cfg(test)]
154mod tests {
155    use super::*;
156
157    #[test]
158    fn test_point_in_finite_field_new() {
159        let p = PointInFiniteField::new(BigNumber::from_number(5), BigNumber::from_number(10));
160        assert_eq!(p.x.cmp(&BigNumber::from_number(5)), 0);
161        assert_eq!(p.y.cmp(&BigNumber::from_number(10)), 0);
162    }
163
164    #[test]
165    fn test_point_in_finite_field_mod_p() {
166        let curve = Curve::secp256k1();
167        // Value larger than p should be reduced
168        let large = curve.p.add(&BigNumber::from_number(1));
169        let p = PointInFiniteField::new(large, BigNumber::from_number(5));
170        assert_eq!(p.x.cmp(&BigNumber::from_number(1)), 0);
171    }
172
173    #[test]
174    fn test_point_in_finite_field_string_roundtrip() {
175        let p =
176            PointInFiniteField::new(BigNumber::from_number(12345), BigNumber::from_number(67890));
177        let s = p.to_string_repr();
178        let recovered = PointInFiniteField::from_string_repr(&s).unwrap();
179        assert_eq!(recovered.x.cmp(&p.x), 0);
180        assert_eq!(recovered.y.cmp(&p.y), 0);
181    }
182
183    #[test]
184    fn test_polynomial_value_at_intercept() {
185        // A polynomial through (0, 42) and (1, 100) evaluated at x=0 should return 42
186        let points = vec![
187            PointInFiniteField::new(BigNumber::zero(), BigNumber::from_number(42)),
188            PointInFiniteField::new(BigNumber::one(), BigNumber::from_number(100)),
189        ];
190        let poly = Polynomial::new(points, Some(2));
191        let val = poly.value_at(&BigNumber::zero());
192        assert_eq!(val.cmp(&BigNumber::from_number(42)), 0);
193    }
194
195    #[test]
196    fn test_polynomial_value_at_known_point() {
197        // A polynomial through (0, 42) and (1, 100) evaluated at x=1 should return 100
198        let points = vec![
199            PointInFiniteField::new(BigNumber::zero(), BigNumber::from_number(42)),
200            PointInFiniteField::new(BigNumber::one(), BigNumber::from_number(100)),
201        ];
202        let poly = Polynomial::new(points, Some(2));
203        let val = poly.value_at(&BigNumber::one());
204        assert_eq!(val.cmp(&BigNumber::from_number(100)), 0);
205    }
206
207    #[test]
208    fn test_polynomial_lagrange_three_points() {
209        // Three points: (1, 5), (2, 10), (3, 17)
210        // Lagrange interpolation at x=0 should recover the secret
211        let points = vec![
212            PointInFiniteField::new(BigNumber::from_number(1), BigNumber::from_number(5)),
213            PointInFiniteField::new(BigNumber::from_number(2), BigNumber::from_number(10)),
214            PointInFiniteField::new(BigNumber::from_number(3), BigNumber::from_number(17)),
215        ];
216        let poly = Polynomial::new(points, Some(3));
217        let secret = poly.value_at(&BigNumber::zero());
218
219        // Verify: the polynomial is y = x^2 + x + 2 (or something that fits)
220        // Actually let's compute manually:
221        // L1(0) at x1=1: (0-2)(0-3)/((1-2)(1-3)) = (-2)(-3)/((-1)(-2)) = 6/2 = 3
222        // L2(0) at x2=2: (0-1)(0-3)/((2-1)(2-3)) = (-1)(-3)/((1)(-1)) = 3/(-1) = -3
223        // L3(0) at x3=3: (0-1)(0-2)/((3-1)(3-2)) = (-1)(-2)/((2)(1)) = 2/2 = 1
224        // secret = 5*3 + 10*(-3) + 17*1 = 15 - 30 + 17 = 2
225        assert_eq!(secret.cmp(&BigNumber::from_number(2)), 0);
226    }
227
228    #[test]
229    fn test_polynomial_from_private_key() {
230        let key_bytes = BigNumber::from_number(42).to_array(Endian::Big, Some(32));
231        let poly = Polynomial::from_private_key(&key_bytes, 3);
232        assert_eq!(poly.points.len(), 3);
233        assert_eq!(poly.threshold, 3);
234
235        // First point should be (0, 42)
236        assert_eq!(poly.points[0].x.cmp(&BigNumber::zero()), 0);
237        assert_eq!(poly.points[0].y.cmp(&BigNumber::from_number(42)), 0);
238    }
239
240    #[test]
241    fn test_polynomial_from_private_key_reconstruct() {
242        // Create polynomial from key, evaluate at several x values,
243        // then use those points to reconstruct the key at x=0
244        let secret = BigNumber::from_number(123456789);
245        let key_bytes = secret.to_array(Endian::Big, Some(32));
246        let poly = Polynomial::from_private_key(&key_bytes, 3);
247
248        // Evaluate at x=1, 2, 3 to get shares
249        let shares: Vec<PointInFiniteField> = (1..=3)
250            .map(|i| {
251                let x = BigNumber::from_number(i);
252                let y = poly.value_at(&x);
253                PointInFiniteField::new(x, y)
254            })
255            .collect();
256
257        // Reconstruct using all 3 shares
258        let recon_poly = Polynomial::new(shares, Some(3));
259        let recovered = recon_poly.value_at(&BigNumber::zero());
260        assert_eq!(recovered.cmp(&secret), 0, "Should recover original secret");
261    }
262}
bsv/primitives/polynomial.rs

bsv/primitives/
polynomial.rs
