primitives/sharing/
reconstructible.rs

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

primitives/sharing/
reconstructible.rs
