Struct rs_merkle::MerkleTree

pub struct MerkleTree<T: Hasher> { /* private fields */ }

MerkleTree is a Merkle Tree that is well suited for both basic and advanced usage.

Basic features include the creation and verification of Merkle proofs from a set of leaves. This is often done in various cryptocurrencies.

Advanced features include being able to make transactional changes to a tree with being able to roll back to any previously committed state of the tree. This scenario is similar to Git and can be found in databases and file systems.

Implementations

impl<T: Hasher> MerkleTree<T>

pub fn new() -> Self

Creates a new instance of Merkle Tree. Requires a hash algorithm to be specified.

Examples

use rs_merkle::{MerkleTree, algorithms::Sha256};

let merkle_tree: MerkleTree<Sha256> = MerkleTree::new();

let another_merkle_tree = MerkleTree::<Sha256>::new();

pub fn from_leaves(leaves: &[T::Hash]) -> Self

Clones the leaves and builds the tree from them

Examples

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);

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

Returns the tree root - the top hash of the tree. Used in the inclusion proof verification.

Examples

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);

let indices_to_prove = vec![0, 1];
let leaves_to_prove = leaves.get(0..2).ok_or("can't get leaves to prove")?;

let proof = merkle_tree.proof(&indices_to_prove);
let root = merkle_tree.root().ok_or("couldn't get the merkle root")?;

assert!(proof.verify(root, &indices_to_prove, leaves_to_prove, leaves.len()));

pub fn root_hex(&self) -> Option<String>

Similar to MerkleTree::root, but returns a hex encoded string instead of Hasher::Hash.

Examples

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);
let root = merkle_tree.root_hex().ok_or("couldn't get the merkle root")?;

assert_eq!(
    root,
    "7075152d03a5cd92104887b476862778ec0c87be5c2fa1c0a90f87c49fad6eff".to_string()
);

pub fn proof(&self, leaf_indices: &[usize]) -> MerkleProof<T>

Returns the Merkle proof required to prove the inclusion of items in a data set.

Examples

let leaves: Vec<[u8; 32]> = ["a", "b", "c", "d", "e", "f"]
    .iter()
    .map(|x| Sha256::hash(x.as_bytes()))
    .collect();

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);
let indices_to_prove = vec![3, 4];
let leaves_to_prove = leaves.get(3..5).ok_or("can't get leaves to prove")?;
let merkle_proof = merkle_tree.proof(&indices_to_prove);
let merkle_root = merkle_tree.root().ok_or("couldn't get the merkle root")?;
// Serialize proof to pass it to the client
let proof_bytes = merkle_proof.to_bytes();

// Parse proof back on the client
let proof = MerkleProof::<Sha256>::try_from(proof_bytes)?;

assert!(proof.verify(merkle_root, &indices_to_prove, leaves_to_prove, leaves.len()));

pub fn insert(&mut self, leaf: T::Hash) -> &mut Self

Inserts a new leaf. Please note it won’t modify the root just yet; For the changes to be applied to the root, MerkleTree::commit method should be called first. To get the root of the new tree without applying the changes, you can use MerkleTree::uncommitted_root

Examples

Get the root after an insert:

let mut merkle_tree = MerkleTree::<Sha256>::new();
merkle_tree.insert(Sha256::hash("a".as_bytes()));

assert_eq!(merkle_tree.root(), None);

merkle_tree.commit();
assert_eq!(
    merkle_tree.root_hex(),
    Some("ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb".to_string())
);

Inserts also can be chained with MerkleTree::commit for convenience:

let mut merkle_tree = MerkleTree::<Sha256>::new();
merkle_tree
    .insert(Sha256::hash("a".as_bytes()))
    .commit();

assert_eq!(
    merkle_tree.root_hex(),
    Some("ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb".to_string())
);

pub fn append(&mut self, leaves: &mut Vec<T::Hash>) -> &mut Self

Appends leaves to the tree. Behaves similarly to MerkleTree::insert, but for a list of items. Takes ownership of the elements of the std::vec::Vec<T>, similarly to std::vec::Vec::append.

Examples

let mut merkle_tree = MerkleTree::<Sha256>::new();
let mut leaves = vec![
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
];
merkle_tree
    .append(&mut leaves)
    .commit();

assert_eq!(
    merkle_tree.root_hex(),
    Some("e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a".to_string())
);

pub fn commit(&mut self)

Commits the changes made by MerkleTree::insert and MerkleTree::append and modifies the root. Commits are saved to the history, so the tree can be rolled back to any previous commit using MerkleTree::rollback

Examples

let mut merkle_tree = MerkleTree::<Sha256>::new();
let mut leaves = vec![
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
];
merkle_tree.append(&mut leaves);
assert_eq!(
    merkle_tree.root_hex(),
    None
);

merkle_tree.commit();
assert_eq!(
    merkle_tree.root_hex(),
    Some("e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a".to_string())
);

pub fn rollback(&mut self)

Rolls back one commit and reverts the tree to the previous state. Removes the most recent commit from the history.

Examples

let mut merkle_tree = MerkleTree::<Sha256>::new();

merkle_tree.insert(Sha256::hash("a".as_bytes())).commit();
assert_eq!(
    merkle_tree.root_hex(),
    Some("ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb".to_string())
);

merkle_tree.insert(Sha256::hash("b".as_bytes())).commit();
assert_eq!(
    merkle_tree.root_hex(),
    Some("e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a".to_string())
);

// Rollback to the previous state
merkle_tree.rollback();
assert_eq!(
    merkle_tree.root_hex(),
    Some("ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb".to_string())
);

pub fn uncommitted_root(&self) -> Option<T::Hash>

Calculates the root of the uncommitted changes as if they were committed. Will return the same hash as MerkleTree::root after MerkleTree::commit

For examples, please check MerkleTree::uncommitted_root_hex

pub fn uncommitted_root_hex(&self) -> Option<String>

Calculates the root of the uncommitted changes as if they were committed. Serializes the result as a hex string. Will return the same hash as MerkleTree::root_hex after MerkleTree::commit

Examples

let mut merkle_tree = MerkleTree::<Sha256>::new();
let mut leaves = vec![
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
];
merkle_tree.append(&mut leaves);
assert_eq!(
    merkle_tree.root_hex(),
    None
);
assert_eq!(
     merkle_tree.uncommitted_root_hex(),
     Some("e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a".to_string())
);

merkle_tree.commit();
assert_eq!(
    merkle_tree.root_hex(),
    Some("e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a".to_string())
);

pub fn abort_uncommitted(&mut self)

Clears all uncommitted changes made by MerkleTree::insert and MerkleTree::append operations without applying them to the tree.

Examples

let mut merkle_tree = MerkleTree::<Sha256>::new();
let mut leaves = vec![
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
];
assert_eq!(
    merkle_tree.root(),
    None
);

merkle_tree.append(&mut leaves);
merkle_tree.abort_uncommitted();
merkle_tree.commit();

assert_eq!(
    merkle_tree.root(),
    None
);

pub fn depth(&self) -> usize

Returns the tree depth. A tree depth is how many layers there is between the leaves and the root

Examples

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);
assert_eq!(merkle_tree.depth(), 2);

pub fn leaves(&self) -> Option<Vec<T::Hash>>

Returns a copy of the tree leaves - the base level of the tree.

Examples

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);
assert_eq!(merkle_tree.leaves(), Some(leaves.to_vec()));

pub fn leaves_len(&self) -> usize

Returns the number of leaves in the tree.

Examples

let leaves = [
    Sha256::hash("a".as_bytes()),
    Sha256::hash("b".as_bytes()),
    Sha256::hash("c".as_bytes()),
];

let merkle_tree = MerkleTree::<Sha256>::from_leaves(&leaves);
assert_eq!(merkle_tree.leaves_len(), 3);

Trait Implementations

impl<T: Clone + Hasher> Clone for MerkleTree<T> where
    T::Hash: Clone, 

fn clone(&self) -> MerkleTree<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Hasher> Default for MerkleTree<T>

fn default() -> Self

Returns the “default value” for a type.