vid/avid_m/
namespaced.rs

1//! This file implements the namespaced AvidM scheme.
2
3use std::ops::Range;
4
5use jf_merkle_tree::MerkleTreeScheme;
6use serde::{Deserialize, Serialize};
7
8use super::{AvidMCommit, AvidMShare, RawAvidMShare};
9use crate::{
10    avid_m::{AvidMScheme, MerkleTree},
11    VidError, VidResult, VidScheme,
12};
13
14/// Dummy struct for namespaced AvidM scheme
15pub struct NsAvidMScheme;
16
17/// Namespaced commitment type
18pub type NsAvidMCommit = super::AvidMCommit;
19/// Namespaced parameter type
20pub type NsAvidMParam = super::AvidMParam;
21
22/// Namespaced share for each storage node
23#[derive(Clone, Debug, Hash, Serialize, Deserialize, Eq, PartialEq, Default)]
24pub struct NsAvidMShare {
25    /// Index number of the given share.
26    pub(crate) index: u32,
27    /// The list of all namespace commitments
28    pub(crate) ns_commits: Vec<AvidMCommit>,
29    /// The size of each namespace
30    pub(crate) ns_lens: Vec<usize>,
31    /// Actual share content
32    pub(crate) content: Vec<RawAvidMShare>,
33}
34
35impl NsAvidMShare {
36    /// Return the number of namespaces.
37    /// WARN: it assume that the share is well formed, i.e. `ns_commits`, `ns_lens`, and `content` have the same length.
38    pub fn num_nss(&self) -> usize {
39        self.ns_commits.len()
40    }
41
42    /// Return the inner share for a given namespace if there exists one.
43    pub fn inner_ns_share(&self, ns_index: usize) -> Option<AvidMShare> {
44        if ns_index >= self.ns_lens.len() || ns_index >= self.content.len() {
45            return None;
46        }
47        Some(AvidMShare {
48            index: self.index,
49            payload_byte_len: self.ns_lens[ns_index],
50            content: self.content[ns_index].clone(),
51        })
52    }
53
54    /// Return the length of underlying payload in bytes
55    pub fn payload_byte_len(&self) -> usize {
56        self.ns_lens.iter().sum()
57    }
58
59    /// Peek if the share contains a given namespace.
60    pub fn contains_ns(&self, ns_index: usize) -> bool {
61        self.ns_commits.len() > ns_index
62            && self.ns_lens.len() > ns_index
63            && self.content.len() > ns_index
64    }
65
66    /// Return the list of namespace commitments.
67    pub fn ns_commits(&self) -> &[AvidMCommit] {
68        &self.ns_commits
69    }
70
71    /// Return the list of namespace byte lengths.
72    pub fn ns_lens(&self) -> &[usize] {
73        &self.ns_lens
74    }
75
76    /// Return the commitment for a given namespace.
77    /// WARN: will panic if `ns_index` is out of bound.
78    pub fn ns_commit(&self, ns_index: usize) -> &AvidMCommit {
79        &self.ns_commits[ns_index]
80    }
81
82    /// Return the byte length of a given namespace.
83    /// WARN: will panic if `ns_index` is out of bound.
84    pub fn ns_len(&self, ns_index: usize) -> usize {
85        self.ns_lens[ns_index]
86    }
87}
88
89impl NsAvidMScheme {
90    /// Setup an instance for AVID-M scheme
91    pub fn setup(recovery_threshold: usize, total_weights: usize) -> VidResult<NsAvidMParam> {
92        NsAvidMParam::new(recovery_threshold, total_weights)
93    }
94
95    /// Commit to a payload given namespace table.
96    /// WARN: it assumes that the namespace table is well formed, i.e. ranges
97    /// are non-overlapping and cover the whole payload.
98    pub fn commit(
99        param: &NsAvidMParam,
100        payload: &[u8],
101        ns_table: impl IntoIterator<Item = Range<usize>>,
102    ) -> VidResult<NsAvidMCommit> {
103        let ns_commits = ns_table
104            .into_iter()
105            .map(|ns_range| {
106                AvidMScheme::commit(param, &payload[ns_range]).map(|commit| commit.commit)
107            })
108            .collect::<Result<Vec<_>, _>>()?;
109        Ok(NsAvidMCommit {
110            commit: MerkleTree::from_elems(None, &ns_commits)
111                .map_err(|err| VidError::Internal(err.into()))?
112                .commitment(),
113        })
114    }
115
116    /// Disperse a payload according to a distribution table and a namespace
117    /// table.
118    /// WARN: it assumes that the namespace table is well formed, i.e. ranges
119    /// are non-overlapping and cover the whole payload.
120    pub fn ns_disperse(
121        param: &NsAvidMParam,
122        distribution: &[u32],
123        payload: &[u8],
124        ns_table: impl IntoIterator<Item = Range<usize>>,
125    ) -> VidResult<(NsAvidMCommit, Vec<NsAvidMShare>)> {
126        let mut ns_commits = vec![];
127        let mut disperses = vec![];
128        let mut ns_lens = vec![];
129        for ns_range in ns_table {
130            ns_lens.push(ns_range.len());
131            let (commit, shares) = AvidMScheme::disperse(param, distribution, &payload[ns_range])?;
132            ns_commits.push(commit.commit);
133            disperses.push(shares);
134        }
135        let commit = NsAvidMCommit {
136            commit: MerkleTree::from_elems(None, &ns_commits)
137                .map_err(|err| VidError::Internal(err.into()))?
138                .commitment(),
139        };
140        let ns_commits: Vec<_> = ns_commits
141            .into_iter()
142            .map(|comm| AvidMCommit { commit: comm })
143            .collect();
144        let mut shares = vec![NsAvidMShare::default(); disperses[0].len()];
145        shares.iter_mut().for_each(|share| {
146            share.index = disperses[0][0].index;
147            share.ns_commits = ns_commits.clone();
148            share.ns_lens = ns_lens.clone();
149        });
150        disperses.into_iter().for_each(|ns_disperse| {
151            shares
152                .iter_mut()
153                .zip(ns_disperse)
154                .for_each(|(share, ns_share)| share.content.push(ns_share.content))
155        });
156        Ok((commit, shares))
157    }
158
159    /// Verify a namespaced share
160    pub fn verify_share(
161        param: &NsAvidMParam,
162        commit: &NsAvidMCommit,
163        share: &NsAvidMShare,
164    ) -> VidResult<crate::VerificationResult> {
165        if !(share.ns_commits.len() == share.ns_lens.len()
166            && share.ns_commits.len() == share.content.len())
167        {
168            return Err(VidError::InvalidShare);
169        }
170        // Verify the share for each namespace
171        for (commit, content) in share.ns_commits.iter().zip(share.content.iter()) {
172            if AvidMScheme::verify_internal(param, commit, content)?.is_err() {
173                return Ok(Err(()));
174            }
175        }
176        // Verify the namespace MT commitment
177        let expected_commit = NsAvidMCommit {
178            commit: MerkleTree::from_elems(
179                None,
180                share.ns_commits.iter().map(|commit| commit.commit),
181            )
182            .map_err(|err| VidError::Internal(err.into()))?
183            .commitment(),
184        };
185        Ok(if &expected_commit == commit {
186            Ok(())
187        } else {
188            Err(())
189        })
190    }
191
192    /// Recover the entire payload from enough share
193    pub fn recover(param: &NsAvidMParam, shares: &[NsAvidMShare]) -> VidResult<Vec<u8>> {
194        if shares.is_empty() {
195            return Err(VidError::InsufficientShares);
196        }
197        let mut result = vec![];
198        for ns_index in 0..shares[0].ns_lens.len() {
199            result.append(&mut Self::ns_recover(param, ns_index, shares)?)
200        }
201        Ok(result)
202    }
203
204    /// Recover the payload for a given namespace.
205    /// Given namespace ID should be valid for all shares, i.e. `ns_commits` and `content` have
206    /// at least `ns_index` elements for all shares.
207    pub fn ns_recover(
208        param: &NsAvidMParam,
209        ns_index: usize,
210        shares: &[NsAvidMShare],
211    ) -> VidResult<Vec<u8>> {
212        if shares.is_empty() {
213            return Err(VidError::InsufficientShares);
214        }
215        if shares
216            .iter()
217            .any(|share| ns_index >= share.ns_lens.len() || ns_index >= share.content.len())
218        {
219            return Err(VidError::IndexOutOfBound);
220        }
221        let ns_commit = shares[0].ns_commits[ns_index];
222        let shares: Vec<_> = shares
223            .iter()
224            .filter_map(|share| share.inner_ns_share(ns_index))
225            .collect();
226        AvidMScheme::recover(param, &ns_commit, &shares)
227    }
228}
229
230/// Unit tests
231#[cfg(test)]
232pub mod tests {
233    use rand::{seq::SliceRandom, RngCore};
234
235    use crate::avid_m::namespaced::NsAvidMScheme;
236
237    #[test]
238    fn round_trip() {
239        // play with these items
240        let num_storage_nodes = 9;
241        let recovery_threshold = 3;
242        let ns_lens = [15, 33];
243        let ns_table = [(0usize..15), (15..48)];
244        let payload_byte_len = ns_lens.iter().sum();
245
246        // more items as a function of the above
247
248        let mut rng = jf_utils::test_rng();
249
250        let weights: Vec<u32> = (0..num_storage_nodes)
251            .map(|_| rng.next_u32() % 5 + 1)
252            .collect();
253        let total_weights: u32 = weights.iter().sum();
254        let params = NsAvidMScheme::setup(recovery_threshold, total_weights as usize).unwrap();
255
256        println!(
257            "recovery_threshold:: {recovery_threshold} num_storage_nodes: {num_storage_nodes} payload_byte_len: {payload_byte_len}"
258        );
259        println!("weights: {weights:?}");
260
261        let payload = {
262            let mut bytes_random = vec![0u8; payload_byte_len];
263            rng.fill_bytes(&mut bytes_random);
264            bytes_random
265        };
266
267        let (commit, mut shares) =
268            NsAvidMScheme::ns_disperse(&params, &weights, &payload, ns_table.iter().cloned())
269                .unwrap();
270
271        assert_eq!(shares.len(), num_storage_nodes);
272
273        assert_eq!(
274            commit,
275            NsAvidMScheme::commit(&params, &payload, ns_table.iter().cloned()).unwrap()
276        );
277
278        // verify shares
279        shares.iter().for_each(|share| {
280            assert!(NsAvidMScheme::verify_share(&params, &commit, share).is_ok_and(|r| r.is_ok()))
281        });
282
283        // test payload recovery on a random subset of shares
284        shares.shuffle(&mut rng);
285        let mut cumulated_weights = 0;
286        let mut cut_index = 0;
287        while cumulated_weights <= recovery_threshold {
288            cumulated_weights += shares[cut_index].content[0].range.len();
289            cut_index += 1;
290        }
291        let ns0_payload_recovered =
292            NsAvidMScheme::ns_recover(&params, 0, &shares[..cut_index]).unwrap();
293        assert_eq!(ns0_payload_recovered[..], payload[ns_table[0].clone()]);
294        let ns1_payload_recovered =
295            NsAvidMScheme::ns_recover(&params, 1, &shares[..cut_index]).unwrap();
296        assert_eq!(ns1_payload_recovered[..], payload[ns_table[1].clone()]);
297        let payload_recovered = NsAvidMScheme::recover(&params, &shares[..cut_index]).unwrap();
298        assert_eq!(payload_recovered, payload);
299    }
300}
vid/avid_m/namespaced.rs

vid/avid_m/
namespaced.rs
