Struct winter_crypto::MerkleTree
source · pub struct MerkleTree<H: Hasher> { /* private fields */ }
Expand description
A fully-balanced Merkle tree.
In this implementation, a Merkle tree consists of two types of nodes: leaves and internal nodes (one of which is a tree root). All nodes must be instances of the digest specified by the Hasher used to build the tree.
* <- tree root
/ \
/ \
* * <- internal nodes
/ \ / \
o o o o <- leaves
| | | |
# # # # <- values
A tree can be built from a slice of leaves using MerkleTree::new() function. Thus, the user is responsible for performing the first level of hashing (i.e., hashing values into leaf nodes). The number of leaves must always be a power of two so that the tree is fully balanced, and a tree must contain at least two leaves.
The depth of a tree is zero-based. Thus, a tree with two leaves has depth 1, a tree with four leaves has depth 2 etc.
When the crate is compiled with concurrent
feature enabled, tree construction will be
performed in multiple threads (usually, as many threads as there are logical cores on the
machine). The number of threads can be configured via RAYON_NUM_THREADS
environment variable.
To generate an inclusion proof for a given leaf, MerkleTree::prove() method can be used. You can also use MerkleTree::prove_batch() method to generate inclusion proofs for multiple leaves. The advantage of the batch method is that redundant internal nodes are removed from the batch proof, thereby compressing it (we use a variation of the Octopus algorithm).
To verify proofs, MerkleTree::verify() and MerkleTree::verify_batch() functions can be used respectively.
§Examples
type Blake3 = Blake3_256::<BaseElement>;
// build a tree
let leaves = [
Blake3::hash(&[1u8]),
Blake3::hash(&[2u8]),
Blake3::hash(&[3u8]),
Blake3::hash(&[4u8]),
];
let tree = MerkleTree::<Blake3>::new(leaves.to_vec()).unwrap();
assert_eq!(2, tree.depth());
assert_eq!(leaves, tree.leaves());
// generate a proof
let proof = tree.prove(2).unwrap();
assert_eq!(3, proof.len());
assert_eq!(leaves[2], proof[0]);
// verify proof
assert!(MerkleTree::<Blake3>::verify(*tree.root(), 2, &proof).is_ok());
assert!(MerkleTree::<Blake3>::verify(*tree.root(), 1, &proof).is_err());
Implementations§
source§impl<H: Hasher> MerkleTree<H>
impl<H: Hasher> MerkleTree<H>
sourcepub fn new(leaves: Vec<H::Digest>) -> Result<Self, MerkleTreeError>
pub fn new(leaves: Vec<H::Digest>) -> Result<Self, MerkleTreeError>
Returns new Merkle tree built from the provide leaves using hash function specified by the
H
generic parameter.
When concurrent
feature is enabled, the tree is built using multiple threads.
§Errors
Returns an error if:
- Fewer than two leaves were provided.
- Number of leaves is not a power of two.
sourcepub fn from_raw_parts(
nodes: Vec<H::Digest>,
leaves: Vec<H::Digest>
) -> Result<Self, MerkleTreeError>
pub fn from_raw_parts( nodes: Vec<H::Digest>, leaves: Vec<H::Digest> ) -> Result<Self, MerkleTreeError>
sourcepub fn depth(&self) -> usize
pub fn depth(&self) -> usize
Returns depth of the tree.
The depth of a tree is zero-based. Thus, a tree with two leaves has depth 1, a tree with four leaves has depth 2 etc.
sourcepub fn prove(&self, index: usize) -> Result<Vec<H::Digest>, MerkleTreeError>
pub fn prove(&self, index: usize) -> Result<Vec<H::Digest>, MerkleTreeError>
Returns a Merkle path to a leaf at the specified index
.
The leaf itself will be the first element in the path.
§Errors
Returns an error if the specified index is greater than or equal to the number of leaves in the tree.
sourcepub fn prove_batch(
&self,
indexes: &[usize]
) -> Result<BatchMerkleProof<H>, MerkleTreeError>
pub fn prove_batch( &self, indexes: &[usize] ) -> Result<BatchMerkleProof<H>, MerkleTreeError>
Computes Merkle paths for the provided indexes and compresses the paths into a single proof.
§Errors
Returns an error if:
- No indexes were provided (i.e.,
indexes
is an empty slice). - Number of provided indexes is greater than 255.
- Any of the provided indexes are greater than or equal to the number of leaves in the tree.
- List of indexes contains duplicates.
sourcepub fn verify(
root: H::Digest,
index: usize,
proof: &[H::Digest]
) -> Result<(), MerkleTreeError>
pub fn verify( root: H::Digest, index: usize, proof: &[H::Digest] ) -> Result<(), MerkleTreeError>
Checks whether the proof
for the specified index
is valid.
§Errors
Returns an error if the specified proof
(which is a Merkle path) does not resolve to the
specified root
.
sourcepub fn verify_batch(
root: &H::Digest,
indexes: &[usize],
proof: &BatchMerkleProof<H>
) -> Result<(), MerkleTreeError>
pub fn verify_batch( root: &H::Digest, indexes: &[usize], proof: &BatchMerkleProof<H> ) -> Result<(), MerkleTreeError>
Checks whether the batch proof contains Merkle paths for the of the specified indexes
.
§Errors
Returns an error if:
- No indexes were provided (i.e.,
indexes
is an empty slice). - Number of provided indexes is greater than 255.
- Any of the specified
indexes
is greater than or equal to the number of leaves in the tree from which the batch proof was generated. - List of indexes contains duplicates.
- Any of the paths in the batch proof does not resolve to the specified
root
.