vote_commitment_tree/
memory_server.rs

1//! [`SyncableServer`] — augments [`GenericTreeServer`] with per-block leaf
2//! tracking and implements [`TreeSyncApi`] for in-process sync.
3//!
4//! [`MemoryTreeServer`] is a convenience alias for
5//! `SyncableServer<MemoryShardStore<…>>`. Tests that do not need sync can use
6//! `GenericTreeServer<MemoryShardStore<MerkleHashVote, u32>>` directly.
7//!
8//! For the production incremental path use [`crate::server::TreeServer`]
9//! backed by [`crate::kv_shard_store::KvShardStore`].
10
11use std::convert::Infallible;
12
13use pasta_curves::Fp;
14use shardtree::store::ShardStore;
15
16use crate::hash::MerkleHashVote;
17use crate::server::SyncableServer;
18use crate::sync_api::{BlockCommitments, TreeState, TreeSyncApi};
19
20// ---------------------------------------------------------------------------
21// TreeSyncApi implementation for SyncableServer<S>
22// ---------------------------------------------------------------------------
23
24impl<S> TreeSyncApi for SyncableServer<S>
25where
26    S: ShardStore<H = MerkleHashVote, CheckpointId = u32>,
27    S::Error: std::fmt::Debug,
28{
29    /// `SyncableServer` never fails when serving sync data — the `blocks` map
30    /// is an in-memory `BTreeMap` and all root lookups are infallible.
31    type Error = Infallible;
32
33    fn get_block_commitments(
34        &self,
35        from_height: u32,
36        to_height: u32,
37    ) -> Result<Vec<BlockCommitments>, Infallible> {
38        let blocks = self
39            .blocks
40            .range(from_height..=to_height)
41            .map(|(_, bc)| bc.clone())
42            .collect();
43        Ok(blocks)
44    }
45
46    fn get_root_at_height(&self, height: u32) -> Result<Option<Fp>, Infallible> {
47        Ok(self.root_at_height(height))
48    }
49
50    fn get_tree_state(&self) -> Result<TreeState, Infallible> {
51        Ok(TreeState {
52            next_index: self.size(),
53            root: self.root(),
54            height: self.latest_checkpoint().unwrap_or(0),
55        })
56    }
57}
58
59// ---------------------------------------------------------------------------
60// Tests
61// ---------------------------------------------------------------------------
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66    use crate::anchor::Anchor;
67    use crate::hash::EMPTY_ROOTS;
68    use crate::server::{CheckpointError, MemoryTreeServer};
69
70    fn fp(x: u64) -> Fp {
71        Fp::from(x)
72    }
73
74    #[test]
75    fn empty_tree_has_deterministic_root() {
76        let t1 = MemoryTreeServer::empty();
77        let t2 = MemoryTreeServer::empty();
78        assert_eq!(t1.root(), t2.root());
79        assert_eq!(t1.size(), 0);
80    }
81
82    #[test]
83    fn empty_roots_are_consistent() {
84        use crate::hash::{MerkleHashVote, TREE_DEPTH};
85        use incrementalmerkletree::{Hashable, Level};
86
87        let leaf = MerkleHashVote::empty_leaf();
88        assert_eq!(EMPTY_ROOTS[0], leaf);
89        let mut expected = leaf;
90        for level in 0..TREE_DEPTH {
91            assert_eq!(EMPTY_ROOTS[level], expected, "level {level}");
92            expected = MerkleHashVote::combine(Level::from(level as u8), &expected, &expected);
93        }
94    }
95
96    #[test]
97    fn append_one_and_path() {
98        let mut tree = MemoryTreeServer::empty();
99        let idx = tree.append(fp(100)).unwrap();
100        assert_eq!(idx, 0);
101        assert_eq!(tree.size(), 1);
102        tree.checkpoint(1).unwrap();
103        let path = tree.path(0, 1).unwrap();
104        assert!(path.verify(fp(100), tree.root()));
105    }
106
107    #[test]
108    fn append_two_leaves_paths_verify() {
109        let mut tree = MemoryTreeServer::empty();
110        tree.append(fp(1)).unwrap();
111        tree.append(fp(2)).unwrap();
112        tree.checkpoint(1).unwrap();
113        let root = tree.root();
114        for i in 0..2u64 {
115            let path = tree.path(i, 1).unwrap();
116            assert!(path.verify(Fp::from(i + 1), root));
117        }
118    }
119
120    #[test]
121    fn checkpoint_preserves_root() {
122        let mut tree = MemoryTreeServer::empty();
123        tree.append(fp(1)).unwrap();
124        tree.append(fp(2)).unwrap();
125        tree.checkpoint(10).unwrap();
126        let root_at_10 = tree.root_at_height(10).unwrap();
127        tree.append(fp(3)).unwrap();
128        tree.checkpoint(11).unwrap();
129        assert_eq!(tree.root_at_height(10).unwrap(), root_at_10);
130        assert_ne!(tree.root_at_height(11).unwrap(), root_at_10);
131    }
132
133    #[test]
134    fn anchor_empty_tree() {
135        let anchor = Anchor::empty_tree();
136        let tree = MemoryTreeServer::empty();
137        assert_eq!(anchor.inner(), tree.root());
138    }
139
140    #[test]
141    fn checkpoint_monotonicity_returns_error_on_regression() {
142        let mut tree = MemoryTreeServer::empty();
143        tree.append(fp(1)).unwrap();
144        tree.checkpoint(5).unwrap();
145        tree.append(fp(2)).unwrap();
146
147        // Equal height: must return NotMonotonic.
148        let err = tree.checkpoint(5).expect_err("expected error on duplicate checkpoint height");
149        assert!(
150            matches!(err, CheckpointError::NotMonotonic { prev: 5, requested: 5 }),
151            "unexpected error variant: {:?}",
152            err,
153        );
154
155        // Regressing height: must also return NotMonotonic.
156        let err = tree.checkpoint(3).expect_err("expected error on regressing checkpoint height");
157        assert!(
158            matches!(err, CheckpointError::NotMonotonic { prev: 5, requested: 3 }),
159            "unexpected error variant: {:?}",
160            err,
161        );
162
163        // The tree must still be usable: a strictly increasing height succeeds.
164        tree.checkpoint(6).expect("checkpoint with higher height must succeed");
165    }
166
167    /// Verifies that old checkpoints are evicted from the store once the
168    /// in-memory `MemoryShardStore` exceeds its `MAX_CHECKPOINTS` window.
169    #[test]
170    fn old_checkpoints_pruned_after_max_checkpoints() {
171        use crate::hash::MAX_CHECKPOINTS;
172
173        let mut tree = MemoryTreeServer::empty();
174        let total = MAX_CHECKPOINTS + 1;
175        for h in 1u32..=(total as u32) {
176            tree.append(Fp::from(h as u64)).unwrap();
177            tree.checkpoint(h).unwrap();
178        }
179
180        assert!(
181            tree.root_at_height(1).is_none(),
182            "checkpoint at height 1 should be pruned after {} blocks",
183            total
184        );
185
186        let first_retained = (total - MAX_CHECKPOINTS + 1) as u32;
187        assert!(
188            tree.root_at_height(first_retained).is_some(),
189            "checkpoint at height {} should still be present",
190            first_retained
191        );
192        assert!(
193            tree.root_at_height(total as u32).is_some(),
194            "latest checkpoint must be present"
195        );
196    }
197}
vote_commitment_tree/memory_server.rs

vote_commitment_tree/
memory_server.rs
