Crate akd

An implementation of an auditable key directory (AKD), also known as a verifiable registry or authenticated dictionary.

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, 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: Allows the directory server to insert and update new entries into the directory.
• 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: 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: 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 awaited. 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{};

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 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::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 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.

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.

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::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.

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.

// 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.

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:

Re-exports

• pub use append_only_zks::Azks;
• pub use directory::Directory;
• pub use directory::HistoryParams;
• pub use helper_structs::EpochHash;

Modules

• append_only_zks
  An implementation of an append-only zero knowledge set
• auditor
  Code for an auditor of a authenticated key directory
• client
  Code for a client of a auditable key directory
• configuration
  Defines the configuration trait and implementations for various configurations
• directory
  Implementation of an auditable key directory
• ecvrf
  This module contains implementations of a verifiable random function (currently only ECVRF). VRFs are used, in the case of this crate, to anonymize the user id <-> node label mapping into a 1-way hash, which is verifyable without being regeneratable without the secret key.
• errors
  Errors for various data structure operations.
• hash
  This module contains all the hashing utilities needed for the AKD directory and verification operations
• helper_structs
  Helper structs that are used for various data structures, to make it easier to pass arguments around.
• local_auditing
  This module contains all the type conversions between internal AKD & message types with the protobuf types
• node_label
  This module contains the specifics for NodeLabel only, other types don’t have the same level of detail and aren’t broken into sub-modules
• proto
  This module contains all the protobuf types for type conversion between internal and external types. NOTE: Protobuf encoding is NOT supported in nostd environments. The generated code is using vector too heavily to be nostd compliant
• storage
  Storage module for a auditable key directory
• tree_node
  The implementation of a node for a history patricia tree
• verify
  This module contains verification calls for different proofs contained in the AKD crate

Structs

• AkdLabel
  The label of a particular entry in the AKD
• AkdValue
  The value of a particular entry in the AKD
• AppendOnlyProof
  Proof that no leaves were deleted from the initial epoch. This is done using a list of SingleAppendOnly proofs, one proof for each epoch between the initial epoch and final epochs which are being audited.
• AzksElement
  Represents an element to be inserted into the AZKS. This is a pair consisting of a label (NodeLabel) and a value. The purpose of the directory publish is to convert an insertion set of (AkdLabel, AkdValue) tuples into a set of AzksElements, which are then inserted into the AZKS.
• AzksValue
  The value associated with an element of the AZKS
• AzksValueWithEpoch
  Used to denote an azks value that has been hashed together with an epoch
• ExampleLabel
  An example domain separation label (this should not be used in a production setting!)
• ExperimentalConfiguration
  An experimental configuration
• HistoryProof
  This proof is just an array of UpdateProofs.
• LookupProof
  Proof that a given label was at a particular state at the given epoch. This means we need to show that the state and version we are claiming for this node must have been:
• MembershipProof
  Merkle proof of membership of a NodeLabel with a particular hash value in the tree at a given epoch
• NodeLabel
  Represents the label of a AKD node
• NonMembershipProof
  Merkle Patricia proof of non-membership for a NodeLabel in the tree at a given epoch.
• SiblingProof
  Represents a specific level of the tree with the parental sibling and the direction of the parent for use in tree hash calculations
• SingleAppendOnlyProof
  Proof that no leaves were deleted from the initial epoch. This means that unchanged_nodes should hash to the initial root hash and the vec of inserted is the set of leaves inserted between these epochs. If we built the tree using the nodes in inserted and the nodes in unchanged_nodes as the leaves with the correct epoch of insertion, it should result in the final root hash.
• UpdateProof
  A vector of UpdateProofs are sent as the proof to a history query for a particular key. For each version of the value associated with the key, the verifier must check that:
• VerifyResult
  The payload that is outputted as a result of successful verification of a LookupProof or HistoryProof. This includes the fields containing the epoch that the leaf was published in, the version corresponding to the value, and the value itself.

Enums

• Direction
  This type is used to indicate a direction for a particular node relative to its parent. We use 0 to represent “left” and 1 to represent “right”.
• HistoryVerificationParams
  Parameters for customizing how history proof verification proceeds
• PrefixOrdering
  This type is used to indicate whether or not one label is a prefix of another, and if so, whether the longer string has a 0 after the prefix, or a 1 after the prefix. If the first label is equal to the second, or not a prefix of the second, then it is considered invalid.
• VersionFreshness
  Whether or not a node is marked as stale or fresh Stale nodes are no longer active because a newer version exists to replace them.

Constants

• ARITY
  The number of children each non-leaf node has in the tree
• EMPTY_VALUE
  The value to be hashed every time an empty node’s hash is to be considered
• LEAF_LEN
  The length of a leaf node’s label (in bits)
• ROOT_LABEL
  The label used for a root node
• TOMBSTONE
  A “tombstone” is a false value in an AKD ValueState denoting that a real value has been removed (e.g. data rentention policies). Should a tombstone be encountered, we have to assume that the hash of the value is correct, and we move forward without being able to verify the raw value. We utilize an empty array to save space in the storage layer

Traits

• Configuration
  Trait for customizing the directory’s cryptographic operations
• DomainLabel
  Trait for specifying a domain separation label that should be specific to the application
• SizeOf
  Retrieve the in-memory size of a structure

Type Aliases

• Digest
  A hash digest of a specified number of bytes