commonware_storage/qmdb/store/
mod.rs

1//! Traits for interacting with stores whose state is derived from an append-only log of
2//! state-changing operations.
3//!
4//! # Pruning
5//!
6//! Maintains a location before which all operations are inactive, called the _inactivity floor_.
7//! These operations can be cleaned from storage by calling [PrunableStore::prune].
8
9use crate::{
10    mmr::{Location, Proof},
11    qmdb::Error,
12};
13use commonware_codec::CodecShared;
14use commonware_cryptography::Digest;
15use core::future::Future;
16use std::num::NonZeroU64;
17
18pub mod db;
19
20/// A trait for a store based on an append-only log of operations.
21pub trait LogStore: Send + Sync {
22    type Value: CodecShared + Clone;
23
24    /// Return [start, end) where `start` and `end - 1` are the Locations of the oldest and newest
25    /// retained operations respectively.
26    fn bounds(&self) -> impl Future<Output = std::ops::Range<Location>> + Send;
27
28    /// Return the Location of the next operation appended to this db.
29    fn size(&self) -> impl Future<Output = Location> + Send {
30        async { self.bounds().await.end }
31    }
32
33    /// Get the metadata associated with the last commit.
34    fn get_metadata(&self) -> impl Future<Output = Result<Option<Self::Value>, Error>> + Send;
35}
36
37/// A trait for stores that can be pruned.
38pub trait PrunableStore: LogStore {
39    /// Prune historical operations prior to `loc`.
40    fn prune(&mut self, loc: Location) -> impl Future<Output = Result<(), Error>> + Send;
41
42    /// The location before which all operations can be pruned without affecting the state of the
43    /// database.
44    fn inactivity_floor_loc(&self) -> impl Future<Output = Location> + Send;
45}
46
47/// A trait for stores that support authentication through merkleization and inclusion proofs.
48pub trait MerkleizedStore: LogStore {
49    /// The digest type used for authentication.
50    type Digest: Digest;
51
52    /// The operation type stored in the log.
53    type Operation;
54
55    /// Returns the root digest of the authenticated store.
56    fn root(&self) -> Self::Digest;
57
58    /// Generate and return:
59    ///  1. a proof of all operations applied to the store in the range starting at (and including)
60    ///     location `start_loc`, and ending at the first of either:
61    ///     - the last operation performed, or
62    ///     - the operation `max_ops` from the start.
63    ///  2. the operations corresponding to the leaves in this range.
64    ///
65    /// # Errors
66    ///
67    /// Returns [crate::mmr::Error::LocationOverflow] if `start_loc` > [crate::mmr::MAX_LOCATION].
68    /// Returns [crate::mmr::Error::RangeOutOfBounds] if `start_loc` >= `op_count`.
69    #[allow(clippy::type_complexity)]
70    fn proof(
71        &self,
72        start_loc: Location,
73        max_ops: NonZeroU64,
74    ) -> impl Future<Output = Result<(Proof<Self::Digest>, Vec<Self::Operation>), Error>> + Send
75    {
76        async move {
77            self.historical_proof(self.bounds().await.end, start_loc, max_ops)
78                .await
79        }
80    }
81
82    /// Generate and return:
83    ///  1. a proof of all operations applied to the store in the range starting at (and including)
84    ///     location `start_loc`, and ending at the first of either:
85    ///     - the last operation performed, or
86    ///     - the operation `max_ops` from the start.
87    ///  2. the operations corresponding to the leaves in this range.
88    ///
89    /// for the store when it had `historical_size` operations.
90    ///
91    /// # Errors
92    ///
93    /// Returns [crate::mmr::Error::LocationOverflow] if `start_loc` > [crate::mmr::MAX_LOCATION].
94    /// Returns [crate::mmr::Error::RangeOutOfBounds] if `start_loc` >= `op_count`.
95    #[allow(clippy::type_complexity)]
96    fn historical_proof(
97        &self,
98        historical_size: Location,
99        start_loc: Location,
100        max_ops: NonZeroU64,
101    ) -> impl Future<Output = Result<(Proof<Self::Digest>, Vec<Self::Operation>), Error>> + Send;
102}
103
104#[cfg(test)]
105pub(crate) mod tests {
106    use super::{LogStore, MerkleizedStore, PrunableStore};
107    use crate::mmr::Location;
108    use commonware_codec::Codec;
109    use commonware_cryptography::{sha256, Hasher};
110    use commonware_utils::{Array, NZU64};
111    use core::fmt::Debug;
112
113    pub fn assert_send<T: Send>(_: T) {}
114
115    #[allow(dead_code)]
116    pub fn assert_log_store<T: LogStore>(db: &T) {
117        assert_send(db.get_metadata());
118    }
119
120    #[allow(dead_code)]
121    pub fn assert_prunable_store<T: PrunableStore>(db: &mut T, loc: Location) {
122        assert_send(db.prune(loc));
123    }
124
125    #[allow(dead_code)]
126    pub fn assert_merkleized_store<T: MerkleizedStore>(db: &T, loc: Location) {
127        assert_send(db.proof(loc, NZU64!(1)));
128    }
129
130    pub trait TestKey: Array + Copy + Send + Sync {
131        fn from_seed(seed: u64) -> Self;
132    }
133
134    pub trait TestValue: Codec + Eq + PartialEq + Debug + Send + Sync {
135        fn from_seed(seed: u64) -> Self;
136    }
137
138    impl TestKey for sha256::Digest {
139        fn from_seed(seed: u64) -> Self {
140            commonware_cryptography::Sha256::hash(&seed.to_be_bytes())
141        }
142    }
143
144    impl<D: TestKey> TestValue for D {
145        fn from_seed(seed: u64) -> Self {
146            D::from_seed(seed)
147        }
148    }
149
150    impl TestValue for Vec<u8> {
151        fn from_seed(seed: u64) -> Self {
152            vec![seed as u8; 32]
153        }
154    }
155}
commonware_storage/qmdb/store/mod.rs

commonware_storage/qmdb/store/
mod.rs
