Module qmdb 

A collection of authenticated databases inspired by QMDB (Quick Merkle Database).

Terminology

A database’s state is derived from an append-only log of state-changing operations.

In a keyed database, a key either has a value or it doesn’t, and different types of operations modify the state of a specific key. A key that has a value can change to one without a value through the delete operation. The update operation gives a key a specific value. We sometimes call an update for a key that doesn’t already have a value a create operation, but its representation in the log is the same.

Keys with values are called active. An operation is called active if (1) its key is active, (2) it is an update operation, and (3) it is the most recent operation for that key.

Database Lifecycle

All variants are modified through a batch API that follows a common pattern:

1. Create a batch from the database.
2. Stage mutations on the batch.
3. Merkleize the batch – this resolves mutations against the current state and computes the Merkle root that would result from applying them.
4. Inspect the root or create child batches.
5. Apply the batch to the database (uncommitted ancestors are applied automatically).

The specific mutation methods vary by variant. See each variant’s module documentation for the concrete API and usage examples.

Durability

commit() makes applied state durable. start_sync() is its pipelined form, which also tries to advance the recovery watermark to bound startup recovery. sync() makes applied state durable and guarantees no recovery is needed on startup after a crash.

Ownership

Mutating methods take the database by value and return it on success. If a mutating method returns an error, or its future is dropped before it finishes, the database is gone: state that was not yet durable is discarded, but everything already on disk stays recoverable. This applies to validation errors too (e.g. rejecting a stale batch); use each database’s validate_batch to pre-check a batch without risking the handle.

Traits

Keyed mutable variants (any and current) implement any::traits::DbAny.

Acknowledgments

The following resources were used as references when implementing this crate:

• QMDB: Quick Merkle Database
• Merkle Mountain Ranges

Re-exports

pub use verify::create_multi_proof;

pub use verify::create_proof_store;

pub use verify::verify_multi_proof;

pub use verify::verify_proof;

pub use verify::verify_proof_and_extract_digests;

pub use verify::verify_proof_and_pinned_nodes;

Modules

any

An Any authenticated database provides succinct proofs of any value ever associated with a key.

batch_chain

Shared validation for QMDB batch chains.

current

A Current authenticated database provides succinct proofs of any value ever associated with a key, and also whether that value is the current value associated with it.

immutable

An authenticated database that only supports adding new keyed values (no updates or deletions).

keyless

The Keyless qmdb allows for append-only storage of data that can later be retrieved by its location. Both fixed-size and variable-size values are supported via the fixed and variable submodules.

operation

Shared traits and codecs for QMDB operations.

store

Store module containing the unauthenticated key-value store and test helpers.

sync

Shared sync types and functionality for authenticated databases.

verify

Enums

Error

Errors that can occur when interacting with an authenticated database.

Traits

SnapshotBuild

Builds a database’s snapshot index from the operations log.

Functions

hasher

Return the Merkle hasher configuration used by QMDB operation roots and proofs.