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    pub ns_payload: Vec<u8>,
246    /// The merkle proof of the namespace payload against the namespaced VID commitment.
247    pub ns_proof: MerkleProof,
248}
249
250impl NsAvidMScheme {
251    /// Generate a proof of inclusion for a namespace payload.
252    /// WARN: for the current implementation, no proof can be generated if any namespace is malformed.
253    pub fn namespace_proof(
254        param: &AvidMParam,
255        payload: &[u8],
256        ns_index: usize,
257        ns_table: impl IntoIterator<Item = Range<usize>>,
258    ) -> VidResult<NsProof> {
259        let ns_table = ns_table.into_iter().collect::<Vec<_>>();
260        let ns_payload_range = ns_table[ns_index].clone();
261        let ns_commits = ns_table
262            .into_iter()
263            .map(|ns_range| {
264                AvidMScheme::commit(param, &payload[ns_range]).map(|commit| commit.commit)
265            })
266            .collect::<Result<Vec<_>, _>>()?;
267        let mt = MerkleTree::from_elems(None, &ns_commits)?;
268        Ok(NsProof {
269            ns_index,
270            ns_payload: payload[ns_payload_range].to_vec(),
271            ns_proof: mt
272                .lookup(ns_index as u64)
273                .expect_ok()
274                .expect("MT lookup shouldn't fail")
275                .1,
276        })
277    }
278
279    /// Verify a namespace proof against a namespaced VID commitment.
280    pub fn verify_namespace_proof(
281        param: &AvidMParam,
282        commit: &NsAvidMCommit,
283        proof: &NsProof,
284    ) -> VidResult<VerificationResult> {
285        let ns_commit = AvidMScheme::commit(param, &proof.ns_payload)?;
286        Ok(MerkleTree::verify(
287            &commit.commit,
288            proof.ns_index as u64,
289            &ns_commit.commit,
290            &proof.ns_proof,
291        )?)
292    }
293}
294
295#[cfg(test)]
296mod tests {
297    use ark_poly::EvaluationDomain;
298    use jf_merkle_tree::MerkleTreeScheme;
299    use rand::{seq::SliceRandom, Rng};
300
301    use crate::{
302        avid_m::{
303            config::AvidMConfig,
304            namespaced::{NsAvidMCommit, NsAvidMScheme, NsAvidMShare},
305            proofs::AvidMBadEncodingProof,
306            radix2_domain, AvidMCommit, AvidMScheme, AvidMShare, Config, MerkleTree, RawAvidMShare,
307            F,
308        },
309        utils::bytes_to_field,
310        VidScheme,
311    };
312
313    #[test]
314    fn test_proof_of_incorrect_encoding() {
315        let mut rng = jf_utils::test_rng();
316        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
317        let weights = [1u32; 10];
318        let payload_byte_len = bytes_to_field::elem_byte_capacity::<F>() * 4;
319        let domain = radix2_domain::<F>(param.total_weights).unwrap();
320
321        let high_degree_polynomial = vec![F::from(1u64); 10];
322        let mal_payload: Vec<_> = domain
323            .fft(&high_degree_polynomial)
324            .into_iter()
325            .take(param.total_weights)
326            .map(|v| vec![v])
327            .collect();
328
329        let mt = MerkleTree::from_elems(
330            None,
331            mal_payload
332                .iter()
333                .map(|v| Config::raw_share_digest(v).unwrap()),
334        )
335        .unwrap();
336
337        let (commit, mut shares) =
338            AvidMScheme::distribute_shares(&param, &weights, mt, mal_payload, payload_byte_len)
339                .unwrap();
340
341        shares.shuffle(&mut rng);
342
343        // not enough shares
344        assert!(AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares[..1]).is_err());
345
346        // successful proof generation
347        let proof =
348            AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares[..5]).unwrap();
349        assert!(proof.verify(&param, &commit).unwrap().is_ok());
350
351        // proof generation shall not work on good commitment and shares
352        let payload = [1u8; 50];
353        let (commit, mut shares) = AvidMScheme::disperse(&param, &weights, &payload).unwrap();
354        shares.shuffle(&mut rng);
355        assert!(AvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares).is_err());
356
357        let witness = AvidMScheme::pad_to_fields(&param, &payload);
358        let bad_proof = AvidMBadEncodingProof {
359            recovered_poly: witness.clone(),
360            raw_shares: shares
361                .iter()
362                .map(|share| (share.index as usize, share.content.mt_proofs[0].clone()))
363                .collect(),
364        };
365        assert!(bad_proof.verify(&param, &commit).is_err());
366
367        // duplicate indices may fool the verification
368        let mut bad_witness = vec![F::from(0u64); 5];
369        bad_witness[0] = shares[0].content.payload[0][0];
370        let bad_proof2 = AvidMBadEncodingProof {
371            recovered_poly: bad_witness,
372            raw_shares: std::iter::repeat_n(bad_proof.raw_shares[0].clone(), 6).collect(),
373        };
374        assert!(bad_proof2.verify(&param, &commit).is_err());
375    }
376
377    #[test]
378    fn test_ns_proof() {
379        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
380        let payload = vec![1u8; 100];
381        let ns_table = vec![(0..10), (10..21), (21..33), (33..48), (48..100)];
382        let commit = NsAvidMScheme::commit(&param, &payload, ns_table.clone()).unwrap();
383
384        for (i, _) in ns_table.iter().enumerate() {
385            let proof =
386                NsAvidMScheme::namespace_proof(&param, &payload, i, ns_table.clone()).unwrap();
387            assert!(
388                NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
389                    .unwrap()
390                    .is_ok()
391            );
392        }
393        let mut proof =
394            NsAvidMScheme::namespace_proof(&param, &payload, 1, ns_table.clone()).unwrap();
395        proof.ns_index = 0;
396        assert!(
397            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
398                .unwrap()
399                .is_err()
400        );
401        proof.ns_index = 1;
402        proof.ns_payload[0] = 0u8;
403        assert!(
404            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
405                .unwrap()
406                .is_err()
407        );
408        proof.ns_index = 100;
409        assert!(
410            NsAvidMScheme::verify_namespace_proof(&param, &commit, &proof)
411                .unwrap()
412                .is_err()
413        );
414    }
415
416    #[test]
417    fn test_ns_proof_of_incorrect_encoding() {
418        let mut rng = jf_utils::test_rng();
419        let param = AvidMScheme::setup(5usize, 10usize).unwrap();
420        let mut payload = [1u8; 100];
421        rng.fill(&mut payload[..]);
422        let distribution = [1u32; 10];
423        let ns_table = [(0..10), (10..21), (21..33), (33..48), (48..100)];
424        let domain = radix2_domain::<F>(param.total_weights).unwrap();
425
426        // Manually distribute the payload, with second namespace being malicious
427        let mut ns_commits = vec![];
428        let mut disperses = vec![];
429        let mut ns_lens = vec![];
430        for ns_range in ns_table.iter() {
431            ns_lens.push(ns_range.len());
432            if ns_range.start == 10 {
433                // second namespace is malicious, commit to a high-degree polynomial
434                let high_degree_polynomial = vec![F::from(1u64); 10];
435                let mal_payload: Vec<_> = domain
436                    .fft(&high_degree_polynomial)
437                    .into_iter()
438                    .take(param.total_weights)
439                    .map(|v| vec![v])
440                    .collect();
441                let bad_mt = MerkleTree::from_elems(
442                    None,
443                    mal_payload
444                        .iter()
445                        .map(|v| Config::raw_share_digest(v).unwrap()),
446                )
447                .unwrap();
448                ns_commits.push(bad_mt.commitment());
449                let shares: Vec<_> = mal_payload
450                    .into_iter()
451                    .enumerate()
452                    .map(|(i, v)| AvidMShare {
453                        index: i as u32,
454                        payload_byte_len: ns_range.len(),
455                        content: RawAvidMShare {
456                            range: (i..i + 1),
457                            payload: vec![v],
458                            mt_proofs: vec![bad_mt.lookup(i as u64).expect_ok().unwrap().1],
459                        },
460                    })
461                    .collect();
462                disperses.push(shares);
463            } else {
464                let (commit, shares) =
465                    AvidMScheme::disperse(&param, &distribution, &payload[ns_range.clone()])
466                        .unwrap();
467                ns_commits.push(commit.commit);
468                disperses.push(shares);
469            }
470        }
471        let commit = NsAvidMCommit {
472            commit: MerkleTree::from_elems(None, &ns_commits)
473                .unwrap()
474                .commitment(),
475        };
476        let ns_commits: Vec<_> = ns_commits
477            .into_iter()
478            .map(|comm| AvidMCommit { commit: comm })
479            .collect();
480        let mut shares = vec![NsAvidMShare::default(); disperses[0].len()];
481        shares.iter_mut().for_each(|share| {
482            share.index = disperses[0][0].index;
483            share.ns_commits = ns_commits.clone();
484            share.ns_lens = ns_lens.clone();
485        });
486        disperses.into_iter().for_each(|ns_disperse| {
487            shares
488                .iter_mut()
489                .zip(ns_disperse)
490                .for_each(|(share, ns_share)| share.content.push(ns_share.content))
491        });
492
493        // generate bad encoding proof for the second namespace
494        let proof =
495            NsAvidMScheme::proof_of_incorrect_encoding_for_namespace(&param, 1, &commit, &shares)
496                .unwrap();
497        assert!(proof.verify(&param, &commit).unwrap().is_ok());
498
499        // Good namespaces
500        for ns_index in [0, 2, 3, 4] {
501            assert!(NsAvidMScheme::proof_of_incorrect_encoding_for_namespace(
502                &param, ns_index, &commit, &shares
503            )
504            .is_err());
505        }
506
507        let proof = NsAvidMScheme::proof_of_incorrect_encoding(&param, &commit, &shares).unwrap();
508        assert_eq!(proof.ns_index, 1);
509        assert!(proof.verify(&param, &commit).unwrap().is_ok());
510    }
511}
vid/avid_m/proofs.rs

vid/avid_m/
proofs.rs
