commonware_storage/qmdb/current/ordered/
variable.rs

1//! An _ordered_ variant of a [crate::qmdb::current] authenticated database for variable-size values
2//!
3//! This variant maintains the lexicographic-next active key for each active key, enabling exclusion
4//! proofs (proving a key is currently inactive). Use [crate::qmdb::current::unordered::variable] if
5//! exclusion proofs are not needed.
6//!
7//! See [Db] for the main database type and [super::ExclusionProof] for proving key inactivity.
8
9pub use super::db::KeyValueProof;
10use crate::{
11    bitmap::MerkleizedBitMap,
12    journal::contiguous::variable::Journal,
13    mmr::{Location, StandardHasher},
14    qmdb::{
15        any::{
16            ordered::variable::{Db as AnyDb, Operation},
17            value::VariableEncoding,
18            VariableValue,
19        },
20        current::{
21            db::{merkleize_grafted_bitmap, root, Merkleized},
22            VariableConfig as Config,
23        },
24        Durable, Error,
25    },
26    translator::Translator,
27};
28use commonware_codec::{FixedSize, Read};
29use commonware_cryptography::{DigestOf, Hasher};
30use commonware_runtime::{Clock, Metrics, Storage as RStorage};
31use commonware_utils::Array;
32
33pub type Db<E, K, V, H, T, const N: usize, S = Merkleized<DigestOf<H>>, D = Durable> =
34    super::db::Db<E, Journal<E, Operation<K, V>>, K, VariableEncoding<V>, H, T, N, S, D>;
35
36// Functionality for the Merkleized state - init only.
37impl<
38        E: RStorage + Clock + Metrics,
39        K: Array,
40        V: VariableValue,
41        H: Hasher,
42        T: Translator,
43        const N: usize,
44    > Db<E, K, V, H, T, N, Merkleized<DigestOf<H>>, Durable>
45where
46    Operation<K, V>: Read,
47{
48    /// Initializes a [Db] from the given `config`. Leverages parallel Merkleization to initialize
49    /// the bitmap MMR if a thread pool is provided.
50    pub async fn init(
51        context: E,
52        config: Config<T, <Operation<K, V> as Read>::Cfg>,
53    ) -> Result<Self, Error> {
54        // TODO: Re-evaluate assertion placement after `generic_const_exprs` is stable.
55        const {
56            // A compile-time assertion that the chunk size is some multiple of digest size. A
57            // multiple of 1 is optimal with respect to proof size, but a higher multiple allows for
58            // a smaller (RAM resident) merkle tree over the structure.
59            assert!(
60                N.is_multiple_of(H::Digest::SIZE),
61                "chunk size must be some multiple of the digest size",
62            );
63            // A compile-time assertion that chunk size is a power of 2, which is necessary to allow
64            // the status bitmap tree to be aligned with the underlying operations MMR.
65            assert!(N.is_power_of_two(), "chunk size must be a power of 2");
66        }
67
68        let thread_pool = config.thread_pool.clone();
69        let bitmap_metadata_partition = config.bitmap_metadata_partition.clone();
70
71        let mut hasher = StandardHasher::<H>::new();
72        let mut status = MerkleizedBitMap::init(
73            context.with_label("bitmap"),
74            &bitmap_metadata_partition,
75            thread_pool,
76            &mut hasher,
77        )
78        .await?
79        .into_dirty();
80
81        // Initialize the anydb with a callback that initializes the status bitmap.
82        let last_known_inactivity_floor = Location::new_unchecked(status.len());
83        let any = AnyDb::init_with_callback(
84            context.with_label("any"),
85            config.into(),
86            Some(last_known_inactivity_floor),
87            |append: bool, loc: Option<Location>| {
88                status.push(append);
89                if let Some(loc) = loc {
90                    status.set_bit(*loc, false);
91                }
92            },
93        )
94        .await?;
95
96        let status = merkleize_grafted_bitmap(&mut hasher, status, &any.log.mmr).await?;
97
98        // Compute and cache the root
99        let root = root(&mut hasher, &status, &any.log.mmr).await?;
100
101        Ok(Self {
102            any,
103            status,
104            state: Merkleized { root },
105        })
106    }
107}
108
109#[cfg(test)]
110mod test {
111    use crate::{
112        bitmap::MerkleizedBitMap,
113        kv::tests::{assert_batchable, assert_deletable, assert_gettable, assert_send},
114        mmr::{hasher::Hasher as _, Location, StandardHasher},
115        qmdb::{
116            any::ordered::variable::Operation,
117            current::{
118                db::{Merkleized, Unmerkleized},
119                ordered::{db::KeyValueProof, variable::Db},
120                proof::{OperationProof, RangeProof},
121                tests::{self, apply_random_ops},
122                VariableConfig as Config,
123            },
124            store::{
125                batch_tests,
126                tests::{assert_log_store, assert_merkleized_store, assert_prunable_store},
127                LogStore,
128            },
129            Durable, Error, NonDurable,
130        },
131        translator::OneCap,
132    };
133    use commonware_cryptography::{sha256::Digest, Hasher as _, Sha256};
134    use commonware_macros::test_traced;
135    use commonware_runtime::{buffer::paged::CacheRef, deterministic, Runner as _};
136    use commonware_utils::{NZUsize, NZU16, NZU64};
137    use rand::RngCore;
138    use std::num::{NonZeroU16, NonZeroUsize};
139
140    const PAGE_SIZE: NonZeroU16 = NZU16!(88);
141    const PAGE_CACHE_SIZE: NonZeroUsize = NZUsize!(8);
142
143    fn current_db_config(partition_prefix: &str) -> Config<OneCap, ()> {
144        Config {
145            mmr_journal_partition: format!("{partition_prefix}_journal_partition"),
146            mmr_metadata_partition: format!("{partition_prefix}_metadata_partition"),
147            mmr_items_per_blob: NZU64!(11),
148            mmr_write_buffer: NZUsize!(1024),
149            log_partition: format!("{partition_prefix}_log_partition"),
150            log_items_per_blob: NZU64!(7),
151            log_write_buffer: NZUsize!(1024),
152            log_compression: None,
153            log_codec_config: (),
154            bitmap_metadata_partition: format!("{partition_prefix}_bitmap_metadata_partition"),
155            translator: OneCap,
156            thread_pool: None,
157            page_cache: CacheRef::new(PAGE_SIZE, PAGE_CACHE_SIZE),
158        }
159    }
160
161    /// A type alias for the concrete [Db] type used in these unit tests (Merkleized, Durable).
162    type CleanCurrentTest =
163        Db<deterministic::Context, Digest, Digest, Sha256, OneCap, 32, Merkleized<Digest>, Durable>;
164
165    /// A type alias for the Mutable variant of CurrentTest (Unmerkleized, NonDurable state).
166    type MutableCurrentTest =
167        Db<deterministic::Context, Digest, Digest, Sha256, OneCap, 32, Unmerkleized, NonDurable>;
168
169    /// Return a [Db] database initialized with a fixed config.
170    async fn open_db(
171        context: deterministic::Context,
172        partition_prefix: String,
173    ) -> CleanCurrentTest {
174        CleanCurrentTest::init(context, current_db_config(&partition_prefix))
175            .await
176            .unwrap()
177    }
178
179    #[test_traced("DEBUG")]
180    pub fn test_current_db_build_small_close_reopen() {
181        super::super::tests::test_build_small_close_reopen::<CleanCurrentTest, _, _>(open_db);
182    }
183
184    #[test_traced("WARN")]
185    fn test_current_db_build_big() {
186        // Expected values after commit + merkleize + prune for ordered variant.
187        tests::test_current_db_build_big::<CleanCurrentTest, _, _>(open_db, 4241, 3383);
188    }
189
190    // Test that merkleization state changes don't reset `steps`.
191    #[test_traced("DEBUG")]
192    fn test_current_ordered_variable_db_steps_not_reset() {
193        let executor = deterministic::Runner::default();
194        executor.start(|context| async move {
195            let db = open_db(context, "steps_test".to_string()).await;
196            crate::qmdb::any::test::test_any_db_steps_not_reset(db).await;
197        });
198    }
199
200    /// Build a tiny database and make sure we can't convince the verifier that some old value of a
201    /// key is active. We specifically test over the partial chunk case, since these bits are yet to
202    /// be committed to the underlying MMR.
203    #[test_traced("DEBUG")]
204    pub fn test_current_db_verify_proof_over_bits_in_uncommitted_chunk() {
205        let executor = deterministic::Runner::default();
206        executor.start(|context| async move {
207            let mut hasher = StandardHasher::<Sha256>::new();
208            let partition = "build_small".to_string();
209            let mut db = open_db(context, partition).await.into_mutable();
210
211            // Add one key.
212            let k = Sha256::fill(0x01);
213            let v1 = Sha256::fill(0xA1);
214            db.update(k, v1).await.unwrap();
215            let (db, _) = db.commit(None).await.unwrap();
216            let db = db.into_merkleized().await.unwrap();
217
218            let (_, op_loc) = db.any.get_with_loc(&k).await.unwrap().unwrap();
219            let proof = db.key_value_proof(hasher.inner(), k).await.unwrap();
220
221            // Proof should be verifiable against current root.
222            let root = db.root();
223            assert!(CleanCurrentTest::verify_key_value_proof(
224                hasher.inner(),
225                k,
226                v1,
227                &proof,
228                &root,
229            ));
230
231            let v2 = Sha256::fill(0xA2);
232            // Proof should not verify against a different value.
233            assert!(!CleanCurrentTest::verify_key_value_proof(
234                hasher.inner(),
235                k,
236                v2,
237                &proof,
238                &root,
239            ));
240            // Proof should not verify against a mangled next_key.
241            let mut mangled_proof = proof.clone();
242            mangled_proof.next_key = Sha256::fill(0xFF);
243            assert!(!CleanCurrentTest::verify_key_value_proof(
244                hasher.inner(),
245                k,
246                v1,
247                &mangled_proof,
248                &root,
249            ));
250
251            // Update the key to a new value (v2), which inactivates the previous operation.
252            let mut db = db.into_mutable();
253            db.update(k, v2).await.unwrap();
254            let (db, _) = db.commit(None).await.unwrap();
255            let db = db.into_merkleized().await.unwrap();
256            let root = db.root();
257
258            // New value should not be verifiable against the old proof.
259            assert!(!CleanCurrentTest::verify_key_value_proof(
260                hasher.inner(),
261                k,
262                v2,
263                &proof,
264                &root,
265            ));
266
267            // But the new value should verify against a new proof.
268            let proof = db.key_value_proof(hasher.inner(), k).await.unwrap();
269            assert!(CleanCurrentTest::verify_key_value_proof(
270                hasher.inner(),
271                k,
272                v2,
273                &proof,
274                &root,
275            ));
276            // Old value will not verify against new proof.
277            assert!(!CleanCurrentTest::verify_key_value_proof(
278                hasher.inner(),
279                k,
280                v1,
281                &proof,
282                &root,
283            ));
284
285            // Create a proof of the now-inactive update operation assigning v1 to k against the
286            // current root.
287            let (p, _, chunks) = db
288                .range_proof(hasher.inner(), op_loc, NZU64!(1))
289                .await
290                .unwrap();
291            let proof_inactive = KeyValueProof {
292                proof: OperationProof {
293                    loc: op_loc,
294                    chunk: chunks[0],
295                    range_proof: p,
296                },
297                next_key: k,
298            };
299            // This proof should verify using verify_range_proof which does not check activity
300            // status.
301            let op = Operation::Update(crate::qmdb::any::ordered::Update {
302                key: k,
303                value: v1,
304                next_key: k,
305            });
306            assert!(CleanCurrentTest::verify_range_proof(
307                hasher.inner(),
308                &proof_inactive.proof.range_proof,
309                proof_inactive.proof.loc,
310                &[op],
311                &[proof_inactive.proof.chunk],
312                &root,
313            ));
314            // But this proof should *not* verify as a key value proof, since verification will see
315            // that the operation is inactive.
316            assert!(!CleanCurrentTest::verify_key_value_proof(
317                hasher.inner(),
318                k,
319                v1,
320                &proof_inactive,
321                &root,
322            ));
323
324            // Attempt #1 to "fool" the verifier:  change the location to that of an active
325            // operation. This should not fool the verifier if we're properly validating the
326            // inclusion of the operation itself, and not just the chunk.
327            let (_, active_loc) = db.any.get_with_loc(&k).await.unwrap().unwrap();
328            // The new location should differ but still be in the same chunk.
329            assert_ne!(active_loc, proof_inactive.proof.loc);
330            assert_eq!(
331                MerkleizedBitMap::<deterministic::Context, Digest, 32>::leaf_pos(*active_loc),
332                MerkleizedBitMap::<deterministic::Context, Digest, 32>::leaf_pos(
333                    *proof_inactive.proof.loc
334                )
335            );
336            let mut fake_proof = proof_inactive.clone();
337            fake_proof.proof.loc = active_loc;
338            assert!(!CleanCurrentTest::verify_key_value_proof(
339                hasher.inner(),
340                k,
341                v1,
342                &fake_proof,
343                &root,
344            ));
345
346            // Attempt #2 to "fool" the verifier: Modify the chunk in the proof info to make it look
347            // like the operation is active by flipping its corresponding bit to 1. This should not
348            // fool the verifier if we are correctly incorporating the partial chunk information
349            // into the root computation.
350            let mut modified_chunk = proof_inactive.proof.chunk;
351            let bit_pos = *proof_inactive.proof.loc;
352            let byte_idx = bit_pos / 8;
353            let bit_idx = bit_pos % 8;
354            modified_chunk[byte_idx as usize] |= 1 << bit_idx;
355
356            let mut fake_proof = proof_inactive.clone();
357            fake_proof.proof.chunk = modified_chunk;
358            assert!(!CleanCurrentTest::verify_key_value_proof(
359                hasher.inner(),
360                k,
361                v1,
362                &fake_proof,
363                &root,
364            ));
365
366            db.destroy().await.unwrap();
367        });
368    }
369
370    #[test_traced("DEBUG")]
371    pub fn test_current_db_range_proofs() {
372        let executor = deterministic::Runner::default();
373        executor.start(|mut context| async move {
374            let partition = "range_proofs".to_string();
375            let mut hasher = StandardHasher::<Sha256>::new();
376            let db = open_db(context.clone(), partition).await;
377            let root = db.root();
378
379            // Empty range proof should not crash or verify, since even an empty db has a single
380            // commit op.
381            let proof = RangeProof {
382                proof: crate::mmr::Proof::default(),
383                partial_chunk_digest: None,
384            };
385            assert!(!CleanCurrentTest::verify_range_proof(
386                hasher.inner(),
387                &proof,
388                Location::new_unchecked(0),
389                &[],
390                &[],
391                &root,
392            ));
393
394            let rng_seed = context.next_u64();
395            let db = apply_random_ops::<CleanCurrentTest>(200, true, rng_seed, db.into_mutable())
396                .await
397                .unwrap();
398            let (db, _) = db.commit(None).await.unwrap();
399            let db = db.into_merkleized().await.unwrap();
400            let root = db.root();
401
402            // Make sure size-constrained batches of operations are provable from the oldest
403            // retained op to tip.
404            let max_ops = 4;
405            let end_loc = db.size();
406            let start_loc = db.any.inactivity_floor_loc();
407
408            for loc in *start_loc..*end_loc {
409                let loc = Location::new_unchecked(loc);
410                let (proof, ops, chunks) = db
411                    .range_proof(hasher.inner(), loc, NZU64!(max_ops))
412                    .await
413                    .unwrap();
414                assert!(
415                    CleanCurrentTest::verify_range_proof(
416                        hasher.inner(),
417                        &proof,
418                        loc,
419                        &ops,
420                        &chunks,
421                        &root
422                    ),
423                    "failed to verify range at start_loc {start_loc}",
424                );
425                // Proof should not verify if we include extra chunks.
426                let mut chunks_with_extra = chunks.clone();
427                chunks_with_extra.push(chunks[chunks.len() - 1]);
428                assert!(!CleanCurrentTest::verify_range_proof(
429                    hasher.inner(),
430                    &proof,
431                    loc,
432                    &ops,
433                    &chunks_with_extra,
434                    &root,
435                ));
436            }
437
438            db.destroy().await.unwrap();
439        });
440    }
441
442    #[test_traced("DEBUG")]
443    pub fn test_current_db_key_value_proof() {
444        let executor = deterministic::Runner::default();
445        executor.start(|mut context| async move {
446            let partition = "range_proofs".to_string();
447            let mut hasher = StandardHasher::<Sha256>::new();
448            let db = open_db(context.clone(), partition.clone())
449                .await
450                .into_mutable();
451            let db = apply_random_ops::<CleanCurrentTest>(500, true, context.next_u64(), db)
452                .await
453                .unwrap();
454            let (db, _) = db.commit(None).await.unwrap();
455            let db = db.into_merkleized().await.unwrap();
456            let root = db.root();
457
458            // Confirm bad keys produce the expected error.
459            let bad_key = Sha256::fill(0xAA);
460            let res = db.key_value_proof(hasher.inner(), bad_key).await;
461            assert!(matches!(res, Err(Error::KeyNotFound)));
462
463            let start = *db.inactivity_floor_loc();
464            for i in start..db.status.len() {
465                if !db.status.get_bit(i) {
466                    continue;
467                }
468                // Found an active operation! Create a proof for its active current key/value if
469                // it's a key-updating operation.
470                let op = db.any.log.read(Location::new_unchecked(i)).await.unwrap();
471                let (key, value) = match op {
472                    Operation::Update(key_data) => (key_data.key, key_data.value),
473                    Operation::CommitFloor(_, _) => continue,
474                    _ => unreachable!("expected update or commit floor operation"),
475                };
476                let proof = db.key_value_proof(hasher.inner(), key).await.unwrap();
477
478                // Proof should validate against the current value and correct root.
479                assert!(CleanCurrentTest::verify_key_value_proof(
480                    hasher.inner(),
481                    key,
482                    value,
483                    &proof,
484                    &root
485                ));
486                // Proof should fail against the wrong value. Use hash instead of fill to ensure
487                // the value differs from any key/value created by TestKey::from_seed (which uses
488                // fill patterns).
489                let wrong_val = Sha256::hash(&[0xFF]);
490                assert!(!CleanCurrentTest::verify_key_value_proof(
491                    hasher.inner(),
492                    key,
493                    wrong_val,
494                    &proof,
495                    &root
496                ));
497                // Proof should fail against the wrong key.
498                let wrong_key = Sha256::hash(&[0xEE]);
499                assert!(!CleanCurrentTest::verify_key_value_proof(
500                    hasher.inner(),
501                    wrong_key,
502                    value,
503                    &proof,
504                    &root
505                ));
506                // Proof should fail against the wrong root.
507                let wrong_root = Sha256::hash(&[0xDD]);
508                assert!(!CleanCurrentTest::verify_key_value_proof(
509                    hasher.inner(),
510                    key,
511                    value,
512                    &proof,
513                    &wrong_root,
514                ));
515                // Proof should fail with the wrong next-key.
516                let mut bad_proof = proof.clone();
517                bad_proof.next_key = wrong_key;
518                assert!(!CleanCurrentTest::verify_key_value_proof(
519                    hasher.inner(),
520                    key,
521                    value,
522                    &bad_proof,
523                    &root,
524                ));
525            }
526
527            db.destroy().await.unwrap();
528        });
529    }
530
531    /// This test builds a random database, and makes sure that its state is correctly restored
532    /// after closing and re-opening.
533    #[test_traced("WARN")]
534    pub fn test_current_db_build_random_close_reopen() {
535        crate::qmdb::current::tests::test_build_random_close_reopen(open_db);
536    }
537
538    /// Repeatedly update the same key to a new value and ensure we can prove its current value
539    /// after each update.
540    #[test_traced("WARN")]
541    pub fn test_current_db_proving_repeated_updates() {
542        let executor = deterministic::Runner::default();
543        executor.start(|context| async move {
544            let mut hasher = StandardHasher::<Sha256>::new();
545            let partition = "build_small".to_string();
546            let mut db = open_db(context, partition).await;
547
548            // Add one key.
549            let k = Sha256::fill(0x00);
550            let mut old_val = Sha256::fill(0x00);
551            for i in 1u8..=255 {
552                let v = Sha256::fill(i);
553                let mut dirty_db = db.into_mutable();
554                dirty_db.update(k, v).await.unwrap();
555                assert_eq!(dirty_db.get(&k).await.unwrap().unwrap(), v);
556                let (dirty_db, _) = dirty_db.commit(None).await.unwrap();
557                let clean_db = dirty_db.into_merkleized().await.unwrap();
558                db = clean_db;
559                let root = db.root();
560
561                // Create a proof for the current value of k.
562                let proof = db.key_value_proof(hasher.inner(), k).await.unwrap();
563                assert!(
564                    CleanCurrentTest::verify_key_value_proof(hasher.inner(), k, v, &proof, &root),
565                    "proof of update {i} failed to verify"
566                );
567                // Ensure the proof does NOT verify if we use the previous value.
568                assert!(
569                    !CleanCurrentTest::verify_key_value_proof(
570                        hasher.inner(),
571                        k,
572                        old_val,
573                        &proof,
574                        &root
575                    ),
576                    "proof of update {i} verified when it should not have"
577                );
578                old_val = v;
579            }
580
581            db.destroy().await.unwrap();
582        });
583    }
584
585    /// This test builds a random database and simulates we can recover from different types of
586    /// failure scenarios.
587    #[test_traced("WARN")]
588    pub fn test_current_db_simulate_write_failures() {
589        crate::qmdb::current::tests::test_simulate_write_failures(open_db);
590    }
591
592    #[test_traced("WARN")]
593    pub fn test_current_db_different_pruning_delays_same_root() {
594        tests::test_different_pruning_delays_same_root::<CleanCurrentTest, _, _>(open_db);
595    }
596
597    #[test_traced("WARN")]
598    pub fn test_current_db_sync_persists_bitmap_pruning_boundary() {
599        tests::test_sync_persists_bitmap_pruning_boundary::<CleanCurrentTest, _, _>(open_db);
600    }
601
602    #[test_traced("DEBUG")]
603    fn test_batch() {
604        batch_tests::test_batch(|mut ctx| async move {
605            let seed = ctx.next_u64();
606            let prefix = format!("current_ordered_variable_batch_{seed}");
607            open_db(ctx, prefix).await.into_mutable()
608        });
609    }
610
611    /// Build a tiny database and confirm exclusion proofs work as expected with variable values.
612    #[test_traced("DEBUG")]
613    pub fn test_current_db_exclusion_proofs() {
614        let executor = deterministic::Runner::default();
615        executor.start(|context| async move {
616            let mut hasher = StandardHasher::<Sha256>::new();
617            let partition = "exclusion_proofs".to_string();
618            let db = open_db(context, partition).await;
619
620            let key_exists_1 = Sha256::fill(0x10);
621
622            // We should be able to prove exclusion for any key against an empty db.
623            let empty_root = db.root();
624            let empty_proof = db
625                .exclusion_proof(hasher.inner(), &key_exists_1)
626                .await
627                .unwrap();
628            assert!(CleanCurrentTest::verify_exclusion_proof(
629                hasher.inner(),
630                &key_exists_1,
631                &empty_proof,
632                &empty_root,
633            ));
634
635            // Add `key_exists_1` and test exclusion proving over the single-key database case.
636            let v1 = Sha256::fill(0xA1);
637            let mut db = db.into_mutable();
638            db.update(key_exists_1, v1).await.unwrap();
639            let (db, _) = db.commit(None).await.unwrap();
640            let db = db.into_merkleized().await.unwrap();
641            let root = db.root();
642
643            // We shouldn't be able to generate an exclusion proof for a key already in the db.
644            let result = db.exclusion_proof(hasher.inner(), &key_exists_1).await;
645            assert!(matches!(result, Err(Error::KeyExists)));
646
647            // Generate some valid exclusion proofs for keys on either side.
648            let greater_key = Sha256::fill(0xFF);
649            let lesser_key = Sha256::fill(0x00);
650            let proof = db
651                .exclusion_proof(hasher.inner(), &greater_key)
652                .await
653                .unwrap();
654            let proof2 = db
655                .exclusion_proof(hasher.inner(), &lesser_key)
656                .await
657                .unwrap();
658
659            // Since there's only one span in the DB, the two exclusion proofs should be identical,
660            // and the proof should verify any key but the one that exists in the db.
661            assert_eq!(proof, proof2);
662            // Any key except the one that exists should verify against this proof.
663            assert!(CleanCurrentTest::verify_exclusion_proof(
664                hasher.inner(),
665                &greater_key,
666                &proof,
667                &root,
668            ));
669            assert!(CleanCurrentTest::verify_exclusion_proof(
670                hasher.inner(),
671                &lesser_key,
672                &proof,
673                &root,
674            ));
675            // Exclusion should fail if we test it on a key that exists.
676            assert!(!CleanCurrentTest::verify_exclusion_proof(
677                hasher.inner(),
678                &key_exists_1,
679                &proof,
680                &root,
681            ));
682
683            // Add a second key and test exclusion proving over the two-key database case.
684            let key_exists_2 = Sha256::fill(0x30);
685            let v2 = Sha256::fill(0xB2);
686
687            let mut db = db.into_mutable();
688            db.update(key_exists_2, v2).await.unwrap();
689            let (db, _) = db.commit(None).await.unwrap();
690            let db = db.into_merkleized().await.unwrap();
691            let root = db.root();
692
693            // Use a lesser/greater key that has a translated-key conflict based
694            // on our use of OneCap translator.
695            let lesser_key = Sha256::fill(0x0F); // < k1=0x10
696            let greater_key = Sha256::fill(0x31); // > k2=0x30
697            let middle_key = Sha256::fill(0x20); // between k1=0x10 and k2=0x30
698            let proof = db
699                .exclusion_proof(hasher.inner(), &greater_key)
700                .await
701                .unwrap();
702            // Test the "cycle around" span. This should prove exclusion of greater_key & lesser
703            // key, but fail on middle_key.
704            assert!(CleanCurrentTest::verify_exclusion_proof(
705                hasher.inner(),
706                &greater_key,
707                &proof,
708                &root,
709            ));
710            assert!(CleanCurrentTest::verify_exclusion_proof(
711                hasher.inner(),
712                &lesser_key,
713                &proof,
714                &root,
715            ));
716            assert!(!CleanCurrentTest::verify_exclusion_proof(
717                hasher.inner(),
718                &middle_key,
719                &proof,
720                &root,
721            ));
722
723            // Due to the cycle, lesser & greater keys should produce the same proof.
724            let new_proof = db
725                .exclusion_proof(hasher.inner(), &lesser_key)
726                .await
727                .unwrap();
728            assert_eq!(proof, new_proof);
729
730            // Test the inner span [k, k2).
731            let proof = db
732                .exclusion_proof(hasher.inner(), &middle_key)
733                .await
734                .unwrap();
735            // `k` should fail since it's in the db.
736            assert!(!CleanCurrentTest::verify_exclusion_proof(
737                hasher.inner(),
738                &key_exists_1,
739                &proof,
740                &root,
741            ));
742            // `middle_key` should succeed since it's in range.
743            assert!(CleanCurrentTest::verify_exclusion_proof(
744                hasher.inner(),
745                &middle_key,
746                &proof,
747                &root,
748            ));
749            assert!(!CleanCurrentTest::verify_exclusion_proof(
750                hasher.inner(),
751                &key_exists_2,
752                &proof,
753                &root,
754            ));
755
756            let conflicting_middle_key = Sha256::fill(0x11); // between k1=0x10 and k2=0x30
757            assert!(CleanCurrentTest::verify_exclusion_proof(
758                hasher.inner(),
759                &conflicting_middle_key,
760                &proof,
761                &root,
762            ));
763
764            // Using lesser/greater keys for the middle-proof should fail.
765            assert!(!CleanCurrentTest::verify_exclusion_proof(
766                hasher.inner(),
767                &greater_key,
768                &proof,
769                &root,
770            ));
771            assert!(!CleanCurrentTest::verify_exclusion_proof(
772                hasher.inner(),
773                &lesser_key,
774                &proof,
775                &root,
776            ));
777
778            // Make the DB empty again by deleting the keys and check the empty case
779            // again.
780            let mut db = db.into_mutable();
781            db.delete(key_exists_1).await.unwrap();
782            db.delete(key_exists_2).await.unwrap();
783            let (db, _) = db.commit(None).await.unwrap();
784            let mut db = db.into_merkleized().await.unwrap();
785            db.sync().await.unwrap();
786            let root = db.root();
787            // This root should be different than the empty root from earlier since the DB now has a
788            // non-zero number of operations.
789            assert!(db.is_empty());
790            assert_ne!(db.bounds().end, 0);
791            assert_ne!(root, empty_root);
792
793            let proof = db
794                .exclusion_proof(hasher.inner(), &key_exists_1)
795                .await
796                .unwrap();
797            assert!(CleanCurrentTest::verify_exclusion_proof(
798                hasher.inner(),
799                &key_exists_1,
800                &proof,
801                &root,
802            ));
803            assert!(CleanCurrentTest::verify_exclusion_proof(
804                hasher.inner(),
805                &key_exists_2,
806                &proof,
807                &root,
808            ));
809
810            // Try fooling the verifier with improper values.
811            assert!(!CleanCurrentTest::verify_exclusion_proof(
812                hasher.inner(),
813                &key_exists_1,
814                &empty_proof, // wrong proof
815                &root,
816            ));
817            assert!(!CleanCurrentTest::verify_exclusion_proof(
818                hasher.inner(),
819                &key_exists_1,
820                &proof,
821                &empty_root, // wrong root
822            ));
823        });
824    }
825
826    #[allow(dead_code)]
827    fn assert_merkleized_db_futures_are_send(
828        db: &mut CleanCurrentTest,
829        key: Digest,
830        loc: Location,
831    ) {
832        assert_gettable(db, &key);
833        assert_log_store(db);
834        assert_prunable_store(db, loc);
835        assert_merkleized_store(db, loc);
836        assert_send(db.sync());
837    }
838
839    #[allow(dead_code)]
840    fn assert_mutable_db_futures_are_send(db: &mut MutableCurrentTest, key: Digest, value: Digest) {
841        assert_gettable(db, &key);
842        assert_log_store(db);
843        assert_send(db.update(key, value));
844        assert_send(db.create(key, value));
845        assert_deletable(db, key);
846        assert_batchable(db, key, value);
847    }
848
849    #[allow(dead_code)]
850    fn assert_mutable_db_commit_is_send(db: MutableCurrentTest) {
851        assert_send(db.commit(None));
852    }
853}
commonware_storage/qmdb/current/ordered/variable.rs

commonware_storage/qmdb/current/ordered/
variable.rs
