primitives/sharing/

mod.rs

// Secret sharing schemes.
pub mod authenticated;
pub mod unauthenticated;

use std::{borrow::Borrow, sync::Arc};

pub use authenticated::*;
use itertools::{enumerate, izip};
use serde::{de::DeserializeOwned, Serialize};
use wincode::{SchemaRead, SchemaWrite};

use crate::{
    algebra::{field::FieldExtension, ops::transpose::transpose},
    errors::PrimitiveError,
    random::{CryptoRngCore, RandomWith},
    types::PeerIndex,
    utils::TakeExact,
};

// ------------------------- //
// ---- Reconstructible ---- //
// ------------------------- //
/// Reconstructs a secret from a collection of openings and a local share.
pub trait Reconstructible: Sized {
    /// The type of the reconstructed value.
    type Secret: Serialize
        + DeserializeOwned
        + for<'de> SchemaRead<'de, Dst = Self::Secret>
        + SchemaWrite<Src = Self::Secret>
        + Clone
        + PartialEq
        + Send
        + Sync
        + 'static;
    /// The type that is sent to / received from other peers.
    type Opening: Serialize
        + DeserializeOwned
        + for<'de> SchemaRead<'de, Dst = Self::Opening>
        + SchemaWrite<Src = Self::Opening>
        + Clone
        + Send
        + Sync
        + 'static;

    /// Open the share towards another peer.
    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError>;

    /// Open the share towards all other peers. Returns an iterator with either one opening for
    /// each peer or a single opening for all peers.
    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening>;

    /// Reconstruct a secret from openings coming from all other parties.
    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError>;

    /// Reconstruct a secret from a collection of shares, by opening each share
    /// towards all other peers, reconstructing `n` secrets from the openings and
    /// checking that they are all equal.
    fn reconstruct_all<T: Borrow<Self>>(shares: &[T]) -> Result<Self::Secret, PrimitiveError> {
        let n_parties = shares.len();
        if n_parties < 2 {
            return Err(PrimitiveError::MinimumLength(2, n_parties));
        }
        // Open each share to all other peers.
        let mut all_openings = shares
            .iter()
            .map(|share| share.borrow().open_to_all_others())
            .collect::<Vec<_>>();
        // Reconstruct each secret.
        enumerate(shares.iter())
            .map(|(i, share)| {
                let my_openings = enumerate(all_openings.iter_mut())
                    .take_exact(n_parties)
                    .filter(|(j, _)| i != *j)
                    .map(|(_, opening)| opening.next())
                    .collect::<Option<Vec<_>>>()
                    .ok_or_else(|| PrimitiveError::InvalidPeerIndex(i, shares.len() - 1))?;
                share.borrow().reconstruct(my_openings.as_slice())
            })
            // Check that all reconstructed secrets are equal.
            .reduce(|previous, current| match (previous, current) {
                (Ok(prev), Ok(curr)) => match prev == curr {
                    true => Ok(prev),
                    false => Err(PrimitiveError::WrongOpening(
                        serde_json::to_string(&prev).unwrap(),
                        serde_json::to_string(&curr).unwrap(),
                    )),
                },
                (Err(e), _) | (_, Err(e)) => Err(e),
            })
            .unwrap() // Safe because `shares.len() >= 2`
    }
}

impl<T: Reconstructible<Opening: Clone>> Reconstructible for Vec<T> {
    type Opening = Vec<T::Opening>;
    type Secret = Vec<T::Secret>;

    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
        self.iter().map(|share| share.open_to(peer_index)).collect()
    }

    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
        let all_openings: Vec<Vec<_>> = self
            .iter()
            .map(|share| share.open_to_all_others().collect())
            .collect();

        transpose(all_openings).into_iter()
    }

    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
        if openings.is_empty() {
            return Err(PrimitiveError::MinimumLength(1, 0));
        }

        if openings[0].len() != self.len() {
            return Err(PrimitiveError::InvalidParameters(
                "Number of openings must match number of shares.".to_string(),
            ));
        }

        // Iterate over all the i-th elements of each entry of openings
        let mut reconstructed = Vec::with_capacity(self.len());
        for (i, share) in self.iter().enumerate() {
            let my_openings: Vec<_> = openings
                .iter()
                .map(|opening| opening.get(i).cloned())
                .collect::<Option<Vec<_>>>()
                .ok_or_else(|| {
                    PrimitiveError::InvalidParameters(
                        "Opening is missing for some share.".to_string(),
                    )
                })?;
            reconstructed.push(share.reconstruct(my_openings.as_slice())?);
        }
        Ok(reconstructed)
    }
}

impl<T: Reconstructible<Opening: Clone>> Reconstructible for Arc<[T]> {
    type Opening = Arc<[T::Opening]>;
    type Secret = Arc<[T::Secret]>;

    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
        self.iter().map(|share| share.open_to(peer_index)).collect()
    }

    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
        let all_openings: Vec<Vec<_>> = self
            .iter()
            .map(|share| share.open_to_all_others().collect())
            .collect();

        transpose(all_openings)
            .into_iter()
            .map(Arc::from)
            .collect::<Vec<_>>()
            .into_iter()
    }

    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
        if openings.is_empty() {
            return Err(PrimitiveError::MinimumLength(1, 0));
        }

        if openings[0].len() != self.len() {
            return Err(PrimitiveError::InvalidParameters(
                "Number of openings must match number of shares.".to_string(),
            ));
        }

        // Iterate over all the i-th elements of each entry of openings
        let mut reconstructed = Vec::with_capacity(self.len());
        for (i, share) in self.iter().enumerate() {
            let my_openings: Vec<_> = openings
                .iter()
                .map(|opening| opening.get(i).cloned())
                .collect::<Option<Vec<_>>>()
                .ok_or_else(|| {
                    PrimitiveError::InvalidParameters(
                        "Opening is missing for some share.".to_string(),
                    )
                })?;
            reconstructed.push(share.reconstruct(my_openings.as_slice())?);
        }

        Ok(reconstructed.into())
    }
}

impl<T: Reconstructible, S: Reconstructible> Reconstructible for (T, S) {
    type Opening = (T::Opening, S::Opening);
    type Secret = (T::Secret, S::Secret);

    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
        Ok((self.0.open_to(peer_index)?, self.1.open_to(peer_index)?))
    }

    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
        let all_openings_t: Vec<_> = self.0.open_to_all_others().collect();
        let all_openings_s: Vec<_> = self.1.open_to_all_others().collect();
        izip!(all_openings_t, all_openings_s).map(|(o1, o2)| (o1, o2))
    }

    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
        let (openings_t, openings_s): (Vec<_>, Vec<_>) = openings.iter().cloned().unzip();
        Ok((
            self.0.reconstruct(&openings_t)?,
            self.1.reconstruct(&openings_s)?,
        ))
    }
}

// ---------------------------- //
// ---- Random for N Peers ---- //
// ---------------------------- //
pub trait RandomAuthenticatedForNPeers<F: FieldExtension>:
    RandomWith<Vec<Vec<GlobalFieldKey<F>>>>
{
    fn random_for_n_peers_with_alphas<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: usize,
        all_alphas: Vec<Vec<GlobalFieldKey<F>>>,
    ) -> Container {
        Self::random_n_with(&mut rng, n_parties, all_alphas)
    }
}

impl<F: FieldExtension, S: RandomWith<Vec<Vec<GlobalFieldKey<F>>>>> RandomAuthenticatedForNPeers<F>
    for S
{
}

pub trait RandomAuthenticatedForNPeersWith<F: FieldExtension, T: Clone>:
    RandomWith<(T, Vec<Vec<GlobalFieldKey<F>>>)>
{
    fn random_authenticated_for_n_peers_with<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: usize,
        value: T,
        all_alphas: Vec<Vec<GlobalFieldKey<F>>>,
    ) -> Container {
        Self::random_n_with(&mut rng, n_parties, (value, all_alphas))
    }
}

impl<F: FieldExtension, T: Clone, S: RandomWith<(T, Vec<Vec<GlobalFieldKey<F>>>)>>
    RandomAuthenticatedForNPeersWith<F, T> for S
{
}

/// A trait used to add a plaintext to a certain type. Commonly used to correct
/// shares after a masked opening, or to add a public constant
pub trait AddPlaintext: Reconstructible {
    type AssociatedInformation: Clone + Send + Sync;

    /// Add a plaintext to the share.
    fn add_plaintext(&self, ptx: &Self::Secret, assoc: Self::AssociatedInformation) -> Self;

    /// Add a plaintext to the share, consuming the share and returning a new one.
    fn add_plaintext_owned(self, ptx: &Self::Secret, assoc: Self::AssociatedInformation) -> Self {
        self.add_plaintext(ptx, assoc)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        algebra::elliptic_curve::Curve25519Ristretto,
        random::Random,
        sharing::ScalarShares,
    };

    #[test]
    fn test_transpose_empty_matrix() {
        let matrix: Vec<Vec<i32>> = vec![];
        let result = transpose(matrix.clone());
        assert_eq!(result, matrix);
    }

    #[test]
    fn test_transpose_empty_rows() {
        let matrix: Vec<Vec<i32>> = vec![];
        let result = transpose(matrix.clone());
        assert_eq!(result, matrix);
    }

    #[test]
    fn test_transpose_single_element() {
        let matrix = vec![vec![1]];
        let result = transpose(matrix);
        assert_eq!(result, vec![vec![1]]);
    }

    #[test]
    fn test_transpose_single_row() {
        let matrix = vec![vec![1, 2, 3]];
        let result = transpose(matrix);
        assert_eq!(result, vec![vec![1], vec![2], vec![3]]);
    }

    #[test]
    fn test_transpose_single_column() {
        let matrix = vec![vec![1], vec![2], vec![3]];
        let result = transpose(matrix);
        assert_eq!(result, vec![vec![1, 2, 3]]);
    }

    #[test]
    fn test_transpose_square_matrix() {
        let matrix = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
        let result = transpose(matrix);
        let expected = vec![vec![1, 4, 7], vec![2, 5, 8], vec![3, 6, 9]];
        assert_eq!(result, expected);
    }

    #[test]
    fn test_transpose_rectangular_matrix() {
        let matrix = vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8]];
        let result = transpose(matrix);
        let expected = vec![vec![1, 5], vec![2, 6], vec![3, 7], vec![4, 8]];
        assert_eq!(result, expected);
    }

    #[test]
    fn test_transpose_with_strings() {
        let matrix = vec![vec!["a", "b"], vec!["c", "d"], vec!["e", "f"]];
        let result = transpose(matrix);
        let expected = vec![vec!["a", "c", "e"], vec!["b", "d", "f"]];
        assert_eq!(result, expected);
    }

    #[test]
    fn test_transpose_double_transpose() {
        let matrix = vec![vec![1, 2, 3], vec![4, 5, 6]];
        let result = transpose(transpose(matrix.clone()));
        assert_eq!(result, matrix);
    }

    #[test]
    fn test_reconstruct_vec() {
        let n_parties = 3;
        let mut rng = crate::random::test_rng();

        let scalar_shares: Vec<_> =
            ScalarShares::<Curve25519Ristretto, typenum::U5>::random_n(&mut rng, n_parties);
        let scalar_shares = scalar_shares
            .into_iter()
            .map(|s| s.into_iter().collect::<Vec<_>>())
            .collect::<Vec<_>>();

        let reconstructed =
            Vec::<ScalarShare<Curve25519Ristretto>>::reconstruct_all(&scalar_shares).unwrap();
        let expected = (0..5)
            .map(|i| {
                ScalarShare::<Curve25519Ristretto>::reconstruct_all(
                    &scalar_shares.iter().map(|v| &v[i]).collect::<Vec<_>>(),
                )
                .unwrap()
            })
            .collect::<Vec<_>>();
        assert_eq!(reconstructed, expected);
    }

    #[test]
    fn test_reconstruct_tuple() {
        let n_parties = 3;
        let mut rng = crate::random::test_rng();

        let scalar_shares: Vec<_> =
            ScalarShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
        let base_field_shares: Vec<_> =
            BaseFieldShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);

        let shares: Vec<(
            ScalarShare<Curve25519Ristretto>,
            BaseFieldShare<Curve25519Ristretto>,
        )> = izip!(&scalar_shares, &base_field_shares)
            .map(|(s, b)| (s.clone(), b.clone()))
            .collect();

        let reconstructed = <(
            ScalarShare<Curve25519Ristretto>,
            BaseFieldShare<Curve25519Ristretto>,
        )>::reconstruct_all(&shares)
        .unwrap();

        assert_eq!(
            reconstructed.0,
            ScalarShare::<Curve25519Ristretto>::reconstruct_all(&scalar_shares).unwrap()
        );
        assert_eq!(
            reconstructed.1,
            BaseFieldShare::<Curve25519Ristretto>::reconstruct_all(&base_field_shares).unwrap()
        );
    }
}