Struct MerkleLog

Source

pub struct MerkleLog<D: Digest<N>, N: Node> { /* private fields */ }

Expand description

A Merkle Tree-Structured Log is a potentially unbalanced merkle tree containing the entries of an append-only log (maximum 2^63 + 1 entries).

It extends the functionality of 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 digest::Output;
use sha2::Sha256;

let mut store = MemoryStore::default();

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

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

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

Implementations§

Source §

impl<D, N> MerkleLog<D, N>
where D: Digest<N>, N: Node,

Source

pub fn new(entry: impl AsRef<[u8]>) -> Self

Creates a new MerkleLog from the first log entry.

Source

pub const fn len(&self) -> u64

The size of the log.

Source

pub const fn head(&self) -> &N

The Node of the current head.

Source

pub const fn head_id(&self) -> TreeID

The unique TreeID of the current head.

Source

pub const fn root(&self) -> &N

The merkle root Node of the log.

Source

pub const fn root_id(&self) -> TreeID

The unique TreeID of the current root.

Source

pub const fn root_height(&self) -> u8

The unique TreeID of the current tree root.

Source

pub fn proving_ids(&self, entry_index: u64) -> impl Iterator<Item = TreeID>

Produces the TreeIDs whose values are required to produce a valid proof of inclusion for a particular leaf entry in the log, starting from the head.

§Examples

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

let mut store = MemoryStore::default();

let entry = b"hello";
let mut log = MerkleLog::<Sha256, [u8; 32]>::new(&entry);
store.set_leaf(log.head_id(), *log.head()).unwrap();

log.append(&entry, &mut store).unwrap(); // new size 2
log.append(&entry, &mut store).unwrap(); // new size 3
assert_eq!(log.proving_ids(1).collect::<Vec<_>>(), &[TreeID::from(0), TreeID::from(4)]);

log.append(&entry, &mut store).unwrap(); // new size 4
assert_eq!(log.proving_ids(1).collect::<Vec<_>>(), &[TreeID::from(0), TreeID::from(5)]);
assert_eq!(log.proving_ids(2).collect::<Vec<_>>(), &[TreeID::from(6), TreeID::from(1)]);

Source

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

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

Source

pub fn verify( &self, entry_index: u64, entry_node: &N, proof: &Proof<N>, ) -> Result<bool, Error>

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

Source

pub fn appending_ids(&self) -> impl Iterator<Item = TreeID>

Produces the TreeIDs whose values are required to append the next entry to log. See TreeID::appending_ids for additional doctests.

§Examples

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

let mut store = MemoryStore::default();

let entry = b"hello";
let mut log = MerkleLog::<Sha256, [u8; 32]>::new(&entry);
store.set_leaf(log.head_id(), *log.head()).unwrap();
assert_eq!(log.appending_ids().collect::<Vec<_>>(), &[TreeID::from(0)]);

log.append(&entry, &mut store).unwrap(); // new size 2
assert_eq!(log.appending_ids().collect::<Vec<_>>(), &[TreeID::from(1)]);

log.append(&entry, &mut store).unwrap(); // new size 3
assert_eq!(log.appending_ids().collect::<Vec<_>>(), &[TreeID::from(1), TreeID::from(4)]);

log.append(&entry, &mut store).unwrap(); // new size 4
assert_eq!(log.appending_ids().collect::<Vec<_>>(), &[TreeID::from(3)]);

Source

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

Appends a new entry to the log, returning the new permanent Nodes to store.

§Examples

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

let mut store = MemoryStore::default();

let mut entry = b"hello";
let mut log = MerkleLog::<Sha256, [u8; 32]>::new(&entry);
store.set_leaf(log.head_id(), *log.head()).unwrap();
assert_eq!(log.len(), 1);
assert_eq!(log.head_id(), TreeID::from(0));
assert_eq!(log.head(), store.get(&log.head_id()).unwrap());

log.append(b"world", &mut store).unwrap();
assert_eq!(log.len(), 2);
assert_eq!(log.head_id(), TreeID::from(2));
assert_eq!(log.root(), store.get(&TreeID::from(1)).unwrap());