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::{BlockCommitmentsPage, 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<BlockCommitmentsPage, Infallible> {
38        let blocks = self
39            .blocks
40            .range(from_height..=to_height)
41            .map(|(_, bc)| bc.clone())
42            .collect();
43        Ok(BlockCommitmentsPage {
44            blocks,
45            next_from_height: 0,
46        })
47    }
48
49    fn get_root_at_height(&self, height: u32) -> Result<Option<Fp>, Infallible> {
50        Ok(self.root_at_height(height))
51    }
52
53    fn get_tree_state(&self) -> Result<TreeState, Infallible> {
54        Ok(TreeState {
55            next_index: self.size(),
56            root: self.root(),
57            height: self.latest_checkpoint().unwrap_or(0),
58        })
59    }
60}
61
62// ---------------------------------------------------------------------------
63// Tests
64// ---------------------------------------------------------------------------
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69    use crate::anchor::Anchor;
70    use crate::hash::EMPTY_ROOTS;
71    use crate::server::{CheckpointError, MemoryTreeServer};
72
73    fn fp(x: u64) -> Fp {
74        Fp::from(x)
75    }
76
77    #[test]
78    fn empty_tree_has_deterministic_root() {
79        let t1 = MemoryTreeServer::empty();
80        let t2 = MemoryTreeServer::empty();
81        assert_eq!(t1.root(), t2.root());
82        assert_eq!(t1.size(), 0);
83    }
84
85    #[test]
86    fn empty_roots_are_consistent() {
87        use crate::hash::{MerkleHashVote, TREE_DEPTH};
88        use incrementalmerkletree::{Hashable, Level};
89
90        let leaf = MerkleHashVote::empty_leaf();
91        assert_eq!(EMPTY_ROOTS[0], leaf);
92        let mut expected = leaf;
93        for level in 0..TREE_DEPTH {
94            assert_eq!(EMPTY_ROOTS[level], expected, "level {level}");
95            expected = MerkleHashVote::combine(Level::from(level as u8), &expected, &expected);
96        }
97    }
98
99    #[test]
100    fn append_one_and_path() {
101        let mut tree = MemoryTreeServer::empty();
102        let idx = tree.append(fp(100)).unwrap();
103        assert_eq!(idx, 0);
104        assert_eq!(tree.size(), 1);
105        tree.checkpoint(1).unwrap();
106        let path = tree.path(0, 1).unwrap();
107        assert!(path.verify(fp(100), tree.root()));
108    }
109
110    #[test]
111    fn append_two_leaves_paths_verify() {
112        let mut tree = MemoryTreeServer::empty();
113        tree.append(fp(1)).unwrap();
114        tree.append(fp(2)).unwrap();
115        tree.checkpoint(1).unwrap();
116        let root = tree.root();
117        for i in 0..2u64 {
118            let path = tree.path(i, 1).unwrap();
119            assert!(path.verify(Fp::from(i + 1), root));
120        }
121    }
122
123    #[test]
124    fn checkpoint_preserves_root() {
125        let mut tree = MemoryTreeServer::empty();
126        tree.append(fp(1)).unwrap();
127        tree.append(fp(2)).unwrap();
128        tree.checkpoint(10).unwrap();
129        let root_at_10 = tree.root_at_height(10).unwrap();
130        tree.append(fp(3)).unwrap();
131        tree.checkpoint(11).unwrap();
132        assert_eq!(tree.root_at_height(10).unwrap(), root_at_10);
133        assert_ne!(tree.root_at_height(11).unwrap(), root_at_10);
134    }
135
136    #[test]
137    fn anchor_empty_tree() {
138        let anchor = Anchor::empty_tree();
139        let tree = MemoryTreeServer::empty();
140        assert_eq!(anchor.inner(), tree.root());
141    }
142
143    #[test]
144    fn checkpoint_monotonicity_returns_error_on_regression() {
145        let mut tree = MemoryTreeServer::empty();
146        tree.append(fp(1)).unwrap();
147        tree.checkpoint(5).unwrap();
148        tree.append(fp(2)).unwrap();
149
150        // Equal height: must return NotMonotonic.
151        let err = tree
152            .checkpoint(5)
153            .expect_err("expected error on duplicate checkpoint height");
154        assert!(
155            matches!(
156                err,
157                CheckpointError::NotMonotonic {
158                    prev: 5,
159                    requested: 5
160                }
161            ),
162            "unexpected error variant: {:?}",
163            err,
164        );
165
166        // Regressing height: must also return NotMonotonic.
167        let err = tree
168            .checkpoint(3)
169            .expect_err("expected error on regressing checkpoint height");
170        assert!(
171            matches!(
172                err,
173                CheckpointError::NotMonotonic {
174                    prev: 5,
175                    requested: 3
176                }
177            ),
178            "unexpected error variant: {:?}",
179            err,
180        );
181
182        // The tree must still be usable: a strictly increasing height succeeds.
183        tree.checkpoint(6)
184            .expect("checkpoint with higher height must succeed");
185    }
186
187    /// Verifies that old checkpoints are evicted from the store once the
188    /// in-memory `MemoryShardStore` exceeds its `MAX_CHECKPOINTS` window.
189    #[test]
190    fn old_checkpoints_pruned_after_max_checkpoints() {
191        use crate::hash::MAX_CHECKPOINTS;
192
193        let mut tree = MemoryTreeServer::empty();
194        let total = MAX_CHECKPOINTS + 1;
195        for h in 1u32..=(total as u32) {
196            tree.append(Fp::from(h as u64)).unwrap();
197            tree.checkpoint(h).unwrap();
198        }
199
200        assert!(
201            tree.root_at_height(1).is_none(),
202            "checkpoint at height 1 should be pruned after {} blocks",
203            total
204        );
205
206        let first_retained = (total - MAX_CHECKPOINTS + 1) as u32;
207        assert!(
208            tree.root_at_height(first_retained).is_some(),
209            "checkpoint at height {} should still be present",
210            first_retained
211        );
212        assert!(
213            tree.root_at_height(total as u32).is_some(),
214            "latest checkpoint must be present"
215        );
216    }
217}
vote_commitment_tree/memory_server.rs

vote_commitment_tree/
memory_server.rs
