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

commonware_storage/qmdb/current/ordered/
fixed.rs
