Struct MerkleTree

pub struct MerkleTree<H: Hasher = Keccak256> {
    pub root: MerkleRoot<H>,
    pub nodes: Vec<H::Hash>,
}

A MerkleTree is a binary tree where each node is the hash of its children.

Fields

root: MerkleRoot<H>

nodes: Vec<H::Hash>

Implementations

impl<H: Hasher> MerkleTree<H>

Implement a MerkleTree-specific interface for interacting with trees.

pub fn new(items: &[&[u8]]) -> Option<Self>

Construct a new MerkleTree from a list of byte slices.

This list does not have to be a set which means the tree may contain duplicate items. It is up to the caller to enforce a strict set-like object if that is desired.

pub fn find_path(&self, index: usize) -> MerklePath<H>

Produces a Proof of membership for an index in the tree.

pub fn verify_path(&self, proof: MerklePath<H>, item: &[u8]) -> bool

Check if a given MerklePath is a valid proof for a corresponding item.

pub fn hash_leaf(leaf: &[u8]) -> H::Hash

pub fn hash_node(l: &H::Hash, r: &H::Hash) -> H::Hash

pub fn hash_null() -> H::Hash

pub fn serialize(&self, slot: u64, ring_size: u32) -> Vec<u8>

Serialize a MerkleTree into a Vec.

Layout:

4 bytes:  magic number
1 byte:   update type
4 byte:   storage id
32 bytes: root hash

TODO: This code does not belong to MerkleTree, we should be using the wire data types in calling code to wrap this value.

Trait Implementations

impl<'a, H: Hasher + 'a> Accumulator<'a> for MerkleTree<H>

Presents an Accumulator friendly interface for MerkleTree.

fn from_set(items: impl Iterator<Item = &'a [u8]>) -> Option<Self>

Construct a MerkleTree from an iterator of items.

fn prove(&'a self, item: &[u8]) -> Option<Self::Proof>

Prove an item is in the tree by returning a MerklePath.

type Proof = MerklePath<H>

fn check(&'a self, proof: Self::Proof, item: &[u8]) -> bool

Verify an item is a member of the accumulator.

impl<H: Hasher> BorshDeserialize for MerkleTree<H>

where MerkleRoot<H>: BorshDeserialize,

fn deserialize_reader<R: Read>(reader: &mut R) -> Result<Self, Error>

fn deserialize(buf: &mut &[u8]) -> Result<Self, Error>

Deserializes this instance from a given slice of bytes. Updates the buffer to point at the remaining bytes.

fn try_from_slice(v: &[u8]) -> Result<Self, Error>

Deserialize this instance from a slice of bytes.

fn try_from_reader<R>(reader: &mut R) -> Result<Self, Error>

where R: Read,

impl<H: Hasher> BorshSerialize for MerkleTree<H>

where MerkleRoot<H>: BorshSerialize,

fn serialize<W: Write>(&self, writer: &mut W) -> Result<(), Error>

fn try_to_vec(&self) -> Result<Vec<u8>, Error>

Serialize this instance into a vector of bytes.

impl<H: Clone + Hasher> Clone for MerkleTree<H>

where H::Hash: Clone,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<H: Debug + Hasher> Debug for MerkleTree<H>

where H::Hash: Debug,

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

Formats the value using the given formatter.

impl<H: Default + Hasher> Default for MerkleTree<H>

where H::Hash: Default,

fn default() -> MerkleTree<H>

Returns the “default value” for a type.

impl<'de, H> Deserialize<'de> for MerkleTree<H>

where H: Deserialize<'de> + Hasher,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<H: PartialEq + Hasher> PartialEq for MerkleTree<H>

where H::Hash: PartialEq,

fn eq(&self, other: &MerkleTree<H>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<H> Serialize for MerkleTree<H>

where H: Serialize + Hasher,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<H: Eq + Hasher> Eq for MerkleTree<H>

where H::Hash: Eq,

impl<H: Hasher> StructuralPartialEq for MerkleTree<H>