1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507
// Copyright (c) Meta Platforms, Inc. and affiliates.
//
// This source code is dual-licensed under either the MIT license found in the
// LICENSE-MIT file in the root directory of this source tree or the Apache
// License, Version 2.0 found in the LICENSE-APACHE file in the root directory
// of this source tree. You may select, at your option, one of the above-listed licenses.
//! An implementation of an auditable key directory (AKD), also known as a verifiable registry or authenticated dictionary.
//!
//! ⚠️ **Warning**: This implementation has not been audited (yet). Use at your own risk!
//!
//! # Overview
//! An auditable key directory (AKD) provides an interface to a data structure that stores key-value
//! mappings in a database in a verifiable manner. The data structure is similar to that of a
//! Python [dict](https://docs.python.org/3/tutorial/datastructures.html), where directory entries are indexed by
//! _keys_, and allow for storing a _value_ with some key and then extracting the value given the key.
//!
//! Keys can also be updated to be associated with different values. Each batch of updates to these key-value
//! mappings are associated with an epoch along with a commitment to the database of entries at that point in time.
//! The server that controls the database can use this library to generate proofs of inclusion to clients that wish
//! to query for keys in the database to retrieve their associated values. These proofs can be _verified_ by a client
//! against the corresponding commitment to the database. We can think of this data structure intuitively as a
//! _verifiable dictionary_.
//!
//! This library can be used as part of a key transparency system to generate commitments and serve proofs for a database
//! of public keys. However, note that a full key transparency solution still needs to provide a way for clients to ensure
//! that they are receiving the same commitment for each database epoch. This is outside of the scope of this library and
//! must be handled separately.
//!
//! ### Operations
//!
//! This library supports the following operations for the directory it maintains:
//! - [Publishing](#publishing): Allows the directory server to insert and update new entries into the directory.
//! - [Lookup Proofs](#lookup-proofs): Handles point queries to the directory, providing proofs of validity based on the server's
//! public key and a root hash for an epoch.
//! - [History Proofs](#history-proofs): For a given index in the directory, provides proofs for the history of updates to this
//! entry, matched against the server's public key and a root hash for an epoch.
//! - [Append-Only Proofs](#append-only-proofs): For a pair of epochs, provides a proof to an auditor that the database has evolved
//! consistently and in an append-only manner. These append-only proofs use a verifiable random function (VRF)
//! to avoid leaking any information about the labels and their corresponding values.
//!
//!
//! ### Asynchronicity
//!
//! Note that all of the library functions must be called asynchronously (within
//! `async { ... }` blocks) and the responses must be `await`ed. In the following examples,
//! the necessary `async` blocks are omitted for simplicity.
//!
//! ## Setup
//! A [`Directory`] represents an AKD. To set up a [`Directory`], we first need to pick on
//! a database, a tree configuration, and a VRF. For this example, we use `WhatsAppV1Configuration`
//! as the configuration,
//! [`storage::memory::AsyncInMemoryDatabase`] as in-memory storage, and [`ecvrf::HardCodedAkdVRF`] as the VRF.
//! The [`directory::ReadOnlyDirectory`] creates a read-only directory which cannot be updated.
//! ```
//! use akd::storage::StorageManager;
//! use akd::storage::memory::AsyncInMemoryDatabase;
//! use akd::ecvrf::HardCodedAkdVRF;
//! use akd::directory::Directory;
//!
//! type Config = akd::WhatsAppV1Configuration;
//!
//! let db = AsyncInMemoryDatabase::new();
//! let storage_manager = StorageManager::new_no_cache(db);
//! let vrf = HardCodedAkdVRF{};
//!
//! # tokio_test::block_on(async {
//! let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf)
//! .await
//! .expect("Could not create a new directory");
//! # });
//! ```
//!
//! For more information on setting configurations, see the [Configurations](#configurations) section.
//!
//! ## Publishing
//! To add label-value pairs (of type [`AkdLabel`] and [`AkdValue`]) to the directory, we can call [`Directory::publish`]
//! with a list of the pairs. In the following example, we derive the labels and values from strings. After publishing,
//! the new epoch number and root hash are returned.
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! use akd::EpochHash;
//! use akd::{AkdLabel, AkdValue};
//! use akd::Digest;
//!
//! let entries = vec![
//! (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//!
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! let EpochHash(epoch, root_hash) = akd.publish(entries)
//! .await.expect("Error with publishing");
//! println!("Published epoch {} with root hash: {}", epoch, hex::encode(root_hash));
//! # });
//! ```
//! This function can be called repeatedly to add entries to the directory, with each invocation
//! producing a new epoch and root hash for the directory.
//!
//! ## Lookup Proofs
//! We can call [`Directory::lookup`] to generate a [`LookupProof`] that proves the correctness
//! of a client lookup for an existing entry.
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! # use akd::EpochHash;
//! # use akd::{AkdLabel, AkdValue};
//! # use akd::Digest;
//! #
//! # let entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! # (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! # ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! #
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! # let EpochHash(epoch, root_hash) = akd.publish(entries)
//! # .await.expect("Error with publishing");
//! let (lookup_proof, epoch_hash) = akd.lookup(
//! AkdLabel::from("first entry")
//! ).await.expect("Could not generate proof");
//! # });
//! ```
//!
//! To verify a valid proof, we call [`client::lookup_verify`], with respect to the root hash and
//! the server's public key.
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! # use akd::EpochHash;
//! # use akd::{AkdLabel, AkdValue};
//! # use akd::Digest;
//! #
//! # let entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! # (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! # ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! #
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! # let _ = akd.publish(entries)
//! # .await.expect("Error with publishing");
//! # let (lookup_proof, epoch_hash) = akd.lookup(
//! # AkdLabel::from("first entry")
//! # ).await.expect("Could not generate proof");
//! let public_key = akd.get_public_key().await.expect("Could not fetch public key");
//!
//! let lookup_result = akd::client::lookup_verify::<Config>(
//! public_key.as_bytes(),
//! epoch_hash.hash(),
//! epoch_hash.epoch(),
//! AkdLabel::from("first entry"),
//! lookup_proof,
//! ).expect("Could not verify lookup proof");
//!
//! assert_eq!(
//! lookup_result,
//! akd::VerifyResult {
//! epoch: 1,
//! version: 1,
//! value: AkdValue::from("first value"),
//! },
//! );
//! # });
//! ```
//!
//! ## History Proofs
//! As mentioned above, the security is defined by consistent views of the value for a key at any epoch.
//! To this end, a server running an AKD needs to provide a way to check the history of a key. Note that in this case,
//! the server is trusted for validating that a particular client is authorized to run a history check on a particular key.
//! We can use [`Directory::key_history`] to prove the history of a key's values at a given epoch. The [HistoryParams] field
//! can be used to limit the history that we issue proofs for, but in this example we default to a complete history.
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! # use akd::EpochHash;
//! # use akd::{AkdLabel, AkdValue};
//! # use akd::Digest;
//! #
//! # let entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! # (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! # ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! #
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! # let EpochHash(epoch, root_hash) = akd.publish(entries)
//! # .await.expect("Error with publishing");
//! use akd::HistoryParams;
//!
//! let EpochHash(epoch2, root_hash2) = akd.publish(
//! vec![(AkdLabel::from("first entry"), AkdValue::from("updated value"))],
//! ).await.expect("Error with publishing");
//! let (history_proof, _) = akd.key_history(
//! &AkdLabel::from("first entry"),
//! HistoryParams::default(),
//! ).await.expect("Could not generate proof");
//! # });
//! ```
//! To verify the above proof, we call [`client::key_history_verify`],
//! with respect to the latest root hash and public key, as follows. This function
//! returns a list of values that have been associated with the specified entry, in
//! reverse chronological order.
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! # use akd::EpochHash;
//! # use akd::HistoryParams;
//! # use akd::{AkdLabel, AkdValue};
//! # use akd::Digest;
//! #
//! # let entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! # (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! # ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! #
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! # let _ = akd.publish(entries)
//! # .await.expect("Error with publishing");
//! # let _ = akd.publish(
//! # vec![(AkdLabel::from("first entry"), AkdValue::from("updated value"))],
//! # ).await.expect("Error with publishing");
//! # let (history_proof, epoch_hash) = akd.key_history(
//! # &AkdLabel::from("first entry"),
//! # HistoryParams::default(),
//! # ).await.expect("Could not generate proof");
//! let public_key = akd.get_public_key().await.expect("Could not fetch public key");
//! let key_history_result = akd::client::key_history_verify::<Config>(
//! public_key.as_bytes(),
//! epoch_hash.hash(),
//! epoch_hash.epoch(),
//! AkdLabel::from("first entry"),
//! history_proof,
//! akd::HistoryVerificationParams::default(),
//! ).expect("Could not verify history");
//!
//! assert_eq!(
//! key_history_result,
//! vec![
//! akd::VerifyResult {
//! epoch: 2,
//! version: 2,
//! value: AkdValue::from("updated value"),
//! },
//! akd::VerifyResult {
//! epoch: 1,
//! version: 1,
//! value: AkdValue::from("first value"),
//! },
//! ],
//! );
//! # });
//! ```
//!
//! ## Append-Only Proofs
//! In addition to the client API calls, the AKD also provides proofs to auditors that its commitments evolved correctly.
//! Below we illustrate how the server responds to an audit query between two epochs.
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! # use akd::EpochHash;
//! # use akd::{AkdLabel, AkdValue};
//! # use akd::Digest;
//! #
//! # let entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! # (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! # ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! #
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! # let EpochHash(epoch, root_hash) = akd.publish(entries)
//! # .await.expect("Error with publishing");
//! // Publish new entries into a second epoch
//! let entries = vec![
//! (AkdLabel::from("first entry"), AkdValue::from("new first value")),
//! (AkdLabel::from("third entry"), AkdValue::from("third value")),
//! ];
//! let EpochHash(epoch2, root_hash2) = akd.publish(entries)
//! .await.expect("Error with publishing");
//!
//! // Generate audit proof for the evolution from epoch 1 to epoch 2.
//! let audit_proof = akd.audit(epoch, epoch2)
//! .await.expect("Error with generating proof");
//! # });
//! ```
//! The auditor then verifies the above [`AppendOnlyProof`] using [`auditor::audit_verify`].
//! ```
//! # use akd::storage::StorageManager;
//! # use akd::storage::memory::AsyncInMemoryDatabase;
//! # use akd::ecvrf::HardCodedAkdVRF;
//! # use akd::directory::Directory;
//! #
//! # type Config = akd::WhatsAppV1Configuration;
//! #
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! # let vrf = HardCodedAkdVRF{};
//! # use akd::EpochHash;
//! # use akd::{AkdLabel, AkdValue};
//! # use akd::Digest;
//! #
//! # let entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("first value")),
//! # (AkdLabel::from("second entry"), AkdValue::from("second value")),
//! # ];
//! # let db = AsyncInMemoryDatabase::new();
//! # let storage_manager = StorageManager::new_no_cache(db);
//! #
//! # tokio_test::block_on(async {
//! # let vrf = HardCodedAkdVRF{};
//! # let mut akd = Directory::<Config, _, _>::new(storage_manager, vrf).await.unwrap();
//! # let EpochHash(epoch, root_hash) = akd.publish(entries)
//! # .await.expect("Error with publishing");
//! # // Publish new entries into a second epoch
//! # let new_entries = vec![
//! # (AkdLabel::from("first entry"), AkdValue::from("new first value")),
//! # (AkdLabel::from("third entry"), AkdValue::from("third value")),
//! # ];
//! # let EpochHash(epoch2, root_hash2) = akd.publish(new_entries)
//! # .await.expect("Error with publishing");
//! #
//! # // Generate audit proof for the evolution from epoch 1 to epoch 2.
//! # let audit_proof = akd.audit(epoch, epoch2)
//! # .await.expect("Error with generating proof");
//! let audit_result = akd::auditor::audit_verify::<Config>(
//! vec![root_hash, root_hash2],
//! audit_proof,
//! ).await;
//! assert!(audit_result.is_ok());
//! # });
//! ```
//!
//! # Advanced Usage
//!
//! ## Configurations
//!
//! This library supports the notion of a [Configuration], which can be used to customize the directory's cryptographic operations. We provide
//! two default configurations: [WhatsAppV1Configuration] and [ExperimentalConfiguration].
//!
//! - [WhatsAppV1Configuration] matches the configuration used for Whatsapp's key transparency deployment
//! - [ExperimentalConfiguration] is the configuration which matches the main branch deployment for AKD
//!
//! An [ExperimentalConfiguration] implements domain separation for its hashing operations by the specifying of a struct that
//! implements [DomainLabel]. For example, to set the domain label as `"ExampleLabel"`, we define the struct [ExampleLabel] as:
//! ```
//! #[derive(Clone)]
//! struct ExampleLabel;
//!
//! impl akd::DomainLabel for ExampleLabel {
//! fn domain_label() -> &'static [u8] {
//! "ExampleLabel".as_bytes()
//! }
//! }
//! ```
//! An application can set their own specific domain label to a custom string achieve domain separation from other applications.
//!
//! ## Compilation Features
//!
//! This crate supports multiple compilation features:
//!
//! Configurations:
//! - `whatsapp_v1`: Enables usage of [WhatsAppV1Configuration]
//! - `experimental`: Enables usage of [ExperimentalConfiguration]
//!
//! Performance optimizations:
//! - `parallel_vrf`: Enables the VRF computations to be run in parallel
//! - `parallel_insert`: Enables nodes to be inserted via multiple threads during a publish operation
//! - `preload_history`: Enable pre-loading of the nodes when generating history proofs
//! - `greedy_lookup_preload`: Greedy loading of lookup proof nodes
//!
//! Benchmarking:
//! - `bench`: Feature used when running benchmarks
//! - `slow_internal_db`: Artifically slow the in-memory database (for benchmarking)
//!
//! Utilities:
//! - `public_auditing`: Enables the publishing of audit proofs
//! - `serde_serialization`: Will enable [`serde`] serialization support on all public structs used in storage & transmission operations. This is helpful
//! in the event you wish to directly serialize the structures to transmit between library <-> storage layer or library <-> clients. If you're
//! also utilizing VRFs (see (2.) below) it will additionally enable the _serde_ feature in the ed25519-dalek crate.
//! - `runtime_metrics`: Collects metrics on the accesses to the storage layer
//! - `public_tests`: Will expose some internal sanity testing functionality, which is often helpful so you don't have to write all your own
//! unit test cases when implementing a storage layer yourself. This helps guarantee the sanity of a given storage implementation. Should be
//! used only in unit testing scenarios by altering your Cargo.toml as such:
//!
#![warn(missing_docs)]
#![allow(clippy::multiple_crate_versions)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#[cfg(feature = "rand")]
extern crate rand;
// Due to the amount of types an implementing storage layer needs to access,
// it's quite unreasonable to expose them all at the crate root, and a storage
// implementer will simply need to import the necessary inner types which are
// a dependency of ths [`Storage`] trait anyways
pub mod append_only_zks;
pub mod auditor;
pub mod client;
pub mod directory;
pub mod errors;
pub mod helper_structs;
pub mod storage;
pub mod tree_node;
#[cfg(feature = "public_auditing")]
pub mod local_auditing;
pub use akd_core::configuration::*;
pub use akd_core::hash::Digest;
pub use akd_core::verify;
pub use akd_core::*;
#[macro_use]
mod utils;
// ========== Type re-exports which are commonly used ========== //
pub use append_only_zks::Azks;
pub use client::HistoryVerificationParams;
pub use directory::{Directory, HistoryParams};
pub use helper_structs::EpochHash;
// ========== Constants and type aliases ========== //
#[cfg(any(test, feature = "public_tests"))]
pub mod test_utils;
#[cfg(test)]
mod tests;
/// The length of a leaf node's label (in bits)
pub const LEAF_LEN: u32 = 256;
/// The label used for a root node
pub const ROOT_LABEL: crate::node_label::NodeLabel = crate::NodeLabel {
label_val: [0u8; 32],
label_len: 0,
};