primitives/sharing/
reconstructible.rs

1use std::{borrow::Borrow, sync::Arc};
2
3use itertools::{enumerate, izip};
4use serde::{de::DeserializeOwned, Serialize};
5use wincode::{SchemaRead, SchemaWrite};
6
7use crate::{
8    algebra::ops::transpose::transpose,
9    errors::PrimitiveError,
10    types::PeerIndex,
11    utils::TakeExact,
12};
13
14/// Reconstructs a secret-shared value from a collection of openings and a local share.
15pub trait Reconstructible: Sized {
16    /// The type of the reconstructed value.
17    type Value: Serialize
18        + DeserializeOwned
19        + for<'de> SchemaRead<'de, Dst = Self::Value>
20        + SchemaWrite<Src = Self::Value>
21        + Clone
22        + PartialEq
23        + Send
24        + Sync
25        + 'static;
26    /// The type that is sent to / received from other peers.
27    type Opening: Serialize
28        + DeserializeOwned
29        + for<'de> SchemaRead<'de, Dst = Self::Opening>
30        + SchemaWrite<Src = Self::Opening>
31        + Clone
32        + Send
33        + Sync
34        + 'static;
35
36    /// Open the share towards another peer.
37    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError>;
38
39    /// Open the share towards all other peers. Returns an iterator with either one opening for
40    /// each peer or a single opening for all peers.
41    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening>;
42
43    /// Reconstruct a secret from openings coming from all other parties.
44    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError>;
45
46    /// Reconstruct a secret from a collection of shares, by opening each share
47    /// towards all other peers, reconstructing `n` secrets from the openings and
48    /// checking that they are all equal.
49    fn reconstruct_all<T: Borrow<Self>>(shares: Vec<T>) -> Result<Self::Value, PrimitiveError> {
50        let n_parties = shares.len();
51        if n_parties < 2 {
52            return Err(PrimitiveError::MinimumLength(2, n_parties));
53        }
54        // Open each share to all other peers.
55        let mut all_openings = shares
56            .iter()
57            .map(|share| share.borrow().open_to_all_others())
58            .collect::<Vec<_>>();
59        // Reconstruct each secret.
60        enumerate(shares.iter())
61            .map(|(i, share)| {
62                let my_openings = enumerate(all_openings.iter_mut())
63                    .take_exact(n_parties)
64                    .filter(|(j, _)| i != *j)
65                    .map(|(_, opening)| opening.next())
66                    .collect::<Option<Vec<_>>>()
67                    .ok_or_else(|| PrimitiveError::InvalidPeerIndex(i, shares.len() - 1))?;
68                share.borrow().reconstruct(my_openings)
69            })
70            // Check that all reconstructed secrets are equal.
71            .reduce(|previous, current| match (previous, current) {
72                (Ok(prev), Ok(curr)) => match prev == curr {
73                    true => Ok(prev),
74                    false => Err(PrimitiveError::WrongOpening(
75                        serde_json::to_string(&prev).unwrap(),
76                        serde_json::to_string(&curr).unwrap(),
77                    )),
78                },
79                (Err(e), _) | (_, Err(e)) => Err(e),
80            })
81            .unwrap() // Safe because `shares.len() >= 2`
82    }
83}
84
85impl<T: Reconstructible<Opening: Clone>> Reconstructible for Vec<T> {
86    type Opening = Vec<T::Opening>;
87    type Value = Vec<T::Value>;
88
89    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
90        self.iter().map(|share| share.open_to(peer_index)).collect()
91    }
92
93    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
94        let all_openings: Vec<Vec<_>> = self
95            .iter()
96            .map(|share| share.open_to_all_others().collect())
97            .collect();
98
99        transpose(all_openings).into_iter()
100    }
101
102    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError> {
103        if openings.is_empty() {
104            return Err(PrimitiveError::MinimumLength(1, 0));
105        }
106
107        if openings[0].len() != self.len() {
108            return Err(PrimitiveError::InvalidParameters(
109                "Number of openings must match number of shares.".to_string(),
110            ));
111        }
112
113        // Iterate over all the i-th elements of each entry of openings
114        let mut reconstructed = Vec::with_capacity(self.len());
115        for (i, share) in self.iter().enumerate() {
116            let my_openings: Vec<_> = openings
117                .iter()
118                .map(|opening| opening.get(i).cloned())
119                .collect::<Option<Vec<_>>>()
120                .ok_or_else(|| {
121                    PrimitiveError::InvalidParameters(
122                        "Opening is missing for some share.".to_string(),
123                    )
124                })?;
125            reconstructed.push(share.reconstruct(my_openings)?);
126        }
127        Ok(reconstructed)
128    }
129}
130
131impl<T: Reconstructible<Opening: Clone>> Reconstructible for Arc<[T]> {
132    type Opening = Arc<[T::Opening]>;
133    type Value = Arc<[T::Value]>;
134
135    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
136        self.iter().map(|share| share.open_to(peer_index)).collect()
137    }
138
139    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
140        let all_openings: Vec<Vec<_>> = self
141            .iter()
142            .map(|share| share.open_to_all_others().collect())
143            .collect();
144
145        transpose(all_openings)
146            .into_iter()
147            .map(Arc::from)
148            .collect::<Vec<_>>()
149            .into_iter()
150    }
151
152    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError> {
153        if openings.is_empty() {
154            return Err(PrimitiveError::MinimumLength(1, 0));
155        }
156
157        if openings[0].len() != self.len() {
158            return Err(PrimitiveError::InvalidParameters(
159                "Number of openings must match number of shares.".to_string(),
160            ));
161        }
162
163        // Iterate over all the i-th elements of each entry of openings
164        let mut reconstructed = Vec::with_capacity(self.len());
165        for (i, share) in self.iter().enumerate() {
166            let my_openings: Vec<_> = openings
167                .iter()
168                .map(|opening| opening.get(i).cloned())
169                .collect::<Option<Vec<_>>>()
170                .ok_or_else(|| {
171                    PrimitiveError::InvalidParameters(
172                        "Opening is missing for some share.".to_string(),
173                    )
174                })?;
175            reconstructed.push(share.reconstruct(my_openings)?);
176        }
177
178        Ok(reconstructed.into())
179    }
180}
181
182impl<T: Reconstructible, S: Reconstructible> Reconstructible for (T, S) {
183    type Opening = (T::Opening, S::Opening);
184    type Value = (T::Value, S::Value);
185
186    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
187        Ok((self.0.open_to(peer_index)?, self.1.open_to(peer_index)?))
188    }
189
190    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
191        let all_openings_t: Vec<_> = self.0.open_to_all_others().collect();
192        let all_openings_s: Vec<_> = self.1.open_to_all_others().collect();
193        izip!(all_openings_t, all_openings_s).map(|(o1, o2)| (o1, o2))
194    }
195
196    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError> {
197        let (openings_t, openings_s): (Vec<_>, Vec<_>) = openings.into_iter().unzip();
198        Ok((
199            self.0.reconstruct(openings_t)?,
200            self.1.reconstruct(openings_s)?,
201        ))
202    }
203}
204
205#[cfg(test)]
206mod tests {
207    use super::*;
208    use crate::{
209        algebra::elliptic_curve::Curve25519Ristretto,
210        random::Random,
211        sharing::{BaseFieldShare, ScalarShare, ScalarShares},
212    };
213
214    #[test]
215    fn test_reconstruct_vec() {
216        let n_parties = 3;
217        let mut rng = crate::random::test_rng();
218
219        let scalar_shares: Vec<_> =
220            ScalarShares::<Curve25519Ristretto, typenum::U5>::random_n(&mut rng, n_parties);
221        let scalar_shares = scalar_shares
222            .into_iter()
223            .map(|s| s.into_iter().collect::<Vec<_>>())
224            .collect::<Vec<_>>();
225
226        let reconstructed =
227            Vec::<ScalarShare<Curve25519Ristretto>>::reconstruct_all(scalar_shares.clone())
228                .unwrap();
229        let expected = (0..5)
230            .map(|i| {
231                ScalarShare::<Curve25519Ristretto>::reconstruct_all(
232                    scalar_shares.iter().map(|v| v[i].clone()).collect(),
233                )
234                .unwrap()
235            })
236            .collect::<Vec<_>>();
237        assert_eq!(reconstructed, expected);
238    }
239
240    #[test]
241    fn test_reconstruct_tuple() {
242        let n_parties = 3;
243        let mut rng = crate::random::test_rng();
244
245        let scalar_shares: Vec<_> =
246            ScalarShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
247        let base_field_shares: Vec<_> =
248            BaseFieldShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
249
250        let shares: Vec<(
251            ScalarShare<Curve25519Ristretto>,
252            BaseFieldShare<Curve25519Ristretto>,
253        )> = izip!(&scalar_shares, &base_field_shares)
254            .map(|(s, b)| (s.clone(), b.clone()))
255            .collect();
256
257        let reconstructed = <(
258            ScalarShare<Curve25519Ristretto>,
259            BaseFieldShare<Curve25519Ristretto>,
260        )>::reconstruct_all(shares)
261        .unwrap();
262
263        assert_eq!(
264            reconstructed.0,
265            ScalarShare::<Curve25519Ristretto>::reconstruct_all(scalar_shares).unwrap()
266        );
267        assert_eq!(
268            reconstructed.1,
269            BaseFieldShare::<Curve25519Ristretto>::reconstruct_all(base_field_shares).unwrap()
270        );
271    }
272}
primitives/sharing/reconstructible.rs

primitives/sharing/
reconstructible.rs
