commonware_storage/qmdb/current/unordered/
variable.rs

1//! An _unordered_ variant of a [crate::qmdb::current] authenticated database for variable-size
2//! values.
3//!
4//! This variant does not maintain key ordering, so it cannot generate exclusion proofs. Use
5//! [crate::qmdb::current::ordered::variable] if exclusion proofs are required.
6//!
7//! See [Db] for the main database type.
8
9pub use super::db::KeyValueProof;
10use crate::{
11    Context,
12    index::unordered::Index,
13    journal::contiguous::variable::Journal,
14    merkle::{Graftable, Location},
15    qmdb::{
16        Error,
17        any::{VariableValue, unordered::variable::Operation, value::VariableEncoding},
18        current::VariableConfig as Config,
19        operation::Key,
20    },
21    translator::Translator,
22};
23use commonware_codec::Read;
24use commonware_cryptography::Hasher;
25use commonware_parallel::Strategy;
26use commonware_runtime::Spawner;
27
28pub type Db<F, E, K, V, H, T, const N: usize, S> = super::db::Db<
29    F,
30    E,
31    Journal<E, Operation<F, K, V>>,
32    K,
33    VariableEncoding<V>,
34    Index<T, Location<F>>,
35    H,
36    N,
37    S,
38>;
39
40impl<
41    F: Graftable,
42    E: Context + Spawner,
43    K: Key,
44    V: VariableValue,
45    H: Hasher,
46    T: Translator,
47    const N: usize,
48    S: Strategy,
49> Db<F, E, K, V, H, T, N, S>
50where
51    Operation<F, K, V>: Read,
52{
53    /// Initializes a [Db] from the given `config`.
54    /// The configured [`Strategy`] is used to parallelize merkleization.
55    pub async fn init(
56        context: E,
57        config: Config<T, <Operation<F, K, V> as Read>::Cfg, S>,
58    ) -> Result<Self, Error<F>> {
59        crate::qmdb::current::init(context, config).await
60    }
61}
62
63pub mod partitioned {
64    //! A variant of [super] that uses a partitioned index for the snapshot.
65
66    use super::*;
67    use crate::index::partitioned::unordered::Index;
68
69    /// A partitioned variant of [super::Db].
70    ///
71    /// The const generic `P` specifies the number of prefix bytes used for partitioning:
72    /// - `P = 1`: 256 partitions
73    /// - `P = 2`: 65,536 partitions
74    /// - `P = 3`: ~16 million partitions
75    pub type Db<F, E, K, V, H, T, const P: usize, const N: usize, S> =
76        crate::qmdb::current::unordered::db::Db<
77            F,
78            E,
79            Journal<E, Operation<F, K, V>>,
80            K,
81            VariableEncoding<V>,
82            Index<T, Location<F>, P>,
83            H,
84            N,
85            S,
86        >;
87
88    impl<
89        F: Graftable,
90        E: Context + Spawner,
91        K: Key,
92        V: VariableValue,
93        H: Hasher,
94        T: Translator,
95        const P: usize,
96        const N: usize,
97        S: Strategy,
98    > Db<F, E, K, V, H, T, P, N, S>
99    where
100        Operation<F, K, V>: Read,
101    {
102        /// Initializes a [Db] from the given `config`.
103        /// The configured [`Strategy`] is used to parallelize merkleization.
104        pub async fn init(
105            context: E,
106            config: Config<T, <Operation<F, K, V> as Read>::Cfg, S, core::num::NonZeroUsize>,
107        ) -> Result<Self, Error<F>> {
108            crate::qmdb::current::init(context, config).await
109        }
110    }
111}
112
113#[cfg(test)]
114mod test {
115    use super::*;
116    use crate::{
117        mmr,
118        qmdb::current::{tests::variable_config, unordered::tests as shared},
119        translator::TwoCap,
120    };
121    use commonware_cryptography::{Sha256, sha256::Digest};
122    use commonware_macros::test_traced;
123    use commonware_runtime::{Runner as _, Supervisor as _, deterministic};
124
125    /// A type alias for the concrete [Db] type used in these unit tests.
126    type CurrentTest = Db<
127        mmr::Family,
128        deterministic::Context,
129        Digest,
130        Digest,
131        Sha256,
132        TwoCap,
133        32,
134        commonware_parallel::Sequential,
135    >;
136
137    /// Return a [Db] database initialized with a variable config.
138    async fn open_db(context: deterministic::Context, partition_prefix: String) -> CurrentTest {
139        let cfg = variable_config::<TwoCap>(&partition_prefix, &context);
140        CurrentTest::init(context, cfg).await.unwrap()
141    }
142
143    #[test_traced("DEBUG")]
144    pub fn test_current_db_verify_proof_over_bits_in_uncommitted_chunk() {
145        shared::test_verify_proof_over_bits_in_uncommitted_chunk(open_db);
146    }
147
148    #[test_traced("DEBUG")]
149    pub fn test_current_db_range_proofs() {
150        shared::test_range_proofs(open_db);
151    }
152
153    #[test_traced("DEBUG")]
154    pub fn test_current_db_key_value_proof() {
155        shared::test_key_value_proof(open_db);
156    }
157
158    #[test_traced("WARN")]
159    pub fn test_current_db_proving_repeated_updates() {
160        shared::test_proving_repeated_updates(open_db);
161    }
162
163    /// A [Db] keyed by variable-length byte keys.
164    type VecKeyTest = Db<
165        mmr::Family,
166        deterministic::Context,
167        Vec<u8>,
168        Digest,
169        Sha256,
170        TwoCap,
171        32,
172        commonware_parallel::Sequential,
173    >;
174
175    #[test_traced("WARN")]
176    pub fn test_current_db_variable_length_keys() {
177        let executor = deterministic::Runner::default();
178        executor.start(|context| async move {
179            // Configure the operation codec for variable-length keys.
180            let base = variable_config::<TwoCap>("vec-keys", &context);
181            let cfg = crate::qmdb::current::VariableConfig {
182                merkle_config: base.merkle_config.clone(),
183                journal_config: crate::journal::contiguous::variable::Config {
184                    partition: base.journal_config.partition.clone(),
185                    items_per_section: base.journal_config.items_per_section,
186                    compression: None,
187                    codec_config: (((0..).into(), ()), ()),
188                    page_cache: base.journal_config.page_cache.clone(),
189                    write_buffer: base.journal_config.write_buffer,
190                    replay_buffer: base.journal_config.replay_buffer,
191                },
192                grafted_metadata_partition: base.grafted_metadata_partition.clone(),
193                translator: TwoCap,
194                init_cache_size: base.init_cache_size,
195                init_buffer: base.init_buffer,
196                init_concurrency: (),
197            };
198
199            // Commit a value and verify its lookup and proof under a variable-length key.
200            let db = VecKeyTest::init(context.child("first"), cfg.clone())
201                .await
202                .unwrap();
203            let key = b"variable-length-key".to_vec();
204            let value = Sha256::hash(&[b"value"]);
205            let merkleized = db
206                .new_batch()
207                .write(key.clone(), Some(value))
208                .merkleize(&db, None)
209                .await
210                .unwrap();
211            let (db, _) = db.apply_batch(merkleized).await.unwrap();
212            let db = db.commit().await.unwrap();
213            assert_eq!(db.get(&key).await.unwrap().unwrap(), value);
214            let root = db.root();
215            let proof = db.key_value_proof(key.clone()).await.unwrap();
216            assert!(VecKeyTest::verify_key_value_proof(
217                key.clone(),
218                value,
219                &proof,
220                &root
221            ));
222            drop(db);
223
224            // Reopen the database and verify the committed root and value.
225            let db = VecKeyTest::init(context.child("second"), cfg)
226                .await
227                .unwrap();
228            assert_eq!(db.root(), root);
229            assert_eq!(db.get(&key).await.unwrap().unwrap(), value);
230            db.destroy().await.unwrap();
231        });
232    }
233}
commonware_storage/qmdb/current/unordered/variable.rs

commonware_storage/qmdb/current/unordered/
variable.rs
