commonware_storage/qmdb/current/ordered/
fixed.rs

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

commonware_storage/qmdb/current/ordered/
fixed.rs
