cmt/
lib.rs

1//! `cmt` — the Canonical Mutable Tree, the **single-algorithm mutable** tree
2//! over the [`spine`] structural core.
3//!
4//! CMT is the mutable peer of the append-only [`cml`](https://docs.rs/cml) log:
5//! both are built on the spine and neither depends on the other (the structural
6//! currency between them is [`spine::Seal`]). Where CML optimizes an append-only
7//! frontier and proves consistency, CMT lets interior cells change — so it keeps
8//! **no frontier and no consistency proofs** (the frontier's left-subtrees-sealed
9//! assumption is unsound under mutation). It is positional and dense, sharing the
10//! spine's proof-spine index space, and supports:
11//!
12//! - construct, [`Cmt::set`] / [`Cmt::get`];
13//! - inclusion proofs and **non-membership** (inclusion of the spine null constant via collapse);
14//! - **per-node multi-hash** — a cell addressable under many algorithms — with **retroactive
15//!   per-node algorithm addition** at `O(log n)` ([`Cmt::add_algorithm_at`]), the structural
16//!   materialization of N per-algorithm roots (D11);
17//! - a one-way [`Cmt::seal`] into the general structural [`spine::Seal`] (no `unseal`).
18//!
19//! **Epoch-free (D13).** The CMT carries no committed timeline and no binding /
20//! combined root. The cross-tree binding of its per-algorithm member roots is the
21//! `polydigest` combinator's facet, added as a wrapper over the structural `Seal`
22//! (`polydigest(cmt)`); the CMT exposes each algorithm's raw [`root`](Cmt::root) and
23//! [`member_roots`](Cmt::member_roots), never a binding root.
24//!
25//! Verification stays in the spine: a proof generated here is checked with
26//! [`spine::verify_inclusion`] against an authenticated `(index, tree_size,
27//! arity, root)`.
28
29mod error;
30mod proof;
31pub mod shape;
32mod tree;
33
34pub use error::{Error, Result};
35// The CMT's own rebalanced topology, supplied to the spine's topology-agnostic
36// verifier: the skeleton a proof is pinned against and the peak fold a member
37// root is bagged with. The mutable peer of the append-only log's mountain range.
38pub use shape::{rebalanced_bag, rebalanced_skeleton};
39// The structural hasher seam and the proof/seal types the public surface returns
40// are re-exported so callers need not also name `spine` directly.
41pub use spine::{Hasher, LeafProof, ProofStep, Seal, verify_inclusion};
42pub use tree::{Cmt, Config};
43
44#[cfg(test)]
45mod tests {
46    use sha2::{Digest, Sha256};
47
48    use super::*;
49
50    #[derive(Debug)]
51    struct Sha256Hasher;
52
53    impl spine::Hasher for Sha256Hasher {
54        fn leaf(&self, data: &[u8]) -> Vec<u8> {
55            Sha256::digest(data).to_vec()
56        }
57
58        fn node(&self, children: &[&[u8]]) -> Vec<u8> {
59            let mut h = Sha256::new();
60            for child in children {
61                h.update(child);
62            }
63            h.finalize().to_vec()
64        }
65
66        fn empty(&self) -> Vec<u8> {
67            Sha256::digest(b"").to_vec()
68        }
69
70        fn hash(&self, data: &[u8]) -> Vec<u8> {
71            Sha256::digest(data).to_vec()
72        }
73
74        fn clone_box(&self) -> Box<dyn spine::Hasher> {
75            Box::new(Sha256Hasher)
76        }
77    }
78
79    const ALG: u64 = 0;
80    const K: u64 = 2;
81
82    fn tree_with(payloads: &[&[u8]]) -> Cmt {
83        let mut t = Cmt::new(Config { arity: K }).expect("valid arity");
84        t.register_algorithm(ALG, Box::new(Sha256Hasher))
85            .expect("fresh alg");
86        for (i, p) in payloads.iter().enumerate() {
87            t.set(i as u64, p.to_vec(), Vec::new()).expect("dense set");
88        }
89        t
90    }
91
92    #[test]
93    fn empty_tree_has_no_root() {
94        let t = Cmt::new(Config::default()).unwrap();
95        assert!(t.is_empty());
96        assert_eq!(t.root(ALG), None);
97    }
98
99    #[test]
100    fn rejects_out_of_range_arity() {
101        assert_eq!(
102            Cmt::new(Config { arity: 1 }).unwrap_err(),
103            Error::InvalidArity(1)
104        );
105        assert_eq!(
106            Cmt::new(Config { arity: 257 }).unwrap_err(),
107            Error::InvalidArity(257)
108        );
109    }
110
111    #[test]
112    fn set_get_round_trips_and_overwrites() {
113        let mut t = tree_with(&[b"a", b"b", b"c"]);
114        assert_eq!(t.get(1), Some(b"b".as_slice()));
115        t.set(1, b"B".to_vec(), Vec::new()).unwrap();
116        assert_eq!(t.get(1), Some(b"B".as_slice()));
117        assert_eq!(t.len(), 3);
118    }
119
120    #[test]
121    fn set_rejects_a_gap() {
122        let mut t = tree_with(&[b"a"]);
123        assert_eq!(
124            t.set(5, b"x".to_vec(), Vec::new()).unwrap_err(),
125            Error::IndexGap { index: 5, len: 1 }
126        );
127    }
128
129    #[test]
130    fn metadata_is_carried_verbatim_and_uninterpreted() {
131        let mut t = tree_with(&[b"a"]);
132        let meta = vec![0xDE, 0xAD, 0xBE, 0xEF];
133        t.set(0, b"a".to_vec(), meta.clone()).unwrap();
134        assert_eq!(t.metadata(0), Some(meta.as_slice()));
135        // Metadata never feeds the digest: same payload, different metadata,
136        // same root.
137        let r_with_meta = t.root(ALG).unwrap();
138        let mut t2 = tree_with(&[b"a"]);
139        t2.set(0, b"a".to_vec(), vec![0x00]).unwrap();
140        assert_eq!(t2.root(ALG).unwrap(), r_with_meta);
141    }
142
143    /// The materialized root equals a from-scratch spine evaluation of the
144    /// canonical subtree — the oracle pinning the materialization to spine semantics.
145    #[test]
146    fn root_matches_spine_evaluate() {
147        for size in 1u64..=20 {
148            let payloads: Vec<Vec<u8>> = (0..size).map(|i| format!("p{i}").into_bytes()).collect();
149            let refs: Vec<&[u8]> = payloads.iter().map(Vec::as_slice).collect();
150            let t = tree_with(&refs);
151            let expected = spine_root(&payloads);
152            assert_eq!(t.root(ALG).unwrap(), expected, "size={size}");
153        }
154    }
155
156    /// Build the canonical spine subtree for a flat sequence at k=2 and
157    /// evaluate it, independent of the CMT's materialization.
158    fn spine_root(payloads: &[Vec<u8>]) -> Vec<u8> {
159        use spine::{Subtree, frontier_for_size};
160        let h = Sha256Hasher;
161        let leaves: Vec<Subtree> = payloads.iter().map(|p| Subtree::Leaf(p.clone())).collect();
162        // Reassemble the same frontier-folded shape the spine topology uses.
163        let coords = frontier_for_size(payloads.len() as u64, K);
164        let mut frontier: Vec<Subtree> = coords
165            .iter()
166            .map(|&(left, height)| perfect(&leaves, left, height))
167            .collect();
168        let k = K as usize;
169        while frontier.len() > k {
170            let split = frontier.len() - k;
171            let group = frontier.split_off(split);
172            frontier.push(Subtree::Node(group));
173        }
174        let shape = if frontier.len() == 1 {
175            frontier.pop().unwrap()
176        } else {
177            Subtree::Node(frontier)
178        };
179        spine::evaluate(&h, &shape)
180    }
181
182    fn perfect(leaves: &[spine::Subtree], left: u64, height: u32) -> spine::Subtree {
183        use spine::Subtree;
184        if height == 0 {
185            return leaves[left as usize].clone();
186        }
187        let span = K.pow(height - 1);
188        let children = (0..K)
189            .map(|c| perfect(leaves, left + c * span, height - 1))
190            .collect();
191        Subtree::Node(children)
192    }
193
194    #[test]
195    fn inclusion_proof_verifies_against_spine() {
196        for size in 1u64..=20 {
197            let payloads: Vec<Vec<u8>> = (0..size).map(|i| format!("v{i}").into_bytes()).collect();
198            let refs: Vec<&[u8]> = payloads.iter().map(Vec::as_slice).collect();
199            let t = tree_with(&refs);
200            let root = t.root(ALG).unwrap();
201            let h = Sha256Hasher;
202            for index in 0..size {
203                let (leaf, path) = t.inclusion_proof(ALG, index).unwrap();
204                let skeleton = rebalanced_skeleton(size, K, index).expect("valid position");
205                assert!(
206                    spine::verify_inclusion(&h, &leaf, &skeleton, &path, &root),
207                    "size={size} index={index}"
208                );
209            }
210        }
211    }
212
213    /// F4 regression guard: off-path siblings are served from the materialized
214    /// cache, not re-evaluated. A fully materialized tree must generate inclusion
215    /// proofs with zero cache misses for every index. A positive miss count means
216    /// the cache is being bypassed and proof generation has silently degraded to
217    /// O(n) rather than O(log n).
218    #[test]
219    fn inclusion_proof_uses_cache_zero_misses() {
220        // Use a reasonably large tree (size > k^2) so there are genuine inner
221        // nodes with off-path siblings that would trigger misses without caching.
222        let size = 32u64;
223        let payloads: Vec<Vec<u8>> = (0..size).map(|i| format!("p{i}").into_bytes()).collect();
224        let refs: Vec<&[u8]> = payloads.iter().map(Vec::as_slice).collect();
225        let t = tree_with(&refs);
226        for index in 0..size {
227            let (_, _, misses) = t
228                .inclusion_proof_miss_count(ALG, index)
229                .expect("in-range index");
230            assert_eq!(
231                misses, 0,
232                "inclusion_proof for index={index} size={size} had {misses} cache miss(es): \
233                 off-path siblings must be served from the materialized cache (F4)"
234            );
235        }
236    }
237
238    #[test]
239    fn inclusion_proof_rejects_wrong_leaf() {
240        let t = tree_with(&[b"a", b"b", b"c", b"d"]);
241        let root = t.root(ALG).unwrap();
242        let h = Sha256Hasher;
243        let (_, path) = t.inclusion_proof(ALG, 2).unwrap();
244        let forged = h.leaf(b"not-c");
245        let skeleton = rebalanced_skeleton(4, K, 2).expect("valid position");
246        assert!(!spine::verify_inclusion(
247            &h, &forged, &skeleton, &path, &root
248        ));
249    }
250
251    #[test]
252    fn non_membership_of_a_null_cell_verifies() {
253        // A cell explicitly set to the null preimage hashes to null(); its
254        // non-membership (inclusion-of-null) proof verifies.
255        let h = Sha256Hasher;
256        let mut t = tree_with(&[b"real", b"x", b"y"]);
257        t.set(1, b"null".to_vec(), Vec::new()).unwrap();
258        let root = t.root(ALG).unwrap();
259        let (leaf, path) = t.non_membership_proof(ALG, 1).expect("cell hashes to null");
260        assert_eq!(leaf, h.null());
261        let skeleton = rebalanced_skeleton(t.len(), K, 1).expect("valid position");
262        assert!(spine::verify_inclusion(&h, &leaf, &skeleton, &path, &root));
263        // A present (non-null) cell has no non-membership proof.
264        assert_eq!(t.non_membership_proof(ALG, 0), None);
265    }
266
267    #[test]
268    fn leaf_proof_accepts_legit_and_rejects_forged() {
269        let h = Sha256Hasher;
270        for size in 1u64..=20 {
271            let payloads: Vec<Vec<u8>> = (0..size).map(|i| format!("v{i}").into_bytes()).collect();
272            let refs: Vec<&[u8]> = payloads.iter().map(Vec::as_slice).collect();
273            let t = tree_with(&refs);
274            let root = t.root(ALG).unwrap();
275            for index in 0..size {
276                let proof = t.leaf_proof(ALG, index).expect("in range");
277                let skeleton = rebalanced_skeleton(size, K, index).expect("valid position");
278                // Legitimate leaf accepted.
279                assert!(
280                    proof.verify(&h, &skeleton, &root),
281                    "size={size} index={index}"
282                );
283                // Forged leaf at the same position rejected.
284                let mut forged = proof.clone();
285                forged.leaf_hash = h.leaf(b"forged");
286                assert!(
287                    !forged.verify(&h, &skeleton, &root),
288                    "size={size} index={index}"
289                );
290            }
291        }
292        // Out-of-range and unknown-algorithm produce no proof.
293        let t = tree_with(&[b"a", b"b"]);
294        assert!(t.leaf_proof(ALG, 2).is_none());
295        assert!(t.leaf_proof(99, 0).is_none());
296    }
297
298    #[test]
299    fn seal_is_one_way_into_structural_seal() {
300        let t = tree_with(&[b"a", b"b", b"c"]);
301        let root = t.root(ALG).unwrap();
302        let sealed = t.seal().expect("non-empty seal");
303        assert_eq!(sealed.tree_size(), 3);
304        assert_eq!(sealed.arity(), 2);
305        // The seal computed the resumable frontier; folding its peaks under the
306        // algorithm's own hash with the CMT's rebalanced bag reproduces the live
307        // root.
308        assert!(sealed.peaks(ALG).is_some());
309        assert_eq!(
310            sealed.member_root(ALG, &Sha256Hasher, rebalanced_bag),
311            Some(root)
312        );
313        // `sealed` is a structural `Seal`; there is no path back to a `Cmt`.
314    }
315
316    #[test]
317    fn empty_tree_cannot_be_sealed() {
318        let t = Cmt::new(Config::default()).unwrap();
319        assert_eq!(t.seal().unwrap_err(), Error::EmptySeal);
320    }
321}
cmt/lib.rs

cmt/
lib.rs
