commonware_coding/
lib.rs

1//! Encode data to enable recovery from a subset of fragments.
2//!
3//! # Status
4//!
5//! `commonware-coding` is **ALPHA** software and is not yet recommended for production use. Developers should
6//! expect breaking changes and occasional instability.
7
8#![doc(
9    html_logo_url = "https://commonware.xyz/imgs/rustdoc_logo.svg",
10    html_favicon_url = "https://commonware.xyz/favicon.ico"
11)]
12
13use bytes::Buf;
14use commonware_codec::{Codec, FixedSize, Read, Write};
15use std::fmt::Debug;
16
17mod reed_solomon;
18use commonware_cryptography::Digest;
19pub use reed_solomon::{Error as ReedSolomonError, ReedSolomon};
20
21mod no_coding;
22pub use no_coding::{NoCoding, NoCodingError};
23
24/// Configuration common to all encoding schemes.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
26pub struct Config {
27    /// The minimum number of shards needed to encode the data.
28    pub minimum_shards: u16,
29    /// Extra shards beyond the minimum number.
30    ///
31    /// Alternatively, one can think of the configuration as having a total number
32    /// `N = extra_shards + minimum_shards`, but by specifying the `extra_shards`
33    /// rather than `N`, we avoid needing to check that `minimum_shards <= N`.
34    pub extra_shards: u16,
35}
36
37impl Config {
38    /// Returns the total number of shards produced by this configuration.
39    pub fn total_shards(&self) -> u16 {
40        self.minimum_shards + self.extra_shards
41    }
42}
43
44impl FixedSize for Config {
45    const SIZE: usize = 2 * <u16 as FixedSize>::SIZE;
46}
47
48impl Write for Config {
49    fn write(&self, buf: &mut impl bytes::BufMut) {
50        self.minimum_shards.write(buf);
51        self.extra_shards.write(buf);
52    }
53}
54
55impl Read for Config {
56    type Cfg = ();
57
58    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
59        Ok(Self {
60            minimum_shards: u16::read_cfg(buf, cfg)?,
61            extra_shards: u16::read_cfg(buf, cfg)?,
62        })
63    }
64}
65
66/// A scheme for encoding data into pieces, and recovering the data from those pieces.
67///
68/// # Example
69/// ```
70/// use commonware_coding::{Config, ReedSolomon, Scheme as _};
71/// use commonware_cryptography::Sha256;
72///
73/// type RS = ReedSolomon<Sha256>;
74///
75/// let config = Config { minimum_shards: 2, extra_shards: 1 };
76/// let data = b"Hello!";
77/// // Turn the data into shards, and a commitment to those shards.
78/// let (commitment, shards) =
79///      RS::encode(&config, data.as_slice()).unwrap();
80///
81/// // Each person produces reshards, their own checked shard, and checking data
82/// // to check other peoples reshards.
83/// let (mut checking_data_w_shard, reshards): (Vec<_>, Vec<_>) = shards
84///         .into_iter()
85///         .enumerate()
86///         .map(|(i, shard)| {
87///             let (checking_data, checked_shard, reshard) = RS::reshard(&config, &commitment, i as u16, shard).unwrap();
88///             ((checking_data, checked_shard), reshard)
89///         })
90///         .collect();
91/// // Let's pretend that the last item is "ours"
92/// let (checking_data, checked_shard) = checking_data_w_shard.pop().unwrap();
93/// // We can use this checking_data to check the other shards.
94/// let mut checked_shards = Vec::new();
95/// checked_shards.push(checked_shard);
96/// for (i, reshard) in reshards.into_iter().enumerate().skip(1) {
97///   checked_shards.push(RS::check(&config, &commitment, &checking_data, i as u16, reshard).unwrap())
98/// }
99///
100/// let data2 = RS::decode(&config, &commitment, checking_data, &checked_shards[..2]).unwrap();
101/// assert_eq!(&data[..], &data2[..]);
102///
103/// // Decoding works with different shards, with a guarantee to get the same result.
104/// let data3 = RS::decode(&config, &commitment, checking_data, &checked_shards[1..]).unwrap();
105/// assert_eq!(&data[..], &data3[..]);
106/// ```
107pub trait Scheme: Debug + Clone + Send + Sync + 'static {
108    /// A commitment attesting to the shards of data.
109    type Commitment: Digest;
110    /// A shard of data, to be received by a participant.
111    type Shard: Clone + Eq + Codec + Send + Sync + 'static;
112    /// A shard shared with other participants, to aid them in reconstruction.
113    ///
114    /// In most cases, this will be the same as `Shard`, but some schemes might
115    /// have extra information in `Shard` that may not be necessary to reconstruct
116    /// the data.
117    type ReShard: Clone + Eq + Codec + Send + Sync + 'static;
118    /// Data which can assist in checking shards.
119    type CheckingData: Clone + Send;
120    /// A shard that has been checked for inclusion in the commitment.
121    ///
122    /// This allows excluding [Scheme::ReShard]s which are invalid, and shouldn't
123    /// be considered as progress towards meeting the minimum number of shards.
124    type CheckedShard;
125    type Error: std::fmt::Debug;
126
127    /// Encode a piece of data, returning a commitment, along with shards, and proofs.
128    ///
129    /// Each shard and proof is intended for exactly one participant. The number of shards returned
130    /// should equal `config.minimum_shards + config.extra_shards`.
131    #[allow(clippy::type_complexity)]
132    fn encode(
133        config: &Config,
134        data: impl Buf,
135    ) -> Result<(Self::Commitment, Vec<Self::Shard>), Self::Error>;
136
137    /// Take your own shard, check it, and produce a [Scheme::ReShard] to forward to others.
138    ///
139    /// This takes in an index, which is the index you expect the shard to be.
140    ///
141    /// This will produce a [Scheme::CheckedShard] which counts towards the minimum
142    /// number of shards you need to reconstruct the data, in [Scheme::decode].
143    ///
144    /// You also get [Scheme::CheckingData], which has information you can use to check
145    /// the shards you receive from others.
146    #[allow(clippy::type_complexity)]
147    fn reshard(
148        config: &Config,
149        commitment: &Self::Commitment,
150        index: u16,
151        shard: Self::Shard,
152    ) -> Result<(Self::CheckingData, Self::CheckedShard, Self::ReShard), Self::Error>;
153
154    /// Check the integrity of a reshard, producing a checked shard.
155    ///
156    /// This requires the [Scheme::CheckingData] produced by [Scheme::reshard].
157    ///
158    /// This takes in an index, to make sure that the reshard you're checking
159    /// is associated with the participant you expect it to be.
160    fn check(
161        config: &Config,
162        commitment: &Self::Commitment,
163        checking_data: &Self::CheckingData,
164        index: u16,
165        reshard: Self::ReShard,
166    ) -> Result<Self::CheckedShard, Self::Error>;
167
168    /// Decode the data from shards received from other participants.
169    ///
170    /// The data must be decodeable with as few as `config.minimum_shards`,
171    /// including your own shard.
172    ///
173    /// Calls to this function with the same commitment, but with different shards,
174    /// or shards in a different should also result in the same output data, or in failure.
175    /// In other words, when using the decoding function in a broader system, you
176    /// get a guarantee that every participant decoding will see the same final
177    /// data, even if they receive different shards, or receive them in a different order.
178    fn decode(
179        config: &Config,
180        commitment: &Self::Commitment,
181        checking_data: Self::CheckingData,
182        shards: &[Self::CheckedShard],
183    ) -> Result<Vec<u8>, Self::Error>;
184}
185
186/// A marker trait indicating that [Scheme::check] proves validity of the encoding.
187///
188/// In more detail, this means that upon a successful call to [Scheme::check],
189/// guarantees that the shard results from a valid encoding of the data, and thus,
190/// if other participants also call check, then the data is guaranteed to be reconstructable.
191pub trait ValidatingScheme: Scheme {}
192
193#[cfg(test)]
194mod test {
195    use super::*;
196    use crate::reed_solomon::ReedSolomon;
197    use commonware_cryptography::Sha256;
198
199    fn test_basic<S: Scheme>() {
200        let data = b"Hello, Reed-Solomon!";
201        let config = Config {
202            minimum_shards: 4,
203            extra_shards: 3,
204        };
205
206        // Encode the data
207        let (commitment, shards) = S::encode(&config, data.as_slice()).unwrap();
208
209        let (mut checking_data, checked_shards): (Vec<_>, Vec<_>) = shards
210            .into_iter()
211            .enumerate()
212            .map(|(i, shard)| {
213                let (checking_data, checked_shard, _) =
214                    S::reshard(&config, &commitment, i as u16, shard).unwrap();
215                (checking_data, checked_shard)
216            })
217            .collect();
218
219        let decoded = S::decode(
220            &config,
221            &commitment,
222            checking_data.pop().unwrap(),
223            &checked_shards[..config.minimum_shards as usize],
224        )
225        .unwrap();
226        assert_eq!(decoded, data, "test_basic_failed");
227    }
228
229    fn test_moderate<S: Scheme>() {
230        let data = b"Testing with more pieces than minimum";
231        let config = Config {
232            minimum_shards: 4,
233            extra_shards: 6,
234        };
235
236        // Encode the data
237        let (commitment, shards) = S::encode(&config, data.as_slice()).unwrap();
238
239        let (mut checking_data, mut checked_shards): (Vec<_>, Vec<_>) = shards
240            .into_iter()
241            .enumerate()
242            .map(|(i, shard)| {
243                let (checking_data, checked_shard, _) =
244                    S::reshard(&config, &commitment, i as u16, shard).unwrap();
245                (checking_data, checked_shard)
246            })
247            .collect();
248
249        // Try to decode with a mix of original and recovery pieces
250        {
251            let (part1, part2) = checked_shards.split_at_mut(config.minimum_shards as usize);
252            std::mem::swap(&mut part1[0], &mut part2[0]);
253        }
254        let decoded = S::decode(
255            &config,
256            &commitment,
257            checking_data.pop().unwrap(),
258            &checked_shards[..config.minimum_shards as usize],
259        )
260        .unwrap();
261        assert_eq!(decoded, data, "test_moderate_failed");
262    }
263
264    fn test_odd_shard_len<S: Scheme>() {
265        let data = b"a";
266        let config = Config {
267            minimum_shards: 2,
268            extra_shards: 1,
269        };
270
271        // Encode the data
272        let (commitment, shards) = S::encode(&config, data.as_slice()).unwrap();
273
274        let (mut checking_data, checked_shards): (Vec<_>, Vec<_>) = shards
275            .into_iter()
276            .enumerate()
277            .map(|(i, shard)| {
278                let (checking_data, checked_shard, _) =
279                    S::reshard(&config, &commitment, i as u16, shard).unwrap();
280                (checking_data, checked_shard)
281            })
282            .collect();
283
284        let decoded = S::decode(
285            &config,
286            &commitment,
287            checking_data.pop().unwrap(),
288            &checked_shards[..config.minimum_shards as usize],
289        )
290        .unwrap();
291        assert_eq!(decoded, data, "test_odd_shard_len_failed");
292    }
293
294    fn test_recovery<S: Scheme>() {
295        let data = b"Testing recovery pieces";
296        let config = Config {
297            minimum_shards: 3,
298            extra_shards: 5,
299        };
300
301        // Encode the data
302        let (commitment, shards) = S::encode(&config, data.as_slice()).unwrap();
303
304        let (mut checking_data, checked_shards): (Vec<_>, Vec<_>) = shards
305            .into_iter()
306            .enumerate()
307            .map(|(i, shard)| {
308                let (checking_data, checked_shard, _) =
309                    S::reshard(&config, &commitment, i as u16, shard).unwrap();
310                (checking_data, checked_shard)
311            })
312            .collect();
313
314        let decoded = S::decode(
315            &config,
316            &commitment,
317            checking_data.pop().unwrap(),
318            &checked_shards[checked_shards.len() - config.minimum_shards as usize..],
319        )
320        .unwrap();
321        assert_eq!(decoded, data, "test_recovery_failed");
322    }
323
324    fn test_empty_data<S: Scheme>() {
325        let data = b"";
326        let config = Config {
327            minimum_shards: 30,
328            extra_shards: 100,
329        };
330
331        // Encode the data
332        let (commitment, shards) = S::encode(&config, data.as_slice()).unwrap();
333
334        let (mut checking_data, checked_shards): (Vec<_>, Vec<_>) = shards
335            .into_iter()
336            .enumerate()
337            .map(|(i, shard)| {
338                let (checking_data, checked_shard, _) =
339                    S::reshard(&config, &commitment, i as u16, shard).unwrap();
340                (checking_data, checked_shard)
341            })
342            .collect();
343
344        let decoded = S::decode(
345            &config,
346            &commitment,
347            checking_data.pop().unwrap(),
348            &checked_shards[..config.minimum_shards as usize],
349        )
350        .unwrap();
351        assert_eq!(decoded, data, "test_empty_data_failed");
352    }
353
354    fn test_large_data<S: Scheme>() {
355        let data = vec![42u8; 1000]; // 1KB of data
356        let config = Config {
357            minimum_shards: 4,
358            extra_shards: 3,
359        };
360
361        // Encode the data
362        let (commitment, shards) = S::encode(&config, data.as_slice()).unwrap();
363
364        let (mut checking_data, checked_shards): (Vec<_>, Vec<_>) = shards
365            .into_iter()
366            .enumerate()
367            .map(|(i, shard)| {
368                let (checking_data, checked_shard, _) =
369                    S::reshard(&config, &commitment, i as u16, shard).unwrap();
370                (checking_data, checked_shard)
371            })
372            .collect();
373
374        let decoded = S::decode(
375            &config,
376            &commitment,
377            checking_data.pop().unwrap(),
378            &checked_shards[..config.minimum_shards as usize],
379        )
380        .unwrap();
381        assert_eq!(decoded, data, "test_large_data_failed");
382    }
383
384    fn test_suite<S: Scheme>() {
385        test_basic::<S>();
386        test_moderate::<S>();
387        test_odd_shard_len::<S>();
388        test_recovery::<S>();
389        test_empty_data::<S>();
390        test_large_data::<S>();
391    }
392
393    #[test]
394    fn test_suite_reed_solomon() {
395        test_suite::<ReedSolomon<Sha256>>();
396    }
397
398    #[test]
399    fn test_suite_no_coding() {
400        test_suite::<NoCoding<Sha256>>();
401    }
402}
commonware_coding/lib.rs

commonware_coding/
lib.rs
