Crate dapol

source ·
Expand description

§Proof of Liabilities protocol implemented in Rust

Implementation of the DAPOL+ protocol introduced in the “Generalized Proof of Liabilities” by Yan Ji and Konstantinos Chalkias ACM CCS 2021 paper, available here.

See the top-level doc for the project if you would like to know more about Proof of Liabilities.

§What is contained in this code

This library offers an efficient build algorithm for constructing a binary Merkle Sum Tree representing the liabilities of an organization. Efficiency is achieved through parallelization. Details on the algorithm used can be found in the multi-threaded builder file.

The paper describes a few different accumulator variants. The Sparse Merkle Sum Tree is the DAPOL+ accumulator, but there are a few different axes of variation, such as how the list of entities is embedded within the tree. The 4 accumulator variants are simply slightly different versions of the Sparse Merkle Sum Tree. Only the Non-Deterministic Mapping Sparse Merkle Tree variant has been implemented so far.

The code offers inclusion proof generation & verification using the Bulletproofs protocol for the range proofs.

§Still to be done

This project is currently still a work in progress, but is ready for use as is. The code has not been audited yet (as of Nov 2023). Progress can be tracked here.

Important tasks still to be done:

Performance can be improved.

Alternate accumulators mentioned in the paper should be built:

Other than the above there are a few minor tasks to do, each of which has an issue for tracking.

§How this code can be used

There is both a Rust API and a CLI. Details for the API can be found below, and details for the CLI can be found here.

§Rust API

The API has the following capabilities:

  • build a tree using the builder pattern or a configuration file
  • generate inclusion proofs from a list of entity IDs (tree required)
  • verify an inclusion proof using a root hash (no tree required)
//! Example of a full PoL workflow.
//!
//! 1. Build a tree
//! 2. Serialize tree & root node
//! 3. Verify a root node
//! 4. Generate an inclusion proof
//! 5. Verify an inclusion proof
//!
//! At the time of writing (Nov 2023) only the NDM-SMT accumulator is supported
//! so this is the only type of tree that is used in this example.

use std::path::Path;
use std::str::FromStr;

extern crate clap_verbosity_flag;
extern crate csv;
extern crate dapol;

use dapol::DapolTree;
use dapol::utils::LogOnErrUnwrap;

fn main() {
    let log_level = clap_verbosity_flag::LevelFilter::Debug;
    dapol::utils::activate_logging(log_level);

    // =========================================================================
    // Tree building.

    let accumulator_type = dapol::AccumulatorType::NdmSmt;

    let dapol_tree_1 = build_dapol_tree_using_config_builder(accumulator_type);
    let dapol_tree_2 = build_dapol_tree_using_config_file();

    // The above 2 builder methods produce a different tree because the entities
    // are mapped randomly to points on the bottom layer for NDM-SMT, but the
    // entity mapping of one tree should simply be a permutation of the other.
    // Let's check this:
    match (dapol_tree_1.entity_mapping(), dapol_tree_2.entity_mapping()) {
        (Some(entity_mapping_1), Some(entity_mapping_2)) => {
            for (entity, _) in entity_mapping_1 {
                assert!(entity_mapping_2.contains_key(&entity));
            }
        }
        _ => panic!("Expected both trees to be NDM-SMT"),
    };

    // Since the mappings are not the same the root hashes won't be either.
    assert_ne!(dapol_tree_1.root_hash(), dapol_tree_2.root_hash());

    // =========================================================================
    // (De)serialization.

    let src_dir = env!("CARGO_MANIFEST_DIR");
    let examples_dir = Path::new(&src_dir).join("examples");
    let serialization_path = examples_dir.join("my_serialized_tree_for_testing.dapoltree");
    let _ = dapol_tree_1.serialize(serialization_path.clone()).unwrap();

    let dapol_tree_1 = DapolTree::deserialize(serialization_path).unwrap();

    let public_root_path = examples_dir.join("public_root_data.json");
    // let _ = dapol_tree_1.serialize_public_root_data(public_root_path.clone()).unwrap();
    let public_root_data = DapolTree::deserialize_public_root_data(public_root_path).unwrap();

    let secret_root_path = examples_dir.join("secret_root_data.json");
    // let _ = dapol_tree_1.serialize_secret_root_data(secret_root_path.clone()).unwrap();
    let secret_root_data = DapolTree::deserialize_secret_root_data(secret_root_path).unwrap();

    // =========================================================================
    // Root node verification.

    DapolTree::verify_root_commitment(&public_root_data.commitment, &secret_root_data).unwrap();

    // =========================================================================
    // Inclusion proof generation & verification.

    let entity_id = dapol::EntityId::from_str("john.doe@example.com").unwrap();
    simple_inclusion_proof_generation_and_verification(&dapol_tree_1, entity_id.clone());
    advanced_inclusion_proof_generation_and_verification(&dapol_tree_1, entity_id);
}

/// Example on how to construct a DAPOL tree.
///
/// Build the tree via the config builder.
pub fn build_dapol_tree_using_config_builder(
    accumulator_type: dapol::AccumulatorType,
) -> dapol::DapolTree {
    let src_dir = env!("CARGO_MANIFEST_DIR");
    let resources_dir = Path::new(&src_dir).join("examples");

    let secrets_file_path = resources_dir.join("dapol_secrets_example.toml");
    let entities_file_path = resources_dir.join("entities_example.csv");

    let height = dapol::Height::expect_from(16u8);
    let salt_b = dapol::Salt::from_str("salt_b").unwrap();
    let salt_s = dapol::Salt::from_str("salt_s").unwrap();
    let max_liability = dapol::MaxLiability::from(10_000_000u64);
    let max_thread_count = dapol::MaxThreadCount::from(8u8);
    let master_secret = dapol::Secret::from_str("master_secret").unwrap();
    let num_entities = 100u64;

    // The builder requires at least the following to be given:
    // - accumulator_type
    // - entities
    // - secrets
    // The rest can be left to be default.
    let mut config_builder = dapol::DapolConfigBuilder::default();
    config_builder
        .accumulator_type(accumulator_type)
        .height(height.clone())
        .salt_b(salt_b.clone())
        .salt_s(salt_s.clone())
        .max_liability(max_liability.clone())
        .max_thread_count(max_thread_count.clone());

    // You only need to specify 1 of the following secret input methods.
    config_builder
        .secrets_file_path(secrets_file_path.clone())
        .master_secret(master_secret.clone());

    // You only need to specify 1 of the following entity input methods.
    config_builder
        .entities_file_path(entities_file_path.clone())
        .num_random_entities(num_entities);

    config_builder.build().unwrap().parse().unwrap()
}

/// Example on how to construct a DAPOL tree.
///
/// Build the tree using a config file.
///
/// This is also an example usage of [dapol][utils][LogOnErrUnwrap].
pub fn build_dapol_tree_using_config_file() -> dapol::DapolTree {
    let src_dir = env!("CARGO_MANIFEST_DIR");
    let resources_dir = Path::new(&src_dir).join("examples");
    let config_file = resources_dir.join("dapol_config_example.toml");

    dapol::DapolConfig::deserialize(config_file)
        .log_on_err_unwrap()
        .parse()
        .log_on_err_unwrap()
}

/// Example on how to generate and verify inclusion proofs.
///
/// An inclusion proof can be generated from only a tree + entity ID.
pub fn simple_inclusion_proof_generation_and_verification(
    dapol_tree: &dapol::DapolTree,
    entity_id: dapol::EntityId,
) {
    let inclusion_proof = dapol_tree.generate_inclusion_proof(&entity_id).unwrap();
    inclusion_proof.verify(dapol_tree.root_hash().clone()).unwrap();
}

/// Example on how to generate and verify inclusion proofs.
///
/// The inclusion proof generation algorithm can be customized via some
/// parameters. See [dapol][InclusionProof] for more details.
pub fn advanced_inclusion_proof_generation_and_verification(
    dapol_tree: &dapol::DapolTree,
    entity_id: dapol::EntityId,
) {
    // Determines how many of the range proofs in the inclusion proof are
    // aggregated together. The ones that are not aggregated are proved
    // individually. The more that are aggregated the faster the proving
    // and verification times.
    let aggregation_percentage = dapol::percentage::ONE_HUNDRED_PERCENT;
    let aggregation_factor = dapol::AggregationFactor::Percent(aggregation_percentage);
    let aggregation_factor = dapol::AggregationFactor::default();

    let inclusion_proof = dapol_tree
        .generate_inclusion_proof_with(&entity_id, aggregation_factor)
        .unwrap();

    inclusion_proof.verify(dapol_tree.root_hash().clone()).unwrap();
}

§Features

§Fuzzing

This feature includes the libraries & features required to run the fuzzing tests.

§Testing

This feature opens up additional functions for use withing the library, for usage in tests. One such functionality is the seeding of the NDM-SMT random mapping mechanism. During tests it’s useful to be able to get deterministic tree builds, which cannot be done with plain NDM-SMT because the entities are randomly mapped to bottom-layer nodes. So adding the testing feature exposes functions that allow calling code to provide seeds for the PRNG from rand.

Modules§

  • cli
    Command Line Interface implementation using clap.
  • percentage
    Wrapper for holding an integer-valued percentage.
  • read_write_utils
    Utility functions for reading and writing to files.
  • utils
    Utilities used across the whole crate.

Structs§

  • DapolConfig
    Configuration needed to construct a DapolTree.
  • DapolConfigBuilder
    Builder for DapolConfig.
  • DapolTree
    Proof of Liabilities Sparse Merkle Sum Tree.
  • Entity
    Container for single liability & ID entry into the tree.
  • EntityId
    Abstract representation of an entity ID.
  • EntityIdsParser
    Parser for files containing a list of entity IDs.
  • Hasher
    Abstraction of a hash function, allows easy switching of hash function.
  • Height
    Abstraction for the height of the tree.
  • InclusionProof
    Inclusion proof for a PoL Merkle Tree.
  • MaxLiability
    Abstraction for the max liabilty value. This is a public value representing the maximum amount that any single entity’s liability can be, and is used in the range proofs: $[0, 2^{\text{height}} \times \text{max liability}]$
  • MaxThreadCount
    Abstraction for the max number of threads. Max size of the thread pool when using the parallelized tree build algorithms.
  • RistrettoPoint
    A RistrettoPoint represents a point in the Ristretto group for Curve25519. Ristretto, a variant of Decaf, constructs a prime-order group as a quotient group of a subgroup of (the Edwards form of) Curve25519.
  • RootPublicData
    The public values of the root node.
  • RootSecretData
    The secret values of the root node.
  • Salt
    Salt data type: a 256-bit data packet.
  • Scalar
    The Scalar struct holds an integer \(s < 2^{255} \) which represents an element of \(\mathbb Z / \ell\).
  • Secret
    Secret data type: a 256-bit data packet.

Enums§

Constants§

Functions§