Struct sp4r53::Tree

pub struct Tree { /* fields omitted */ }

A sparse Merkle tree that only recomputes its branches' hashes when asked.

The tree doesn't compute its branches' hashes after inserting or removing data and instead remove invalidated hashes, and mark itself as invalid. To re-compute the removed hashes and re-validate the tree, you need to flush it.

Implementations

impl Tree

pub fn new() -> Self

Creates a new empty sparse Merkle tree.

pub fn root(&self) -> Option<Hash>

Returns the root hash of the tree, or None if the tree is invalid.

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");
let baz = blake3::hash(b"baz");

let mut tree = Tree::new();

tree.insert(foo);
tree.insert(bar);
tree.insert(baz);

let root1 = tree.flush();
assert_eq!(tree.root(), Some(root1));

tree.remove(bar);

let root2 = tree.flush();
assert_eq!(tree.root(), Some(root2));

tree.insert(bar);

let root3 = tree.flush();
assert_eq!(tree.root(), Some(root3));

pub fn leaves(&self) -> usize

Returns the number of leaves in the tree.

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");
let baz = blake3::hash(b"baz");

let mut tree = Tree::new();

tree.insert(foo);
tree.insert(bar);
tree.insert(baz);

assert_eq!(tree.leaves(), 3);

tree.remove(bar);

assert_eq!(tree.leaves(), 2);

pub fn is_valid(&self) -> bool

Returns whether the tree is valid.

A newly created tree is invalid, and calling insert() or remove() will make a valid tree invalid. Calling flush() or proove() (whether the method returns an error or not), will make the tree valid.

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");

let mut tree = Tree::new();
assert_eq!(tree.is_valid(), false);

tree.flush();
assert_eq!(tree.is_valid(), true);

tree.insert(foo);
tree.insert(bar);
assert_eq!(tree.is_valid(), false);

tree.flush();
assert_eq!(tree.is_valid(), true);

pub fn contains(&self, hash: Hash) -> bool

Returns whether the tree contains a leaf with the provided hash.

pub fn proove(&mut self, hashes: &[Hash]) -> Result<Proof, Error>

Flushes the tree and tries to generate a new Proof of the inclusion of the given hashes.

Note that this is the same as calling flush() and then Proof::new().

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");
let baz = blake3::hash(b"baz");

let mut tree = Tree::new();

tree.insert(foo);
tree.insert(bar);
tree.insert(baz);

let proof = tree.proove(&[foo, baz]).unwrap();

let root = tree.root().unwrap();
assert_eq!(proof.verify(root), true);

let hashes = proof.hashes();
assert_eq!(hashes.len(), 2);
assert_eq!(hashes.contains(&foo), true);
assert_eq!(hashes.contains(&bar), false);
assert_eq!(hashes.contains(&baz), true);

pub fn insert(&mut self, hash: Hash) -> bool

Inserts an hash into the tree, invalidating it and returning true if it didn't already contain it, or false otherwise.

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");

let mut tree = Tree::new();

assert_eq!(tree.insert(foo), true);
assert_eq!(tree.insert(bar), true);
assert_eq!(tree.is_valid(), false);

tree.flush();
assert_eq!(tree.is_valid(), true);

assert_eq!(tree.insert(foo), false);
assert_eq!(tree.insert(bar), false);
assert_eq!(tree.is_valid(), true);

tree.remove(foo);

assert_eq!(tree.insert(foo), true);
assert_eq!(tree.insert(bar), false);
assert_eq!(tree.is_valid(), false);

pub fn remove(&mut self, hash: Hash) -> bool

Removes an hash from the tree, invalidating it and returning true if it contained it, or false otherwise.

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");

let mut tree = Tree::new();

tree.insert(foo);
tree.insert(bar);

assert_eq!(tree.remove(foo), true);
assert_eq!(tree.is_valid(), false);

tree.flush();
assert_eq!(tree.is_valid(), true);

assert_eq!(tree.remove(foo), false);
assert_eq!(tree.is_valid(), true);

tree.insert(foo);

assert_eq!(tree.remove(foo), true);
assert_eq!(tree.remove(bar), true);
assert_eq!(tree.is_valid(), false);

pub fn flush(&mut self) -> Hash

Flushes the tree, recomputing any missing or invalidated branch hash, and marking the tree as valid.

Example

use sp4r53::{blake3, Tree};

let foo = blake3::hash(b"foo");
let bar = blake3::hash(b"bar");
let baz = blake3::hash(b"baz");

let mut tree = Tree::new();

tree.insert(foo);
tree.insert(bar);
tree.insert(baz);

let root1 = tree.flush();

tree.remove(bar);

let root2 = tree.flush();
assert_ne!(root1, root2);

tree.insert(bar);

let root3 = tree.flush();
assert_eq!(root1, root3);

Trait Implementations

impl Debug for Tree

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

Formats the value using the given formatter.

impl Default for Tree

fn default() -> Tree

Returns the "default value" for a type.