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>>(¤t_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>(¤t_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>>(¤t_azks, 1u64).await.unwrap();
let end_root_hash = akd.get_root_hash_at_epoch::<Blake3_256<BaseElement>>(¤t_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
-
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. -
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. -
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
AppendOnlyProof
, MembershipProof
and NonMembershipProof
are Merkle Patricia tree proofs,
while the proofs HistoryProof
and LookupProof
are AKD proofs.