[−][src]Struct sp4r53::Tree
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
[src]
pub fn new() -> Self
[src]
Creates a new empty sparse Merkle tree.
pub fn root(&self) -> Option<Hash>
[src]
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
[src]
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
[src]
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
[src]
Returns whether the tree contains a leaf with the provided hash.
pub fn proove(&mut self, hashes: &[Hash]) -> Result<Proof, Error>
[src]
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
[src]
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
[src]
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
[src]
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
Auto Trait Implementations
impl RefUnwindSafe for Tree
impl Send for Tree
impl Sync for Tree
impl Unpin for Tree
impl UnwindSafe for Tree
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Same<T> for T
type Output = T
Should always be Self
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,