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
10use crate::qmdb::{
11    any::{ordered::fixed::Update, FixedValue},
12    current::proof::OperationProof,
13};
14use commonware_cryptography::Digest;
15use commonware_utils::Array;
16
17pub mod fixed;
18
19/// Proof that a key has no assigned value in the database.
20///
21/// When the database has active keys, exclusion is proven by showing the key falls within a span
22/// between two adjacent active keys. Otherwise exclusion is proven by showing the database contains
23/// no active keys through the most recent commit operation.
24///
25/// Verify using [Db::verify_exclusion_proof](fixed::Db::verify_exclusion_proof).
26#[derive(Clone, Eq, PartialEq, Debug)]
27pub enum ExclusionProof<K: Array, V: FixedValue, D: Digest, const N: usize> {
28    /// Proves that two keys are active in the database and adjacent to each other in the key
29    /// ordering. Any key falling between them (non-inclusively) can be proven excluded.
30    KeyValue(OperationProof<D, N>, Update<K, V>),
31
32    /// Proves that the database has no active keys, allowing any key to be proven excluded.
33    /// Specifically, the proof establishes the most recent Commit operation has an activity floor
34    /// equal to its own location, which is a necessary and sufficient condition for an empty
35    /// database.
36    Commit(OperationProof<D, N>, Option<V>),
37}