spark_cryptography/secret_sharing/

secret_sharing.rs

// use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
use k256::{
    elliptic_curve::{generic_array::GenericArray, PrimeField},
    AffinePoint, ProjectivePoint, PublicKey, Scalar,
};
use rand::{rngs::OsRng, RngCore};
use std::error::Error;

fn scalar_to_pubkey(secret: &k256::Scalar) -> PublicKey {
    let point = ProjectivePoint::GENERATOR * *secret;
    PublicKey::from_affine(AffinePoint::from(point)).expect("invalid public key")
}

/// Polynomial used for secret sharing
#[derive(Clone)]
pub struct Polynomial {
    /// Field modulus of the polynomial
    pub field_modulus: Scalar,

    /// Coefficients of the polynomial
    coefficients: Vec<Scalar>,

    /// Proofs of the polynomial
    pub proofs: Vec<Vec<u8>>,
}

/// Trait for Lagrange interpolation
pub trait LagrangeInterpolatable {
    /// Returns the index of the share
    fn get_index(&self) -> &Scalar;

    /// Returns the share value
    fn get_share(&self) -> &Scalar;

    /// Returns the field modulus
    fn get_field_modulus(&self) -> &Scalar;

    /// Returns the threshold
    fn get_threshold(&self) -> usize;
}

/// Basic secret share structure
#[derive(Debug, Clone)]
pub struct SecretShare {
    /// Field modulus of the share
    pub field_modulus: Scalar,

    /// Threshold of the secret
    pub threshold: usize,

    /// Index of the share
    pub index: Scalar,

    /// Share value
    pub share: Scalar,
}

impl LagrangeInterpolatable for SecretShare {
    fn get_index(&self) -> &Scalar {
        &self.index
    }

    fn get_field_modulus(&self) -> &Scalar {
        &self.field_modulus
    }

    fn get_share(&self) -> &Scalar {
        &self.share
    }

    fn get_threshold(&self) -> usize {
        self.threshold
    }
}

/// Verifiable secret share with proofs
#[derive(Debug, Clone)]
pub struct VerifiableSecretShare {
    /// Base secret share
    pub secret_share: SecretShare,

    /// Proofs for verification
    pub proofs: Vec<Vec<u8>>,
}

impl VerifiableSecretShare {
    pub fn marshal_proto(&self) -> spark_protos::spark::SecretShare {
        spark_protos::spark::SecretShare {
            secret_share: self.secret_share.share.to_bytes().to_vec(),
            proofs: self.proofs.clone(),
        }
    }
}

impl LagrangeInterpolatable for VerifiableSecretShare {
    fn get_index(&self) -> &Scalar {
        &self.secret_share.index
    }

    fn get_field_modulus(&self) -> &Scalar {
        &self.secret_share.field_modulus
    }

    fn get_share(&self) -> &Scalar {
        &self.secret_share.share
    }

    fn get_threshold(&self) -> usize {
        self.secret_share.threshold
    }
}

impl Polynomial {
    /// Evaluates the polynomial at a given point
    pub fn evaluate(&self, x: &Scalar) -> Scalar {
        let mut result = Scalar::ZERO;
        let mut x_power = Scalar::ONE;

        for coeff in self.coefficients.iter() {
            result += *coeff * x_power;
            x_power *= x;
        }
        result
    }
}

/// Performs field division in the given modulus
fn field_div(
    numerator: &k256::Scalar,
    denominator: &k256::Scalar,
    _field_modulus: &k256::Scalar,
) -> Result<k256::Scalar, String> {
    if bool::from(denominator.is_zero()) {
        return Err("division by zero".to_string());
    }

    let inverse = denominator
        .invert()
        .into_option()
        .ok_or("element not invertible".to_string())?;
    Ok(*numerator * inverse)
}

/// Computes Lagrange coefficients for interpolation
pub fn compute_lagrange_coefficients<T: LagrangeInterpolatable>(
    index: &Scalar,
    points: &[T],
) -> Result<Scalar, String> {
    let mut numerator = Scalar::ONE;
    let mut denominator = Scalar::ONE;
    let field_modulus = points[0].get_field_modulus();

    for point in points {
        if point.get_index() == index {
            continue;
        }
        numerator = numerator * point.get_index();
        let value = point.get_index() - index;
        denominator = denominator * value;
    }

    field_div(&numerator, &denominator, &field_modulus)
}

fn bytes_to_scalar(bytes: &[u8]) -> Result<Scalar, String> {
    // Disallow anything larger than 32 bytes.
    if bytes.len() != 32 {
        return Err(format!(
            "Invalid byte length for scalar. Expected 32, got {}",
            bytes.len()
        ));
    }

    // Convert bytes directly to a GenericArray
    let arr = GenericArray::clone_from_slice(bytes);

    // Attempt to create Scalar from bytes representation
    let scalar_opt = Scalar::from_repr(arr);

    // Convert CtOption to Result
    scalar_opt
        .into_option()
        .ok_or_else(|| "Failed to parse Scalar (out of range)".to_string())
}

/// Generates a polynomial for secret sharing
fn generate_polynomial_for_secret_sharing(
    field_modulus: &Scalar,
    secret: &Scalar,
    threshold: usize,
) -> Result<Polynomial, Box<dyn Error>> {
    let mut coefficients = Vec::with_capacity(threshold + 1);
    let mut proofs = Vec::with_capacity(threshold + 1);

    // Set the constant term (secret)
    coefficients.push(*secret);

    // Generate proof for secret
    proofs.push(scalar_to_pubkey(secret).to_sec1_bytes().to_vec());

    // Generate random coefficients for higher terms
    for _ in 1..=threshold {
        let mut random_bytes = [0u8; 32];
        OsRng.fill_bytes(&mut random_bytes);

        // Convert to scalar and ensure it's within field modulus
        let random_scalar = bytes_to_scalar(&random_bytes)?;
        coefficients.push(random_scalar);
        proofs.push(scalar_to_pubkey(&random_scalar).to_sec1_bytes().to_vec());
    }

    Ok(Polynomial {
        field_modulus: *field_modulus,
        coefficients,
        proofs,
    })
}

/// Splits a secret into shares
pub fn split_secret(
    secret: &Scalar,
    field_modulus: &Scalar,
    threshold: usize,
    number_of_shares: usize,
) -> Result<Vec<SecretShare>, Box<dyn Error>> {
    let polynomial = generate_polynomial_for_secret_sharing(field_modulus, secret, threshold - 1)?;

    let mut shares = Vec::with_capacity(number_of_shares);
    for i in 1..=number_of_shares {
        let index = Scalar::from(i as u64);
        let share = polynomial.evaluate(&index);

        shares.push(SecretShare {
            field_modulus: *field_modulus,
            threshold,
            index,
            share,
        });
    }

    Ok(shares)
}

/// Helper function to perform modular exponentiation for k256::Scalar
fn scalar_modpow(base: &Scalar, exp: usize, _modulus: &Scalar) -> Scalar {
    if exp == 0 {
        return Scalar::ONE;
    }

    let mut result = Scalar::ONE;
    let mut base = *base;
    let mut exp = exp;

    while exp > 0 {
        if exp & 1 == 1 {
            result *= base;
        }
        base *= base;
        exp >>= 1;
    }
    result
}

/// Splits a secret into verifiable shares
pub fn split_secret_with_proofs(
    secret: &[u8],
    field_modulus: &[u8],
    threshold: usize,
    number_of_shares: usize,
) -> Result<Vec<VerifiableSecretShare>, Box<dyn Error>> {
    // Ensure secret is valid scalar
    let secret_scalar = bytes_to_scalar(secret)?;
    let field_modulus_scalar = bytes_to_scalar(field_modulus)?;

    // Validate inputs
    if threshold == 0 || threshold > number_of_shares {
        return Err("Invalid threshold".into());
    }

    let polynomial = generate_polynomial_for_secret_sharing(
        &field_modulus_scalar,
        &secret_scalar,
        threshold - 1,
    )?;

    let mut shares = Vec::with_capacity(number_of_shares);
    for i in 1..=number_of_shares {
        let index = Scalar::from(i as u64);
        let share = polynomial.evaluate(&index);

        shares.push(VerifiableSecretShare {
            secret_share: SecretShare {
                field_modulus: field_modulus_scalar,
                threshold,
                index,
                share,
            },
            proofs: polynomial.proofs.clone(),
        });
    }

    Ok(shares)
}

/// Recovers a secret from a set of shares
pub fn recover_secret<T: LagrangeInterpolatable>(shares: &[T]) -> Result<Scalar, String> {
    if shares.len() < shares[0].get_threshold() {
        return Err("not enough shares to recover secret".to_string());
    }

    let mut result = Scalar::ZERO;

    for share in shares {
        let coeff = compute_lagrange_coefficients(share.get_index(), shares)?;
        result += share.get_share() * &coeff;
    }

    Ok(result)
}

/// Validates a verifiable share
pub fn validate_share(share: &VerifiableSecretShare) -> Result<(), String> {
    let target_pubkey = scalar_to_pubkey(&share.secret_share.share);
    let mut result = ProjectivePoint::IDENTITY;

    // Add the base proof
    if let Some(base_proof) = share.proofs.first() {
        let base_pubkey = PublicKey::from_sec1_bytes(base_proof).map_err(|e| e.to_string())?;
        result += ProjectivePoint::from(base_pubkey.as_affine());
    }

    // Add the higher-degree terms
    for (i, proof) in share.proofs.iter().enumerate().skip(1) {
        let pubkey = PublicKey::from_sec1_bytes(proof).map_err(|e| e.to_string())?;
        let exp = scalar_modpow(
            &share.secret_share.index,
            i,
            &share.secret_share.field_modulus,
        );
        result += ProjectivePoint::from(pubkey.as_affine()) * exp;
    }

    if AffinePoint::from(result) == *target_pubkey.as_affine() {
        Ok(())
    } else {
        Err("Share validation failed".to_string())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    use crate::secp256k1::CURVE_ORDER;
    use k256::elliptic_curve::bigint::{Encoding as _, U256};

    // The secp256k1 group order in hex (this is `n`).
    const CURVE_ORDER_HEX: &str =
        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141";

    /// Convert a scalar to fixed 32-byte array
    fn scalar_to_32_bytes(scalar: &Scalar) -> [u8; 32] {
        scalar.to_bytes().into()
    }

    // Helper for an in-range "field modulus" in byte form:
    fn get_test_field_modulus_in_range() -> Vec<u8> {
        let raw = hex::decode(CURVE_ORDER).unwrap();
        let u = U256::from_be_slice(&raw);

        // subtract 1 so that it's definitely in range
        let minus_one = u.saturating_sub(&U256::ONE);
        minus_one.to_be_bytes().to_vec()
    }

    #[test]
    fn test_secret_sharing_basic() -> Result<(), Box<dyn Error>> {
        // Replace 5-byte secret with a 32-byte array containing those 5 bytes at the front
        let mut secret_bytes = [0u8; 32];
        secret_bytes[..5].copy_from_slice(&[1, 2, 3, 4, 5]);
        let secret = bytes_to_scalar(&secret_bytes)?;

        // Use an in-range field modulus rather than the full curve order
        let field_modulus_bytes = get_test_field_modulus_in_range();
        let field_modulus = bytes_to_scalar(&field_modulus_bytes)?;

        let shares = split_secret(&secret, &field_modulus, 3, 5)?;
        let recovered = recover_secret(&shares[0..3])?;

        assert_eq!(secret, recovered);
        Ok(())
    }

    #[test]
    fn test_verifiable_secret_sharing() -> Result<(), Box<dyn Error>> {
        // Again, pad the 5-byte secret to 32 bytes
        let mut secret_arr = [0u8; 32];
        secret_arr[..5].copy_from_slice(&[1, 2, 3, 4, 5]);

        // Use a valid field_modulus that's < group order
        let field_modulus = get_test_field_modulus_in_range();

        let shares = split_secret_with_proofs(&secret_arr, &field_modulus, 3, 5)?;

        // Validate all shares
        for share in &shares {
            validate_share(share)?;
        }

        // Recover secret
        let recovered = recover_secret(&shares[0..3])?;
        assert_eq!(bytes_to_scalar(&secret_arr)?, recovered);

        Ok(())
    }

    #[test]
    fn test_share_bytes_compatibility() -> Result<(), Box<dyn Error>> {
        // Use a field modulus that is definitely in range
        let field_modulus = get_test_field_modulus_in_range();
        let secret_bytes = vec![0x11; 32]; // 32 bytes of 0x11

        // First split and validate
        let shares = split_secret_with_proofs(&secret_bytes, &field_modulus, 3, 5)?;

        // Store the original share bytes
        let original_share_bytes: Vec<Vec<u8>> = shares
            .iter()
            .map(|s| scalar_to_32_bytes(&s.secret_share.share).to_vec())
            .collect();

        // Validate all original shares
        for share in &shares {
            validate_share(share)?;
        }

        // Create new shares with the stored bytes
        let new_shares: Vec<VerifiableSecretShare> = shares
            .iter()
            .enumerate()
            .map(|(i, original_share)| {
                let share_scalar = bytes_to_scalar(&original_share_bytes[i]).unwrap();
                VerifiableSecretShare {
                    secret_share: SecretShare {
                        field_modulus: original_share.secret_share.field_modulus,
                        threshold: original_share.secret_share.threshold,
                        index: Scalar::from((i + 1) as u64),
                        share: share_scalar,
                    },
                    proofs: original_share.proofs.clone(),
                }
            })
            .collect();

        // Validate reconstructed shares
        for share in &new_shares {
            validate_share(share)?;
        }

        // Check byte-for-byte equality
        for (orig, new) in shares.iter().zip(new_shares.iter()) {
            assert_eq!(
                scalar_to_32_bytes(&orig.secret_share.share),
                scalar_to_32_bytes(&new.secret_share.share),
                "Share bytes don't match after reconstruction"
            );
        }

        // Recover secret from both sets of shares
        let recovered_orig = recover_secret(&shares[0..3])?;
        let recovered_new = recover_secret(&new_shares[0..3])?;
        assert_eq!(recovered_orig, recovered_new);

        Ok(())
    }

    #[test]
    fn test_secret_sharing_out_of_range_share() {
        // This share is EXACTLY n, i.e. out of range for k256::Scalar
        let out_of_range_bytes = hex::decode(CURVE_ORDER_HEX).expect("invalid hex for n");

        // Demonstrate that bytes_to_scalar() rejects it
        let result = bytes_to_scalar(&out_of_range_bytes);
        assert!(
            result.is_err(),
            "Expected out-of-range error, but got an Ok(Scalar)?"
        );

        println!("Got expected error: {:?}", result.err().unwrap());
    }
}