commonware_storage/qmdb/current/ordered/
mod.rs

1//! _Ordered_ variants of a [crate::qmdb::current] authenticated database.
2//!
3//! These variants maintain the lexicographic-next active key for each active key, enabling
4//! exclusion proofs via [ExclusionProof]. This adds overhead compared to [super::unordered]
5//! variants.
6//!
7//! Variants:
8//! - [fixed]: Variant optimized for values of fixed size.
9//! - [variable]: Variant for values of variable size.
10
11use crate::qmdb::{
12    any::{ordered::Update, ValueEncoding},
13    current::proof::OperationProof,
14};
15use commonware_cryptography::Digest;
16use commonware_utils::Array;
17
18pub mod db;
19pub mod fixed;
20#[cfg(any(test, feature = "test-traits"))]
21mod test_trait_impls;
22pub mod variable;
23
24#[cfg(test)]
25pub mod tests {
26    //! Shared test utilities for ordered Current QMDB variants.
27
28    use crate::{
29        kv::{Deletable as _, Gettable as _, Updatable as _},
30        mmr::Location,
31        qmdb::{
32            any::states::{CleanAny, MutableAny as _, UnmerkleizedDurableAny as _},
33            current::BitmapPrunedBits,
34            store::{
35                batch_tests::{TestKey, TestValue},
36                LogStore,
37            },
38        },
39    };
40    use commonware_runtime::{
41        deterministic::{self, Context},
42        Metrics as _, Runner as _,
43    };
44    use core::future::Future;
45
46    /// Run `test_current_db_build_small_close_reopen` against an ordered database factory.
47    ///
48    /// This test builds a small database, performs basic operations (create, delete, commit),
49    /// and verifies state is preserved across close/reopen cycles.
50    pub fn test_build_small_close_reopen<C, F, Fut>(mut open_db: F)
51    where
52        C: CleanAny + BitmapPrunedBits,
53        C::Key: TestKey,
54        <C as LogStore>::Value: TestValue,
55        F: FnMut(Context, String) -> Fut,
56        Fut: Future<Output = C>,
57    {
58        let executor = deterministic::Runner::default();
59        executor.start(|context| async move {
60            let partition = "build_small".to_string();
61            let db: C = open_db(context.with_label("first"), partition.clone()).await;
62            assert_eq!(db.bounds().end, Location::new_unchecked(1));
63            assert_eq!(db.inactivity_floor_loc(), Location::new_unchecked(0));
64            assert_eq!(db.oldest_retained(), 0);
65            let root0 = db.root();
66            drop(db);
67            let db: C = open_db(context.with_label("second"), partition.clone()).await;
68            assert_eq!(db.bounds().end, Location::new_unchecked(1));
69            assert!(db.get_metadata().await.unwrap().is_none());
70            assert_eq!(db.root(), root0);
71
72            // Add one key.
73            let k1: C::Key = TestKey::from_seed(0);
74            let v1: <C as LogStore>::Value = TestValue::from_seed(10);
75            let mut db = db.into_mutable();
76            assert!(db.create(k1, v1.clone()).await.unwrap());
77            assert_eq!(db.get(&k1).await.unwrap().unwrap(), v1);
78            let (db, _) = db.commit(None).await.unwrap();
79            let db: C = db.into_merkleized().await.unwrap();
80            assert_eq!(db.bounds().end, Location::new_unchecked(4)); // 1 update, 1 commit, 1 move + 1 initial commit.
81            assert!(db.get_metadata().await.unwrap().is_none());
82            let root1 = db.root();
83            assert_ne!(root1, root0);
84
85            drop(db);
86            let db: C = open_db(context.with_label("third"), partition.clone()).await;
87            assert_eq!(db.bounds().end, Location::new_unchecked(4));
88            assert_eq!(db.root(), root1);
89
90            // Create of same key should fail.
91            let mut db = db.into_mutable();
92            assert!(!db.create(k1, v1.clone()).await.unwrap());
93
94            // Delete that one key.
95            assert!(db.delete(k1).await.unwrap());
96
97            let metadata: <C as LogStore>::Value = TestValue::from_seed(1);
98            let (db, _) = db.commit(Some(metadata.clone())).await.unwrap();
99            let db: C = db.into_merkleized().await.unwrap();
100            assert_eq!(db.bounds().end, Location::new_unchecked(6)); // 1 update, 2 commits, 1 move, 1 delete.
101            assert_eq!(db.get_metadata().await.unwrap().unwrap(), metadata);
102            assert_eq!(db.inactivity_floor_loc(), Location::new_unchecked(5));
103            let root2 = db.root();
104
105            drop(db);
106            let db: C = open_db(context.with_label("fourth"), partition.clone()).await;
107            assert_eq!(db.bounds().end, Location::new_unchecked(6));
108            assert_eq!(db.get_metadata().await.unwrap().unwrap(), metadata);
109            assert_eq!(db.inactivity_floor_loc(), Location::new_unchecked(5));
110            assert_eq!(db.root(), root2);
111
112            // Repeated delete of same key should fail.
113            let mut db = db.into_mutable();
114            assert!(!db.delete(k1).await.unwrap());
115            let (db, _) = db.commit(None).await.unwrap();
116            let db: C = db.into_merkleized().await.unwrap();
117            let root3 = db.root();
118            assert_ne!(root3, root2);
119
120            // Confirm all activity bits except the last are false.
121            for i in 0..*db.bounds().end - 1 {
122                assert!(!db.get_bit(i));
123            }
124            assert!(db.get_bit(*db.bounds().end - 1));
125
126            // Test that we can get a non-durable root.
127            let mut db = db.into_mutable();
128            db.update(k1, v1).await.unwrap();
129            let (db, _) = db.commit(None).await.unwrap();
130            let db: C = db.into_merkleized().await.unwrap();
131            assert_ne!(db.root(), root3);
132
133            db.destroy().await.unwrap();
134        });
135    }
136}
137
138/// Proof that a key has no assigned value in the database.
139///
140/// When the database has active keys, exclusion is proven by showing the key falls within a span
141/// between two adjacent active keys. Otherwise exclusion is proven by showing the database contains
142/// no active keys through the most recent commit operation.
143///
144/// Verify using [Db::verify_exclusion_proof](fixed::Db::verify_exclusion_proof).
145#[derive(Clone, Eq, PartialEq, Debug)]
146pub enum ExclusionProof<K: Array, V: ValueEncoding, D: Digest, const N: usize> {
147    /// Proves that two keys are active in the database and adjacent to each other in the key
148    /// ordering. Any key falling between them (non-inclusively) can be proven excluded.
149    KeyValue(OperationProof<D, N>, Update<K, V>),
150
151    /// Proves that the database has no active keys, allowing any key to be proven excluded.
152    /// Specifically, the proof establishes the most recent Commit operation has an activity floor
153    /// equal to its own location, which is a necessary and sufficient condition for an empty
154    /// database.
155    Commit(OperationProof<D, N>, Option<V::Value>),
156}
commonware_storage/qmdb/current/ordered/mod.rs

commonware_storage/qmdb/current/ordered/
mod.rs
