spine/
lib.rs

1//! `spine` — the Merkle Spine: the structural core.
2//!
3//! The structural engine shared by every tree built above it, **epoch-free** and
4//! **topology-agnostic**: **canonicalization** (collapse + promotion, in [`mr`]),
5//! the perfect-subtree **decomposition** and grouping combinator ([`topology`]),
6//! the [`Hasher`] seam, the **abstract inclusion verifier** (proof pinned against
7//! a consumer-supplied skeleton, in [`proof`]), the [`LeafProof`], the general
8//! structural [`Seal`] (peak storage), and the opaque **metadata channel**
9//! ([`Meta`]). It depends on nothing.
10//!
11//! The spine carries no **commitment topology**: how perfect subtrees are bagged
12//! into one root, and what an inclusion proof points at, are owned by each
13//! consumer (the append-only log's mountain range; the mutable tree's rebalanced
14//! fold). The seam between them is the [`SkeletonStep`] interface — the consumer
15//! computes its concrete skeleton, the spine verifier pins a proof against it.
16//!
17//! Activation, the committed epoch timeline, the null-run-extents, the binding
18//! root, and coupling are **not** here — they are the `polydigest` combinator's
19//! facet, which lifts this structural engine across N algorithms over one
20//! shared data substrate. The spine names no epoch concept.
21
22pub mod hasher;
23pub mod mr;
24pub mod proof;
25pub mod subtree;
26pub mod topology;
27
28pub(crate) mod error;
29pub(crate) mod leaf_proof;
30pub(crate) mod metadata;
31pub(crate) mod seal;
32
33pub use error::{Error, Result};
34pub use hasher::Hasher;
35pub use leaf_proof::LeafProof;
36pub use metadata::Meta;
37pub use mr::{count_leaves, evaluate, nary_mr, within_subtree_path};
38pub use proof::{
39    InclusionProof, ProofStep, constant_time_eq, reconstruct_inclusion_root, verify_inclusion,
40    verify_inclusion_path_structure,
41};
42pub use seal::{RunExtent, Seal};
43pub use subtree::Subtree;
44pub use topology::{
45    ARITY_RANGE, BagFn, SkeletonFn, SkeletonStep, fold_frontier, frontier_for_size,
46};
47
48/// Dynamically generate a null digest constant using the hasher.
49#[must_use]
50pub fn null_digest(hasher: &dyn Hasher) -> Vec<u8> {
51    hasher.hash(b"null")
52}
53
54#[cfg(test)]
55mod tests {
56    use sha2::{Digest, Sha256};
57
58    use super::*;
59    use crate::subtree::Subtree;
60
61    #[derive(Debug)]
62    struct Sha256Hasher;
63
64    impl Hasher for Sha256Hasher {
65        fn leaf(&self, data: &[u8]) -> Vec<u8> {
66            Sha256::digest(data).to_vec()
67        }
68
69        fn node(&self, children: &[&[u8]]) -> Vec<u8> {
70            let mut h = Sha256::new();
71            for child in children {
72                h.update(child);
73            }
74            h.finalize().to_vec()
75        }
76
77        fn empty(&self) -> Vec<u8> {
78            Sha256::digest(b"").to_vec()
79        }
80
81        fn hash(&self, data: &[u8]) -> Vec<u8> {
82            Sha256::digest(data).to_vec()
83        }
84
85        fn clone_box(&self) -> Box<dyn Hasher> {
86            Box::new(Sha256Hasher)
87        }
88    }
89
90    /// A child-tree root carried as `Subtree::Leaf` is indistinguishable from
91    /// a raw-payload leaf carrying the same bytes — the opacity contract.
92    /// The spine sees identical structure regardless of origin.
93    #[test]
94    fn leaf_carrying_child_root_is_opaque() {
95        let hasher = Sha256Hasher;
96        let child_root = evaluate(
97            &hasher,
98            &Subtree::Node(vec![
99                Subtree::Leaf(b"a".to_vec()),
100                Subtree::Leaf(b"b".to_vec()),
101            ]),
102        );
103
104        // A leaf wrapping a child root is structurally identical to a raw-payload
105        // leaf carrying the same bytes — no origin tag exists to distinguish them.
106        let via_child_root = Subtree::Leaf(child_root.clone());
107        let via_raw_payload = Subtree::Leaf(child_root.clone());
108        assert_eq!(via_child_root, via_raw_payload);
109
110        // The spine evaluates both identically: same digest, no branching on origin.
111        assert_eq!(
112            evaluate(&hasher, &via_child_root),
113            evaluate(&hasher, &via_raw_payload)
114        );
115    }
116}
spine/lib.rs

spine/
lib.rs
