commonware_storage/qmdb/current/ordered/
db.rs

1//! Shared implementation for ordered Current QMDB variants.
2//!
3//! This module contains impl blocks that are generic over `ValueEncoding`, allowing them to be
4//! used by both fixed and variable ordered QMDB implementations.
5
6use crate::{
7    index::Ordered as OrderedIndex,
8    journal::contiguous::{Contiguous, Mutable},
9    merkle::{self, Location},
10    qmdb::{
11        any::{
12            ordered::{Operation, Update},
13            ValueEncoding,
14        },
15        current::proof::OperationProof,
16        operation::Key,
17        Error,
18    },
19    Context,
20};
21use bytes::{Buf, BufMut};
22use commonware_codec::{Codec, EncodeSize, Read, Write};
23use commonware_cryptography::{Digest, Hasher};
24use commonware_parallel::Strategy;
25use futures::stream::Stream;
26
27/// Proof information for verifying a key has a particular value in the database.
28#[derive(Clone, Eq, PartialEq, Debug)]
29pub struct KeyValueProof<F: merkle::Graftable, K: Key, D: Digest, const N: usize> {
30    pub proof: OperationProof<F, D, N>,
31    pub next_key: K,
32}
33
34impl<F: merkle::Graftable, K: Key, D: Digest, const N: usize> Write for KeyValueProof<F, K, D, N> {
35    fn write(&self, buf: &mut impl BufMut) {
36        self.proof.write(buf);
37        self.next_key.write(buf);
38    }
39}
40
41impl<F: merkle::Graftable, K: Key, D: Digest, const N: usize> EncodeSize
42    for KeyValueProof<F, K, D, N>
43{
44    fn encode_size(&self) -> usize {
45        self.proof.encode_size() + self.next_key.encode_size()
46    }
47}
48
49impl<F: merkle::Graftable, K: Key, D: Digest, const N: usize> Read for KeyValueProof<F, K, D, N> {
50    /// `(max_digests, key_cfg)`: the Merkle digest cap forwarded to the embedded operation
51    /// proof and the read configuration for the key type.
52    type Cfg = (usize, <K as Read>::Cfg);
53
54    fn read_cfg(
55        buf: &mut impl Buf,
56        (max_digests, key_cfg): &Self::Cfg,
57    ) -> Result<Self, commonware_codec::Error> {
58        let proof = OperationProof::<F, D, N>::read_cfg(buf, max_digests)?;
59        let next_key = K::read_cfg(buf, key_cfg)?;
60        Ok(Self { proof, next_key })
61    }
62}
63
64#[cfg(feature = "arbitrary")]
65impl<F: merkle::Graftable, K: Key, D: Digest, const N: usize> arbitrary::Arbitrary<'_>
66    for KeyValueProof<F, K, D, N>
67where
68    K: for<'a> arbitrary::Arbitrary<'a>,
69    D: for<'a> arbitrary::Arbitrary<'a>,
70    F::PendingChunk<D>: for<'a> arbitrary::Arbitrary<'a>,
71{
72    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
73        Ok(Self {
74            proof: u.arbitrary()?,
75            next_key: u.arbitrary()?,
76        })
77    }
78}
79
80/// The generic Db type for ordered Current QMDB variants.
81///
82/// This type is generic over the index type `I`, allowing it to be used with both regular
83/// and partitioned indices.
84pub type Db<F, E, C, K, V, I, H, const N: usize, S> =
85    crate::qmdb::current::db::Db<F, E, C, I, H, Update<K, V>, N, S>;
86
87// Shared read-only functionality.
88impl<
89        F: merkle::Graftable,
90        E: Context,
91        C: Contiguous<Item = Operation<F, K, V>>,
92        K: Key,
93        V: ValueEncoding,
94        I: OrderedIndex<Value = Location<F>>,
95        H: Hasher,
96        const N: usize,
97        S: Strategy,
98    > Db<F, E, C, K, V, I, H, N, S>
99where
100    Operation<F, K, V>: Codec,
101{
102    /// Get the value of `key` in the db, or None if it has no value.
103    pub async fn get(&self, key: &K) -> Result<Option<V::Value>, Error<F>> {
104        self.any.get(key).await
105    }
106
107    /// Return true if the proof authenticates that `key` currently has value `value` in the db with
108    /// the provided `root`.
109    pub fn verify_key_value_proof(
110        key: K,
111        value: V::Value,
112        proof: &KeyValueProof<F, K, H::Digest, N>,
113        root: &H::Digest,
114    ) -> bool {
115        let op = Operation::Update(Update {
116            key,
117            value,
118            next_key: proof.next_key.clone(),
119        });
120
121        proof.proof.verify::<H, _>(op, root)
122    }
123
124    /// Get the operation that currently defines the span whose range contains `key`, or None if the
125    /// DB is empty.
126    pub async fn get_span(&self, key: &K) -> Result<Option<(Location<F>, Update<K, V>)>, Error<F>> {
127        self.any.get_span(key).await
128    }
129
130    /// Streams all active (key, value) pairs in the database in key order, starting from the first
131    /// active key greater than or equal to `start`.
132    pub async fn stream_range<'a>(
133        &'a self,
134        start: K,
135    ) -> Result<impl Stream<Item = Result<(K, V::Value), Error<F>>> + 'a, Error<F>>
136    where
137        V: 'a,
138    {
139        self.any.stream_range(start).await
140    }
141
142    /// Return true if the proof authenticates that `key` does _not_ exist in the db with the
143    /// provided `root`.
144    pub fn verify_exclusion_proof(
145        key: &K,
146        proof: &super::ExclusionProof<F, K, V, H::Digest, N>,
147        root: &H::Digest,
148    ) -> bool {
149        let (op_proof, op) = match proof {
150            super::ExclusionProof::KeyValue(op_proof, data) => {
151                if data.key == *key {
152                    // The provided `key` is in the DB if it matches the start of the span.
153                    return false;
154                }
155                if !crate::qmdb::any::db::Db::<F, E, C, I, H, Update<K, V>, N, S>::span_contains(
156                    &data.key,
157                    &data.next_key,
158                    key,
159                ) {
160                    // If the key is not within the span, then this proof cannot prove its
161                    // exclusion.
162                    return false;
163                }
164
165                (op_proof, Operation::Update(data.clone()))
166            }
167            super::ExclusionProof::Commit(op_proof, metadata) => {
168                // Handle the case where the proof shows the db is empty, hence any key is proven
169                // excluded. For the db to be empty, the floor must equal the commit operation's
170                // location.
171                let floor_loc = op_proof.loc;
172                (
173                    op_proof,
174                    Operation::CommitFloor(metadata.clone(), floor_loc),
175                )
176            }
177        };
178
179        op_proof.verify::<H, _>(op, root)
180    }
181}
182
183impl<
184        F: merkle::Graftable,
185        E: Context,
186        C: Mutable<Item = Operation<F, K, V>>,
187        K: Key,
188        V: ValueEncoding,
189        I: OrderedIndex<Value = Location<F>>,
190        H: Hasher,
191        const N: usize,
192        S: Strategy,
193    > Db<F, E, C, K, V, I, H, N, S>
194where
195    Operation<F, K, V>: Codec,
196{
197    /// Generate and return a proof of the current value of `key`, along with the other
198    /// [KeyValueProof] required to verify the proof. Returns KeyNotFound error if the key is not
199    /// currently assigned any value.
200    ///
201    /// # Errors
202    ///
203    /// Returns [Error::KeyNotFound] if the key is not currently assigned any value.
204    pub async fn key_value_proof(
205        &self,
206        key: K,
207    ) -> Result<KeyValueProof<F, K, H::Digest, N>, Error<F>> {
208        let op_loc = self.any.get_with_loc(&key).await?;
209        let Some((data, loc)) = op_loc else {
210            return Err(Error::<F>::KeyNotFound);
211        };
212        let proof = self.operation_proof(loc).await?;
213
214        Ok(KeyValueProof {
215            proof,
216            next_key: data.next_key,
217        })
218    }
219
220    /// Generate and return a proof that the specified `key` does not exist in the db.
221    ///
222    /// # Errors
223    ///
224    /// Returns [Error::KeyExists] if the key exists in the db.
225    pub async fn exclusion_proof(
226        &self,
227        key: &K,
228    ) -> Result<super::ExclusionProof<F, K, V, H::Digest, N>, Error<F>> {
229        match self.any.get_span(key).await? {
230            Some((loc, key_data)) => {
231                if key_data.key == *key {
232                    // Cannot prove exclusion of a key that exists in the db.
233                    return Err(Error::<F>::KeyExists);
234                }
235                let op_proof = self.operation_proof(loc).await?;
236                Ok(super::ExclusionProof::KeyValue(op_proof, key_data))
237            }
238            None => {
239                // The DB is empty. Use the last CommitFloor to prove emptiness. The Commit proof
240                // variant requires the CommitFloor's floor to equal its own location (genuinely
241                // empty at commit time). If this doesn't hold, the persisted state is inconsistent.
242                let op = self.any.log.read(*self.any.last_commit_loc).await?;
243                let Operation::CommitFloor(value, floor) = op else {
244                    unreachable!("last_commit_loc should always point to a CommitFloor");
245                };
246                assert_eq!(
247                    floor, self.any.last_commit_loc,
248                    "inconsistent commit floor: expected last_commit_loc={}, got floor={}",
249                    self.any.last_commit_loc, floor
250                );
251                let op_proof = self.operation_proof(self.any.last_commit_loc).await?;
252                Ok(super::ExclusionProof::Commit(op_proof, value))
253            }
254        }
255    }
256}
commonware_storage/qmdb/current/ordered/db.rs

commonware_storage/qmdb/current/ordered/
db.rs
