commonware_storage/qmdb/current/ordered/
mod.rs

1//! _Ordered_ variants of a [crate::qmdb::current] authenticated database.
2//!
3//! These variants maintain the lexicographic-next active key for each active key, enabling
4//! exclusion proofs via [ExclusionProof]. This adds overhead compared to [super::unordered]
5//! variants.
6//!
7//! Variants:
8//! - [fixed]: Variant optimized for values of fixed size.
9//! - [variable]: Variant for values of variable size.
10
11use crate::{
12    merkle::Graftable,
13    qmdb::{
14        any::{ordered::Update, ValueEncoding},
15        current::proof::OperationProof,
16        operation::Key,
17    },
18};
19use commonware_cryptography::Digest;
20
21pub mod db;
22pub mod fixed;
23#[cfg(any(test, feature = "test-traits"))]
24mod test_trait_impls;
25pub mod variable;
26
27/// Proof that a key has no assigned value in the database.
28///
29/// When the database has active keys, exclusion is proven by showing the key falls within a span
30/// between two adjacent active keys. Otherwise exclusion is proven by showing the database contains
31/// no active keys through the most recent commit operation.
32///
33/// Verify using [Db::verify_exclusion_proof](fixed::Db::verify_exclusion_proof).
34#[derive(Clone, Eq, PartialEq, Debug)]
35pub enum ExclusionProof<F: Graftable, K: Key, V: ValueEncoding, D: Digest, const N: usize> {
36    /// Proves that two keys are active in the database and adjacent to each other in the key
37    /// ordering. Any key falling between them (non-inclusively) can be proven excluded.
38    KeyValue(OperationProof<F, D, N>, Update<K, V>),
39
40    /// Proves that the database has no active keys, allowing any key to be proven excluded.
41    /// Specifically, the proof establishes the most recent Commit operation has an activity floor
42    /// equal to its own location, which is a necessary and sufficient condition for an empty
43    /// database.
44    Commit(OperationProof<F, D, N>, Option<V::Value>),
45}
46
47#[cfg(test)]
48pub mod tests {
49    //! Shared test utilities for ordered Current QMDB variants.
50
51    use super::db;
52    use crate::{
53        index::ordered::Index,
54        journal::{contiguous::Mutable, Error as JournalError},
55        merkle::{Graftable, Location, Proof},
56        qmdb::{
57            any::{
58                ordered::{Operation, Update},
59                traits::{DbAny, UnmerkleizedBatch as _},
60                ValueEncoding,
61            },
62            current::{proof::RangeProof, tests::apply_random_ops, BitmapPrunedBits},
63            store::tests::{TestKey, TestValue},
64            Error,
65        },
66        translator::OneCap,
67        Persistable,
68    };
69    use commonware_codec::Codec;
70    use commonware_cryptography::{sha256::Digest, Digest as _, Hasher as _, Sha256};
71    use commonware_runtime::{
72        deterministic::{self, Context},
73        Metrics as _, Runner as _,
74    };
75    use commonware_utils::{
76        bitmap::{Prunable as BitMap, Readable as _},
77        NZU64,
78    };
79    use core::future::Future;
80    use rand::RngCore;
81
82    /// Concrete db type used in the shared proof tests, generic over journal (`C`) and value
83    /// encoding (`V`).
84    type TestDb<F, C, V> =
85        db::Db<F, deterministic::Context, C, Digest, V, Index<OneCap, Location<F>>, Sha256, 32>;
86
87    /// Run `test_current_db_build_small_close_reopen` against an ordered database factory.
88    ///
89    /// This test builds a small database, performs basic operations (create, delete, commit),
90    /// and verifies state is preserved across close/reopen cycles.
91    pub fn test_build_small_close_reopen<F, C, Fn, Fut>(mut open_db: Fn)
92    where
93        F: Graftable,
94        C: DbAny<F> + BitmapPrunedBits,
95        C::Key: TestKey,
96        <C as DbAny<F>>::Value: TestValue,
97        Fn: FnMut(Context, String) -> Fut,
98        Fut: Future<Output = C>,
99    {
100        let executor = deterministic::Runner::default();
101        executor.start(|context| async move {
102            let partition = "build-small".to_string();
103            let db: C = open_db(context.with_label("first"), partition.clone()).await;
104            assert_eq!(db.inactivity_floor_loc().await, Location::<F>::new(0));
105            assert_eq!(db.oldest_retained().await, 0);
106            let root0 = db.root();
107            drop(db);
108            let mut db: C = open_db(context.with_label("second"), partition.clone()).await;
109            assert!(db.get_metadata().await.unwrap().is_none());
110            assert_eq!(db.root(), root0);
111
112            // Add one key.
113            let k1: C::Key = TestKey::from_seed(0);
114            let v1: <C as DbAny<F>>::Value = TestValue::from_seed(10);
115            assert!(db.get(&k1).await.unwrap().is_none());
116            let merkleized = db
117                .new_batch()
118                .write(k1, Some(v1.clone()))
119                .merkleize(&db, None)
120                .await
121                .unwrap();
122            db.apply_batch(merkleized).await.unwrap();
123            db.commit().await.unwrap();
124            assert_eq!(db.get(&k1).await.unwrap().unwrap(), v1);
125            assert!(db.get_metadata().await.unwrap().is_none());
126            let root1 = db.root();
127            assert_ne!(root1, root0);
128
129            drop(db);
130            let mut db: C = open_db(context.with_label("third"), partition.clone()).await;
131            assert_eq!(db.root(), root1);
132
133            // Create of same key should fail (key already exists).
134            assert!(db.get(&k1).await.unwrap().is_some());
135
136            // Delete that one key.
137            assert!(db.get(&k1).await.unwrap().is_some());
138            let metadata: <C as DbAny<F>>::Value = TestValue::from_seed(1);
139            let merkleized = db
140                .new_batch()
141                .write(k1, None)
142                .merkleize(&db, Some(metadata.clone()))
143                .await
144                .unwrap();
145            db.apply_batch(merkleized).await.unwrap();
146            db.commit().await.unwrap();
147            assert_eq!(db.get_metadata().await.unwrap().unwrap(), metadata);
148            let root2 = db.root();
149
150            drop(db);
151            let mut db: C = open_db(context.with_label("fourth"), partition.clone()).await;
152            assert_eq!(db.get_metadata().await.unwrap().unwrap(), metadata);
153            assert_eq!(db.root(), root2);
154
155            // Repeated delete of same key should fail (key already deleted).
156            assert!(db.get(&k1).await.unwrap().is_none());
157            let merkleized = db.new_batch().merkleize(&db, None).await.unwrap();
158            db.apply_batch(merkleized).await.unwrap();
159            db.commit().await.unwrap();
160            let root3 = db.root();
161            assert_ne!(root3, root2);
162
163            // Confirm all activity bits except the last are false.
164            let bounds = db.bounds().await;
165            for i in 0..*bounds.end - 1 {
166                assert!(!db.get_bit(i));
167            }
168            assert!(db.get_bit(*bounds.end - 1));
169
170            // Test that we can get a non-durable root.
171            let merkleized = db
172                .new_batch()
173                .write(k1, Some(v1))
174                .merkleize(&db, None)
175                .await
176                .unwrap();
177            db.apply_batch(merkleized).await.unwrap();
178            assert_ne!(db.root(), root3);
179
180            db.destroy().await.unwrap();
181        });
182    }
183
184    /// Build a tiny database and verify that proofs over uncommitted bitmap chunks are correct.
185    ///
186    /// Tests that the verifier rejects proofs for old values after updates, including attempts
187    /// to forge proofs by swapping locations or flipping activity bits.
188    pub(super) fn test_verify_proof_over_bits_in_uncommitted_chunk<F, C, V, Fn, Fut>(
189        mut open_db: Fn,
190    ) where
191        F: Graftable,
192        C: Mutable<Item = Operation<F, Digest, V>> + Persistable<Error = JournalError> + 'static,
193        V: ValueEncoding<Value = Digest> + 'static,
194        Operation<F, Digest, V>: Codec,
195        TestDb<F, C, V>: DbAny<F, Key = Digest, Value = Digest, Digest = Digest> + 'static,
196        Fn: FnMut(Context, String) -> Fut + 'static,
197        Fut: Future<Output = TestDb<F, C, V>>,
198    {
199        let executor = deterministic::Runner::default();
200        executor.start(|context| async move {
201            let mut hasher = Sha256::new();
202            let partition = "build-small".to_string();
203            let mut db = open_db(context.with_label("db"), partition.clone()).await;
204
205            // Add one key.
206            let k = Sha256::fill(0x01);
207            let v1 = Sha256::fill(0xA1);
208            let merkleized = db
209                .new_batch()
210                .write(k, Some(v1))
211                .merkleize(&db, None)
212                .await
213                .unwrap();
214            db.apply_batch(merkleized).await.unwrap();
215
216            let (_, op_loc) = db.any.get_with_loc(&k).await.unwrap().unwrap();
217            let proof = db.key_value_proof(&mut hasher, k).await.unwrap();
218
219            // Proof should be verifiable against current root.
220            let root = db.root();
221            assert!(TestDb::<F, C, V>::verify_key_value_proof(
222                &mut hasher,
223                k,
224                v1,
225                &proof,
226                &root,
227            ));
228
229            let v2 = Sha256::fill(0xA2);
230            // Proof should not verify against a different value.
231            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
232                &mut hasher,
233                k,
234                v2,
235                &proof,
236                &root,
237            ));
238            // Proof should not verify against a mangled next_key.
239            let mut mangled_proof = proof.clone();
240            mangled_proof.next_key = Sha256::fill(0xFF);
241            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
242                &mut hasher,
243                k,
244                v1,
245                &mangled_proof,
246                &root,
247            ));
248
249            // Update the key to a new value (v2), which inactivates the previous operation.
250            let merkleized = db
251                .new_batch()
252                .write(k, Some(v2))
253                .merkleize(&db, None)
254                .await
255                .unwrap();
256            db.apply_batch(merkleized).await.unwrap();
257            let root = db.root();
258
259            // New value should not be verifiable against the old proof.
260            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
261                &mut hasher,
262                k,
263                v2,
264                &proof,
265                &root,
266            ));
267
268            // But the new value should verify against a new proof.
269            let proof = db.key_value_proof(&mut hasher, k).await.unwrap();
270            assert!(TestDb::<F, C, V>::verify_key_value_proof(
271                &mut hasher,
272                k,
273                v2,
274                &proof,
275                &root,
276            ));
277
278            // Old value will not verify against new proof.
279            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
280                &mut hasher,
281                k,
282                v1,
283                &proof,
284                &root,
285            ));
286
287            // Create a proof of the now-inactive update operation assigning v1 to k against the
288            // current root.
289            let (p, _, chunks) = db
290                .range_proof(&mut hasher, op_loc, NZU64!(1))
291                .await
292                .unwrap();
293            let proof_inactive = db::KeyValueProof {
294                proof: crate::qmdb::current::proof::OperationProof {
295                    loc: op_loc,
296                    chunk: chunks[0],
297                    range_proof: p,
298                },
299                next_key: k,
300            };
301            // This proof should verify using verify_range_proof which does not check activity
302            // status.
303            let op = Operation::Update(Update {
304                key: k,
305                value: v1,
306                next_key: k,
307            });
308            assert!(TestDb::<F, C, V>::verify_range_proof(
309                &mut hasher,
310                &proof_inactive.proof.range_proof,
311                proof_inactive.proof.loc,
312                &[op],
313                &[proof_inactive.proof.chunk],
314                &root,
315            ));
316
317            // But this proof should *not* verify as a key value proof, since verification will see
318            // that the operation is inactive.
319            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
320                &mut hasher,
321                k,
322                v1,
323                &proof_inactive,
324                &root,
325            ));
326
327            // Attempt #1 to "fool" the verifier:  change the location to that of an active
328            // operation. This should not fool the verifier if we're properly validating the
329            // inclusion of the operation itself, and not just the chunk.
330            let (_, active_loc) = db.any.get_with_loc(&k).await.unwrap().unwrap();
331            // The new location should differ but still be in the same chunk.
332            assert_ne!(active_loc, proof_inactive.proof.loc);
333            assert_eq!(
334                BitMap::<32>::to_chunk_index(*active_loc),
335                BitMap::<32>::to_chunk_index(*proof_inactive.proof.loc)
336            );
337            let mut fake_proof = proof_inactive.clone();
338            fake_proof.proof.loc = active_loc;
339            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
340                &mut hasher,
341                k,
342                v1,
343                &fake_proof,
344                &root,
345            ));
346
347            // Attempt #2 to "fool" the verifier: Modify the chunk in the proof info to make it
348            // look like the operation is active by flipping its corresponding bit to 1. This
349            // should not fool the verifier if we are correctly incorporating the partial chunk
350            // information into the root computation.
351            let mut modified_chunk = proof_inactive.proof.chunk;
352            let bit_pos = *proof_inactive.proof.loc;
353            let byte_idx = bit_pos / 8;
354            let bit_idx = bit_pos % 8;
355            modified_chunk[byte_idx as usize] |= 1 << bit_idx;
356
357            let mut fake_proof = proof_inactive.clone();
358            fake_proof.proof.chunk = modified_chunk;
359            assert!(!TestDb::<F, C, V>::verify_key_value_proof(
360                &mut hasher,
361                k,
362                v1,
363                &fake_proof,
364                &root,
365            ));
366
367            db.destroy().await.unwrap();
368        });
369    }
370
371    /// Verify that range proofs are correct across a database populated with random operations.
372    ///
373    /// Tests that every location from the inactivity floor to the tip produces a valid range
374    /// proof, and that adding extra chunks causes verification to fail.
375    pub(super) fn test_range_proofs<F, C, V, Fn, Fut>(mut open_db: Fn)
376    where
377        F: Graftable,
378        C: Mutable<Item = Operation<F, Digest, V>> + Persistable<Error = JournalError> + 'static,
379        V: ValueEncoding<Value = Digest> + 'static,
380        Operation<F, Digest, V>: Codec,
381        TestDb<F, C, V>: DbAny<F, Key = Digest, Value = Digest, Digest = Digest> + 'static,
382        Fn: FnMut(Context, String) -> Fut + 'static,
383        Fut: Future<Output = TestDb<F, C, V>>,
384    {
385        let executor = deterministic::Runner::default();
386        executor.start(|mut context| async move {
387            let partition = "range-proofs".to_string();
388            let mut hasher = Sha256::new();
389            let db = open_db(context.with_label("db"), partition.clone()).await;
390            let root = db.root();
391
392            // Empty range proof should not crash or verify, since even an empty db has a single
393            let proof = RangeProof {
394                proof: Proof::default(),
395                pre_prefix_acc: None,
396                unfolded_prefix_peaks: vec![],
397                partial_chunk_digest: None,
398                ops_root: Digest::EMPTY,
399            };
400            assert!(!TestDb::<F, C, V>::verify_range_proof(
401                &mut hasher,
402                &proof,
403                Location::<F>::new(0),
404                &[],
405                &[],
406                &root,
407            ));
408
409            let mut db = apply_random_ops::<F, TestDb<F, C, V>>(200, true, context.next_u64(), db)
410                .await
411                .unwrap();
412            let merkleized = db.new_batch().merkleize(&db, None).await.unwrap();
413            db.apply_batch(merkleized).await.unwrap();
414            let root = db.root();
415
416            // Make sure size-constrained batches of operations are provable from the oldest
417            // retained op to tip.
418            let max_ops = 4;
419            let end_loc = db.bounds().await.end;
420            let start_loc = db.any.inactivity_floor_loc();
421
422            for loc in *start_loc..*end_loc {
423                let loc = Location::<F>::new(loc);
424                let (proof, ops, chunks) = db
425                    .range_proof(&mut hasher, loc, NZU64!(max_ops))
426                    .await
427                    .unwrap();
428                assert!(
429                    TestDb::<F, C, V>::verify_range_proof(
430                        &mut hasher,
431                        &proof,
432                        loc,
433                        &ops,
434                        &chunks,
435                        &root
436                    ),
437                    "failed to verify range at start_loc {start_loc}",
438                );
439                // Proof should not verify if we include extra chunks.
440                let mut chunks_with_extra = chunks.clone();
441                chunks_with_extra.push(chunks[chunks.len() - 1]);
442                assert!(!TestDb::<F, C, V>::verify_range_proof(
443                    &mut hasher,
444                    &proof,
445                    loc,
446                    &ops,
447                    &chunks_with_extra,
448                    &root,
449                ));
450            }
451
452            db.destroy().await.unwrap();
453        });
454    }
455
456    /// Verify key-value proofs for every active operation in a randomly-populated database.
457    ///
458    /// Checks that proofs validate against the correct key/value/root and fail against
459    /// wrong keys, wrong values, wrong roots, and wrong next-keys.
460    pub(super) fn test_key_value_proof<F, C, V, Fn, Fut>(mut open_db: Fn)
461    where
462        F: Graftable,
463        C: Mutable<Item = Operation<F, Digest, V>> + Persistable<Error = JournalError> + 'static,
464        V: ValueEncoding<Value = Digest> + 'static,
465        Operation<F, Digest, V>: Codec,
466        TestDb<F, C, V>: DbAny<F, Key = Digest, Value = Digest, Digest = Digest> + 'static,
467        Fn: FnMut(Context, String) -> Fut + 'static,
468        Fut: Future<Output = TestDb<F, C, V>>,
469    {
470        let executor = deterministic::Runner::default();
471        executor.start(|mut context| async move {
472            let partition = "range-proofs".to_string();
473            let mut hasher = Sha256::new();
474            let db = open_db(context.with_label("db"), partition.clone()).await;
475            let mut db = apply_random_ops::<F, TestDb<F, C, V>>(500, true, context.next_u64(), db)
476                .await
477                .unwrap();
478            let merkleized = db.new_batch().merkleize(&db, None).await.unwrap();
479            db.apply_batch(merkleized).await.unwrap();
480            let root = db.root();
481
482            // Confirm bad keys produce the expected error.
483            let bad_key = Sha256::fill(0xAA);
484            let res = db.key_value_proof(&mut hasher, bad_key).await;
485            assert!(matches!(res, Err(Error::KeyNotFound)));
486
487            let start = *db.inactivity_floor_loc();
488            for i in start..db.status.len() {
489                if !db.status.get_bit(i) {
490                    continue;
491                }
492                // Found an active operation! Create a proof for its active current key/value if
493                // it's a key-updating operation.
494                let op = db.any.log.read(Location::<F>::new(i)).await.unwrap();
495                let (key, value) = match op {
496                    Operation::Update(key_data) => (key_data.key, key_data.value),
497                    Operation::CommitFloor(_, _) => continue,
498                    _ => unreachable!("expected update or commit floor operation"),
499                };
500                let proof = db.key_value_proof(&mut hasher, key).await.unwrap();
501
502                // Proof should validate against the current value and correct root.
503                assert!(TestDb::<F, C, V>::verify_key_value_proof(
504                    &mut hasher,
505                    key,
506                    value,
507                    &proof,
508                    &root
509                ));
510                // Proof should fail against the wrong value. Use hash instead of fill to ensure
511                // the value differs from any key/value created by TestKey::from_seed (which uses
512                // fill patterns).
513                let wrong_val = Sha256::hash(&[0xFF]);
514                assert!(!TestDb::<F, C, V>::verify_key_value_proof(
515                    &mut hasher,
516                    key,
517                    wrong_val,
518                    &proof,
519                    &root
520                ));
521                // Proof should fail against the wrong key.
522                let wrong_key = Sha256::hash(&[0xEE]);
523                assert!(!TestDb::<F, C, V>::verify_key_value_proof(
524                    &mut hasher,
525                    wrong_key,
526                    value,
527                    &proof,
528                    &root
529                ));
530                // Proof should fail against the wrong root.
531                let wrong_root = Sha256::hash(&[0xDD]);
532                assert!(!TestDb::<F, C, V>::verify_key_value_proof(
533                    &mut hasher,
534                    key,
535                    value,
536                    &proof,
537                    &wrong_root,
538                ));
539                // Proof should fail with the wrong next-key.
540                let mut bad_proof = proof.clone();
541                bad_proof.next_key = wrong_key;
542                assert!(!TestDb::<F, C, V>::verify_key_value_proof(
543                    &mut hasher,
544                    key,
545                    value,
546                    &bad_proof,
547                    &root,
548                ));
549            }
550
551            db.destroy().await.unwrap();
552        });
553    }
554
555    /// Repeatedly update the same key and ensure the proof tracks the latest value.
556    ///
557    /// After each update, verifies that the new value's proof succeeds and the previous
558    /// value's proof fails.
559    pub(super) fn test_proving_repeated_updates<F, C, V, Fn, Fut>(mut open_db: Fn)
560    where
561        F: Graftable,
562        C: Mutable<Item = Operation<F, Digest, V>> + Persistable<Error = JournalError> + 'static,
563        V: ValueEncoding<Value = Digest> + 'static,
564        Operation<F, Digest, V>: Codec,
565        TestDb<F, C, V>: DbAny<F, Key = Digest, Value = Digest, Digest = Digest> + 'static,
566        Fn: FnMut(Context, String) -> Fut + 'static,
567        Fut: Future<Output = TestDb<F, C, V>>,
568    {
569        let executor = deterministic::Runner::default();
570        executor.start(|context| async move {
571            let mut hasher = Sha256::new();
572            let partition = "build-small".to_string();
573            let mut db = open_db(context.with_label("db"), partition.clone()).await;
574
575            // Add one key.
576            let k = Sha256::fill(0x00);
577            let mut old_val = Sha256::fill(0x00);
578            for i in 1u8..=255 {
579                let v = Sha256::fill(i);
580                let merkleized = db
581                    .new_batch()
582                    .write(k, Some(v))
583                    .merkleize(&db, None)
584                    .await
585                    .unwrap();
586                db.apply_batch(merkleized).await.unwrap();
587                assert_eq!(db.get(&k).await.unwrap().unwrap(), v);
588                let root = db.root();
589
590                // Create a proof for the current value of k.
591                let proof = db.key_value_proof(&mut hasher, k).await.unwrap();
592                assert!(
593                    TestDb::<F, C, V>::verify_key_value_proof(&mut hasher, k, v, &proof, &root),
594                    "proof of update {i} failed to verify"
595                );
596                // Ensure the proof does NOT verify if we use the previous value.
597                assert!(
598                    !TestDb::<F, C, V>::verify_key_value_proof(
599                        &mut hasher,
600                        k,
601                        old_val,
602                        &proof,
603                        &root,
604                    ),
605                    "proof of update {i} verified when it should not have"
606                );
607                old_val = v;
608            }
609
610            db.destroy().await.unwrap();
611        });
612    }
613
614    /// Build a tiny database and confirm exclusion proofs work as expected.
615    ///
616    /// Tests empty-db exclusion, single-key exclusion, two-key exclusion with cycle-around
617    /// and inner spans, and re-emptied-db exclusion. Also verifies that wrong proofs and
618    /// wrong roots are rejected.
619    pub(super) fn test_exclusion_proofs<F, C, V, Fn, Fut>(mut open_db: Fn)
620    where
621        F: Graftable + PartialEq,
622        C: Mutable<Item = Operation<F, Digest, V>> + Persistable<Error = JournalError> + 'static,
623        V: ValueEncoding<Value = Digest> + PartialEq + core::fmt::Debug + 'static,
624        Operation<F, Digest, V>: Codec,
625        TestDb<F, C, V>: DbAny<F, Key = Digest, Value = Digest, Digest = Digest> + 'static,
626        Fn: FnMut(Context, String) -> Fut + 'static,
627        Fut: Future<Output = TestDb<F, C, V>>,
628    {
629        let executor = deterministic::Runner::default();
630        executor.start(|context| async move {
631            let mut hasher = Sha256::new();
632            let partition = "exclusion-proofs".to_string();
633            let mut db = open_db(context.with_label("db"), partition.clone()).await;
634
635            let key_exists_1 = Sha256::fill(0x10);
636
637            // We should be able to prove exclusion for any key against an empty db.
638            let empty_root = db.root();
639            let empty_proof = db
640                .exclusion_proof(&mut hasher, &key_exists_1)
641                .await
642                .unwrap();
643            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
644                &mut hasher,
645                &key_exists_1,
646                &empty_proof,
647                &empty_root,
648            ));
649
650            // Add `key_exists_1` and test exclusion proving over the single-key database case.
651            let v1 = Sha256::fill(0xA1);
652            let merkleized = db
653                .new_batch()
654                .write(key_exists_1, Some(v1))
655                .merkleize(&db, None)
656                .await
657                .unwrap();
658            db.apply_batch(merkleized).await.unwrap();
659            let root = db.root();
660
661            // We shouldn't be able to generate an exclusion proof for a key already in the db.
662            let result = db.exclusion_proof(&mut hasher, &key_exists_1).await;
663            assert!(matches!(result, Err(Error::KeyExists)));
664
665            // Generate some valid exclusion proofs for keys on either side.
666            let greater_key = Sha256::fill(0xFF);
667            let lesser_key = Sha256::fill(0x00);
668            let proof = db.exclusion_proof(&mut hasher, &greater_key).await.unwrap();
669            let proof2 = db.exclusion_proof(&mut hasher, &lesser_key).await.unwrap();
670
671            // Since there's only one span in the DB, the two exclusion proofs should be identical,
672            // and the proof should verify any key but the one that exists in the db.
673            assert_eq!(proof, proof2);
674            // Any key except the one that exists should verify against this proof.
675            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
676                &mut hasher,
677                &greater_key,
678                &proof,
679                &root,
680            ));
681            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
682                &mut hasher,
683                &lesser_key,
684                &proof,
685                &root,
686            ));
687            // Exclusion should fail if we test it on a key that exists.
688            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
689                &mut hasher,
690                &key_exists_1,
691                &proof,
692                &root,
693            ));
694
695            // Add a second key and test exclusion proving over the two-key database case.
696            let key_exists_2 = Sha256::fill(0x30);
697            let v2 = Sha256::fill(0xB2);
698
699            let merkleized = db
700                .new_batch()
701                .write(key_exists_2, Some(v2))
702                .merkleize(&db, None)
703                .await
704                .unwrap();
705            db.apply_batch(merkleized).await.unwrap();
706            let root = db.root();
707
708            // Use a lesser/greater key that has a translated-key conflict based
709            // on our use of OneCap translator.
710            let lesser_key = Sha256::fill(0x0F); // < k1=0x10
711            let greater_key = Sha256::fill(0x31); // > k2=0x30
712            let middle_key = Sha256::fill(0x20); // between k1=0x10 and k2=0x30
713            let proof = db.exclusion_proof(&mut hasher, &greater_key).await.unwrap();
714            // Test the "cycle around" span. This should prove exclusion of greater_key & lesser
715            // key, but fail on middle_key.
716            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
717                &mut hasher,
718                &greater_key,
719                &proof,
720                &root,
721            ));
722            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
723                &mut hasher,
724                &lesser_key,
725                &proof,
726                &root,
727            ));
728            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
729                &mut hasher,
730                &middle_key,
731                &proof,
732                &root,
733            ));
734
735            // Due to the cycle, lesser & greater keys should produce the same proof.
736            let new_proof = db.exclusion_proof(&mut hasher, &lesser_key).await.unwrap();
737            assert_eq!(proof, new_proof);
738
739            // Test the inner span [k, k2).
740            let proof = db.exclusion_proof(&mut hasher, &middle_key).await.unwrap();
741            // `k` should fail since it's in the db.
742            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
743                &mut hasher,
744                &key_exists_1,
745                &proof,
746                &root,
747            ));
748            // `middle_key` should succeed since it's in range.
749            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
750                &mut hasher,
751                &middle_key,
752                &proof,
753                &root,
754            ));
755            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
756                &mut hasher,
757                &key_exists_2,
758                &proof,
759                &root,
760            ));
761
762            let conflicting_middle_key = Sha256::fill(0x11); // between k1=0x10 and k2=0x30
763            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
764                &mut hasher,
765                &conflicting_middle_key,
766                &proof,
767                &root,
768            ));
769
770            // Using lesser/greater keys for the middle-proof should fail.
771            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
772                &mut hasher,
773                &greater_key,
774                &proof,
775                &root,
776            ));
777            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
778                &mut hasher,
779                &lesser_key,
780                &proof,
781                &root,
782            ));
783
784            // Make the DB empty again by deleting the keys and check the empty case
785            // again.
786            let merkleized = db
787                .new_batch()
788                .write(key_exists_1, None)
789                .write(key_exists_2, None)
790                .merkleize(&db, None)
791                .await
792                .unwrap();
793            db.apply_batch(merkleized).await.unwrap();
794            db.sync().await.unwrap();
795            let root = db.root();
796            // This root should be different than the empty root from earlier since the DB now has a
797            // non-zero number of operations.
798            assert!(db.is_empty());
799            assert_ne!(db.bounds().await.end, 0);
800            assert_ne!(root, empty_root);
801
802            let proof = db
803                .exclusion_proof(&mut hasher, &key_exists_1)
804                .await
805                .unwrap();
806            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
807                &mut hasher,
808                &key_exists_1,
809                &proof,
810                &root,
811            ));
812            assert!(TestDb::<F, C, V>::verify_exclusion_proof(
813                &mut hasher,
814                &key_exists_2,
815                &proof,
816                &root,
817            ));
818
819            // Try fooling the verifier with improper values.
820            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
821                &mut hasher,
822                &key_exists_1,
823                &empty_proof, // wrong proof
824                &root,
825            ));
826            assert!(!TestDb::<F, C, V>::verify_exclusion_proof(
827                &mut hasher,
828                &key_exists_1,
829                &proof,
830                &empty_root, // wrong root
831            ));
832        });
833    }
834}
commonware_storage/qmdb/current/ordered/mod.rs

commonware_storage/qmdb/current/ordered/
mod.rs
