exoware_qmdb/
proof.rs

1use commonware_codec::{Codec, Encode};
2use commonware_cryptography::{Digest, Hasher};
3use commonware_storage::{
4    mmr::{
5        self, iterator::PeakIterator, storage::Storage as MmrStorage, verification, Location,
6        Position, StandardHasher,
7    },
8    qmdb::{
9        any::ordered::variable::Operation as QmdbOperation,
10        current::{
11            ordered::db::KeyValueProof as CurrentKeyValueProof,
12            proof::{OperationProof as CurrentOperationProof, RangeProof as CurrentRangeProof},
13        },
14        operation::Key as QmdbKey,
15        verify::verify_multi_proof,
16    },
17};
18
19use crate::QmdbError;
20use crate::QmdbVariant;
21
22/// Stable mirror of Commonware's MMR proof payload.
23///
24/// This lets callers retain or transport historical proof material without
25/// depending on the upstream `mmr::Proof` shape directly.
26#[derive(Clone, Debug, PartialEq, Eq)]
27#[must_use]
28pub struct RawMmrProof<D: Digest> {
29    pub leaves: Location,
30    pub digests: Vec<D>,
31}
32
33impl<D: Digest> From<mmr::Proof<D>> for RawMmrProof<D> {
34    fn from(value: mmr::Proof<D>) -> Self {
35        Self {
36            leaves: value.leaves,
37            digests: value.digests,
38        }
39    }
40}
41
42impl<D: Digest> From<RawMmrProof<D>> for mmr::Proof<D> {
43    fn from(value: RawMmrProof<D>) -> Self {
44        Self {
45            leaves: value.leaves,
46            digests: value.digests,
47        }
48    }
49}
50
51impl<D: Digest + Clone> From<&RawMmrProof<D>> for mmr::Proof<D> {
52    fn from(value: &RawMmrProof<D>) -> Self {
53        Self {
54            leaves: value.leaves,
55            digests: value.digests.clone(),
56        }
57    }
58}
59
60/// Historical operation range plus the raw MMR proof material used to verify
61/// it. This is suitable for checkpointing and writer-frontier recovery.
62#[derive(Clone, Debug, PartialEq)]
63#[must_use]
64pub struct OperationRangeCheckpoint<D: Digest> {
65    pub watermark: Location,
66    pub root: D,
67    pub start_location: Location,
68    pub proof: RawMmrProof<D>,
69    pub encoded_operations: Vec<Vec<u8>>,
70}
71
72impl<D: Digest> OperationRangeCheckpoint<D> {
73    pub fn verify<H: Hasher<Digest = D>>(&self) -> bool {
74        let mut hasher = StandardHasher::<H>::new();
75        let proof = mmr::Proof::from(&self.proof);
76        proof.verify_range_inclusion(
77            &mut hasher,
78            &self.encoded_operations,
79            self.start_location,
80            &self.root,
81        )
82    }
83
84    pub fn reconstruct_peaks<H: Hasher<Digest = D>>(
85        &self,
86    ) -> Result<Vec<(Position, u32, D)>, QmdbError> {
87        let mut hasher = StandardHasher::<H>::new();
88        let proof = mmr::Proof::from(&self.proof);
89        let peak_digests = proof
90            .reconstruct_peak_digests(
91                &mut hasher,
92                &self.encoded_operations,
93                self.start_location,
94                None,
95            )
96            .map_err(|e| {
97                QmdbError::CorruptData(format!("reconstruct checkpoint peaks failed: {e}"))
98            })?;
99        let size = Position::try_from(self.proof.leaves)
100            .map_err(|e| QmdbError::CorruptData(format!("invalid checkpoint leaf count: {e}")))?;
101        let peak_entries: Vec<(Position, u32)> = PeakIterator::new(size).collect();
102        if peak_entries.len() != peak_digests.len() {
103            return Err(QmdbError::CorruptData(format!(
104                "checkpoint peak count mismatch: expected {}, got {}",
105                peak_entries.len(),
106                peak_digests.len()
107            )));
108        }
109        Ok(peak_entries
110            .into_iter()
111            .zip(peak_digests)
112            .map(|((pos, height), digest)| (pos, height, digest))
113            .collect())
114    }
115}
116
117/// Stable mirror of the current ordered range-proof payload.
118#[derive(Clone, Debug, PartialEq, Eq)]
119#[must_use]
120pub struct RawCurrentRangeProof<D: Digest> {
121    pub proof: RawMmrProof<D>,
122    pub partial_chunk_digest: Option<D>,
123    pub ops_root: D,
124}
125
126impl<D: Digest> From<CurrentRangeProof<D>> for RawCurrentRangeProof<D> {
127    fn from(value: CurrentRangeProof<D>) -> Self {
128        Self {
129            proof: value.proof.into(),
130            partial_chunk_digest: value.partial_chunk_digest,
131            ops_root: value.ops_root,
132        }
133    }
134}
135
136impl<D: Digest> From<RawCurrentRangeProof<D>> for CurrentRangeProof<D> {
137    fn from(value: RawCurrentRangeProof<D>) -> Self {
138        Self {
139            proof: value.proof.into(),
140            partial_chunk_digest: value.partial_chunk_digest,
141            ops_root: value.ops_root,
142        }
143    }
144}
145
146impl<D: Digest + Clone> From<&RawCurrentRangeProof<D>> for CurrentRangeProof<D> {
147    fn from(value: &RawCurrentRangeProof<D>) -> Self {
148        Self {
149            proof: (&value.proof).into(),
150            partial_chunk_digest: value.partial_chunk_digest,
151            ops_root: value.ops_root,
152        }
153    }
154}
155
156/// Historical multi-proof plus the exact operations it authenticates.
157#[derive(Clone, Debug, PartialEq)]
158#[must_use]
159pub struct RawMultiProof<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync> {
160    pub watermark: Location,
161    pub root: D,
162    pub proof: RawMmrProof<D>,
163    pub operations: Vec<(Location, QmdbOperation<K, V>)>,
164}
165
166impl<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync> RawMultiProof<D, K, V>
167where
168    QmdbOperation<K, V>: Encode,
169{
170    pub fn verify<H: Hasher<Digest = D>>(&self) -> bool {
171        let mut hasher = StandardHasher::<H>::new();
172        let proof = mmr::Proof::from(&self.proof);
173        verify_multi_proof(&mut hasher, &proof, &self.operations, &self.root)
174    }
175}
176
177/// Backend-agnostic historical multi-proof keyed to an authorized batch. The
178/// operations are stored as encoded bytes so this type is shared across
179/// ordered, unordered, immutable, and keyless backends.
180#[derive(Clone, Debug, PartialEq, Eq)]
181#[must_use]
182pub struct RawBatchMultiProof<D: Digest> {
183    pub watermark: Location,
184    pub root: D,
185    pub proof: RawMmrProof<D>,
186    pub operations: Vec<(Location, Vec<u8>)>,
187}
188
189impl<D: Digest> RawBatchMultiProof<D> {
190    pub fn verify<H: Hasher<Digest = D>>(&self) -> bool {
191        let mut hasher = StandardHasher::<H>::new();
192        let proof = mmr::Proof::from(&self.proof);
193        let elements: Vec<(&[u8], Location)> = self
194            .operations
195            .iter()
196            .map(|(loc, bytes)| (bytes.as_slice(), *loc))
197            .collect();
198        proof.verify_multi_inclusion(&mut hasher, &elements, &self.root)
199    }
200}
201
202/// Validate a `[start, start + max_locations)` window against the published
203/// watermark. Returns the exclusive end bound clamped to the watermark's
204/// available count (watermark + 1).
205pub(crate) fn resolve_range_bounds(
206    watermark: Location,
207    start_location: Location,
208    max_locations: u32,
209) -> Result<Location, crate::QmdbError> {
210    if max_locations == 0 {
211        return Err(crate::QmdbError::InvalidRangeLength);
212    }
213    let count = watermark
214        .checked_add(1)
215        .ok_or_else(|| crate::QmdbError::CorruptData("watermark overflow".to_string()))?;
216    if start_location >= count {
217        return Err(crate::QmdbError::RangeStartOutOfBounds {
218            start: start_location,
219            count,
220        });
221    }
222    Ok(start_location
223        .saturating_add(max_locations as u64)
224        .min(count))
225}
226
227/// Build and self-verify a `RawBatchMultiProof` over the given operations,
228/// sourcing MMR nodes from `storage` and using the caller-supplied `root`.
229pub(crate) async fn build_batch_multi_proof<H, S>(
230    storage: &S,
231    watermark: Location,
232    root: H::Digest,
233    operations: Vec<(Location, Vec<u8>)>,
234) -> Result<RawBatchMultiProof<H::Digest>, crate::QmdbError>
235where
236    H: Hasher,
237    S: MmrStorage<H::Digest>,
238{
239    if operations.is_empty() {
240        return Err(crate::QmdbError::EmptyProofRequest);
241    }
242    let locations: Vec<Location> = operations.iter().map(|(loc, _)| *loc).collect();
243    let proof = verification::multi_proof(storage, &locations)
244        .await
245        .map_err(|e| crate::QmdbError::CommonwareMmr(e.to_string()))?;
246    let raw = RawBatchMultiProof {
247        watermark,
248        root,
249        proof: proof.into(),
250        operations,
251    };
252    if !raw.verify::<H>() {
253        return Err(crate::QmdbError::ProofVerification {
254            kind: crate::ProofKind::BatchMulti,
255        });
256    }
257    Ok(raw)
258}
259
260/// Build and self-verify an `OperationRangeCheckpoint` over the given
261/// contiguous span, sourcing MMR nodes from `storage` and using the
262/// caller-supplied `root` and pre-loaded `encoded_operations`.
263pub(crate) async fn build_operation_range_checkpoint<H, S>(
264    storage: &S,
265    watermark: Location,
266    start_location: Location,
267    end_location_exclusive: Location,
268    root: H::Digest,
269    encoded_operations: Vec<Vec<u8>>,
270) -> Result<OperationRangeCheckpoint<H::Digest>, crate::QmdbError>
271where
272    H: Hasher,
273    S: MmrStorage<H::Digest>,
274{
275    let proof = verification::range_proof(storage, start_location..end_location_exclusive)
276        .await
277        .map_err(|e| crate::QmdbError::CommonwareMmr(e.to_string()))?;
278    let checkpoint = OperationRangeCheckpoint {
279        watermark,
280        root,
281        start_location,
282        proof: proof.into(),
283        encoded_operations,
284    };
285    if !checkpoint.verify::<H>() {
286        return Err(crate::QmdbError::ProofVerification {
287            kind: crate::ProofKind::RangeCheckpoint,
288        });
289    }
290    Ok(checkpoint)
291}
292
293/// Stable mirror of the current ordered key-value proof payload.
294#[derive(Clone, Debug, PartialEq)]
295#[must_use]
296pub struct RawKeyValueProof<
297    D: Digest,
298    K: QmdbKey + Codec,
299    V: Codec + Clone + Send + Sync,
300    const N: usize,
301> {
302    pub watermark: Location,
303    pub root: D,
304    pub location: Location,
305    pub chunk: [u8; N],
306    pub range_proof: RawCurrentRangeProof<D>,
307    pub operation: QmdbOperation<K, V>,
308}
309
310impl<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync, const N: usize>
311    RawKeyValueProof<D, K, V, N>
312where
313    QmdbOperation<K, V>: Encode + Clone,
314{
315    pub fn verify<H: Hasher<Digest = D>>(&self) -> bool {
316        let QmdbOperation::Update(_) = &self.operation else {
317            return false;
318        };
319        let proof = CurrentOperationProof {
320            loc: self.location,
321            chunk: self.chunk,
322            range_proof: (&self.range_proof).into(),
323        };
324        let mut hasher = H::default();
325        proof.verify(&mut hasher, self.operation.clone(), &self.root)
326    }
327}
328
329// `Verified*` types below all share one invariant: the MMR proof has already
330// been checked against the store's root and the proof blob has been dropped.
331// Callers work with the plain payload fields.
332
333/// Contiguous range of operations verified against the store's root. Shared
334/// across ordered, unordered, immutable, and keyless variants.
335#[derive(Clone, Debug, PartialEq)]
336#[must_use]
337pub struct VerifiedOperationRange<D: Digest, Op> {
338    pub root: D,
339    pub start_location: Location,
340    pub operations: Vec<Op>,
341}
342
343/// Set of (location, operation) pairs verified as a multi-proof.
344#[derive(Clone, Debug, PartialEq)]
345#[must_use]
346pub struct VerifiedMultiOperations<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync> {
347    pub root: D,
348    pub operations: Vec<(Location, QmdbOperation<K, V>)>,
349}
350
351/// A single key's `Update` operation verified against the current-state root.
352/// `operation.next_key` is the value that verification was checked against.
353#[derive(Clone, Debug, PartialEq)]
354#[must_use]
355pub struct VerifiedKeyValue<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync> {
356    pub root: D,
357    pub location: Location,
358    pub operation: QmdbOperation<K, V>,
359}
360
361/// Contiguous range of operations plus bitmap chunks verified against the
362/// current-state root.
363#[derive(Clone, Debug, PartialEq)]
364#[must_use]
365pub struct VerifiedCurrentRange<
366    D: Digest,
367    K: QmdbKey + Codec,
368    V: Codec + Clone + Send + Sync,
369    const N: usize,
370> {
371    pub root: D,
372    pub start_location: Location,
373    pub operations: Vec<QmdbOperation<K, V>>,
374    pub chunks: Vec<[u8; N]>,
375}
376
377/// Variant-tagged verified range: either the historical (`Any`) shape without
378/// chunks, or the current-state shape with bitmap chunks.
379#[derive(Clone, Debug, PartialEq)]
380#[must_use]
381pub enum VerifiedVariantRange<
382    D: Digest,
383    K: QmdbKey + Codec,
384    V: Codec + Clone + Send + Sync,
385    const N: usize,
386> {
387    Any(VerifiedOperationRange<D, QmdbOperation<K, V>>),
388    Current(VerifiedCurrentRange<D, K, V, N>),
389}
390
391impl<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync, const N: usize>
392    VerifiedVariantRange<D, K, V, N>
393{
394    pub fn variant(&self) -> QmdbVariant {
395        match self {
396            Self::Any(_) => QmdbVariant::Any,
397            Self::Current(_) => QmdbVariant::Current,
398        }
399    }
400}
401
402#[derive(Clone, Debug, PartialEq, Eq)]
403pub struct VariantRoot<D: Digest> {
404    pub watermark: Location,
405    pub variant: QmdbVariant,
406    pub root: D,
407}
408
409#[derive(Clone, Debug, PartialEq)]
410#[must_use]
411pub(crate) struct MultiProofResult<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync> {
412    pub watermark: Location,
413    pub root: D,
414    pub proof: mmr::Proof<D>,
415    pub operations: Vec<(Location, QmdbOperation<K, V>)>,
416}
417
418impl<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync> From<MultiProofResult<D, K, V>>
419    for RawMultiProof<D, K, V>
420{
421    fn from(value: MultiProofResult<D, K, V>) -> Self {
422        Self {
423            watermark: value.watermark,
424            root: value.root,
425            proof: value.proof.into(),
426            operations: value.operations,
427        }
428    }
429}
430
431#[derive(Clone, Debug, PartialEq)]
432#[must_use]
433pub(crate) struct CurrentOperationRangeProofResult<
434    D: Digest,
435    K: QmdbKey + Codec,
436    V: Codec + Clone + Send + Sync,
437    const N: usize,
438> {
439    pub watermark: Location,
440    pub root: D,
441    pub start_location: Location,
442    pub proof: CurrentRangeProof<D>,
443    pub operations: Vec<QmdbOperation<K, V>>,
444    pub chunks: Vec<[u8; N]>,
445}
446
447impl<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync, const N: usize>
448    CurrentOperationRangeProofResult<D, K, V, N>
449where
450    QmdbOperation<K, V>: Encode,
451{
452    pub fn verify<H: Hasher<Digest = D>>(&self) -> bool {
453        let mut hasher = H::default();
454        self.proof.verify(
455            &mut hasher,
456            self.start_location,
457            &self.operations,
458            &self.chunks,
459            &self.root,
460        )
461    }
462}
463
464#[derive(Clone, Debug, PartialEq)]
465#[must_use]
466pub(crate) struct KeyValueProofResult<
467    D: Digest,
468    K: QmdbKey + Codec,
469    V: Codec + Clone + Send + Sync,
470    const N: usize,
471> {
472    pub watermark: Location,
473    pub root: D,
474    pub proof: CurrentKeyValueProof<K, D, N>,
475    pub operation: QmdbOperation<K, V>,
476}
477
478impl<D: Digest, K: QmdbKey + Codec, V: Codec + Clone + Send + Sync, const N: usize>
479    From<KeyValueProofResult<D, K, V, N>> for RawKeyValueProof<D, K, V, N>
480{
481    fn from(value: KeyValueProofResult<D, K, V, N>) -> Self {
482        Self {
483            watermark: value.watermark,
484            root: value.root,
485            location: value.proof.proof.loc,
486            chunk: value.proof.proof.chunk,
487            range_proof: value.proof.proof.range_proof.into(),
488            operation: value.operation,
489        }
490    }
491}
exoware_qmdb/proof.rs

exoware_qmdb/
proof.rs
