commonware_storage/qmdb/keyless/
variable.rs

1//! A keyless authenticated database for variable-length data.
2//!
3//! For fixed-size values, use [super::fixed].
4
5use crate::{
6    Context,
7    journal::{
8        authenticated,
9        contiguous::variable::{self, Config as JournalConfig},
10    },
11    merkle::Family,
12    qmdb::{
13        Error, ROOT_BAGGING,
14        any::value::{VariableEncoding, VariableValue},
15        keyless::operation::Operation as BaseOperation,
16        operation::Committable,
17    },
18};
19use commonware_codec::Read;
20use commonware_cryptography::Hasher;
21use commonware_parallel::Strategy;
22
23/// Keyless operation for variable-length values.
24pub type Operation<F, V> = BaseOperation<F, VariableEncoding<V>>;
25
26/// A keyless authenticated database for variable-length data.
27pub type Db<F, E, V, H, S> =
28    super::Keyless<F, E, VariableEncoding<V>, variable::Journal<E, Operation<F, V>>, H, S>;
29
30/// A compact keyless authenticated db for variable-length data.
31pub type CompactDb<F, E, V, H, C, S> = super::CompactDb<F, E, VariableEncoding<V>, H, C, S>;
32
33type Journal<F, E, V, H, S> =
34    authenticated::Journal<F, E, variable::Journal<E, Operation<F, V>>, H, S>;
35
36/// Configuration for a variable-size [keyless](super) authenticated db.
37pub type Config<C, S> = super::Config<JournalConfig<C>, S>;
38
39/// Configuration for a variable-size [keyless](super) compact db.
40pub type CompactConfig<C, S> = super::CompactConfig<C, S>;
41
42impl<F: Family, E: Context, V: VariableValue, H: Hasher, S: Strategy> Db<F, E, V, H, S> {
43    /// Returns a [Db] initialized from `cfg`. Any uncommitted operations will be
44    /// discarded and the state of the db will be as of the last committed operation.
45    pub async fn init(
46        context: E,
47        cfg: Config<<Operation<F, V> as Read>::Cfg, S>,
48    ) -> Result<Self, Error<F>> {
49        let journal: Journal<F, E, V, H, S> = Journal::new(
50            context.child("journal"),
51            cfg.merkle,
52            cfg.log,
53            Operation::<F, V>::is_commit,
54            ROOT_BAGGING,
55        )
56        .await?;
57        Self::init_from_journal(journal, context).await
58    }
59}
60
61impl<
62    F: Family,
63    E: Context,
64    V: VariableValue,
65    H: Hasher,
66    C: Clone + Send + Sync + 'static,
67    S: Strategy,
68> CompactDb<F, E, V, H, C, S>
69where
70    Operation<F, V>: Read<Cfg = C>,
71{
72    /// Returns a [CompactDb] initialized from `cfg`.
73    pub async fn init(context: E, cfg: CompactConfig<C, S>) -> Result<Self, Error<F>> {
74        let merkle = crate::merkle::compact::Merkle::new(cfg.strategy);
75        Self::init_from_merkle(
76            merkle,
77            context.child("witness"),
78            cfg.witness,
79            cfg.commit_codec_config,
80        )
81        .await
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88    use crate::{
89        merkle::{mmb, mmr},
90        qmdb::keyless::tests::{self, keyless_tests},
91    };
92    use commonware_cryptography::Sha256;
93    use commonware_macros::{boxed, test_traced};
94    use commonware_parallel::Sequential;
95    use commonware_runtime::{
96        BufferPooler, Runner as _, Supervisor as _, buffer::paged::CacheRef, deterministic,
97    };
98    use commonware_utils::{NZU16, NZU64, NZUsize};
99    use std::num::{NonZeroU16, NonZeroUsize};
100
101    // Use some weird sizes here to test boundary conditions.
102    const PAGE_SIZE: NonZeroU16 = NZU16!(101);
103    const PAGE_CACHE_SIZE: NonZeroUsize = NZUsize!(11);
104
105    fn db_config(
106        suffix: &str,
107        pooler: &impl BufferPooler,
108    ) -> Config<(commonware_codec::RangeCfg<usize>, ()), Sequential> {
109        let page_cache = CacheRef::from_pooler(pooler, PAGE_SIZE, PAGE_CACHE_SIZE);
110        Config {
111            merkle: crate::merkle::full::Config {
112                journal_partition: format!("journal-{suffix}"),
113                metadata_partition: format!("metadata-{suffix}"),
114                items_per_blob: NZU64!(11),
115                write_buffer: NZUsize!(1024),
116                replay_buffer: NZUsize!(1024),
117                strategy: Sequential,
118                page_cache: page_cache.clone(),
119            },
120            log: JournalConfig {
121                partition: format!("log-journal-{suffix}"),
122                items_per_section: NZU64!(7),
123                compression: None,
124                codec_config: ((0..=10000).into(), ()),
125                page_cache,
126                write_buffer: NZUsize!(1024),
127                replay_buffer: NZUsize!(1024),
128            },
129        }
130    }
131
132    type TestDb<F> = Db<F, deterministic::Context, Vec<u8>, Sha256, Sequential>;
133    type TestCompactDb<F> = CompactDb<
134        F,
135        deterministic::Context,
136        Vec<u8>,
137        Sha256,
138        (commonware_codec::RangeCfg<usize>, ()),
139        Sequential,
140    >;
141
142    /// Return a [Db] database initialized with a fixed config.
143    async fn open_db<F: Family>(context: deterministic::Context) -> TestDb<F> {
144        open_db_with_suffix("partition", context).await
145    }
146
147    async fn open_db_with_suffix<F: Family>(
148        suffix: &str,
149        context: deterministic::Context,
150    ) -> TestDb<F> {
151        let cfg = db_config(suffix, &context);
152        TestDb::init(context, cfg).await.unwrap()
153    }
154
155    async fn open_compact<F: crate::merkle::Family>(
156        context: deterministic::Context,
157    ) -> TestCompactDb<F> {
158        let cfg = CompactConfig {
159            strategy: Sequential,
160            witness: crate::journal::contiguous::variable::Config {
161                partition: "compact-keyless-variable-witness".into(),
162                items_per_section: NZU64!(64),
163                compression: None,
164                codec_config: (),
165                page_cache: CacheRef::from_pooler(&context, PAGE_SIZE, PAGE_CACHE_SIZE),
166                write_buffer: NZUsize!(1024),
167                replay_buffer: NZUsize!(1024),
168            },
169            commit_codec_config: ((0..=10000usize).into(), ()),
170        };
171        TestCompactDb::init(context, cfg).await.unwrap()
172    }
173
174    fn reopen<F: Family>() -> tests::Reopen<TestDb<F>> {
175        Box::new(|ctx| Box::pin(open_db(ctx)))
176    }
177
178    keyless_tests! {
179        test_keyless_variable_empty => run_empty, reopen_indexed;
180        test_keyless_variable_build_basic => run_build_basic, reopen_indexed;
181        test_keyless_variable_recovery => run_recovery, reopen_indexed;
182        test_keyless_variable_non_empty_recovery => run_non_empty_recovery, reopen_indexed;
183        test_keyless_variable_proof => run_proof, db;
184        test_keyless_variable_proof_comprehensive => run_proof_comprehensive, db;
185        test_keyless_variable_proof_with_pruning => run_proof_with_pruning, reopen_indexed;
186        test_keyless_variable_empty_db_recovery => run_empty_db_recovery, reopen_indexed;
187        test_keyless_variable_replay_with_trailing_appends => run_replay_with_trailing_appends, reopen_indexed;
188        test_keyless_variable_get_out_of_bounds => run_get_out_of_bounds, db;
189        test_keyless_variable_metadata => run_metadata, db;
190        test_keyless_variable_pruning => run_pruning, reopen;
191        test_keyless_variable_batch_get => run_batch_get, db;
192        test_keyless_variable_batch_stacked_get => run_batch_stacked_get, db;
193        test_keyless_variable_batch_speculative_root => run_batch_speculative_root, db;
194        test_keyless_variable_merkleized_batch_get => run_merkleized_batch_get, db;
195        test_keyless_variable_batch_chained => run_batch_chained, db;
196        test_keyless_variable_operations_match_applied_log => run_operations_match_applied_log, db;
197        test_keyless_variable_batch_chained_apply_sequential => run_batch_chained_apply_sequential, db;
198        test_keyless_variable_batch_many_sequential => run_batch_many_sequential, db;
199        test_keyless_variable_batch_empty => run_batch_empty, db;
200        test_keyless_variable_batch_chained_merkleized_get => run_batch_chained_merkleized_get, db;
201        test_keyless_variable_batch_large => run_batch_large, db;
202        test_keyless_variable_stale_batch => run_stale_batch, reopen;
203        test_keyless_variable_stale_batch_chained => run_stale_batch_chained, db;
204        test_keyless_variable_sequential_commit_parent_then_child => run_sequential_commit_parent_then_child, db;
205        test_keyless_variable_stale_batch_child_before_parent => run_stale_batch_child_before_parent, db;
206        test_keyless_variable_to_batch => run_to_batch, db;
207        test_keyless_variable_child_root_matches_pending_and_committed => run_child_root_matches_pending_and_committed, db;
208        test_keyless_variable_rewind_recovery => run_rewind_recovery, reopen;
209        test_keyless_variable_rewind_pruned_target_errors => run_rewind_pruned_target_errors, reopen;
210        test_keyless_variable_floor_tracking => run_floor_tracking, reopen_indexed;
211        test_keyless_variable_floor_regression_rejected => run_floor_regression_rejected, reopen;
212        test_keyless_variable_floor_beyond_commit_loc_rejected => run_floor_beyond_commit_loc_rejected, reopen;
213        test_keyless_variable_rewind_restores_floor => run_rewind_restores_floor, db;
214        test_keyless_variable_floor_at_commit_loc_accepted => run_floor_at_commit_loc_accepted, db;
215        test_keyless_variable_rewind_after_reopen_with_floor => run_rewind_after_reopen_with_floor, reopen_indexed;
216        test_keyless_variable_ancestor_floor_regression_rejected => run_ancestor_floor_regression_rejected, reopen;
217        test_keyless_variable_ancestor_floor_beyond_commit_loc_rejected => run_ancestor_floor_beyond_commit_loc_rejected, db;
218        test_keyless_variable_chained_apply_with_valid_floors_succeeds => run_chained_apply_with_valid_floors_succeeds, db;
219        test_keyless_variable_single_commit_live_set => run_single_commit_live_set, reopen_indexed;
220        test_keyless_variable_commit_after_sync_recovery => run_commit_after_sync_recovery, reopen_indexed;
221        test_keyless_variable_get_many => run_get_many, db;
222        test_keyless_variable_partial_ancestor_commit => run_partial_ancestor_commit, db;
223        test_keyless_variable_delayed_merkleize_after_ancestor_apply => run_delayed_merkleize_after_ancestor_apply, db;
224    }
225
226    /// Regression: when pruning leaves `bounds.start` mid-blob ahead of the first retained commit,
227    /// `historical_proof` for sizes in that leading interval must report `HistoricalFloorPruned`
228    /// (the floor metadata is gone) rather than the misleading `UnexpectedData` (which sounds like
229    /// data corruption).
230    ///
231    /// Items_per_section=7 with batches of 3 appends + 1 commit places commits at locations 0, 4,
232    /// 8, 12, .... Pruning to loc=8 removes blob 0 (end=7 <=
233    /// 8) and retains blob 1 ([7, 14)). `bounds.start = 7` is a non-commit op (an Append), and the
234    /// previous commit at location 4 was pruned. `historical_proof(op_count=8, ...)` asks for the
235    /// state just before the first retained commit, which has no retained governing floor.
236    #[test_traced("INFO")]
237    fn test_keyless_variable_historical_proof_floor_pruned() {
238        use crate::merkle::Location;
239        deterministic::Runner::default().start(|ctx| async move {
240            let mut db = open_db::<mmr::Family>(ctx.child("db")).await;
241
242            // Build commits at 0, 4, 8, 12, ... (3 appends + 1 commit per batch).
243            for batch_idx in 0u64..15 {
244                let mut batch = db.new_batch();
245                for j in 0..3 {
246                    batch =
247                        batch.append(<Vec<u8> as crate::qmdb::keyless::tests::TestValue>::make(
248                            batch_idx * 10 + j,
249                        ));
250                }
251                let new_commit_loc = db.last_commit_loc() + 1 + 3;
252                let merkleized = batch.merkleize(&db, None, new_commit_loc).await;
253                (db, _) = db.apply_batch(merkleized).await.unwrap();
254            }
255
256            // Prune to loc=8: blob 0 ([0,7)) end=7 <= 8 -> pruned. bounds.start = 7, first retained
257            // commit is at 8.
258            let db = db.prune(Location::new(8)).await.unwrap();
259            let bounds = db.bounds();
260            assert_eq!(*bounds.start, 7);
261
262            // op_count = first retained commit (= state just before that commit). Expected:
263            // HistoricalFloorPruned, NOT UnexpectedData.
264            let result = db
265                .historical_proof(Location::new(8), bounds.start, NZU64!(5))
266                .await;
267            assert!(
268                !matches!(result, Err(Error::UnexpectedData(_))),
269                "must not surface as UnexpectedData; got {result:?}",
270            );
271            assert!(
272                matches!(result, Err(Error::HistoricalFloorPruned(loc)) if loc == Location::new(8)),
273                "expected HistoricalFloorPruned(8), got {result:?}",
274            );
275
276            // Sanity: a commit-boundary size whose floor is retained still works. First retained
277            // commit at 8 declares some floor; op_count=9 is the post-commit size whose governing
278            // floor is the one declared at op 8.
279            db.historical_proof(Location::new(9), Location::new(8), NZU64!(1))
280                .await
281                .expect("commit-boundary historical_proof should succeed");
282
283            db.destroy().await.unwrap();
284        });
285    }
286
287    #[boxed]
288    async fn assert_compact_root_compatibility<F: crate::merkle::Family>(
289        ctx: deterministic::Context,
290    ) {
291        let db = open_db::<F>(ctx.child("db")).await;
292        let compact = open_compact::<F>(ctx.child("compact")).await;
293        assert_eq!(db.root(), compact.root());
294
295        let v1 = b"hello".to_vec();
296        let v2 = b"world".to_vec();
297        let metadata = b"metadata".to_vec();
298
299        let floor = db.inactivity_floor_loc();
300        let retained = db
301            .new_batch()
302            .append(v1.clone())
303            .append(v2.clone())
304            .merkleize(&db, Some(metadata.clone()), floor)
305            .await;
306        let compact_batch = compact
307            .new_batch()
308            .append(v1)
309            .append(v2)
310            .merkleize(&compact, Some(metadata.clone()), floor)
311            .await;
312
313        assert_eq!(retained.root(), compact_batch.root());
314
315        let (db, _) = db.apply_batch(retained).await.unwrap();
316        let (compact, _) = compact.apply_batch(compact_batch).await.unwrap();
317        let db = db.commit().await.unwrap();
318        let compact = compact.sync().await.unwrap();
319
320        assert_eq!(db.root(), compact.root());
321        assert_eq!(compact.get_metadata(), Some(metadata.clone()));
322
323        drop(compact);
324        let reopened = open_compact::<F>(ctx.child("reopen")).await;
325        assert_eq!(db.root(), reopened.root());
326        assert_eq!(reopened.get_metadata(), Some(metadata));
327
328        reopened.destroy().await.unwrap();
329        db.destroy().await.unwrap();
330    }
331
332    #[test_traced("INFO")]
333    fn test_keyless_variable_compact_root_compatibility() {
334        deterministic::Runner::default().start(|ctx| async move {
335            assert_compact_root_compatibility::<mmr::Family>(ctx).await;
336        });
337    }
338
339    #[test_traced("INFO")]
340    fn test_keyless_variable_compact_root_compatibility_mmb() {
341        deterministic::Runner::default().start(|ctx| async move {
342            assert_compact_root_compatibility::<mmb::Family>(ctx).await;
343        });
344    }
345
346    #[test_traced("INFO")]
347    fn test_keyless_variable_floor_changes_root_mmb() {
348        deterministic::Runner::default().start(|ctx| async move {
349            let db_a = open_db_with_suffix::<mmb::Family>("root-a", ctx.child("a")).await;
350            let db_b = open_db_with_suffix::<mmb::Family>("root-b", ctx.child("b")).await;
351            tests::run_floor_changes_root(db_a, db_b).await;
352        });
353    }
354
355    #[test_traced("INFO")]
356    fn test_keyless_variable_floor_changes_root() {
357        deterministic::Runner::default().start(|ctx| async move {
358            let db_a = open_db_with_suffix::<mmr::Family>("root-a", ctx.child("a")).await;
359            let db_b = open_db_with_suffix::<mmr::Family>("root-b", ctx.child("b")).await;
360            tests::run_floor_changes_root(db_a, db_b).await;
361        });
362    }
363
364    fn is_send<T: Send>(_: T) {}
365
366    #[allow(dead_code)]
367    fn assert_db_futures_are_send(
368        db: TestDb<mmr::Family>,
369        loc: crate::merkle::Location<mmr::Family>,
370    ) {
371        is_send(db.get_metadata());
372        is_send(db.proof(loc, NZU64!(1)));
373        is_send(db.get(loc));
374        is_send(db.sync());
375    }
376
377    #[allow(dead_code)]
378    fn assert_rewind_is_send(db: TestDb<mmr::Family>, loc: crate::merkle::Location<mmr::Family>) {
379        is_send(db.rewind(loc));
380    }
381}
commonware_storage/qmdb/keyless/variable.rs

commonware_storage/qmdb/keyless/
variable.rs
