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

bsv/primitives/
polynomial.rs
