vid/avidm_gf2/
proofs.rs

1//! This module implements encoding proofs for the Avid-M Scheme.
2
3use jf_merkle_tree::MerkleTreeScheme;
4use serde::{Deserialize, Serialize};
5
6use crate::{
7    avidm_gf2::{
8        namespaced::{NsAvidmGf2Commit, NsAvidmGf2Common, NsAvidmGf2Scheme},
9        AvidmGf2Scheme, MerkleProof, MerkleTree,
10    },
11    VerificationResult, VidError, VidResult, VidScheme,
12};
13
14/// A proof of a namespace payload.
15/// It consists of the index of the namespace, the namespace payload, and a merkle proof
16/// of the namespace payload against the namespaced VID commitment.
17#[derive(Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
18pub struct NsProof {
19    /// The index of the namespace.
20    pub ns_index: usize,
21    /// The namespace payload.
22    #[serde(with = "base64_bytes")]
23    pub ns_payload: Vec<u8>,
24    /// The merkle proof of the namespace payload against the namespaced VID commitment.
25    pub ns_proof: MerkleProof,
26}
27
28impl NsAvidmGf2Scheme {
29    /// Generate a proof of inclusion for a namespace payload.
30    pub fn namespace_proof(
31        common: &NsAvidmGf2Common,
32        payload: &[u8],
33        ns_index: usize,
34    ) -> VidResult<NsProof> {
35        if common.ns_commits.len() != common.ns_lens.len() {
36            return Err(VidError::Internal(anyhow::anyhow!(
37                "Inconsistent common data"
38            )));
39        }
40        if ns_index >= common.ns_lens.len() {
41            return Err(VidError::IndexOutOfBound);
42        }
43        let ns_payload_range_start = common.ns_lens[..ns_index].iter().sum::<usize>();
44        let ns_payload_range_end = ns_payload_range_start + common.ns_lens[ns_index];
45        if ns_payload_range_end > payload.len() {
46            return Err(VidError::Internal(anyhow::anyhow!(
47                "Payload length is inconsistent with namespace lengths"
48            )));
49        }
50
51        let mt = MerkleTree::from_elems(None, common.ns_commits.iter().map(|c| c.commit))?;
52        Ok(NsProof {
53            ns_index,
54            ns_payload: payload[ns_payload_range_start..ns_payload_range_end].to_vec(),
55            ns_proof: mt
56                .lookup(ns_index as u64)
57                .expect_ok()
58                .expect("MT lookup shouldn't fail")
59                .1,
60        })
61    }
62
63    /// Verify a namespace proof against a namespaced VID commitment.
64    pub fn verify_namespace_proof(
65        commit: &NsAvidmGf2Commit,
66        common: &NsAvidmGf2Common,
67        proof: &NsProof,
68    ) -> VidResult<VerificationResult> {
69        let ns_commit = AvidmGf2Scheme::commit(&common.param, &proof.ns_payload)?;
70        Ok(MerkleTree::verify(
71            &commit.commit,
72            proof.ns_index as u64,
73            &ns_commit.commit,
74            &proof.ns_proof,
75        )?)
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use crate::avidm_gf2::{namespaced::NsAvidmGf2Scheme, AvidmGf2Scheme};
82
83    #[test]
84    fn test_ns_proof() {
85        let param = AvidmGf2Scheme::setup(5usize, 10usize).unwrap();
86        let payload = vec![1u8; 100];
87        let ns_table = vec![(0..10), (10..21), (21..33), (33..48), (48..100)];
88        let (commit, common) =
89            NsAvidmGf2Scheme::commit(&param, &payload, ns_table.clone()).unwrap();
90
91        for (i, _) in ns_table.iter().enumerate() {
92            let proof = NsAvidmGf2Scheme::namespace_proof(&common, &payload, i).unwrap();
93            assert!(
94                NsAvidmGf2Scheme::verify_namespace_proof(&commit, &common, &proof)
95                    .unwrap()
96                    .is_ok()
97            );
98        }
99        let mut proof = NsAvidmGf2Scheme::namespace_proof(&common, &payload, 1).unwrap();
100        proof.ns_index = 0;
101        assert!(
102            NsAvidmGf2Scheme::verify_namespace_proof(&commit, &common, &proof)
103                .unwrap()
104                .is_err()
105        );
106        proof.ns_index = 1;
107        proof.ns_payload[0] = 0u8;
108        assert!(
109            NsAvidmGf2Scheme::verify_namespace_proof(&commit, &common, &proof)
110                .unwrap()
111                .is_err()
112        );
113        proof.ns_index = 100;
114        assert!(
115            NsAvidmGf2Scheme::verify_namespace_proof(&commit, &common, &proof)
116                .unwrap()
117                .is_err()
118        );
119    }
120}
vid/avidm_gf2/proofs.rs

vid/avidm_gf2/
proofs.rs
