Crate ct_merkle

Crate ct_merkle 

Source
Expand description

§CT Merkle

Crate Docs CI

This is an implementation of the Merkle tree functionality described in the Certificate Transparency specification (RFC 6962). Two properties can be proven about trees:

  1. Inclusion proofs state that a particular item appears in a given tree at a given index.
  2. Consistency proofs state that one tree is a prefix of another tree, i.e., that tree #2 is the result of appending some number of items to the end of tree #1. The number of items can be 0.

This crate provides an append-only memory-backed Merkle tree with inclusion and consistency proof functionality, as well as functions for proof verification. In addition, this crate provides functions for building proofs when the full tree does not fit in memory, e.g., in Certificate Transparency.

§Crate Features

Default feature flags: none

Feature flag list:

  • std - Implements std::error::Error for all error types
  • serde - Implements serde::Serialize and serde::Deserialize for MemoryBackedTree

§License

Licensed under either of

at your option.

§Warning

This code has not been audited in any sense of the word. Use it at your own peril.

§Example usage

Below is an example of two ways to construct an inclusion proof.

use ct_merkle::{
    indices_for_inclusion_proof, InclusionProof,
    mem_backed_tree::MemoryBackedTree
};
use sha2::Sha256;

// Make a new tree whose leaves are strings
let mut tree = MemoryBackedTree::<Sha256, String>::new();
tree.push("hello".to_string());
tree.push("world".to_string());
let root = tree.root();

// Prove inclusion of the last item in the tree
let items_pushed = tree.len();
let item_to_prove = items_pushed - 1;
let inclusion_proof = tree.prove_inclusion(item_to_prove as usize);
// Verify the inclusion
assert!(root
    .verify_inclusion(&"world", item_to_prove, &inclusion_proof)
    .is_ok());

// Now imagine we don't have a memory-backed tree. We will get the indices for
// the hashes to fetch and then build the proof
let indices_to_fetch = indices_for_inclusion_proof(items_pushed, item_to_prove);

//
// Imagine here we fetch the indices in order and place them into `digests`...
//

let digests: Vec<&digest::Output<Sha256>> = inclusion_proof
    .as_bytes()
    .chunks(32)
    .map(TryInto::try_into)
    .collect::<Result<Vec<_>, _>>()
    .unwrap();
let inclusion_proof = InclusionProof::from_digests(digests);
// Verify the inclusion
assert!(root
    .verify_inclusion(&"world", item_to_prove, &inclusion_proof)
    .is_ok());

Re-exports§

pub use digest;

Modules§

mem_backed_tree

Structs§

ConsistencyProof
A proof that one Merkle tree is a prefix of another. In other words, tree #2 is the result of appending some number of items to the end of tree #1.
InclusionProof
A proof that a value appears in a Merkle tree
RootHash
The root hash of a Merkle tree. This uniquely represents the tree.

Enums§

ConsistencyVerifError
An error representing what went wrong when verifying a consistency proof
InclusionVerifError
An error representing what went wrong when verifying an inclusion proof

Traits§

HashableLeaf
Represents a leaf that can be included in a Merkle tree. This only requires that the leaf have a unique hash representation.

Functions§

indices_for_consistency_proof
Given a tree size and number of additions, produces a list of tree node indices whose values in the new tree (i.e., including the additions) are needed to build the consistency proof.
indices_for_inclusion_proof
Given a tree size and index, produces a list of tree node indices whose values we need in order to build the inclusion proof.