spark-cryptography 0.1.11

/*!
# Shamir's Secret Sharing Implementation

This module provides an implementation of Shamir's Secret Sharing (SSS) scheme with verifiable shares.
The implementation uses the secp256k1 curve (via k256) for cryptographic operations and supports
both basic and verifiable secret sharing.

## Overview

Shamir's Secret Sharing is a cryptographic algorithm that splits a secret into multiple shares,
where a minimum number of shares (threshold) are required to reconstruct the original secret.
This implementation includes:

- Basic secret sharing with polynomial-based share generation
- Verifiable secret sharing with cryptographic proofs
- Lagrange interpolation for secret recovery
- Share validation using elliptic curve cryptography

## Security Properties

- The secret is split into n shares, where any k shares (k ≤ n) can reconstruct the secret
- Individual shares reveal no information about the secret
- Verifiable shares include proofs that can be used to validate share authenticity
- All operations are performed in the secp256k1 scalar field

## Usage Example

```rust
use spark_cryptography::secret_sharing::{split_secret_with_proofs, recover_secret, validate_share};
use k256::{
    elliptic_curve::{PrimeField, generic_array::GenericArray},
    Scalar,
};
use rand::{rngs::OsRng, RngCore};
use std::error::Error;

// Generate a secret (32 bytes) and convert to k256::Scalar
let secret_bytes = [1u8; 32];
let generic_array = GenericArray::from_slice(&secret_bytes);
let secret_scalar = Scalar::from_repr_vartime(*generic_array).unwrap();

// Split into 5 shares with threshold of 3
let shares = split_secret_with_proofs(&secret_scalar, 3, 5).unwrap();

// Validate shares
for share in &shares {
    validate_share(share).unwrap();
}

// Recover secret using any 3 shares
let recovered = recover_secret(&shares[0..3]).unwrap();
```

## Implementation Details

The implementation uses:
- k256 for secp256k1 curve operations
- Random number generation via OsRng
- Polynomial evaluation for share generation
- Lagrange interpolation for secret recovery
- Cryptographic proofs for share verification
*/

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
///
/// Represents a polynomial over the secp256k1 scalar field with coefficients
/// and associated cryptographic proofs for verification.
#[derive(Clone)]
pub struct Polynomial {
    /// Coefficients of the polynomial in ascending order (constant term first)
    coefficients: Vec<Scalar>,

    /// Cryptographic proofs for each coefficient, used in share verification
    pub proofs: Vec<Vec<u8>>,
}

/// Trait for Lagrange interpolation
///
/// Provides the necessary methods for performing Lagrange interpolation
/// on a set of shares to recover the original secret.
pub trait LagrangeInterpolatable {
    /// Returns the index of the share (x-coordinate)
    fn get_index(&self) -> &Scalar;

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

    /// Returns the threshold required to recover the secret
    fn get_threshold(&self) -> usize;
}

/// Basic secret share structure
///
/// Represents a single share in the secret sharing scheme, containing
/// the threshold, index, and share value.
#[derive(Debug, Clone)]
pub struct SecretShare {
    /// Number of shares required to recover the secret
    pub threshold: usize,

    /// Index (x-coordinate) of the share
    pub index: Scalar,

    /// Share value (y-coordinate)
    pub share: Scalar,
}

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

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

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

/// Verifiable secret share with proofs
///
/// Extends the basic secret share with cryptographic proofs that can be used
/// to verify the authenticity of the share without revealing the secret.
#[derive(Debug, Clone)]
pub struct VerifiableSecretShare {
    /// Base secret share containing threshold, index, and share value
    pub secret_share: SecretShare,

    /// Cryptographic proofs for share 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_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: &U256,
) -> 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 *= point.get_index();
        let value = point.get_index() - index;
        denominator *= value;
    }

    field_div(&numerator, &denominator)
}

/// Converts a byte slice to a Scalar
///
/// # Arguments
///
/// * `bytes` - The byte slice to convert
///
/// # Returns
pub fn from_bytes_to_k256_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 using variable-time operation
    Scalar::from_repr_vartime(arr)
        .ok_or_else(|| "Failed to parse Scalar (out of range)".to_string())
}

/// Generates a polynomial for secret sharing
fn generate_polynomial_for_secret_sharing(
    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 = from_bytes_to_k256_scalar(&random_bytes)?;
        coefficients.push(random_scalar);
        proofs.push(scalar_to_pubkey(&random_scalar).to_sec1_bytes().to_vec());
    }

    Ok(Polynomial {
        coefficients,
        proofs,
    })
}

/// Splits a secret into shares using Shamir's Secret Sharing
///
/// # Arguments
///
/// * `secret` - The secret to be shared (32 bytes)
/// * `threshold` - Minimum number of shares required to recover the secret
/// * `number_of_shares` - Total number of shares to generate
///
/// # Returns
///
/// A vector of `SecretShare` structs containing the generated shares.
///
/// # Errors
///
/// Returns an error if:
/// * The secret is not a valid scalar
/// * The threshold is invalid (0 or greater than number_of_shares)
/// * Share generation fails
pub fn split_secret(
    secret: &Scalar,
    threshold: usize,
    number_of_shares: usize,
) -> Result<Vec<SecretShare>, Box<dyn Error>> {
    let polynomial = generate_polynomial_for_secret_sharing(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 {
            threshold,
            index,
            share,
        });
    }

    Ok(shares)
}

/// Helper function to perform modular exponentiation for k256::Scalar
fn scalar_modpow(base: &Scalar, exp: usize) -> 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 with cryptographic proofs
///
/// # Arguments
///
/// * `secret_scalar` - The secret to be shared as a scalar
/// * `threshold` - Minimum number of shares required to recover the secret
/// * `number_of_shares` - Total number of shares to generate
///
/// # Returns
///
/// A vector of `VerifiableSecretShare` structs containing the generated shares
/// and their associated proofs.
///
/// # Errors
///
/// Returns an error if:
/// * The threshold is invalid (0 or greater than number_of_shares)
/// * Share generation fails
pub fn split_secret_with_proofs(
    secret_scalar: &Scalar,
    threshold: usize,
    number_of_shares: usize,
) -> Result<Vec<VerifiableSecretShare>, Box<dyn Error>> {
    // Validate inputs
    if threshold == 0 || threshold > number_of_shares {
        return Err("Invalid threshold".into());
    }

    let polynomial = generate_polynomial_for_secret_sharing(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 {
                threshold,
                index,
                share,
            },
            proofs: polynomial.proofs.clone(),
        });
    }

    Ok(shares)
}

/// Recovers a secret from a set of shares using Lagrange interpolation
///
/// # Arguments
///
/// * `shares` - A slice of shares implementing `LagrangeInterpolatable`
///
/// # Returns
///
/// The recovered secret as a scalar.
///
/// # Errors
///
/// Returns an error if:
/// * There are fewer shares than the threshold
/// * Lagrange interpolation fails
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 using its cryptographic proofs
///
/// # Arguments
///
/// * `share` - The verifiable share to validate
///
/// # Returns
///
/// Ok(()) if the share is valid, an error otherwise.
///
/// # Errors
///
/// Returns an error if:
/// * The proofs are invalid
/// * The share fails verification
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::*;

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

    #[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 = from_bytes_to_k256_scalar(&secret_bytes)?;

        let shares = split_secret(&secret, 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_bytes = [0u8; 32];
        secret_bytes[..5].copy_from_slice(&[1, 2, 3, 4, 5]);
        let secret_scalar = from_bytes_to_k256_scalar(&secret_bytes)?;

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

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

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

        Ok(())
    }

    #[test]
    fn test_share_bytes_compatibility() -> Result<(), Box<dyn Error>> {
        // Generate a secret scalar, split it into 5 shares
        let secret_scalar = from_bytes_to_k256_scalar(&[0x11; 32])?;
        let shares = split_secret_with_proofs(&secret_scalar, 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 = from_bytes_to_k256_scalar(&original_share_bytes[i]).unwrap();
                VerifiableSecretShare {
                    secret_share: SecretShare {
                        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(())
    }
}