commonware_storage/qmdb/current/ordered/
proof.rs

1//! Ordered current proofs with fixed-size or runtime-sized bitmap chunks.
2
3use super::{COMMIT_CONTEXT, KEY_VALUE_CONTEXT};
4use crate::{
5    merkle::Graftable,
6    qmdb::{
7        any::{
8            ValueEncoding,
9            ordered::{Operation, Update},
10        },
11        current::proof::operation::Proof as OperationProof,
12        operation::Key,
13    },
14};
15use bytes::BufMut;
16use commonware_codec::{Buf, Codec, EncodeSize, Read, ReadExt as _, Write};
17use commonware_cryptography::{Digest, Hasher};
18use commonware_utils::range::contains_cyclic;
19
20/// Proofs with fixed-size bitmap chunks.
21pub mod constant {
22    /// Proof information for verifying a key has a particular value in the database.
23    pub type KeyValueProof<F, K, D, const N: usize> = super::KeyValueProof<F, K, D, [u8; N]>;
24
25    /// Proof that a key has no assigned value in the database.
26    pub type ExclusionProof<F, K, V, D, const N: usize> =
27        super::ExclusionProof<F, K, V, D, [u8; N]>;
28}
29
30/// Proofs with runtime-sized bitmap chunks.
31pub mod dynamic {
32    /// Proof information for verifying a key has a particular value in the database.
33    pub type KeyValueProof<F, K, D> = super::KeyValueProof<F, K, D, bytes::Bytes>;
34
35    /// Proof that a key has no assigned value in the database.
36    pub type ExclusionProof<F, K, V, D> = super::ExclusionProof<F, K, V, D, bytes::Bytes>;
37}
38
39/// Proof information for verifying a key has a particular value in the database.
40///
41/// `C` stores the embedded operation proof's bitmap chunk.
42#[derive(Clone, Eq, PartialEq, Debug)]
43pub struct KeyValueProof<F: Graftable, K: Key, D: Digest, C> {
44    /// The proof authenticating the active update operation.
45    pub proof: OperationProof<F, D, C>,
46
47    /// The next active key in lexicographic order, wrapping at the end.
48    pub next_key: K,
49}
50
51impl<F: Graftable, K: Key, D: Digest, C: AsRef<[u8]>> KeyValueProof<F, K, D, C> {
52    /// Return true if the proof authenticates that `key` currently has `value` in the database
53    /// with the provided `root`.
54    ///
55    /// `V` selects the fixed or variable value encoding used by the database.
56    pub fn verify<H, V>(&self, key: K, value: V::Value, root: &D) -> bool
57    where
58        H: Hasher<Digest = D>,
59        V: ValueEncoding,
60        Operation<F, K, V>: Codec,
61    {
62        let op = Operation::<F, K, V>::Update(Update {
63            key,
64            value,
65            next_key: self.next_key.clone(),
66        });
67
68        self.proof.verify::<H, _>(op, root)
69    }
70}
71
72impl<F: Graftable, K: Key, D: Digest, C: AsRef<[u8]>> Write for KeyValueProof<F, K, D, C> {
73    fn write(&self, buf: &mut impl BufMut) {
74        self.proof.write(buf);
75        self.next_key.write(buf);
76    }
77}
78
79impl<F: Graftable, K: Key, D: Digest, C: AsRef<[u8]>> EncodeSize for KeyValueProof<F, K, D, C> {
80    fn encode_size(&self) -> usize {
81        self.proof.encode_size() + self.next_key.encode_size()
82    }
83}
84
85impl<F: Graftable, K: Key, D: Digest, C> Read for KeyValueProof<F, K, D, C>
86where
87    OperationProof<F, D, C>: Read,
88{
89    /// `(proof_cfg, key_cfg)`: the read configurations for the embedded operation proof and key.
90    type Cfg = (<OperationProof<F, D, C> as Read>::Cfg, <K as Read>::Cfg);
91
92    fn read_cfg(
93        buf: &mut impl Buf,
94        (proof_cfg, key_cfg): &Self::Cfg,
95    ) -> Result<Self, commonware_codec::Error> {
96        let proof = OperationProof::<F, D, C>::read_cfg(buf, proof_cfg)?;
97        let next_key = K::read_cfg(buf, key_cfg)?;
98        Ok(Self { proof, next_key })
99    }
100}
101
102#[cfg(feature = "arbitrary")]
103impl<F: Graftable, K: Key, D: Digest, C> arbitrary::Arbitrary<'_> for KeyValueProof<F, K, D, C>
104where
105    K: for<'a> arbitrary::Arbitrary<'a>,
106    OperationProof<F, D, C>: for<'a> arbitrary::Arbitrary<'a>,
107{
108    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
109        Ok(Self {
110            proof: u.arbitrary()?,
111            next_key: u.arbitrary()?,
112        })
113    }
114}
115
116/// Proof that a key has no assigned value in the database.
117///
118/// When the database has active keys, exclusion is proven by showing the key falls within a span
119/// between two adjacent active keys. Otherwise exclusion is proven by showing the database contains
120/// no active keys through the most recent commit operation.
121///
122/// `C` stores the embedded operation proof's bitmap chunk. Verify using [Self::verify].
123#[derive(Clone, Eq, PartialEq, Debug)]
124pub enum ExclusionProof<F: Graftable, K: Key, V: ValueEncoding, D: Digest, C> {
125    /// Proves that two keys are active in the database and adjacent to each other in the key
126    /// ordering. Any key falling between them (non-inclusively) can be proven excluded.
127    KeyValue(OperationProof<F, D, C>, Update<K, V>),
128
129    /// Proves that the database has no active keys, allowing any key to be proven excluded.
130    /// The commit operation's activity floor must equal its own location.
131    Commit(OperationProof<F, D, C>, Option<V::Value>),
132}
133
134impl<F, K, V, D, C> ExclusionProof<F, K, V, D, C>
135where
136    F: Graftable,
137    K: Key,
138    V: ValueEncoding,
139    D: Digest,
140    C: AsRef<[u8]>,
141    Operation<F, K, V>: Codec,
142{
143    /// Return true if the proof authenticates that `key` does not exist in the database with
144    /// the provided `root`.
145    pub fn verify<H: Hasher<Digest = D>>(&self, key: &K, root: &D) -> bool {
146        let (op_proof, op) = match self {
147            Self::KeyValue(op_proof, data) => {
148                if data.key == *key || !contains_cyclic(&data.key..&data.next_key, key) {
149                    return false;
150                }
151
152                (op_proof, Operation::Update(data.clone()))
153            }
154            Self::Commit(op_proof, metadata) => {
155                // An empty database's commit floor equals the commit operation's location
156                (
157                    op_proof,
158                    Operation::CommitFloor(metadata.clone(), op_proof.loc),
159                )
160            }
161        };
162
163        op_proof.verify::<H, _>(op, root)
164    }
165}
166
167impl<F, K, V, D, C> Write for ExclusionProof<F, K, V, D, C>
168where
169    F: Graftable,
170    K: Key,
171    V: ValueEncoding,
172    D: Digest,
173    C: AsRef<[u8]>,
174    Update<K, V>: Write,
175{
176    fn write(&self, buf: &mut impl BufMut) {
177        match self {
178            Self::KeyValue(op_proof, update) => {
179                KEY_VALUE_CONTEXT.write(buf);
180                op_proof.write(buf);
181                update.write(buf);
182            }
183            Self::Commit(op_proof, value) => {
184                COMMIT_CONTEXT.write(buf);
185                op_proof.write(buf);
186                value.write(buf);
187            }
188        }
189    }
190}
191
192impl<F, K, V, D, C> EncodeSize for ExclusionProof<F, K, V, D, C>
193where
194    F: Graftable,
195    K: Key,
196    V: ValueEncoding,
197    D: Digest,
198    C: AsRef<[u8]>,
199    Update<K, V>: EncodeSize,
200{
201    fn encode_size(&self) -> usize {
202        1 + match self {
203            Self::KeyValue(op_proof, update) => op_proof.encode_size() + update.encode_size(),
204            Self::Commit(op_proof, value) => op_proof.encode_size() + value.encode_size(),
205        }
206    }
207}
208
209impl<F, K, V, D, C> Read for ExclusionProof<F, K, V, D, C>
210where
211    F: Graftable,
212    K: Key,
213    V: ValueEncoding,
214    D: Digest,
215    OperationProof<F, D, C>: Read,
216    Update<K, V>: Read,
217{
218    /// `(proof_cfg, update_cfg, value_cfg)`: the read configurations for the embedded operation
219    /// proof, [Update], and commit metadata value.
220    type Cfg = (
221        <OperationProof<F, D, C> as Read>::Cfg,
222        <Update<K, V> as Read>::Cfg,
223        <V::Value as Read>::Cfg,
224    );
225
226    fn read_cfg(
227        buf: &mut impl Buf,
228        (proof_cfg, update_cfg, value_cfg): &Self::Cfg,
229    ) -> Result<Self, commonware_codec::Error> {
230        match u8::read(buf)? {
231            KEY_VALUE_CONTEXT => {
232                let op_proof = OperationProof::<F, D, C>::read_cfg(buf, proof_cfg)?;
233                let update = Update::<K, V>::read_cfg(buf, update_cfg)?;
234                Ok(Self::KeyValue(op_proof, update))
235            }
236            COMMIT_CONTEXT => {
237                let op_proof = OperationProof::<F, D, C>::read_cfg(buf, proof_cfg)?;
238                let value = Option::<V::Value>::read_cfg(buf, value_cfg)?;
239                Ok(Self::Commit(op_proof, value))
240            }
241            tag => Err(commonware_codec::Error::InvalidEnum(tag)),
242        }
243    }
244}
245
246#[cfg(feature = "arbitrary")]
247impl<F, K, V, D, C> arbitrary::Arbitrary<'_> for ExclusionProof<F, K, V, D, C>
248where
249    F: Graftable,
250    K: Key + for<'a> arbitrary::Arbitrary<'a>,
251    V: ValueEncoding,
252    D: Digest,
253    V::Value: for<'a> arbitrary::Arbitrary<'a>,
254    OperationProof<F, D, C>: for<'a> arbitrary::Arbitrary<'a>,
255{
256    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
257        let op_proof = u.arbitrary()?;
258        if u.arbitrary()? {
259            Ok(Self::KeyValue(op_proof, u.arbitrary()?))
260        } else {
261            Ok(Self::Commit(op_proof, u.arbitrary()?))
262        }
263    }
264}
commonware_storage/qmdb/current/ordered/proof.rs

commonware_storage/qmdb/current/ordered/
proof.rs
