commonware_coding/lib.rs
1//! Encode data to enable recovery from a subset of fragments.
2//!
3//! # Status
4//!
5//! Stability varies by primitive. See [README](https://github.com/commonwarexyz/monorepo#stability) for details.
6
7#![doc(
8 html_logo_url = "https://commonware.xyz/imgs/rustdoc_logo.svg",
9 html_favicon_url = "https://commonware.xyz/favicon.ico"
10)]
11
12commonware_macros::stability_scope!(ALPHA {
13 use commonware_codec::{Buf, Codec, FixedSize, Read, Write};
14 use commonware_cryptography::Digest;
15 use commonware_parallel::Strategy;
16 use std::{fmt::Debug, num::NonZeroU16};
17
18 mod reed_solomon;
19 pub use reed_solomon::{Error as ReedSolomonError, ReedSolomon};
20
21 /// Configuration common to all encoding schemes.
22 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
23 pub struct Config {
24 /// The minimum number of shards needed to encode the data.
25 pub minimum_shards: NonZeroU16,
26 /// Extra shards beyond the minimum number.
27 ///
28 /// Alternatively, one can think of the configuration as having a total number
29 /// `N = extra_shards + minimum_shards`, but by specifying the `extra_shards`
30 /// rather than `N`, we avoid needing to check that `minimum_shards <= N`.
31 pub extra_shards: NonZeroU16,
32 }
33
34 impl Config {
35 /// Returns the total number of shards produced by this configuration.
36 pub fn total_shards(&self) -> u32 {
37 u32::from(self.minimum_shards.get()) + u32::from(self.extra_shards.get())
38 }
39 }
40
41 impl FixedSize for Config {
42 const SIZE: usize = 2 * <NonZeroU16 as FixedSize>::SIZE;
43 }
44
45 impl Write for Config {
46 fn write(&self, buf: &mut impl bytes::BufMut) {
47 self.minimum_shards.write(buf);
48 self.extra_shards.write(buf);
49 }
50 }
51
52 impl Read for Config {
53 type Cfg = ();
54
55 fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
56 Ok(Self {
57 minimum_shards: NonZeroU16::read_cfg(buf, cfg)?,
58 extra_shards: NonZeroU16::read_cfg(buf, cfg)?,
59 })
60 }
61 }
62
63 #[cfg(feature = "arbitrary")]
64 impl<'a> arbitrary::Arbitrary<'a> for Config {
65 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
66 let minimum_shards = commonware_utils::NZU16!(u.int_in_range(1..=u16::MAX)?);
67 let extra_shards = commonware_utils::NZU16!(u.int_in_range(1..=u16::MAX)?);
68 Ok(Self {
69 minimum_shards,
70 extra_shards,
71 })
72 }
73 }
74
75 /// A scheme for encoding data into pieces, and recovering the data from those pieces.
76 ///
77 /// # Example
78 /// ```
79 /// use commonware_coding::{Config, ReedSolomon, Scheme as _};
80 /// use commonware_cryptography::Sha256;
81 /// use commonware_parallel::Sequential;
82 /// use commonware_utils::NZU16;
83 ///
84 /// const STRATEGY: Sequential = Sequential;
85 ///
86 /// type RS = ReedSolomon<Sha256>;
87 ///
88 /// let config = Config {
89 /// minimum_shards: NZU16!(2),
90 /// extra_shards: NZU16!(1),
91 /// };
92 /// let data = b"Hello!";
93 /// // Turn the data into shards, and a commitment to those shards.
94 /// let (commitment, shards) =
95 /// RS::encode(&config, data.as_slice(), &STRATEGY).unwrap();
96 ///
97 /// // Each participant checks their shard against the commitment.
98 /// let checked_shards: Vec<_> = shards
99 /// .iter()
100 /// .enumerate()
101 /// .map(|(i, shard)| {
102 /// RS::check(&config, &commitment, i as u16, shard, &STRATEGY).unwrap()
103 /// })
104 /// .collect();
105 ///
106 /// // Decode from any minimum_shards-sized subset.
107 /// let data2 = RS::decode(&config, &commitment, checked_shards[..2].iter(), &STRATEGY).unwrap();
108 /// assert_eq!(&data[..], &data2[..]);
109 ///
110 /// // Decoding works with different shards, with a guarantee to get the same result.
111 /// let data3 = RS::decode(&config, &commitment, checked_shards[1..].iter(), &STRATEGY).unwrap();
112 /// assert_eq!(&data[..], &data3[..]);
113 /// ```
114 ///
115 /// # Guarantees
116 ///
117 /// Here are additional properties that implementors of this trait need to
118 /// consider, and that users of this trait can rely on.
119 ///
120 /// ## Check Agreement
121 ///
122 /// [`Scheme::check`] should agree across honest parties, even for malicious
123 /// encoders.
124 ///
125 /// It should not be possible for parties A and B to both call `check`
126 /// successfully on their own shards, but then have either of them fail
127 /// when calling `check` on the other's shard.
128 ///
129 /// In other words, if an honest party considers their shard to be correctly
130 /// formed, then other honest parties which have also successfully checked
131 /// their own shards will agree with that shard being correct.
132 ///
133 /// A violation of this property would be, for example, if a malicious
134 /// payload could convince two parties that they both have valid shards, but
135 /// then checking each other's shards reports issues with those shards.
136 ///
137 /// ## Unique Commitments
138 ///
139 /// [`Scheme::encode`] MUST be deterministic.
140 ///
141 /// For a given [`Config`] and `data`, the only [`Scheme::Commitment`] which
142 /// should pass [`Scheme::decode`] MUST be that produced by [`Scheme::encode`].
143 ///
144 /// In other words, a data has a unique valid commitment associated with it.
145 pub trait Scheme: Debug + Clone + Send + Sync + 'static {
146 /// A commitment attesting to the shards of data.
147 type Commitment: Digest;
148 /// A shard of data, to be received by a participant.
149 ///
150 /// Shards decode with a [`Config`] and the maximum number of input data bytes. Their data
151 /// portion must be no wider than [`Self::encode`] produces for those inputs.
152 type Shard: Clone + Debug + Eq + Codec<Cfg = (Config, usize)> + Send + Sync + 'static;
153 /// A shard that has been checked for inclusion in the commitment.
154 ///
155 /// This allows excluding invalid shards from the function signature of [`Self::decode`].
156 type CheckedShard: Clone + Send + Sync;
157 /// The type of errors that can occur during encoding, checking, and decoding.
158 type Error: std::fmt::Debug + Send;
159
160 /// Returns an upper bound on the encoded size of any shard [`Self::encode`] produces under
161 /// `config` from at most `data` bytes, using each encoded type's maximum width.
162 fn max_shard_size(config: &Config, data: usize) -> usize;
163
164 /// Encode a piece of data, returning a commitment, along with shards, and proofs.
165 ///
166 /// The input is a stream of bytes and may borrow its storage.
167 ///
168 /// Each shard and proof is intended for exactly one participant. The number of shards returned
169 /// should equal `config.minimum_shards + config.extra_shards`.
170 #[allow(clippy::type_complexity)]
171 fn encode(
172 config: &Config,
173 data: impl bytes::Buf,
174 strategy: &impl Strategy,
175 ) -> Result<(Self::Commitment, Vec<Self::Shard>), Self::Error>;
176
177 /// Check the integrity of a shard, producing a checked shard.
178 ///
179 /// This takes in an index, to make sure that the shard you're checking
180 /// is associated with the participant you expect it to be.
181 fn check(
182 config: &Config,
183 commitment: &Self::Commitment,
184 index: u16,
185 shard: &Self::Shard,
186 strategy: &impl Strategy,
187 ) -> Result<Self::CheckedShard, Self::Error>;
188
189 /// Check the integrity of multiple shards.
190 ///
191 /// Returns one result per input in the same order. Each result is equivalent
192 /// to calling [`Self::check`] independently with that input's index and shard.
193 fn check_many(
194 config: &Config,
195 commitment: &Self::Commitment,
196 shards: &[(u16, &Self::Shard)],
197 strategy: &impl Strategy,
198 ) -> Vec<Result<Self::CheckedShard, Self::Error>> {
199 strategy.map_collect_vec(shards, |&(index, shard)| {
200 Self::check(config, commitment, index, shard, strategy)
201 })
202 }
203
204 /// Decode the data from shards received from other participants.
205 ///
206 /// The data must be decodeable with as few as `config.minimum_shards`,
207 /// including your own shard.
208 ///
209 /// Calls to this function with the same commitment, but with different shards,
210 /// or shards in a different order should also result in the same output data,
211 /// or in failure. In other words, when using the decoding function in a broader
212 /// system, you get a guarantee that every participant decoding will see the same
213 /// final data, even if they receive different shards, or receive them in a
214 /// different order.
215 ///
216 /// ## Commitment Binding
217 ///
218 /// Implementations must reject shards that were checked against a different
219 /// commitment than the one passed to `decode`. Mixing checked shards from
220 /// separate `encode` calls (and thus different commitments) must return an
221 /// error.
222 fn decode<'a>(
223 config: &Config,
224 commitment: &Self::Commitment,
225 shards: impl Iterator<Item = &'a Self::CheckedShard>,
226 strategy: &impl Strategy,
227 ) -> Result<Vec<u8>, Self::Error>;
228 }
229});
230
231#[cfg(test)]
232mod test {
233 use super::*;
234 use arbitrary::Unstructured;
235 use commonware_cryptography::Sha256;
236 use commonware_invariants::minifuzz;
237 use commonware_utils::NZU16;
238
239 const MAX_SHARDS: u16 = 32;
240 const MAX_DATA: usize = 1024;
241 const MIN_EXTRA_SHARDS: u16 = 1;
242
243 fn generate_case(u: &mut Unstructured<'_>) -> arbitrary::Result<(Config, Vec<u8>, Vec<u16>)> {
244 let minimum_shards = (u.arbitrary::<u16>()? % MAX_SHARDS) + 1;
245 let extra_shards =
246 MIN_EXTRA_SHARDS + (u.arbitrary::<u16>()? % (MAX_SHARDS - MIN_EXTRA_SHARDS + 1));
247 let total_shards = minimum_shards + extra_shards;
248
249 let data_len = usize::from(u.arbitrary::<u16>()?) % (MAX_DATA + 1);
250 let data = u.bytes(data_len)?.to_vec();
251
252 let selected_len = usize::from(minimum_shards)
253 + (usize::from(u.arbitrary::<u16>()?) % (usize::from(extra_shards) + 1));
254 let mut selected: Vec<u16> = (0..total_shards).collect();
255 for i in 0..selected_len {
256 let remaining = usize::from(total_shards) - i;
257 let j = i + (usize::from(u.arbitrary::<u16>()?) % remaining);
258 selected.swap(i, j);
259 }
260 selected.truncate(selected_len);
261
262 Ok((
263 Config {
264 minimum_shards: NZU16!(minimum_shards),
265 extra_shards: NZU16!(extra_shards),
266 },
267 data,
268 selected,
269 ))
270 }
271
272 mod scheme {
273 use super::*;
274 use crate::{Scheme, reed_solomon::ReedSolomon};
275 use commonware_codec::Encode;
276 use commonware_parallel::Sequential;
277
278 fn roundtrip<S: Scheme>(config: &Config, data: &[u8], selected: &[u16]) {
279 let (commitment, shards) = S::encode(config, data, &Sequential).unwrap();
280 let read_cfg = (*config, data.len().max(MAX_DATA));
281 for shard in &shards {
282 let decoded_shard = S::Shard::read_cfg(&mut shard.encode(), &read_cfg).unwrap();
283 assert_eq!(decoded_shard, *shard);
284 }
285
286 let mut checked_shards = Vec::new();
287 for (i, shard) in shards.into_iter().enumerate() {
288 if !selected.contains(&(i as u16)) {
289 continue;
290 }
291 let checked = S::check(config, &commitment, i as u16, &shard, &Sequential).unwrap();
292 checked_shards.push(checked);
293 }
294
295 checked_shards.reverse();
296 let decoded =
297 S::decode(config, &commitment, checked_shards.iter(), &Sequential).unwrap();
298 assert_eq!(decoded, data);
299 }
300
301 fn decode_rejects_mixed_commitments<S: Scheme>(
302 config: &Config,
303 data_a: &[u8],
304 data_b: &[u8],
305 ) {
306 let (commitment_a, shards_a) = S::encode(config, data_a, &Sequential).unwrap();
307 let (commitment_b, shards_b) = S::encode(config, data_b, &Sequential).unwrap();
308
309 let checked_a = S::check(config, &commitment_a, 0, &shards_a[0], &Sequential).unwrap();
310 let checked_b = S::check(config, &commitment_b, 1, &shards_b[1], &Sequential).unwrap();
311
312 let result = S::decode(
313 config,
314 &commitment_a,
315 [checked_a, checked_b].iter(),
316 &Sequential,
317 );
318 assert!(
319 result.is_err(),
320 "decode must reject shards checked against different commitments"
321 );
322 }
323
324 fn decode_rejects_empty_checked_shards<S: Scheme>(config: &Config, data: &[u8]) {
325 let (commitment, _) = S::encode(config, data, &Sequential).unwrap();
326 let result = S::decode(config, &commitment, core::iter::empty(), &Sequential);
327 assert!(
328 result.is_err(),
329 "decode must reject empty checked shard sets"
330 );
331 }
332
333 #[test]
334 fn decode_rejects_mixed_commitment_shards() {
335 let config = Config {
336 minimum_shards: NZU16!(2),
337 extra_shards: NZU16!(1),
338 };
339
340 decode_rejects_mixed_commitments::<ReedSolomon<Sha256>>(
341 &config,
342 b"alpha payload",
343 b"bravo payload",
344 );
345 decode_rejects_empty_checked_shards::<ReedSolomon<Sha256>>(&config, b"alpha payload");
346 }
347
348 #[test]
349 fn roundtrip_empty_data() {
350 let config = Config {
351 minimum_shards: NZU16!(30),
352 extra_shards: NZU16!(70),
353 };
354 let selected: Vec<u16> = (0..30).collect();
355
356 roundtrip::<ReedSolomon<Sha256>>(&config, b"", &selected);
357 }
358
359 #[test]
360 fn roundtrip_2_pow_16_25_total_shards() {
361 let config = Config {
362 minimum_shards: NZU16!(8),
363 extra_shards: NZU16!(17),
364 };
365 let data = vec![0x67; 1 << 16];
366 let selected: Vec<u16> = (0..8).collect();
367
368 roundtrip::<ReedSolomon<Sha256>>(&config, &data, &selected);
369 }
370
371 #[test]
372 fn minifuzz_roundtrip_reed_solomon() {
373 minifuzz::test(|u| {
374 let (config, data, selected) = generate_case(u)?;
375 roundtrip::<ReedSolomon<Sha256>>(&config, &data, &selected);
376 Ok(())
377 });
378 }
379 }
380
381 #[cfg(feature = "arbitrary")]
382 mod conformance {
383 use super::*;
384 use commonware_codec::conformance::CodecConformance;
385
386 commonware_conformance::conformance_tests! {
387 CodecConformance<Config>,
388 }
389 }
390}