Crate akd

source ·
Expand description

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

⚠️ Warning: This implementation has not been audited and is not ready for use in a real system. Use at your own risk!

Overview

An authenticated key directory (AKD) is an example of an authenticated data structure. An AKD lets a server commit to a key-value store as it evolves over a sequence of timesteps, also known as epochs.

The security of this protocol relies on the following two assumptions for all parties:

  • a small commitment is viewable by all users,
  • at any given epoch transition, there exists at least one honest auditor, who audits the server’s latest commitment, relative to the previous commitment.

Statelessness

This library is meant to be stateless, in that it runs without storing a majority of the data locally, where the code is running, and instead, uses a storage::Storable trait for each type to be stored in an external database.

Setup

A directory::Directory represents an AKD. To setup a directory::Directory, we first need to decide on a database and a hash function. For this example, we use the winter_crypto::hashers::Blake3_256 as the hash function, storage::memory::AsyncInMemoryDatabase as storage and ecvrf::HardCodedAkdVRF.

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;
type Blake3 = Blake3_256<BaseElement>;
use akd::directory::Directory;

type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
};

Adding key-value pairs to the akd

To add key-value pairs to the akd, we assume that the types of keys and the corresponding values are String. After adding key-value pairs to the akd’s data structure, it also needs to be committed. To do this, after running the setup, as in the previous step, we use the publish function of an akd. The argument of publish is a vector of tuples of type (AkdLabel::from_utf8_str(String), AkdValue::from_utf8_str(String)). See below for example usage.

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;
type Blake3 = Blake3_256<BaseElement>;
use akd::directory::Directory;

type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    // commit the latest changes
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
         (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
      .await;
};

Responding to a client lookup

We can use the lookup API call of the directory::Directory to prove the correctness of a client lookup at a given epoch. If

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::directory::Directory;
type Blake3 = Blake3_256<BaseElement>;
type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;

let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
        (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
         .await.unwrap();
    // Generate latest proof
    let lookup_proof = akd.lookup::<Blake3_256<BaseElement>>(AkdLabel::from_utf8_str("hello")).await;
};

Verifying a lookup proof

To verify the above proof, we call the client’s verification algorithm, with respect to the latest commitment, as follows:

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::directory::Directory;
use akd::client;
type Blake3 = Blake3_256<BaseElement>;
type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;

let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
        (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
         .await.unwrap();
    // Generate latest proof
    let lookup_proof = akd.lookup::<Blake3_256<BaseElement>>(AkdLabel::from_utf8_str("hello")).await.unwrap();
    let current_azks = akd.retrieve_current_azks().await.unwrap();
    // Get the latest commitment, i.e. azks root hash
    let root_hash = akd.get_root_hash::<Blake3_256<BaseElement>>(&current_azks).await.unwrap();
    // Get the VRF public key of the server
    let vrf_pk = akd.get_public_key().await.unwrap();
    client::lookup_verify::<Blake3_256<BaseElement>>(
        &vrf_pk,
        root_hash,
        AkdLabel::from_utf8_str("hello"),
        lookup_proof,
    ).unwrap();
};

Responding to a client history query

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 the key_history API call of the directory::Directory to prove the history of a key’s values at a given epoch, as follows.

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::directory::Directory;
type Blake3 = Blake3_256<BaseElement>;
type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;

let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
        (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
         .await.unwrap();
    // Generate latest proof
    let history_proof = akd.key_history::<Blake3_256<BaseElement>>(&AkdLabel::from_utf8_str("hello")).await;
};

Verifying a key history proof

To verify the above proof, we again call the client’s verification algorithm, defined in client, with respect to the latest commitment, as follows:

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::client::key_history_verify;
use akd::directory::Directory;
type Blake3 = Blake3_256<BaseElement>;
type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;
let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
        (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
         .await.unwrap();
    // Generate latest proof
    let history_proof = akd.key_history::<Blake3_256<BaseElement>>(&AkdLabel::from_utf8_str("hello")).await.unwrap();
    let current_azks = akd.retrieve_current_azks().await.unwrap();
    // Get the azks root hashes at the required epochs
    let (root_hashes, previous_root_hashes) = akd::directory::get_key_history_hashes::<_, Blake3_256<BaseElement>, HardCodedAkdVRF>(&akd, &history_proof).await.unwrap();
    let current_azks = akd.retrieve_current_azks().await.unwrap();
    let current_epoch = current_azks.get_latest_epoch();
    let root_hash = akd.get_root_hash::<Blake3>(&current_azks).await.unwrap();
    let vrf_pk = akd.get_public_key().await.unwrap();
    key_history_verify::<Blake3_256<BaseElement>>(
        &vrf_pk,
        root_hash,
        current_epoch,
        AkdLabel::from_utf8_str("hello"),
        history_proof,
        false,
        ).unwrap();
    };

Responding to an audit query

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 winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::directory::Directory;
type Blake3 = Blake3_256<BaseElement>;
type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;

let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    // Commit to the first epoch
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
        (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
         .await.unwrap();
    // Commit to the second epoch
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello3"), AkdValue::from_utf8_str("world3")),
        (AkdLabel::from_utf8_str("hello4"), AkdValue::from_utf8_str("world4")),])
         .await.unwrap();
    // Generate audit proof for the evolution from epoch 1 to epoch 2.
    let audit_proof = akd.audit::<Blake3_256<BaseElement>>(1u64, 2u64).await.unwrap();
};

Verifying an audit proof

The auditor verifies the above proof and the code for this is in auditor.

use winter_crypto::Hasher;
use winter_crypto::hashers::Blake3_256;
use winter_math::fields::f128::BaseElement;
use akd::auditor;
use akd::directory::Directory;
type Blake3 = Blake3_256<BaseElement>;
type Blake3Digest = <Blake3_256<winter_math::fields::f128::BaseElement> as Hasher>::Digest;
use akd::storage::types::{AkdLabel, AkdValue, DbRecord, ValueState, ValueStateRetrievalFlag};
use akd::storage::Storage;
use akd::storage::memory::AsyncInMemoryDatabase;
use akd::ecvrf::HardCodedAkdVRF;

let db = AsyncInMemoryDatabase::new();
async {
    let vrf = HardCodedAkdVRF{};
    let mut akd = Directory::<_, HardCodedAkdVRF>::new::<Blake3_256<BaseElement>>(&db, &vrf, false).await.unwrap();
    // Commit to the first epoch
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello"), AkdValue::from_utf8_str("world")),
        (AkdLabel::from_utf8_str("hello2"), AkdValue::from_utf8_str("world2")),])
         .await.unwrap();
    // Commit to the second epoch
    akd.publish::<Blake3_256<BaseElement>>(vec![(AkdLabel::from_utf8_str("hello3"), AkdValue::from_utf8_str("world3")),
        (AkdLabel::from_utf8_str("hello4"), AkdValue::from_utf8_str("world4")),])
         .await.unwrap();
    // Generate audit proof for the evolution from epoch 1 to epoch 2.
    let audit_proof = akd.audit::<Blake3_256<BaseElement>>(1u64, 2u64).await.unwrap();
    let current_azks = akd.retrieve_current_azks().await.unwrap();
    // Get the latest commitment, i.e. azks root hash
    let start_root_hash = akd.get_root_hash_at_epoch::<Blake3_256<BaseElement>>(&current_azks, 1u64).await.unwrap();
    let end_root_hash = akd.get_root_hash_at_epoch::<Blake3_256<BaseElement>>(&current_azks, 2u64).await.unwrap();
    let hashes = vec![start_root_hash, end_root_hash];
    auditor::audit_verify::<Blake3_256<BaseElement>>(
        hashes,
        audit_proof,
    ).await.unwrap();
};

Compilation Features

The akd crate supports multiple compilation features

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

  2. vrf (on by-default): Will enable support of verifiable random function (VRF) usage within the library. See ecvrf for documentation about the VRF functionality being utilized within AKD. This functionality is added protection so auditors don’t see user identifiers directly and applies a level of user-randomness (think hashing) in the node labels such that clients cannot trivially generate node labels themselves for given identifiers, however they can verify that a label is valid for a given identitifier. Transitively will add dependencies on crates [curve25519-dalek] and [ed25519-dalek]. You can disable the VRF functionality by adding the no-default-features flags to your cargo dependencies.

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

[dependencies]
akd = { version = "0.5", features = ["vrf"] }

[dev-dependencies]
akd = { version = "0.5", features = ["vrf", "public-tests"] }

Re-exports

pub use append_only_zks::Azks;
pub use directory::Directory;
pub use helper_structs::EpochHash;
pub use helper_structs::Node;
pub use node_label::NodeLabel;
pub use storage::types::AkdLabel;
pub use storage::types::AkdValue;

Modules

An implementation of an append-only zero knowledge set
Code for an auditor of a authenticated key directory
Code for a client of a auditable key directory
Implementation of a auditable key directory
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 for various data structure operations.
Helper structs that are used for various data structures, to make it easier to pass arguments around.
The representation for the label of a tree node.
Note that the proofs AppendOnlyProof, MembershipProof and NonMembershipProof are Merkle Patricia tree proofs, while the proofs HistoryProof and LookupProof are AKD proofs.
This module contains serialization calls for helping serialize/deserialize digests
Storage module for a auditable key directory
The implementation of a node for a history patricia tree

Constants

The arity of the underlying tree structure of the akd.
The label used for an empty node
The value to be hashed every time an empty node’s hash is to be considered
The length of a leaf node’s label
The label used for a root node
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

Type Definitions

This type is used to indicate a direction for a particular node relative to its parent.