commonware_storage/adb/
mod.rs

1//! A collection of authenticated databases (ADB).
2//!
3//! # Terminology
4//!
5//! A _key_ in an authenticated database either has a _value_ or it doesn't. Two types of
6//! _operations_ can be applied to the db to modify the state of a specific key. A key that has a
7//! value can change to one without a value through the _delete_ operation. The _update_ operation
8//! gives a key a specific value whether it previously had no value or had a different value.
9//!
10//! Keys with values are called _active_. An operation is called _active_ if (1) its key is active,
11//! (2) it is an update operation, and (3) it is the most recent operation for that key.
12
13use crate::{
14    journal::contiguous::fixed::Journal,
15    mmr::{journaled, Location},
16};
17use commonware_cryptography::Hasher;
18use commonware_runtime::{Clock, Metrics, Storage};
19use thiserror::Error;
20
21pub mod any;
22pub mod current;
23pub mod immutable;
24pub mod keyless;
25pub mod operation;
26pub mod store;
27pub mod sync;
28pub mod verify;
29use tracing::warn;
30pub use verify::{
31    create_multi_proof, create_proof, create_proof_store, create_proof_store_from_digests,
32    digests_required_for_proof, extract_pinned_nodes, verify_multi_proof, verify_proof,
33    verify_proof_and_extract_digests,
34};
35
36/// Errors that can occur when interacting with an authenticated database.
37#[derive(Error, Debug)]
38pub enum Error {
39    #[error("mmr error: {0}")]
40    Mmr(#[from] crate::mmr::Error),
41
42    #[error("metadata error: {0}")]
43    Metadata(#[from] crate::metadata::Error),
44
45    #[error("journal error: {0}")]
46    Journal(#[from] crate::journal::Error),
47
48    #[error("runtime error: {0}")]
49    Runtime(#[from] commonware_runtime::Error),
50
51    #[error("operation pruned: {0}")]
52    OperationPruned(Location),
53
54    /// The requested key was not found in the snapshot.
55    #[error("key not found")]
56    KeyNotFound,
57
58    /// The key exists in the db, so we cannot prove its exclusion.
59    #[error("key exists")]
60    KeyExists,
61
62    #[error("unexpected data at location: {0}")]
63    UnexpectedData(Location),
64
65    #[error("location out of bounds: {0} >= {1}")]
66    LocationOutOfBounds(Location, Location),
67
68    #[error("prune location {0} beyond last commit {1}")]
69    PruneBeyondCommit(Location, Location),
70
71    #[error("prune location {0} beyond inactivity floor {1}")]
72    PruneBeyondInactivityFloor(Location, Location),
73
74    #[error("uncommitted operations present")]
75    UncommittedOperations,
76}
77
78/// Utility to align the sizes of an MMR and location journal pair, used by keyless, immutable &
79/// variable adb recovery. Returns the aligned size.
80async fn align_mmr_and_locations<E: Storage + Clock + Metrics, H: Hasher>(
81    mmr: &mut journaled::Mmr<E, H>,
82    locations: &mut Journal<E, u32>,
83) -> Result<u64, Error> {
84    let aligned_size = {
85        let locations_size = locations.size().await;
86        let mmr_leaves = *mmr.leaves();
87        if locations_size > mmr_leaves {
88            warn!(
89                mmr_leaves,
90                locations_size, "rewinding misaligned locations journal"
91            );
92            locations.rewind(mmr_leaves).await?;
93            locations.sync().await?;
94            mmr_leaves
95        } else if mmr_leaves > locations_size {
96            warn!(mmr_leaves, locations_size, "rewinding misaligned mmr");
97            mmr.pop((mmr_leaves - locations_size) as usize).await?;
98            locations_size
99        } else {
100            locations_size // happy path
101        }
102    };
103
104    // Verify post-conditions hold.
105    assert_eq!(aligned_size, locations.size().await);
106    assert_eq!(aligned_size, mmr.leaves());
107
108    Ok(aligned_size)
109}
commonware_storage/adb/mod.rs

commonware_storage/adb/
mod.rs
