vid/avid_m/
proofs.rs

1//! This module implements encoding proofs for the Avid-M Scheme.
2
3use std::{collections::HashSet, ops::Range};
4
5use jf_merkle_tree::MerkleTreeScheme;
6use jf_utils::canonical;
7use serde::{Deserialize, Serialize};
8
9use crate::{
10    avid_m::{
11        config::AvidMConfig,
12        namespaced::{NsAvidMCommit, NsAvidMScheme, NsAvidMShare},
13        AvidMCommit, AvidMParam, AvidMScheme, AvidMShare, Config, MerkleProof, MerkleTree, F,
14    },
15    VerificationResult, VidError, VidResult, VidScheme,
16};
17
18/// A proof of incorrect encoding.
19/// When the disperser is malicious, he can disperse an incorrectly encoded block, resulting in a merkle root of
20/// a Merkle tree containing invalid share (i.e. inconsistent with shares from correctly encoded block). Disperser
21/// would disperse them to all replicas with valid Merkle proof against this incorrect root, or else the replicas
22/// won't even vote if the merkle proof is wrong. By the time of reconstruction, replicas can come together with
23/// at least `threshold` shares to interpolate back the original block (in polynomial form), and by recomputing the
24/// corresponding encoded block on this recovered polynomial, we can derive another merkle root of encoded shares.
25/// If the merkle root matches the one dispersed earlier, then the encoding was correct.
26/// If not, this mismatch can serve as a proof of incorrect encoding.
27///
28/// In short, the proof contains the recovered poly (from the received shares) and the merkle proofs (against the wrong root)
29/// being distributed by the malicious disperser.
30#[derive(Clone, Debug, Eq, PartialEq, Hash, Serialize, Deserialize)]
31pub struct AvidMBadEncodingProof {
32    /// The recovered polynomial from VID shares.
33    #[serde(with = "canonical")]
34    recovered_poly: Vec<F>,
35    /// The Merkle proofs against the original commitment.
36    #[serde(with = "canonical")]
37    raw_shares: Vec<(usize, MerkleProof)>,
38}
39
40impl AvidMScheme {
41    /// Generate a proof of incorrect encoding
42    /// See [`MalEncodingProof`] for details.
43    pub fn proof_of_incorrect_encoding(
44        param: &AvidMParam,
45        commit: &AvidMCommit,
46        shares: &[AvidMShare],
47    ) -> VidResult<AvidMBadEncodingProof> {
48        // First filter out the invalid shares
49        let shares = shares
50            .iter()
51            .filter(|share| {
52                AvidMScheme::verify_share(param, commit, share).is_ok_and(|r| r.is_ok())
53            })
54            .cloned()
55            .collect::<Vec<_>>();
56        // Recover the original payload in fields representation.
57        // Length of `payload` is always a multiple of `recovery_threshold`.
58        let witness = Self::recover_fields(param, &shares)?;
59        let (mt, _) = Self::raw_encode(param, &witness)?;
60        if mt.commitment() == commit.commit {
61            return Err(VidError::Argument(
62                "Cannot generate the proof of incorrect encoding: encoding is good.".to_string(),
63            ));
64        }
65
66        let mut raw_shares = vec![];
67        let mut visited_indices = HashSet::new();
68        for share in shares {
69            for (index, mt_proof) in share
70                .content
71                .range
72                .clone()
73                .zip(share.content.mt_proofs.iter())
74            {
75                if index > param.total_weights {
76                    return Err(VidError::InvalidShare);
77                }
78                if visited_indices.contains(&index) {
79                    return Err(VidError::InvalidShare);
80                }
81                raw_shares.push((index, mt_proof.clone()));
82                visited_indices.insert(index);
83                if raw_shares.len() == param.recovery_threshold {
84                    break;
85                }
86            }
87            if raw_shares.len() == param.recovery_threshold {
88                break;
89            }
90        }
91        if raw_shares.len() != param.recovery_threshold {
92            return Err(VidError::InsufficientShares);
93        }
94
95        Ok(AvidMBadEncodingProof {
96            recovered_poly: witness,
97            raw_shares,
98        })
99    }
100}
101
102impl AvidMBadEncodingProof {
103    /// Verify a proof of incorrect encoding
104    pub fn verify(
105        &self,
106        param: &AvidMParam,
107        commit: &AvidMCommit,
108    ) -> VidResult<VerificationResult> {
109        // A bad encoding proof should have exactly `recovery_threshold` raw shares
110        if self.raw_shares.len() != param.recovery_threshold {
111            return Err(VidError::InvalidParam);
112        }
113        if self.recovered_poly.len() > param.recovery_threshold {
114            // recovered polynomial should be of low degree
115            return Err(VidError::InvalidParam);
116        }
117        let (mt, raw_shares) = AvidMScheme::raw_encode(param, &self.recovered_poly)?;
118        if mt.commitment() == commit.commit {
119            return Ok(Err(()));
120        }
121        let mut visited_indices = HashSet::new();
122        for (index, proof) in self.raw_shares.iter() {
123            if *index >= param.total_weights || visited_indices.contains(index) {
124                return Err(VidError::InvalidShare);
125            }
126            let digest = Config::raw_share_digest(&raw_shares[*index])?;
127            if MerkleTree::verify(&commit.commit, *index as u64, &digest, proof)?.is_err() {
128                return Ok(Err(()));
129            }
130            visited_indices.insert(*index);
131        }
132        Ok(Ok(()))
133    }
134}
135
136/// A proof of incorrect encoding for a namespace.
137/// It consists of the index of the namespace, the merkle proof of the namespace payload against the namespaced VID commitment,
138/// and the proof of incorrect encoding.
139#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
140pub struct NsAvidMBadEncodingProof {
141    /// The index of the namespace.
142    pub ns_index: usize,
143    /// The commitment of the namespaced VID.
144    pub ns_commit: AvidMCommit,
145    /// The outer merkle proof of the namespace against the namespaced VID commitment.
146    pub ns_mt_proof: MerkleProof,
147    /// The proof of incorrect encoding.
148    pub ns_proof: AvidMBadEncodingProof,
149}
150
151impl NsAvidMScheme {
152    /// Generate a proof of incorrect encoding for a namespace.
153    pub fn proof_of_incorrect_encoding_for_namespace(
154        param: &AvidMParam,
155        ns_index: usize,
156        commit: &NsAvidMCommit,
157        shares: &[NsAvidMShare],
158    ) -> VidResult<NsAvidMBadEncodingProof> {
159        if shares.is_empty() {
160            return Err(VidError::InsufficientShares);
161        }
162        if shares.iter().any(|share| !share.contains_ns(ns_index)) {
163            return Err(VidError::IndexOutOfBound);
164        }
165        let mt = MerkleTree::from_elems(
166            None,
167            shares[0].ns_commits().iter().map(|commit| commit.commit),
168        )?;
169        if mt.commitment() != commit.commit {
170            return Err(VidError::InvalidParam);
171        }
172        let (ns_commit, ns_mt_proof) = mt
173            .lookup(ns_index as u64)
174            .expect_ok()
175            .expect("MT lookup shouldn't fail");
176        let ns_commit = AvidMCommit { commit: *ns_commit };
177        let shares = shares
178            .iter()
179            .filter_map(|share| share.inner_ns_share(ns_index))
180            .collect::<Vec<_>>();
181        Ok(NsAvidMBadEncodingProof {
182            ns_index,
183            ns_commit,
184            ns_mt_proof,
185            ns_proof: AvidMScheme::proof_of_incorrect_encoding(param, &ns_commit, &shares)?,
186        })
187    }
188
189    /// Generate a proof of incorrect encoding.
190    pub fn proof_of_incorrect_encoding(
191        param: &AvidMParam,
192        commit: &NsAvidMCommit,
193        shares: &[NsAvidMShare],
194    ) -> VidResult<NsAvidMBadEncodingProof> {
195        if shares.is_empty() {
196            return Err(VidError::InsufficientShares);
197        }
198        for ns_index in 0..shares[0].ns_commits().len() {
199            let result =
200                Self::proof_of_incorrect_encoding_for_namespace(param, ns_index, commit, shares);
201            // Early break if there's a bad namespace, or if the shares/param are invalid
202            if matches!(
203                result,
204                Ok(_)
205                    | Err(VidError::InvalidShare)
206                    | Err(VidError::IndexOutOfBound)
207                    | Err(VidError::InsufficientShares)
208            ) {
209                return result;
210            }
211        }
212        Err(VidError::InvalidParam)
213    }
214}
215
216impl NsAvidMBadEncodingProof {
217    /// Verify an incorrect encoding proof.
218    pub fn verify(
219        &self,
220        param: &AvidMParam,
221        commit: &NsAvidMCommit,
222    ) -> VidResult<VerificationResult> {
223        if MerkleTree::verify(
224            &commit.commit,
225            self.ns_index as u64,
226            &self.ns_commit.commit,
227            &self.ns_mt_proof,
228        )?
229        .is_err()
230        {
231            return Ok(Err(()));
232        }
233        self.ns_proof.verify(param, &self.ns_commit)
234    }
235}
236
237/// A proof of a namespace payload.
238/// It consists of the index of the namespace, the namespace payload, and a merkle proof
239/// of the namespace payload against the namespaced VID commitment.
240#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
241pub struct NsProof {
242    /// The index of the namespace.
243    pub ns_index: usize,
244    /// The namespace payload.
245    #[serde(with = "base64_bytes")]
246    pub ns_payload: Vec<u8>,
247    /// The merkle proof of the namespace payload against the namespaced VID commitment.
248    pub ns_proof: MerkleProof,
249}
250
251impl NsAvidMScheme {
252    /// Generate a proof of inclusion for a namespace payload.
253    /// WARN: for the current implementation, no proof can be generated if any namespace is malformed.
254    pub fn namespace_proof(
255        param: &AvidMParam,
256        payload: &[u8],
257        ns_index: usize,
258        ns_table: impl IntoIterator<Item = Range<usize>>,
259    ) -> VidResult<NsProof> {
260        let ns_table = ns_table.into_iter().collect::<Vec<_>>();
261        let ns_payload_range = ns_table[ns_index].clone();
262        let ns_commits = ns_table
263            .into_iter()
264            .map(|ns_range| {
265                AvidMScheme::commit(param, &payload[ns_range]).map(|commit| commit.commit)
266            })
267            .collect::<Result<Vec<_>, _>>()?;
268        let mt = MerkleTree::from_elems(None, &ns_commits)?;
269        Ok(NsProof {
270            ns_index,
271            ns_payload: payload[ns_payload_range].to_vec(),
272            ns_proof: mt
273                .lookup(ns_index as u64)
274                .expect_ok()
275                .expect("MT lookup shouldn't fail")
276                .1,
277        })
278    }
279
280    /// Verify a namespace proof against a namespaced VID commitment.
281    pub fn verify_namespace_proof(
282        param: &AvidMParam,
283        commit: &NsAvidMCommit,
284        proof: &NsProof,
285    ) -> VidResult<VerificationResult> {
286        let ns_commit = AvidMScheme::commit(param, &proof.ns_payload)?;
287        Ok(MerkleTree::verify(
288            &commit.commit,
289            proof.ns_index as u64,
290            &ns_commit.commit,
291            &proof.ns_proof,
292        )?)
293    }
294}
295
296#[cfg(test)]
297mod tests {
298    use ark_poly::EvaluationDomain;
299    use jf_merkle_tree::MerkleTreeScheme;
300    use rand::{seq::SliceRandom, Rng};
301
302    use crate::{
303        avid_m::{
304            config::AvidMConfig,
305            namespaced::{NsAvidMCommit, NsAvidMScheme, NsAvidMShare},
306            proofs::AvidMBadEncodingProof,
307            radix2_domain, AvidMCommit, AvidMScheme, AvidMShare, Config, MerkleTree, RawAvidMShare,
308            F,
309        },
310        utils::bytes_to_field,
311        VidScheme,
312    };
313
314    #[test]
315    fn test_proof_of_incorrect_encoding() {
316        let mut rng = jf_utils::test_rng();
317        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
318        let weights = [1u32; 10];
319        let payload_byte_len = bytes_to_field::elem_byte_capacity::<F>() * 4;
320        let domain = radix2_domain::<F>(param.total_weights).unwrap();
321
322        let high_degree_polynomial = vec![F::from(1u64); 10];
323        let mal_payload: Vec<_> = domain
324            .fft(&high_degree_polynomial)
325            .into_iter()
326            .take(param.total_weights)
327            .map(|v| vec![v])
328            .collect();
329
330        let mt = MerkleTree::from_elems(
331            None,
332            mal_payload
333                .iter()
334                .map(|v| Config::raw_share_digest(v).unwrap()),
335        )
336        .unwrap();
337
338        let (commit, mut shares) =
339            AvidMScheme::distribute_shares(&param, &weights, mt, mal_payload, payload_byte_len)
340                .unwrap();
341
342        shares.shuffle(&mut rng);
343
344        // not enough shares
345        assert!(AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares[..1]).is_err());
346
347        // successful proof generation
348        let proof =
349            AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares[..5]).unwrap();
350        assert!(proof.verify(&param, &commit).unwrap().is_ok());
351
352        // proof generation shall not work on good commitment and shares
353        let payload = [1u8; 50];
354        let (commit, mut shares) = AvidMScheme::disperse(&param, &weights, &payload).unwrap();
355        shares.shuffle(&mut rng);
356        assert!(AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares).is_err());
357
358        let witness = AvidMScheme::pad_to_fields(&param, &payload);
359        let bad_proof = AvidMBadEncodingProof {
360            recovered_poly: witness.clone(),
361            raw_shares: shares
362                .iter()
363                .map(|share| (share.index as usize, share.content.mt_proofs[0].clone()))
364                .collect(),
365        };
366        assert!(bad_proof.verify(&param, &commit).is_err());
367
368        // duplicate indices may fool the verification
369        let mut bad_witness = vec![F::from(0u64); 5];
370        bad_witness[0] = shares[0].content.payload[0][0];
371        let bad_proof2 = AvidMBadEncodingProof {
372            recovered_poly: bad_witness,
373            raw_shares: std::iter::repeat_n(bad_proof.raw_shares[0].clone(), 6).collect(),
374        };
375        assert!(bad_proof2.verify(&param, &commit).is_err());
376    }
377
378    #[test]
379    fn test_ns_proof() {
380        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
381        let payload = vec![1u8; 100];
382        let ns_table = vec![(0..10), (10..21), (21..33), (33..48), (48..100)];
383        let commit = NsAvidMScheme::commit(&param, &payload, ns_table.clone()).unwrap();
384
385        for (i, _) in ns_table.iter().enumerate() {
386            let proof =
387                NsAvidMScheme::namespace_proof(&param, &payload, i, ns_table.clone()).unwrap();
388            assert!(
389                NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
390                    .unwrap()
391                    .is_ok()
392            );
393        }
394        let mut proof =
395            NsAvidMScheme::namespace_proof(&param, &payload, 1, ns_table.clone()).unwrap();
396        proof.ns_index = 0;
397        assert!(
398            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
399                .unwrap()
400                .is_err()
401        );
402        proof.ns_index = 1;
403        proof.ns_payload[0] = 0u8;
404        assert!(
405            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
406                .unwrap()
407                .is_err()
408        );
409        proof.ns_index = 100;
410        assert!(
411            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
412                .unwrap()
413                .is_err()
414        );
415    }
416
417    #[test]
418    fn test_ns_proof_of_incorrect_encoding() {
419        let mut rng = jf_utils::test_rng();
420        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
421        let mut payload = [1u8; 100];
422        rng.fill(&mut payload[..]);
423        let distribution = [1u32; 10];
424        let ns_table = [(0..10), (10..21), (21..33), (33..48), (48..100)];
425        let domain = radix2_domain::<F>(param.total_weights).unwrap();
426
427        // Manually distribute the payload, with second namespace being malicious
428        let mut ns_commits = vec![];
429        let mut disperses = vec![];
430        let mut ns_lens = vec![];
431        for ns_range in ns_table.iter() {
432            ns_lens.push(ns_range.len());
433            if ns_range.start == 10 {
434                // second namespace is malicious, commit to a high-degree polynomial
435                let high_degree_polynomial = vec![F::from(1u64); 10];
436                let mal_payload: Vec<_> = domain
437                    .fft(&high_degree_polynomial)
438                    .into_iter()
439                    .take(param.total_weights)
440                    .map(|v| vec![v])
441                    .collect();
442                let bad_mt = MerkleTree::from_elems(
443                    None,
444                    mal_payload
445                        .iter()
446                        .map(|v| Config::raw_share_digest(v).unwrap()),
447                )
448                .unwrap();
449                ns_commits.push(bad_mt.commitment());
450                let shares: Vec<_> = mal_payload
451                    .into_iter()
452                    .enumerate()
453                    .map(|(i, v)| AvidMShare {
454                        index: i as u32,
455                        payload_byte_len: ns_range.len(),
456                        content: RawAvidMShare {
457                            range: (i..i + 1),
458                            payload: vec![v],
459                            mt_proofs: vec![bad_mt.lookup(i as u64).expect_ok().unwrap().1],
460                        },
461                    })
462                    .collect();
463                disperses.push(shares);
464            } else {
465                let (commit, shares) =
466                    AvidMScheme::disperse(&param, &distribution, &payload[ns_range.clone()])
467                        .unwrap();
468                ns_commits.push(commit.commit);
469                disperses.push(shares);
470            }
471        }
472        let commit = NsAvidMCommit {
473            commit: MerkleTree::from_elems(None, &ns_commits)
474                .unwrap()
475                .commitment(),
476        };
477        let ns_commits: Vec<_> = ns_commits
478            .into_iter()
479            .map(|comm| AvidMCommit { commit: comm })
480            .collect();
481        let mut shares = vec![NsAvidMShare::default(); disperses[0].len()];
482        shares.iter_mut().for_each(|share| {
483            share.index = disperses[0][0].index;
484            share.ns_commits = ns_commits.clone();
485            share.ns_lens = ns_lens.clone();
486        });
487        disperses.into_iter().for_each(|ns_disperse| {
488            shares
489                .iter_mut()
490                .zip(ns_disperse)
491                .for_each(|(share, ns_share)| share.content.push(ns_share.content))
492        });
493
494        // generate bad encoding proof for the second namespace
495        let proof =
496            NsAvidMScheme::proof_of_incorrect_encoding_for_namespace(&param, 1, &commit, &shares)
497                .unwrap();
498        assert!(proof.verify(&param, &commit).unwrap().is_ok());
499
500        // Good namespaces
501        for ns_index in [0, 2, 3, 4] {
502            assert!(NsAvidMScheme::proof_of_incorrect_encoding_for_namespace(
503                &param, ns_index, &commit, &shares
504            )
505            .is_err());
506        }
507
508        let proof = NsAvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares).unwrap();
509        assert_eq!(proof.ns_index, 1);
510        assert!(proof.verify(&param, &commit).unwrap().is_ok());
511    }
512}
vid/avid_m/proofs.rs

vid/avid_m/
proofs.rs
