dig_evidence/
range_inclusion.rs

1//! [`RangeInclusionEvidence`] (#1437) — proof that a content range's leaf is included under a claimed
2//! generation root.
3//!
4//! This is a SELF-CONTAINED, OFFLINE evidence type: everything it needs is supplied in the claim (a
5//! leaf digest + its bottom-up inclusion path + the claimed generation root), so [`gather`] performs
6//! no chain reads — it authenticates the supplied inputs by folding the path and confirming it reaches
7//! the claimed root. The merkle machinery is REUSED from `dig-capsule` verbatim
8//! ([`dig_capsule::merkle::MerkleProof`] / [`ProofStep`]), so the domain-separation tags
9//! ([`LEAF_TAG`](dig_capsule::merkle::LEAF_TAG) = `b"digstore:leaf:v1"` /
10//! [`NODE_TAG`](dig_capsule::merkle::NODE_TAG) = `b"digstore:node:v1"`) are byte-for-byte identical to
11//! the producer's — a range proof this crate accepts is exactly a range proof the store emitted.
12//!
13//! Proving inclusion under a root does NOT prove the root is genuine; pairing it with
14//! [`RootAnchorEvidence`](crate::RootAnchorEvidence) does (see [`ReadIntegrityEvidence`](crate::ReadIntegrityEvidence)).
15
16use dig_capsule::format::Bytes32 as CapsuleBytes32;
17use dig_capsule::merkle::{MerkleProof, ProofStep};
18use dig_chainsource_interface::ChainSource;
19
20use crate::error::{EvidenceError, EvidenceResult};
21use crate::evidence::Evidence;
22
23/// What a range-inclusion proof claims: that `leaf` folds, via `path`, to `generation_root`.
24///
25/// `leaf` is the range's merkle leaf digest and `path` is its bottom-up sibling path — both exactly as
26/// produced by `dig-capsule`'s [`MerkleTree`](dig_capsule::merkle::MerkleTree). `generation_root` is
27/// the root the caller claims the leaf is contained under.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub struct RangeInclusionClaim {
30    /// The range's merkle leaf digest (the value the inclusion path starts from).
31    pub leaf: CapsuleBytes32,
32    /// The bottom-up inclusion path (sibling + side per level), verbatim from the producer.
33    pub path: Vec<ProofStep>,
34    /// The generation root the leaf is claimed to be included under.
35    pub generation_root: CapsuleBytes32,
36}
37
38/// Authenticated evidence that a range leaf is included under a generation root.
39///
40/// Its fields are PRIVATE and exposed only through accessors: the only way to obtain a value is
41/// [`gather`](Evidence::gather), which folds the supplied path and confirms it reaches the claimed
42/// root. A value therefore witnesses that the inclusion genuinely holds.
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct RangeInclusionEvidence {
45    proof: MerkleProof,
46}
47
48impl RangeInclusionEvidence {
49    /// The generation root the range leaf is proven to be included under.
50    pub fn generation_root(&self) -> CapsuleBytes32 {
51        self.proof.root
52    }
53
54    /// The range's merkle leaf digest this evidence proves inclusion of.
55    pub fn leaf(&self) -> CapsuleBytes32 {
56        self.proof.leaf
57    }
58
59    /// The inclusion path (sibling hashes + sides) folded to reach the root.
60    pub fn path(&self) -> &[ProofStep] {
61        &self.proof.path
62    }
63}
64
65impl Evidence for RangeInclusionEvidence {
66    type Claim = RangeInclusionClaim;
67
68    /// Authenticates the supplied inclusion inputs OFFLINE — `chain` is unused because a range proof is
69    /// fully self-contained. Builds the [`MerkleProof`] from the claim and folds it; a path that does
70    /// not reach `generation_root` is rejected with [`EvidenceError::ProofDoesNotFold`].
71    fn gather<S: ChainSource>(claim: &Self::Claim, _chain: &S) -> EvidenceResult<Self> {
72        let proof = MerkleProof {
73            leaf: claim.leaf,
74            path: claim.path.clone(),
75            root: claim.generation_root,
76        };
77        if !proof.verify() {
78            return Err(EvidenceError::ProofDoesNotFold);
79        }
80        Ok(Self { proof })
81    }
82
83    /// Re-folds the stored path offline and confirms it still reaches the stored root.
84    fn verify(&self) -> EvidenceResult<()> {
85        if self.proof.verify() {
86            Ok(())
87        } else {
88            Err(EvidenceError::ProofDoesNotFold)
89        }
90    }
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    use dig_capsule::merkle::MerkleTree;
97    use dig_chainsource_interface::MockChainSource;
98
99    /// Builds a tree over `n` distinct chunks and returns (root, leaf, path) for `index`.
100    fn tree_proof(n: usize, index: usize) -> (CapsuleBytes32, CapsuleBytes32, Vec<ProofStep>) {
101        let chunks: Vec<Vec<u8>> = (0..n).map(|i| vec![i as u8; 8]).collect();
102        let tree = MerkleTree::build(&chunks);
103        let proof = tree.prove(index).expect("index in range");
104        (tree.root(), proof.leaf, proof.path)
105    }
106
107    #[test]
108    fn a_valid_range_proof_gathers_and_verifies() {
109        let (root, leaf, path) = tree_proof(5, 2);
110        let claim = RangeInclusionClaim {
111            leaf,
112            path,
113            generation_root: root,
114        };
115        let evidence =
116            RangeInclusionEvidence::gather(&claim, &MockChainSource::new()).expect("valid proof");
117        assert_eq!(evidence.generation_root(), root);
118        assert_eq!(evidence.leaf(), leaf);
119        assert!(evidence.verify().is_ok());
120    }
121
122    #[test]
123    fn a_tampered_leaf_is_rejected() {
124        let (root, _leaf, path) = tree_proof(5, 2);
125        let forged = RangeInclusionClaim {
126            leaf: CapsuleBytes32([0xff; 32]),
127            path,
128            generation_root: root,
129        };
130        assert_eq!(
131            RangeInclusionEvidence::gather(&forged, &MockChainSource::new()).unwrap_err(),
132            EvidenceError::ProofDoesNotFold
133        );
134    }
135
136    #[test]
137    fn a_wrong_claimed_root_is_rejected() {
138        let (_root, leaf, path) = tree_proof(8, 5);
139        let forged = RangeInclusionClaim {
140            leaf,
141            path,
142            generation_root: CapsuleBytes32([0x00; 32]),
143        };
144        assert_eq!(
145            RangeInclusionEvidence::gather(&forged, &MockChainSource::new()).unwrap_err(),
146            EvidenceError::ProofDoesNotFold
147        );
148    }
149
150    #[test]
151    fn a_tampered_path_step_is_rejected() {
152        let (root, leaf, mut path) = tree_proof(6, 1);
153        if let Some(step) = path.first_mut() {
154            step.hash = CapsuleBytes32([0x77; 32]);
155        }
156        let forged = RangeInclusionClaim {
157            leaf,
158            path,
159            generation_root: root,
160        };
161        assert_eq!(
162            RangeInclusionEvidence::gather(&forged, &MockChainSource::new()).unwrap_err(),
163            EvidenceError::ProofDoesNotFold
164        );
165    }
166}
dig_evidence/range_inclusion.rs

dig_evidence/
range_inclusion.rs
