vsss-rs 6.0.0

//! Share element and identifier implementations using [`ConstMontyForm`] and [`MontyForm`]
//! from the `crypto-bigint` 0.7 crate (Montgomery form residue).
//!
//! For a **constant modulus** (compile-time), use [`IdentifierConstMontyResidue`] with
//! [`crypto_bigint::impl_modulus!`]:
//!
//! ```ignore
//! use crypto_bigint::{impl_modulus, U256};
//! use vsss_rs::IdentifierConstMontyResidue;
//!
//! impl_modulus!(MyModulus, U256, "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001");
//!
//! type MyResidue = IdentifierConstMontyResidue<MyModulus, 4>;
//! ```
//!
//! For a **runtime modulus**, use [`IdentifierMontyResidue`] with [`FixedMontyParams`];
//! create values via `zero_with_params`, `one_with_params`, `new`, and `random_with_params`.

use core::{
    fmt::{self, Display, Formatter},
    hash::{Hash, Hasher},
    ops::{Deref, DerefMut, Mul},
};
use crypto_bigint::{
    Encoding, RandomMod, Uint,
    modular::{ConstMontyForm, ConstMontyParams, FixedMontyForm, FixedMontyParams},
};
use rand_core::CryptoRng;
use subtle::{Choice, ConstantTimeEq};

use super::*;
use crate::*;

// =============================================================================
// ConstMontyForm (compile-time modulus)
// =============================================================================

/// A share value represented as a [`ConstMontyForm<MOD, LIMBS>`].
pub type ValueConstMontyResidue<MOD, const LIMBS: usize> = IdentifierConstMontyResidue<MOD, LIMBS>;

/// A share identifier represented as a residue in Montgomery form modulo a constant modulus
/// (crypto-bigint 0.7 [`ConstMontyForm`]).
#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(transparent)]
pub struct IdentifierConstMontyResidue<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize>(
    pub ConstMontyForm<MOD, LIMBS>,
)
where
    Uint<LIMBS>: Encoding;

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Display
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        let bytes = <Uint<LIMBS> as Encoding>::to_be_bytes(&self.0.retrieve());
        for &b in bytes.as_ref() {
            write!(f, "{:02x}", b)?;
        }
        Ok(())
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Hash
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.retrieve().hash(state);
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Ord
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.0.retrieve().cmp(&other.0.retrieve())
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> PartialOrd
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Deref
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    type Target = ConstMontyForm<MOD, LIMBS>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> DerefMut
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> AsRef<ConstMontyForm<MOD, LIMBS>>
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn as_ref(&self) -> &ConstMontyForm<MOD, LIMBS> {
        &self.0
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> AsMut<ConstMontyForm<MOD, LIMBS>>
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn as_mut(&mut self) -> &mut ConstMontyForm<MOD, LIMBS> {
        &mut self.0
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> From<ConstMontyForm<MOD, LIMBS>>
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: ConstMontyForm<MOD, LIMBS>) -> Self {
        Self(value)
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> From<&ConstMontyForm<MOD, LIMBS>>
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: &ConstMontyForm<MOD, LIMBS>) -> Self {
        Self(*value)
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize>
    From<&IdentifierConstMontyResidue<MOD, LIMBS>> for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: &IdentifierConstMontyResidue<MOD, LIMBS>) -> Self {
        Self(value.0)
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> From<IdentifierConstMontyResidue<MOD, LIMBS>>
    for ConstMontyForm<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: IdentifierConstMontyResidue<MOD, LIMBS>) -> Self {
        value.0
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Mul<&IdentifierConstMontyResidue<MOD, LIMBS>>
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    type Output = IdentifierConstMontyResidue<MOD, LIMBS>;

    fn mul(self, rhs: &IdentifierConstMontyResidue<MOD, LIMBS>) -> Self {
        Self(ConstMontyForm::<MOD, LIMBS>::mul(&self.0, &rhs.0))
    }
}

#[cfg(feature = "zeroize")]
impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> zeroize::DefaultIsZeroes
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding + zeroize::DefaultIsZeroes,
    ConstMontyForm<MOD, LIMBS>: zeroize::DefaultIsZeroes,
{
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ShareElement
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    type Serialization = <Uint<LIMBS> as Encoding>::Repr;
    type Inner = ConstMontyForm<MOD, LIMBS>;

    fn random(mut rng: impl CryptoRng) -> Self {
        let raw = Uint::<LIMBS>::random_mod_vartime(&mut rng, MOD::PARAMS.modulus().as_nz_ref());
        Self(ConstMontyForm::<MOD, LIMBS>::new(&raw))
    }

    fn zero() -> Self {
        Self(ConstMontyForm::<MOD, LIMBS>::ZERO)
    }

    fn one() -> Self {
        Self(ConstMontyForm::<MOD, LIMBS>::ONE)
    }

    fn is_zero(&self) -> Choice {
        ConstantTimeEq::ct_eq(&self.0, &ConstMontyForm::<MOD, LIMBS>::ZERO)
    }

    fn serialize(&self) -> Self::Serialization {
        <Uint<LIMBS> as Encoding>::to_be_bytes(&self.0.retrieve())
    }

    fn deserialize(serialized: &Self::Serialization) -> VsssResult<Self> {
        uint::IdentifierUint::<LIMBS>::deserialize(serialized)
            .map(|inner| Self(ConstMontyForm::<MOD, LIMBS>::new(&inner.0)))
    }

    fn from_slice(vec: &[u8]) -> VsssResult<Self> {
        uint::IdentifierUint::<LIMBS>::from_slice(vec)
            .map(|inner| Self(ConstMontyForm::<MOD, LIMBS>::new(&inner.0)))
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    fn to_vec(&self) -> Vec<u8> {
        self.serialize().as_ref().to_vec()
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ShareIdentifier
    for IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn inc(&mut self, increment: &Self) {
        self.0 += increment.0;
    }

    fn invert(&self) -> VsssResult<Self> {
        Option::from(self.0.invert())
            .map(Self)
            .ok_or(Error::InvalidShareElement)
    }
}

impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> IdentifierConstMontyResidue<MOD, LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    /// Identifier with the value 0.
    pub const ZERO: Self = Self(ConstMontyForm::<MOD, LIMBS>::ZERO);
    /// Identifier with the value 1.
    pub const ONE: Self = Self(ConstMontyForm::<MOD, LIMBS>::ONE);
}

// =============================================================================
// FixedMontyForm (runtime modulus)
// =============================================================================

/// A share value represented as a [`FixedMontyForm<LIMBS>`] (runtime modulus).
pub type ValueMontyResidue<const LIMBS: usize> = IdentifierMontyResidue<LIMBS>;

/// A share identifier represented as a residue in Montgomery form modulo a modulus
/// chosen at runtime (crypto-bigint 0.7 [`FixedMontyForm`]).
///
/// Use [`IdentifierMontyResidue::zero_with_params`], [`IdentifierMontyResidue::one_with_params`],
/// [`IdentifierMontyResidue::new`], and [`IdentifierMontyResidue::random_with_params`] to create
/// values; the modulus is not known at compile time so this type does not implement
/// [`ShareElement`].
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[repr(transparent)]
pub struct IdentifierMontyResidue<const LIMBS: usize>(pub FixedMontyForm<LIMBS>)
where
    Uint<LIMBS>: Encoding;

impl<const LIMBS: usize> IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    /// Create the additive identity (zero) for the given params.
    pub fn zero_with_params(params: FixedMontyParams<LIMBS>) -> Self {
        Self(FixedMontyForm::<LIMBS>::zero(&params))
    }

    /// Create the multiplicative identity (one) for the given params.
    pub fn one_with_params(params: FixedMontyParams<LIMBS>) -> Self {
        Self(FixedMontyForm::<LIMBS>::one(&params))
    }

    /// Create a residue representing `integer` mod the modulus in `params`.
    pub fn new(integer: &Uint<LIMBS>, params: FixedMontyParams<LIMBS>) -> Self {
        Self(FixedMontyForm::<LIMBS>::new(integer, &params))
    }

    /// Generate a random residue mod the modulus in `params`.
    pub fn random_with_params(mut rng: impl CryptoRng, params: FixedMontyParams<LIMBS>) -> Self {
        let raw = Uint::<LIMBS>::random_mod_vartime(&mut rng, params.modulus().as_nz_ref());
        Self(FixedMontyForm::<LIMBS>::new(&raw, &params))
    }

    /// Params (modulus etc.) for this residue.
    pub fn params(&self) -> &FixedMontyParams<LIMBS> {
        self.0.params()
    }
}

impl<const LIMBS: usize> Display for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        let bytes = <Uint<LIMBS> as Encoding>::to_be_bytes(&self.0.retrieve());
        for &b in bytes.as_ref() {
            write!(f, "{:02x}", b)?;
        }
        Ok(())
    }
}

impl<const LIMBS: usize> Hash for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.retrieve().hash(state);
    }
}

impl<const LIMBS: usize> Ord for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.0.retrieve().cmp(&other.0.retrieve())
    }
}

impl<const LIMBS: usize> PartialOrd for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl<const LIMBS: usize> Deref for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    type Target = FixedMontyForm<LIMBS>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<const LIMBS: usize> DerefMut for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl<const LIMBS: usize> AsRef<FixedMontyForm<LIMBS>> for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn as_ref(&self) -> &FixedMontyForm<LIMBS> {
        &self.0
    }
}

impl<const LIMBS: usize> AsMut<FixedMontyForm<LIMBS>> for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn as_mut(&mut self) -> &mut FixedMontyForm<LIMBS> {
        &mut self.0
    }
}

impl<const LIMBS: usize> From<FixedMontyForm<LIMBS>> for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: FixedMontyForm<LIMBS>) -> Self {
        Self(value)
    }
}

impl<const LIMBS: usize> From<&FixedMontyForm<LIMBS>> for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: &FixedMontyForm<LIMBS>) -> Self {
        Self(*value)
    }
}

impl<const LIMBS: usize> From<IdentifierMontyResidue<LIMBS>> for FixedMontyForm<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    fn from(value: IdentifierMontyResidue<LIMBS>) -> Self {
        value.0
    }
}

impl<const LIMBS: usize> Mul<&IdentifierMontyResidue<LIMBS>> for IdentifierMontyResidue<LIMBS>
where
    Uint<LIMBS>: Encoding,
{
    type Output = IdentifierMontyResidue<LIMBS>;

    fn mul(self, rhs: &IdentifierMontyResidue<LIMBS>) -> Self {
        Self(FixedMontyForm::<LIMBS>::mul(&self.0, &rhs.0))
    }
}

#[cfg(test)]
mod tests {
    use super::{
        ConstMontyForm, FixedMontyForm, FixedMontyParams, IdentifierConstMontyResidue,
        IdentifierMontyResidue,
    };
    use crate::{Error, ShareElement, ShareIdentifier};
    use crypto_bigint::{Odd, U64, const_monty_params};
    use rand_core::SeedableRng;
    use std::{
        collections::hash_map::DefaultHasher,
        hash::{Hash, Hasher},
        string::ToString,
    };

    const_monty_params!(TestMontyMod, U64, "000000000000000d");

    type ConstId = IdentifierConstMontyResidue<TestMontyMod, 1>;

    fn const_id(value: u64) -> ConstId {
        IdentifierConstMontyResidue(ConstMontyForm::<TestMontyMod, 1>::new(&U64::from(value)))
    }

    fn params() -> FixedMontyParams<1> {
        FixedMontyParams::<1>::new(Odd::new(U64::from(13u64)).unwrap())
    }

    fn runtime_id(value: u64) -> IdentifierMontyResidue<1> {
        IdentifierMontyResidue::new(&U64::from(value), params())
    }

    #[test]
    fn const_monty_identifier_share_element_methods_round_trip() {
        let identifier = const_id(3);
        let serialized = identifier.serialize();

        assert_eq!(identifier.to_string(), "0000000000000003");
        assert_eq!(serialized.as_ref(), [0, 0, 0, 0, 0, 0, 0, 3]);
        assert_eq!(ConstId::deserialize(&serialized), Ok(identifier));
        assert_eq!(ConstId::from_slice(serialized.as_ref()), Ok(identifier));
        assert_eq!(identifier.to_vec(), serialized.as_ref());
        assert_eq!(
            ConstId::from_slice(&[1, 2]),
            Err(Error::InvalidShareElement)
        );
        assert_eq!(ConstId::ZERO, ConstId::zero());
        assert_eq!(ConstId::ONE, ConstId::one());
        assert_eq!(ConstId::zero().is_zero().unwrap_u8(), 1);
        assert_eq!(ConstId::one().is_zero().unwrap_u8(), 0);
    }

    #[test]
    fn const_monty_identifier_ordering_hashing_conversion_and_arithmetic_work() {
        let two = const_id(2);
        let three = const_id(3);
        let six = const_id(6);

        assert!(two < three);
        let mut hasher = DefaultHasher::new();
        two.hash(&mut hasher);
        assert_ne!(hasher.finish(), 0);
        assert_eq!(ConstId::from(&two), two);
        assert_eq!(ConstId::from(two.0), two);
        assert_eq!(ConstId::from(&two.0), two);
        let inner: ConstMontyForm<TestMontyMod, 1> = two.into();
        assert_eq!(ConstId::from(inner), const_id(2));
        assert_eq!(const_id(2) * &three, six);

        let mut incremented = const_id(12);
        incremented.inc(&const_id(1));
        assert_eq!(incremented, ConstId::zero());
        assert_eq!(ConstId::one().invert(), Ok(ConstId::one()));
        assert_eq!(ConstId::zero().invert(), Err(Error::InvalidShareElement));
    }

    #[test]
    fn const_monty_reference_access_works() {
        let mut identifier = const_id(2);

        assert_eq!(identifier.as_ref().retrieve(), U64::from(2u64));
        assert_eq!((*identifier).retrieve(), U64::from(2u64));
        *identifier.as_mut() = ConstMontyForm::<TestMontyMod, 1>::ONE;
        assert_eq!(identifier, ConstId::one());
        *identifier = ConstMontyForm::<TestMontyMod, 1>::new(&U64::from(4u64));
        assert_eq!(identifier, const_id(4));
    }

    #[test]
    fn runtime_monty_identifier_methods_use_supplied_params() {
        let two = runtime_id(2);
        let three = runtime_id(3);
        let six = runtime_id(6);
        let zero = IdentifierMontyResidue::zero_with_params(params());
        let one = IdentifierMontyResidue::one_with_params(params());

        assert_eq!(two.to_string(), "0000000000000002");
        assert!(two < three);
        assert_eq!(two * &three, six);
        assert_eq!(zero.0.retrieve(), U64::ZERO);
        assert_eq!(one.0.retrieve(), U64::ONE);
        assert_eq!(two.params().modulus(), params().modulus());
        assert_eq!(IdentifierMontyResidue::from(&two.0), two);
        let inner = two.0;
        assert_eq!(IdentifierMontyResidue::from(inner), two);

        let mut hasher = DefaultHasher::new();
        two.hash(&mut hasher);
        assert_ne!(hasher.finish(), 0);
    }

    #[test]
    fn runtime_monty_reference_access_random_and_conversion_work() {
        let mut identifier = runtime_id(2);
        let params = params();

        assert_eq!(identifier.as_ref().retrieve(), U64::from(2u64));
        assert_eq!((*identifier).retrieve(), U64::from(2u64));
        *identifier.as_mut() = FixedMontyForm::<1>::one(&params);
        assert_eq!(identifier.0.retrieve(), U64::ONE);
        *identifier = FixedMontyForm::<1>::new(&U64::from(4u64), &params);
        assert_eq!(identifier.0.retrieve(), U64::from(4u64));

        let inner: FixedMontyForm<1> = identifier.into();
        assert_eq!(inner.retrieve(), U64::from(4u64));

        let mut rng = rand_chacha::ChaCha8Rng::from_seed([3u8; 32]);
        let random = IdentifierMontyResidue::random_with_params(&mut rng, params);
        assert!(random.0.retrieve() < U64::from(13u64));
        assert_eq!(random.params().modulus(), params.modulus());
    }
}