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

commonware_storage/qmdb/current/ordered/
mod.rs
