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;
#[derive(Clone, Debug)]
pub struct KeyShares {
pub points: Vec<PointInFiniteField>,
pub threshold: usize,
pub integrity: String,
}
impl KeyShares {
pub fn new(points: Vec<PointInFiniteField>, threshold: usize, integrity: String) -> Self {
Self {
points,
threshold,
integrity,
}
}
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)?;
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,
})
}
pub fn to_backup_format(&self) -> Vec<String> {
self.points
.iter()
.map(|point| {
format!(
"{}.{}.{}",
point.to_point_string(),
self.threshold,
self.integrity
)
})
.collect()
}
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_degenerate_xs(&self.points)?;
let poly = Polynomial::new(self.points.clone(), self.threshold);
let secret = poly.value_at(&BigNumber::zero());
let secret_bytes = secret.to_bytes_be(32);
let key = PrivateKey::from_bytes(&secret_bytes)?;
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)
}
}
pub fn split_private_key(key: &PrivateKey, threshold: usize, total: usize) -> Result<KeyShares> {
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();
let secret = BigNumber::from_bytes_be(&key.to_bytes());
let mut coefficients = Vec::with_capacity(threshold);
coefficients.push(secret);
for _ in 1..threshold {
let random_key = PrivateKey::random();
let coeff = BigNumber::from_bytes_be(&random_key.to_bytes()).modulo(&p);
coefficients.push(coeff);
}
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));
}
let integrity = compute_integrity(key);
Ok(KeyShares {
points,
threshold,
integrity,
})
}
fn evaluate_polynomial(
coefficients: &[BigNumber],
x: &BigNumber,
modulus: &BigNumber,
) -> BigNumber {
let mut result = BigNumber::zero();
for coeff in coefficients.iter().rev() {
result = result.mul(x).add(coeff).modulo(modulus);
}
result
}
fn compute_integrity(key: &PrivateKey) -> String {
let hash = sha256(&key.to_bytes());
let b58 = to_base58(&hash);
if b58.len() >= 4 {
b58[..4].to_string()
} else {
b58
}
}
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
)));
}
let x = decode_field(components[0], idx)?;
let y = decode_field(components[1], idx)?;
let point = PointInFiniteField::new(x, y);
let threshold: usize = components[2].parse().map_err(|e| {
Error::CryptoError(format!(
"Invalid threshold in share: {} ({})",
components[2], e
))
})?;
let integrity = components[3].to_string();
Ok((point, threshold, integrity))
}
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)
}
}
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)
}
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;