bsv-rs 0.8.8

BSV SDK for Rust: primitives, the script interpreter, transactions and BEEF/SPV, BRC-42 wallets, BRC-103 auth, the overlay network. Reference parity with the TypeScript SDK, native and wasm32.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
//! Shamir Secret Sharing for private key backup and recovery.
//!
//! This module implements Shamir's Secret Sharing scheme for splitting a private key
//! into multiple shares, where any threshold number of shares can reconstruct the
//! original key, but fewer shares reveal nothing about it.
//!
//! # Example
//!
//! ```rust
//! use bsv_rs::primitives::bsv::shamir::{split_private_key, KeyShares};
//! use bsv_rs::primitives::ec::PrivateKey;
//!
//! // Generate a random private key
//! let key = PrivateKey::random();
//!
//! // Split into 5 shares with threshold of 3
//! let shares = split_private_key(&key, 3, 5).unwrap();
//!
//! // Export to backup format
//! let backup = shares.to_backup_format();
//! assert_eq!(backup.len(), 5);
//!
//! // Recover from any 3 shares
//! let subset = KeyShares::from_backup_format(&backup[0..3]).unwrap();
//! let recovered = subset.recover_private_key().unwrap();
//!
//! assert_eq!(key.to_bytes(), recovered.to_bytes());
//! ```
//!
//! # Backup Format
//!
//! Each share is serialized as: `base58(x).base58(y).threshold.integrity`
//!
//! - `base58(x)` and `base58(y)` are the point coordinates
//! - `threshold` is the minimum number of shares needed for recovery
//! - `integrity` is the first 4 characters of base58(sha256(secret)) for verification
//!
//! Reading a share set refuses a coordinate field that is not the canonical
//! base58 of a value below the field prime, an x of zero, and a repeated x.

use std::collections::HashSet;

use crate::error::{Error, Result};
use crate::primitives::bsv::polynomial::{PointInFiniteField, Polynomial};
use crate::primitives::encoding::{from_base58, to_base58};
use crate::primitives::hash::sha256;
use crate::primitives::BigNumber;
use crate::primitives::PrivateKey;

/// A collection of key shares that can be used to recover a private key.
///
/// Contains the share points, the threshold needed for recovery, and an
/// integrity checksum to verify successful recovery.
#[derive(Clone, Debug)]
pub struct KeyShares {
    /// The share points (x, y coordinates in the finite field).
    pub points: Vec<PointInFiniteField>,
    /// The minimum number of shares needed for recovery.
    pub threshold: usize,
    /// Integrity check: first 4 characters of base58(sha256(secret)).
    pub integrity: String,
}

impl KeyShares {
    /// Creates a new KeyShares instance.
    ///
    /// # Arguments
    ///
    /// * `points` - The share points
    /// * `threshold` - The minimum number of shares needed for recovery
    /// * `integrity` - The integrity checksum string
    pub fn new(points: Vec<PointInFiniteField>, threshold: usize, integrity: String) -> Self {
        Self {
            points,
            threshold,
            integrity,
        }
    }

    /// Parses key shares from backup format strings.
    ///
    /// Each share string must be in the format: `base58(x).base58(y).threshold.integrity`
    ///
    /// # Arguments
    ///
    /// * `shares` - The backup format strings
    ///
    /// # Returns
    ///
    /// The parsed KeyShares, or an error if parsing fails or shares are inconsistent
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - Any share string has an invalid format
    /// - Shares have different thresholds
    /// - Shares have different integrity values
    /// - A share's coordinate field is not the canonical base58 of a value
    ///   below the field prime
    /// - Two shares have the same x coordinate, or a share's x is zero
    ///
    /// # Example
    ///
    /// ```rust
    /// use bsv_rs::primitives::bsv::shamir::KeyShares;
    ///
    /// let backup = vec![
    ///     "2.someY.3.abcd".to_string(),
    ///     "3.otherY.3.abcd".to_string(),
    ///     "4.anotherY.3.abcd".to_string(),
    /// ];
    /// // Note: This example would fail because "someY" etc. aren't valid base58
    /// // In practice, use actual share strings from split_private_key()
    /// ```
    pub fn from_backup_format(shares: &[String]) -> Result<Self> {
        if shares.is_empty() {
            return Err(Error::CryptoError(
                "No shares provided for recovery".to_string(),
            ));
        }

        let mut points = Vec::with_capacity(shares.len());
        let mut threshold: Option<usize> = None;
        let mut integrity: Option<String> = None;

        for (idx, share) in shares.iter().enumerate() {
            let (point, t, i) = decode_share(share, idx)?;

            // Validate consistency
            if let Some(existing_threshold) = threshold {
                if existing_threshold != t {
                    return Err(Error::CryptoError(format!(
                        "Threshold mismatch: share 0 has threshold {}, share {} has threshold {}",
                        existing_threshold, idx, t
                    )));
                }
            } else {
                threshold = Some(t);
            }

            if let Some(ref existing_integrity) = integrity {
                if existing_integrity != &i {
                    return Err(Error::CryptoError(format!(
                        "Integrity mismatch: share 0 has integrity '{}', share {} has integrity '{}'",
                        existing_integrity, idx, i
                    )));
                }
            } else {
                integrity = Some(i);
            }

            points.push(point);
        }

        let (Some(threshold), Some(integrity)) = (threshold, integrity) else {
            return Err(Error::CryptoError("No shares to recombine".to_string()));
        };
        refuse_degenerate_xs(&points)?;
        Ok(Self {
            points,
            threshold,
            integrity,
        })
    }

    /// Converts the key shares to backup format strings.
    ///
    /// Each share is serialized as: `base58(x).base58(y).threshold.integrity`
    ///
    /// # Returns
    ///
    /// A vector of backup format strings, one per share
    ///
    /// # Example
    ///
    /// ```rust
    /// use bsv_rs::primitives::bsv::shamir::split_private_key;
    /// use bsv_rs::primitives::ec::PrivateKey;
    ///
    /// let key = PrivateKey::random();
    /// let shares = split_private_key(&key, 2, 3).unwrap();
    /// let backup = shares.to_backup_format();
    ///
    /// // Each string can be stored separately
    /// for (i, share_str) in backup.iter().enumerate() {
    ///     println!("Share {}: {}", i + 1, share_str);
    /// }
    /// ```
    pub fn to_backup_format(&self) -> Vec<String> {
        self.points
            .iter()
            .map(|point| {
                format!(
                    "{}.{}.{}",
                    point.to_point_string(),
                    self.threshold,
                    self.integrity
                )
            })
            .collect()
    }

    /// Recovers the private key from the shares using Lagrange interpolation.
    ///
    /// The secret is the y-intercept (value at x=0) of the polynomial that passes
    /// through all the share points.
    ///
    /// # Returns
    ///
    /// The recovered private key, or an error if:
    /// - There are fewer shares than the threshold
    /// - A share's x coordinate is zero, or two points share one
    /// - The integrity check fails
    /// - The recovered value is not a valid private key
    ///
    /// # Example
    ///
    /// ```rust
    /// use bsv_rs::primitives::bsv::shamir::split_private_key;
    /// use bsv_rs::primitives::ec::PrivateKey;
    ///
    /// let key = PrivateKey::random();
    /// let shares = split_private_key(&key, 3, 5).unwrap();
    ///
    /// // Recover from exactly 3 shares
    /// let recovered = shares.recover_private_key().unwrap();
    /// assert_eq!(key.to_bytes(), recovered.to_bytes());
    /// ```
    pub fn recover_private_key(&self) -> Result<PrivateKey> {
        if self.points.len() < self.threshold {
            return Err(Error::CryptoError(format!(
                "Insufficient shares: have {}, need {}",
                self.points.len(),
                self.threshold
            )));
        }

        // Refuse the x coordinates interpolation cannot judge, before it runs
        refuse_degenerate_xs(&self.points)?;

        // Create polynomial from points and evaluate at x=0
        let poly = Polynomial::new(self.points.clone(), self.threshold);
        let secret = poly.value_at(&BigNumber::zero());

        // Convert to 32-byte representation
        // The secret should fit in 32 bytes (it's a private key value)
        let secret_bytes = secret.to_bytes_be(32);

        // Create the private key
        let key = PrivateKey::from_bytes(&secret_bytes)?;

        // Verify integrity
        let computed_integrity = compute_integrity(&key);
        if computed_integrity != self.integrity {
            return Err(Error::CryptoError(format!(
                "Integrity check failed: computed '{}', expected '{}'",
                computed_integrity, self.integrity
            )));
        }

        Ok(key)
    }
}

/// Splits a private key into multiple shares using Shamir's Secret Sharing.
///
/// The secret (private key) becomes the constant term of a random polynomial.
/// Shares are generated by evaluating the polynomial at x = 1, 2, 3, ..., total.
///
/// # Arguments
///
/// * `key` - The private key to split
/// * `threshold` - The minimum number of shares needed for recovery (must be >= 2)
/// * `total` - The total number of shares to generate (must be >= threshold)
///
/// # Returns
///
/// The generated key shares, or an error if the parameters are invalid
///
/// # Example
///
/// ```rust
/// use bsv_rs::primitives::bsv::shamir::split_private_key;
/// use bsv_rs::primitives::ec::PrivateKey;
///
/// let key = PrivateKey::random();
///
/// // Create 5 shares where any 3 can recover the key
/// let shares = split_private_key(&key, 3, 5).unwrap();
///
/// assert_eq!(shares.points.len(), 5);
/// assert_eq!(shares.threshold, 3);
/// ```
///
/// # Security
///
/// - Choose threshold based on your security requirements
/// - Higher threshold = more shares needed = more secure against partial compromise
/// - Lower threshold = easier to recover = less secure
/// - Typical values: 2-of-3, 3-of-5, etc.
pub fn split_private_key(key: &PrivateKey, threshold: usize, total: usize) -> Result<KeyShares> {
    // Validate parameters
    if threshold < 2 {
        return Err(Error::CryptoError(
            "Threshold must be at least 2".to_string(),
        ));
    }
    if total < threshold {
        return Err(Error::CryptoError(format!(
            "Total shares ({}) must be at least threshold ({})",
            total, threshold
        )));
    }
    if threshold > 255 {
        return Err(Error::CryptoError(
            "Threshold cannot exceed 255".to_string(),
        ));
    }

    let p = BigNumber::secp256k1_prime();

    // The secret is the private key as a BigNumber
    let secret = BigNumber::from_bytes_be(&key.to_bytes());

    // Generate random polynomial coefficients a_1, a_2, ..., a_{t-1}
    // The constant term a_0 is the secret
    let mut coefficients = Vec::with_capacity(threshold);
    coefficients.push(secret);

    for _ in 1..threshold {
        // Generate random 32-byte coefficient
        let random_key = PrivateKey::random();
        let coeff = BigNumber::from_bytes_be(&random_key.to_bytes()).modulo(&p);
        coefficients.push(coeff);
    }

    // Generate shares by evaluating polynomial at x = 1, 2, ..., total
    let mut points = Vec::with_capacity(total);

    for i in 1..=total {
        let x = BigNumber::from_u64(i as u64);
        let y = evaluate_polynomial(&coefficients, &x, &p);
        points.push(PointInFiniteField::new(x, y));
    }

    // Compute integrity checksum
    let integrity = compute_integrity(key);

    Ok(KeyShares {
        points,
        threshold,
        integrity,
    })
}

/// Evaluates a polynomial at a given point.
///
/// Given coefficients [a_0, a_1, ..., a_{n-1}], computes:
/// f(x) = a_0 + a_1*x + a_2*x^2 + ... + a_{n-1}*x^{n-1}
///
/// Uses Horner's method for efficiency.
fn evaluate_polynomial(
    coefficients: &[BigNumber],
    x: &BigNumber,
    modulus: &BigNumber,
) -> BigNumber {
    // Horner's method: f(x) = a_0 + x*(a_1 + x*(a_2 + ... + x*a_{n-1}))
    let mut result = BigNumber::zero();

    for coeff in coefficients.iter().rev() {
        result = result.mul(x).add(coeff).modulo(modulus);
    }

    result
}

/// Computes the integrity checksum for a private key.
///
/// Returns the first 4 characters of base58(sha256(key_bytes)).
fn compute_integrity(key: &PrivateKey) -> String {
    let hash = sha256(&key.to_bytes());
    let b58 = to_base58(&hash);

    // Take first 4 characters
    if b58.len() >= 4 {
        b58[..4].to_string()
    } else {
        b58
    }
}

/// Decodes a share from its backup format string.
///
/// Format: `base58(x).base58(y).threshold.integrity`
///
/// Returns the point, threshold, and integrity string.
fn decode_share(share: &str, idx: usize) -> Result<(PointInFiniteField, usize, String)> {
    let components: Vec<&str> = share.split('.').collect();

    if components.len() != 4 {
        return Err(Error::CryptoError(format!(
            "Invalid share format: expected 'base58(x).base58(y).threshold.integrity', got '{}'",
            share
        )));
    }

    // Parse x and y from base58, each the canonical field of a value below
    // the field prime
    let x = decode_field(components[0], idx)?;
    let y = decode_field(components[1], idx)?;

    let point = PointInFiniteField::new(x, y);

    // Parse threshold
    let threshold: usize = components[2].parse().map_err(|e| {
        Error::CryptoError(format!(
            "Invalid threshold in share: {} ({})",
            components[2], e
        ))
    })?;

    // Integrity is the last component
    let integrity = components[3].to_string();

    Ok((point, threshold, integrity))
}

/// The canonical base58 text of a coordinate: its minimal bytes, `1` for zero.
fn canonical_field_text(value: &BigNumber) -> String {
    let bytes = value.to_bytes_be_min();
    if bytes.is_empty() {
        "1".to_string()
    } else {
        to_base58(&bytes)
    }
}

/// Reads one coordinate field of a share: 1 to 64 base58 characters, the
/// canonical text of a value below the field prime. A field the reader would
/// silently reduce, or a text two values share, is not the share the holder
/// wrote (`Polynomial.ts:32-45`'s bounds, the reference's own reader).
fn decode_field(field: &str, idx: usize) -> Result<BigNumber> {
    if field.is_empty() || field.len() > 64 {
        return Err(Error::CryptoError(format!(
            "Invalid canonical share data in share {idx}"
        )));
    }
    let bytes = from_base58(field)?;
    let value = BigNumber::from_bytes_be(&bytes);
    let reduced = value.modulo(&BigNumber::secp256k1_prime());
    if field != canonical_field_text(&reduced) {
        return Err(Error::InvalidBase58(
            "Finite-field point must use a bounded canonical Base58 representation".into(),
        ));
    }
    Ok(reduced)
}

/// Refuses the x coordinates interpolation cannot judge, before it runs: an x
/// of zero, where a share's y is the secret itself and the whole set can
/// substitute another key for the holder's, and a duplicate x, where the
/// Lagrange weights divide by zero. One scan for both doors; the duplicate's
/// words are the reference's (`PrivateKey.ts:76-88`), the zero's this
/// crate's.
fn refuse_degenerate_xs(points: &[PointInFiniteField]) -> Result<()> {
    let mut seen: HashSet<Vec<u8>> = HashSet::with_capacity(points.len());
    for (idx, point) in points.iter().enumerate() {
        if point.x.is_zero() {
            return Err(Error::CryptoError(format!(
                "Zero x coordinate in share {idx}"
            )));
        }
        if !seen.insert(point.x.to_bytes_be_min()) {
            return Err(Error::CryptoError(
                "Duplicate share detected, each must be unique.".to_string(),
            ));
        }
    }
    Ok(())
}

#[cfg(test)]
#[path = "shamir_tests.rs"]
mod tests;