Struct merkle_log::MerkleLog

pub struct MerkleLog<D: Digest> { /* fields omitted */ }

A Merkle Tree-Structured Log is a potentially unbalanced merkle tree containing the entries of an append-only log.

It extends a traditional merkle tree by allowing for:

• continually appending new entries (even when the length of the log is not a power of two)
• providing proofs that a previous log head is a prefix of (contained within) the current log.

Example

use merkle_log::{MemoryStore, MerkleLog, Store};
use sha2::Sha256;

#[async_std::main]
async fn main() {
    let mut store = MemoryStore::default();

    // first entry
    let entry = b"hello";
    let mut log = MerkleLog::<Sha256>::new(&entry, &mut store).await.unwrap();
    let initial_head = *log.head();
    let initial_log = log.clone();

    // second entry
    let entry = b"world";
    log.append(entry, &mut store).await.unwrap();

    // prove existence of initial entry by its digest
    let proof = log.prove(0, &initial_head, &store).await.unwrap();
    assert!(log.verify(0, &initial_head, &proof));

    // prove that head is a prefix of the current log
    let (prefix_proof, head_proof) = log.prove_prefix(&initial_log, &store).await.unwrap();
    assert!(log.verify_prefix(&head_proof, &initial_log, &prefix_proof));
}

Implementations

impl<D: Digest> MerkleLog<D>

pub async fn new<S: Store>(
    entry: impl AsRef<[u8]>,
    store: &mut S
) -> Result<Self, Error>

Creates a new MerkleLog from the first log entry.

pub fn root_id(&self) -> TreeID

The unique TreeID of the current tree root. TreeID: crate::TreeID

pub fn head_id(&self) -> TreeID

The unique TreeID of the current head. TreeID: crate::TreeID

pub fn size(&self) -> u64

The size of the log.

pub fn head(&self) -> &Node

The digest of the current head.

pub fn root(&self) -> &Node

The merkle root of the log.

pub async fn prove<S: Store>(
    &self,
    entry_index: u64,
    entry_node: &Node,
    store: &S
) -> Result<Proof, Error>

Creates a proof that an entry is contained within the current log.

pub fn verify(&self, entry_index: u64, entry_node: &Node, proof: &Proof) -> bool

Verifies a proof asserting that theentry_node exists at entry_index within the current log.

pub async fn prove_prefix<S: Store>(
    &self,
    prefix: &Self,
    store: &S
) -> Result<(Proof, Proof), Error>

Creates a proof that a prior log head is a prefix of the current log, as well as a proof that the current head is within the same log.

This involves producing a set of nodes, some of which are common to the subtree containing the prefix and the full tree containing both the prefix and the head. Verifying these proofs should convince the verifier that both the prefix and the head belong to the same log.

pub fn verify_prefix(
    &self,
    head_proof: &Proof,
    prefix: &Self,
    prefix_proof: &Proof
) -> bool

Verifies the prefix and head proofs against a known prefix and the current log.

pub async fn append<S: Store>(
    &mut self,
    entry: impl AsRef<[u8]>,
    store: &mut S
) -> Result<Node, Error>

Appends a new entry to the log.

Trait Implementations

impl<D: Clone + Digest> Clone for MerkleLog<D>

fn clone(&self) -> MerkleLog<D>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<D: Clone + Digest> Copy for MerkleLog<D> where
    Output<D>: Copy, 

impl<D: Debug + Digest> Debug for MerkleLog<D>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.