vid/avidm/
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    VerificationResult, VidError, VidResult, VidScheme,
11    avidm::{
12        AvidMCommit, AvidMParam, AvidMScheme, AvidMShare, Config, F, MerkleProof, MerkleTree,
13        config::AvidMConfig,
14        namespaced::{NsAvidMCommit, NsAvidMScheme, NsAvidMShare},
15    },
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        param.validate()?;
110        // A bad encoding proof should have exactly `recovery_threshold` raw shares
111        if self.raw_shares.len() != param.recovery_threshold {
112            return Err(VidError::InvalidParam);
113        }
114        if self.recovered_poly.len() > param.recovery_threshold {
115            // recovered polynomial should be of low degree
116            return Err(VidError::InvalidParam);
117        }
118        let (mt, raw_shares) = AvidMScheme::raw_encode(param, &self.recovered_poly)?;
119        if mt.commitment() == commit.commit {
120            return Ok(Err(()));
121        }
122        let mut visited_indices = HashSet::new();
123        for (index, proof) in self.raw_shares.iter() {
124            if *index >= param.total_weights || visited_indices.contains(index) {
125                return Err(VidError::InvalidShare);
126            }
127            let digest = Config::raw_share_digest(&raw_shares[*index])?;
128            if MerkleTree::verify(&commit.commit, *index as u64, &digest, proof)?.is_err() {
129                return Ok(Err(()));
130            }
131            visited_indices.insert(*index);
132        }
133        Ok(Ok(()))
134    }
135}
136
137/// A proof of incorrect encoding for a namespace.
138/// It consists of the index of the namespace, the merkle proof of the namespace payload against the namespaced VID commitment,
139/// and the proof of incorrect encoding.
140#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
141pub struct NsAvidMBadEncodingProof {
142    /// The index of the namespace.
143    pub ns_index: usize,
144    /// The commitment of the namespaced VID.
145    pub ns_commit: AvidMCommit,
146    /// The outer merkle proof of the namespace against the namespaced VID commitment.
147    pub ns_mt_proof: MerkleProof,
148    /// The proof of incorrect encoding.
149    pub ns_proof: AvidMBadEncodingProof,
150}
151
152impl NsAvidMScheme {
153    /// Generate a proof of incorrect encoding for a namespace.
154    pub fn proof_of_incorrect_encoding_for_namespace(
155        param: &AvidMParam,
156        ns_index: usize,
157        commit: &NsAvidMCommit,
158        shares: &[NsAvidMShare],
159    ) -> VidResult<NsAvidMBadEncodingProof> {
160        if shares.is_empty() {
161            return Err(VidError::InsufficientShares);
162        }
163        if shares.iter().any(|share| !share.contains_ns(ns_index)) {
164            return Err(VidError::IndexOutOfBound);
165        }
166        let mt = MerkleTree::from_elems(
167            None,
168            shares[0].ns_commits().iter().map(|commit| commit.commit),
169        )?;
170        if mt.commitment() != commit.commit {
171            return Err(VidError::InvalidParam);
172        }
173        let (ns_commit, ns_mt_proof) = mt
174            .lookup(ns_index as u64)
175            .expect_ok()
176            .expect("MT lookup shouldn't fail");
177        let ns_commit = AvidMCommit { commit: *ns_commit };
178        let shares = shares
179            .iter()
180            .filter_map(|share| share.inner_ns_share(ns_index))
181            .collect::<Vec<_>>();
182        Ok(NsAvidMBadEncodingProof {
183            ns_index,
184            ns_commit,
185            ns_mt_proof,
186            ns_proof: AvidMScheme::proof_of_incorrect_encoding(param, &ns_commit, &shares)?,
187        })
188    }
189
190    /// Generate a proof of incorrect encoding.
191    pub fn proof_of_incorrect_encoding(
192        param: &AvidMParam,
193        commit: &NsAvidMCommit,
194        shares: &[NsAvidMShare],
195    ) -> VidResult<NsAvidMBadEncodingProof> {
196        if shares.is_empty() {
197            return Err(VidError::InsufficientShares);
198        }
199        for ns_index in 0..shares[0].ns_commits().len() {
200            let result =
201                Self::proof_of_incorrect_encoding_for_namespace(param, ns_index, commit, shares);
202            // Early break if there's a bad namespace, or if the shares/param are invalid
203            if matches!(
204                result,
205                Ok(_)
206                    | Err(VidError::InvalidShare)
207                    | Err(VidError::IndexOutOfBound)
208                    | Err(VidError::InsufficientShares)
209            ) {
210                return result;
211            }
212        }
213        Err(VidError::InvalidParam)
214    }
215}
216
217impl NsAvidMBadEncodingProof {
218    /// Verify an incorrect encoding proof.
219    pub fn verify(
220        &self,
221        param: &AvidMParam,
222        commit: &NsAvidMCommit,
223    ) -> VidResult<VerificationResult> {
224        if MerkleTree::verify(
225            &commit.commit,
226            self.ns_index as u64,
227            &self.ns_commit.commit,
228            &self.ns_mt_proof,
229        )?
230        .is_err()
231        {
232            return Ok(Err(()));
233        }
234        self.ns_proof.verify(param, &self.ns_commit)
235    }
236}
237
238/// A proof of a namespace payload.
239/// It consists of the index of the namespace, the namespace payload, and a merkle proof
240/// of the namespace payload against the namespaced VID commitment.
241#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
242pub struct NsProof {
243    /// The index of the namespace.
244    pub ns_index: usize,
245    /// The namespace payload.
246    #[serde(with = "base64_bytes")]
247    pub ns_payload: Vec<u8>,
248    /// The merkle proof of the namespace payload against the namespaced VID commitment.
249    pub ns_proof: MerkleProof,
250}
251
252impl NsAvidMScheme {
253    /// Generate a proof of inclusion for a namespace payload.
254    /// WARN: for the current implementation, no proof can be generated if any namespace is malformed.
255    pub fn namespace_proof(
256        param: &AvidMParam,
257        payload: &[u8],
258        ns_index: usize,
259        ns_table: impl IntoIterator<Item = Range<usize>>,
260    ) -> VidResult<NsProof> {
261        let ns_table = ns_table.into_iter().collect::<Vec<_>>();
262        let ns_payload_range = ns_table[ns_index].clone();
263        let ns_commits = ns_table
264            .into_iter()
265            .map(|ns_range| {
266                AvidMScheme::commit(param, &payload[ns_range]).map(|commit| commit.commit)
267            })
268            .collect::<Result<Vec<_>, _>>()?;
269        let mt = MerkleTree::from_elems(None, &ns_commits)?;
270        Ok(NsProof {
271            ns_index,
272            ns_payload: payload[ns_payload_range].to_vec(),
273            ns_proof: mt
274                .lookup(ns_index as u64)
275                .expect_ok()
276                .expect("MT lookup shouldn't fail")
277                .1,
278        })
279    }
280
281    /// Verify a namespace proof against a namespaced VID commitment.
282    pub fn verify_namespace_proof(
283        param: &AvidMParam,
284        commit: &NsAvidMCommit,
285        proof: &NsProof,
286    ) -> VidResult<VerificationResult> {
287        let ns_commit = AvidMScheme::commit(param, &proof.ns_payload)?;
288        Ok(MerkleTree::verify(
289            &commit.commit,
290            proof.ns_index as u64,
291            &ns_commit.commit,
292            &proof.ns_proof,
293        )?)
294    }
295}
296
297#[cfg(test)]
298mod tests {
299    use ark_poly::EvaluationDomain;
300    use jf_merkle_tree::MerkleTreeScheme;
301    use rand::{Rng, seq::SliceRandom};
302
303    use crate::{
304        VidError, VidScheme,
305        avidm::{
306            AvidMCommit, AvidMParam, AvidMScheme, AvidMShare, Config, F, MerkleTree, RawAvidMShare,
307            config::AvidMConfig,
308            namespaced::{NsAvidMCommit, NsAvidMScheme, NsAvidMShare},
309            proofs::AvidMBadEncodingProof,
310            radix2_domain,
311        },
312        utils::bytes_to_field,
313    };
314
315    #[test]
316    fn test_proof_of_incorrect_encoding() {
317        let mut rng = jf_utils::test_rng();
318        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
319        let weights = [1u32; 10];
320        let payload_byte_len = bytes_to_field::elem_byte_capacity::<F>() * 4;
321        let domain = radix2_domain::<F>(param.total_weights).unwrap();
322
323        let high_degree_polynomial = vec![F::from(1u64); 10];
324        let mal_payload: Vec<_> = domain
325            .fft(&high_degree_polynomial)
326            .into_iter()
327            .take(param.total_weights)
328            .map(|v| vec![v])
329            .collect();
330
331        let mt = MerkleTree::from_elems(
332            None,
333            mal_payload
334                .iter()
335                .map(|v| Config::raw_share_digest(v).unwrap()),
336        )
337        .unwrap();
338
339        let (commit, mut shares) =
340            AvidMScheme::distribute_shares(&param, &weights, mt, mal_payload, payload_byte_len)
341                .unwrap();
342
343        shares.shuffle(&mut rng);
344
345        // not enough shares
346        assert!(AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares[..1]).is_err());
347
348        // successful proof generation
349        let proof =
350            AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares[..5]).unwrap();
351        assert!(proof.verify(&param, &commit).unwrap().is_ok());
352
353        // proof generation shall not work on good commitment and shares
354        let payload = [1u8; 50];
355        let (commit, mut shares) = AvidMScheme::disperse(&param, &weights, &payload).unwrap();
356        shares.shuffle(&mut rng);
357        assert!(AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares).is_err());
358
359        let witness = AvidMScheme::pad_to_fields(&param, &payload);
360        let bad_proof = AvidMBadEncodingProof {
361            recovered_poly: witness.clone(),
362            raw_shares: shares
363                .iter()
364                .map(|share| (share.index as usize, share.content.mt_proofs[0].clone()))
365                .collect(),
366        };
367        assert!(bad_proof.verify(&param, &commit).is_err());
368
369        // duplicate indices may fool the verification
370        let mut bad_witness = vec![F::from(0u64); 5];
371        bad_witness[0] = shares[0].content.payload[0][0];
372        let bad_proof2 = AvidMBadEncodingProof {
373            recovered_poly: bad_witness,
374            raw_shares: std::iter::repeat_n(bad_proof.raw_shares[0].clone(), 6).collect(),
375        };
376        assert!(bad_proof2.verify(&param, &commit).is_err());
377    }
378
379    #[test]
380    fn test_ns_proof() {
381        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
382        let payload = vec![1u8; 100];
383        let ns_table = vec![(0..10), (10..21), (21..33), (33..48), (48..100)];
384        let commit = NsAvidMScheme::commit(&param, &payload, ns_table.clone()).unwrap();
385
386        for (i, _) in ns_table.iter().enumerate() {
387            let proof =
388                NsAvidMScheme::namespace_proof(&param, &payload, i, ns_table.clone()).unwrap();
389            assert!(
390                NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
391                    .unwrap()
392                    .is_ok()
393            );
394        }
395        let mut proof =
396            NsAvidMScheme::namespace_proof(&param, &payload, 1, ns_table.clone()).unwrap();
397        proof.ns_index = 0;
398        assert!(
399            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
400                .unwrap()
401                .is_err()
402        );
403        proof.ns_index = 1;
404        proof.ns_payload[0] = 0u8;
405        assert!(
406            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
407                .unwrap()
408                .is_err()
409        );
410        proof.ns_index = 100;
411        assert!(
412            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
413                .unwrap()
414                .is_err()
415        );
416    }
417
418    #[test]
419    fn test_ns_proof_of_incorrect_encoding() {
420        let mut rng = jf_utils::test_rng();
421        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
422        let mut payload = [1u8; 100];
423        rng.fill(&mut payload[..]);
424        let distribution = [1u32; 10];
425        let ns_table = [(0..10), (10..21), (21..33), (33..48), (48..100)];
426        let domain = radix2_domain::<F>(param.total_weights).unwrap();
427
428        // Manually distribute the payload, with second namespace being malicious
429        let mut ns_commits = vec![];
430        let mut disperses = vec![];
431        let mut ns_lens = vec![];
432        for ns_range in ns_table.iter() {
433            ns_lens.push(ns_range.len());
434            if ns_range.start == 10 {
435                // second namespace is malicious, commit to a high-degree polynomial
436                let high_degree_polynomial = vec![F::from(1u64); 10];
437                let mal_payload: Vec<_> = domain
438                    .fft(&high_degree_polynomial)
439                    .into_iter()
440                    .take(param.total_weights)
441                    .map(|v| vec![v])
442                    .collect();
443                let bad_mt = MerkleTree::from_elems(
444                    None,
445                    mal_payload
446                        .iter()
447                        .map(|v| Config::raw_share_digest(v).unwrap()),
448                )
449                .unwrap();
450                ns_commits.push(bad_mt.commitment());
451                let shares: Vec<_> = mal_payload
452                    .into_iter()
453                    .enumerate()
454                    .map(|(i, v)| AvidMShare {
455                        index: i as u32,
456                        payload_byte_len: ns_range.len(),
457                        content: RawAvidMShare {
458                            range: (i..i + 1),
459                            payload: vec![v],
460                            mt_proofs: vec![bad_mt.lookup(i as u64).expect_ok().unwrap().1],
461                        },
462                    })
463                    .collect();
464                disperses.push(shares);
465            } else {
466                let (commit, shares) =
467                    AvidMScheme::disperse(&param, &distribution, &payload[ns_range.clone()])
468                        .unwrap();
469                ns_commits.push(commit.commit);
470                disperses.push(shares);
471            }
472        }
473        let commit = NsAvidMCommit {
474            commit: MerkleTree::from_elems(None, &ns_commits)
475                .unwrap()
476                .commitment(),
477        };
478        let ns_commits: Vec<_> = ns_commits
479            .into_iter()
480            .map(|comm| AvidMCommit { commit: comm })
481            .collect();
482        let mut shares = vec![NsAvidMShare::default(); disperses[0].len()];
483        shares.iter_mut().for_each(|share| {
484            share.index = disperses[0][0].index;
485            share.ns_commits = ns_commits.clone();
486            share.ns_lens = ns_lens.clone();
487        });
488        disperses.into_iter().for_each(|ns_disperse| {
489            shares
490                .iter_mut()
491                .zip(ns_disperse)
492                .for_each(|(share, ns_share)| share.content.push(ns_share.content))
493        });
494
495        // generate bad encoding proof for the second namespace
496        let proof =
497            NsAvidMScheme::proof_of_incorrect_encoding_for_namespace(&param, 1, &commit, &shares)
498                .unwrap();
499        assert!(proof.verify(&param, &commit).unwrap().is_ok());
500
501        // Good namespaces
502        for ns_index in [0, 2, 3, 4] {
503            assert!(
504                NsAvidMScheme::proof_of_incorrect_encoding_for_namespace(
505                    &param, ns_index, &commit, &shares
506                )
507                .is_err()
508            );
509        }
510
511        let proof = NsAvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares).unwrap();
512        assert_eq!(proof.ns_index, 1);
513        assert!(proof.verify(&param, &commit).unwrap().is_ok());
514    }
515
516    #[test]
517    fn test_bad_encoding_proof_rejects_boundary_index() {
518        // Regression test: proof_of_incorrect_encoding must reject shares with
519        // index == total_weights (off-by-one, previously used `>` instead of `>=`).
520        let param = AvidMScheme::setup(3usize, 6usize).unwrap();
521        let payload = [1u8; 50];
522        let weights = [1u32; 6];
523        let (commit, shares) = AvidMScheme::disperse(&param, &weights, &payload).unwrap();
524
525        // Construct a share whose range.end == total_weights (last valid share).
526        // This should succeed since range 5..6 means index 5 which is < 6.
527        let last_share = &shares[5];
528        assert_eq!(last_share.content.range.end, param.total_weights);
529        assert!(
530            AvidMScheme::verify_internal(&param, &commit, &last_share.content)
531                .is_ok_and(|r| r.is_ok())
532        );
533
534        // Construct a fake share with range.end > total_weights. This must be rejected.
535        let mut bad_share = shares[5].clone();
536        bad_share.content.range = param.total_weights..param.total_weights + 1;
537        assert!(
538            AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &[bad_share]).is_err(),
539            "proof_of_incorrect_encoding must reject share with index >= total_weights"
540        );
541    }
542
543    #[test]
544    fn bad_encoding_proof_rejects_zero_threshold() {
545        let forged = AvidMParam {
546            total_weights: 4,
547            recovery_threshold: 0,
548        };
549        // Must stay empty, the shape checks also return InvalidParam.
550        let proof = AvidMBadEncodingProof {
551            recovered_poly: vec![],
552            raw_shares: vec![],
553        };
554        assert!(matches!(
555            proof.verify(&forged, &AvidMCommit::default()),
556            Err(VidError::InvalidParam)
557        ));
558    }
559}
vid/avidm/proofs.rs

vid/avidm/
proofs.rs
