commonware_storage/qmdb/current/ordered/
fixed.rs

1//! An _ordered_ variant of a [crate::qmdb::current] authenticated database optimized for fixed-size
2//! values.
3//!
4//! This variant maintains the lexicographic-next active key for each active key, enabling exclusion
5//! proofs (proving a key is currently inactive). Use [crate::qmdb::current::unordered::fixed] if
6//! exclusion proofs are not needed.
7//!
8//! See [Db] for the main database type and [super::ExclusionProof] for proving key inactivity.
9
10pub use super::db::KeyValueProof;
11use crate::{
12    index::ordered::Index,
13    journal::contiguous::fixed::Journal,
14    merkle::{Graftable, Location},
15    qmdb::{
16        any::{ordered::fixed::Operation, value::FixedEncoding, FixedValue},
17        current::FixedConfig as Config,
18        Error,
19    },
20    translator::Translator,
21    Context,
22};
23use commonware_cryptography::Hasher;
24use commonware_parallel::Strategy;
25use commonware_utils::Array;
26
27pub type Db<F, E, K, V, H, T, const N: usize, S> = super::db::Db<
28    F,
29    E,
30    Journal<E, Operation<F, K, V>>,
31    K,
32    FixedEncoding<V>,
33    Index<T, Location<F>>,
34    H,
35    N,
36    S,
37>;
38
39impl<
40        F: Graftable,
41        E: Context,
42        K: Array,
43        V: FixedValue,
44        H: Hasher,
45        T: Translator,
46        const N: usize,
47        S: Strategy,
48    > Db<F, E, K, V, H, T, N, S>
49{
50    /// Initializes a [Db] from the given `config`.
51    /// The configured [`Strategy`] is used to parallelize merkleization.
52    pub async fn init(context: E, config: Config<T, S>) -> Result<Self, Error<F>> {
53        crate::qmdb::current::init(context, config).await
54    }
55}
56
57pub mod partitioned {
58    //! A variant of [super] that uses a partitioned index for the snapshot.
59
60    use super::*;
61    use crate::index::partitioned::ordered::Index;
62
63    /// A partitioned variant of [super::Db].
64    ///
65    /// The const generic `P` specifies the number of prefix bytes used for partitioning:
66    /// - `P = 1`: 256 partitions
67    /// - `P = 2`: 65,536 partitions
68    /// - `P = 3`: ~16 million partitions
69    pub type Db<F, E, K, V, H, T, const P: usize, const N: usize, S> =
70        crate::qmdb::current::ordered::db::Db<
71            F,
72            E,
73            Journal<E, Operation<F, K, V>>,
74            K,
75            FixedEncoding<V>,
76            Index<T, Location<F>, P>,
77            H,
78            N,
79            S,
80        >;
81
82    impl<
83            F: Graftable,
84            E: Context,
85            K: Array,
86            V: FixedValue,
87            H: Hasher,
88            T: Translator,
89            const P: usize,
90            const N: usize,
91            S: Strategy,
92        > Db<F, E, K, V, H, T, P, N, S>
93    {
94        /// Initializes a [Db] authenticated database from the given `config`.
95        /// The configured [`Strategy`] is used to parallelize merkleization.
96        pub async fn init(context: E, config: Config<T, S>) -> Result<Self, Error<F>> {
97            crate::qmdb::current::init(context, config).await
98        }
99    }
100}
101
102#[cfg(test)]
103pub mod test {
104    use super::*;
105    use crate::{
106        mmr,
107        qmdb::{
108            current::{ordered::tests as shared, tests::fixed_config},
109            Error,
110        },
111        translator::OneCap,
112    };
113    use commonware_cryptography::{sha256::Digest, Sha256};
114    use commonware_macros::test_traced;
115    use commonware_runtime::{deterministic, Runner as _, Supervisor as _};
116    use commonware_utils::{
117        bitmap::{Prunable as BitMap, Readable as _},
118        NZU64,
119    };
120
121    /// A type alias for the concrete [Db] type used in these unit tests.
122    type CurrentTest = Db<
123        mmr::Family,
124        deterministic::Context,
125        Digest,
126        Digest,
127        Sha256,
128        OneCap,
129        32,
130        commonware_parallel::Sequential,
131    >;
132
133    /// Return an [Db] database initialized with a fixed config.
134    async fn open_db(context: deterministic::Context, partition_prefix: String) -> CurrentTest {
135        let cfg = fixed_config::<OneCap>(&partition_prefix, &context);
136        CurrentTest::init(context, cfg).await.unwrap()
137    }
138
139    #[test_traced("DEBUG")]
140    pub fn test_current_db_verify_proof_over_bits_in_uncommitted_chunk() {
141        shared::test_verify_proof_over_bits_in_uncommitted_chunk(open_db);
142    }
143
144    #[test_traced("DEBUG")]
145    pub fn test_current_db_range_proofs() {
146        shared::test_range_proofs(open_db);
147    }
148
149    /// Regression test: requesting a range proof for a location in a pruned bitmap chunk
150    /// must return `Error::OperationPruned`, not panic in the bitmap accessor.
151    #[test_traced("DEBUG")]
152    pub fn test_range_proof_returns_error_on_pruned_chunks() {
153        let executor = deterministic::Runner::default();
154        executor.start(|context| async move {
155            let partition = "range-proofs-pruned".to_string();
156            let mut db = open_db(context.child("db"), partition).await;
157
158            let chunk_bits = BitMap::<32>::CHUNK_SIZE_BITS;
159
160            // Repeatedly update the same key to generate many inactive operations,
161            // pushing the inactivity floor past at least one full bitmap chunk.
162            let key = Sha256::fill(0x11);
163            for i in 0..chunk_bits + 10 {
164                let value = Sha256::hash(&i.to_be_bytes());
165                let merkleized = db
166                    .new_batch()
167                    .write(key, Some(value))
168                    .merkleize(&db, None)
169                    .await
170                    .unwrap();
171                db.apply_batch(merkleized).await.unwrap();
172            }
173
174            // Prune the database
175            db.prune(db.sync_boundary()).await.unwrap();
176
177            assert!(
178                db.any.bitmap.pruned_chunks() > 0,
179                "expected at least one pruned chunk"
180            );
181
182            // Requesting a range proof at location 0 (in the pruned range) should return
183            // OperationPruned, not panic.
184            let result = db.range_proof(Location::new(0), NZU64!(1)).await;
185            assert!(
186                matches!(result, Err(Error::OperationPruned(_))),
187                "expected OperationPruned, got {result:?}"
188            );
189
190            db.destroy().await.unwrap();
191        });
192    }
193
194    #[test_traced("DEBUG")]
195    pub fn test_current_db_key_value_proof() {
196        shared::test_key_value_proof(open_db);
197    }
198
199    #[test_traced("WARN")]
200    pub fn test_current_db_proving_repeated_updates() {
201        shared::test_proving_repeated_updates(open_db);
202    }
203
204    #[test_traced("DEBUG")]
205    pub fn test_current_db_exclusion_proofs() {
206        shared::test_exclusion_proofs(open_db);
207    }
208
209    crate::qmdb::current::tests::staged_merkleize_parity_test!(
210        test_current_ordered_fixed_staged_merkleize_parity,
211        open_db
212    );
213}
commonware_storage/qmdb/current/ordered/fixed.rs

commonware_storage/qmdb/current/ordered/
fixed.rs
