Struct MerkleTree

pub struct MerkleTree<E, H, I, const ARITY: usize, T>
where
    E: Element,
    H: DigestAlgorithm<E, I, T>,
    I: Index,
    T: NodeValue,
{ /* private fields */ }

A standard append only Merkle tree implementation

Implementations

impl<E, H, I, const ARITY: usize, T> MerkleTree<E, H, I, ARITY, T>

where E: Element, H: DigestAlgorithm<E, I, T>, I: Index, T: NodeValue,

pub fn new(height: usize) -> Self

Initialize an empty Merkle tree.

impl<E, H, const ARITY: usize, T> MerkleTree<E, H, u64, ARITY, T>

where E: Element, H: DigestAlgorithm<E, u64, T>, T: NodeValue,

pub fn from_elems( height: Option<usize>, elems: impl IntoIterator<Item = impl Borrow<E>>, ) -> Result<Self, MerkleTreeError>

Construct a new Merkle tree with given height from a data slice

• height - height of the Merkle tree, if None, it will calculate the minimum height that could hold all elements.
• elems - an iterator to all elements
• returns - A constructed Merkle tree, or Err() if errors

Trait Implementations

impl<E, H, const ARITY: usize, T> AppendableMerkleTreeScheme for MerkleTree<E, H, u64, ARITY, T>

where E: Element, H: DigestAlgorithm<E, u64, T>, T: NodeValue,

fn push( &mut self, elem: impl Borrow<Self::Element>, ) -> Result<(), MerkleTreeError>

Insert a new value at the leftmost available slot

fn extend( &mut self, elems: impl IntoIterator<Item = impl Borrow<Self::Element>>, ) -> Result<(), MerkleTreeError>

Insert a list of new values at the leftmost available slots

impl<E, H, I, const ARITY: usize, T> Clone for MerkleTree<E, H, I, ARITY, T>

where E: Element + Clone, H: DigestAlgorithm<E, I, T> + Clone, I: Index + Clone, T: NodeValue + Clone,

fn clone(&self) -> MerkleTree<E, H, I, ARITY, T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<E, H, I, const ARITY: usize, T> Debug for MerkleTree<E, H, I, ARITY, T>

where E: Element + Debug, H: DigestAlgorithm<E, I, T> + Debug, I: Index + Debug, T: NodeValue + Debug,

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

Formats the value using the given formatter.

impl<'de, E, H, I, const ARITY: usize, T> Deserialize<'de> for MerkleTree<E, H, I, ARITY, T>

where E: Element + CanonicalSerialize + CanonicalDeserialize, H: DigestAlgorithm<E, I, T>, I: Index + CanonicalSerialize + CanonicalDeserialize, T: NodeValue,

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<E, H, I, const ARITY: usize, T> ForgetableMerkleTreeScheme for MerkleTree<E, H, I, ARITY, T>

where E: Element, H: DigestAlgorithm<E, I, T>, I: Index + ToTraversalPath<ARITY>, T: NodeValue,

fn from_commitment( com: impl Borrow<Self::Commitment>, height: usize, num_leaves: u64, ) -> Self

Rebuild a merkle tree from a commitment. Return a tree which is entirely forgotten.

fn forget( &mut self, pos: impl Borrow<Self::Index>, ) -> LookupResult<Self::Element, Self::MembershipProof, ()>

Trim the leaf at position i from memory, if present. Should not trim if position i is the last inserted leaf position. Return is identical to result if get_leaf(pos) were called before this call.

fn remember( &mut self, pos: impl Borrow<Self::Index>, element: impl Borrow<Self::Element>, proof: impl Borrow<Self::MembershipProof>, ) -> Result<(), MerkleTreeError>

“Re-insert” a leaf into the tree using its proof. Returns Ok(()) if insertion is successful, or Err(err) if the proof disagrees with the merkle tree

impl<E, H, I, const ARITY: usize, T> Hash for MerkleTree<E, H, I, ARITY, T>

where E: Element + Hash, H: DigestAlgorithm<E, I, T> + Hash, I: Index + Hash, T: NodeValue + Hash,

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<'a, E, H, I, const ARITY: usize, T> IntoIterator for &'a MerkleTree<E, H, I, ARITY, T>

where E: Element, H: DigestAlgorithm<E, I, T>, I: Index + ToTraversalPath<ARITY>, T: NodeValue,

type Item = (&'a I, &'a E)

The type of the elements being iterated over.

type IntoIter = MerkleTreeIter<'a, E, I, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<E, H, I, const ARITY: usize, T> IntoIterator for MerkleTree<E, H, I, ARITY, T>

where E: Element, H: DigestAlgorithm<E, I, T>, I: Index + ToTraversalPath<ARITY>, T: NodeValue,

type Item = (I, E)

The type of the elements being iterated over.

type IntoIter = MerkleTreeIntoIter<E, I, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<E, H, I, const ARITY: usize, T> MerkleTreeScheme for MerkleTree<E, H, I, ARITY, T>

where E: Element, H: DigestAlgorithm<E, I, T>, I: Index + ToTraversalPath<ARITY>, T: NodeValue,

const ARITY: usize = ARITY

Tree ARITY

type Element = E

Merkle tree element type

type Index = I

Index type for this merkle tree

type NodeValue = T

Internal and root node value

type MembershipProof = MerkleTreeProof<T>

Merkle proof

type BatchMembershipProof = ()

Batch proof

type Commitment = T

Merkle tree commitment

fn height(&self) -> usize

Return the height of this merkle tree

fn capacity(&self) -> BigUint

Return the maximum allowed number leaves

fn num_leaves(&self) -> u64

Return the current number of leaves

fn commitment(&self) -> Self::Commitment

Return a merkle commitment

fn lookup( &self, pos: impl Borrow<Self::Index>, ) -> LookupResult<&Self::Element, Self::MembershipProof, ()>

Returns the leaf value given a position

fn verify( commitment: impl Borrow<Self::Commitment>, pos: impl Borrow<Self::Index>, element: impl Borrow<Self::Element>, proof: impl Borrow<Self::MembershipProof>, ) -> Result<Result<(), ()>, MerkleTreeError>

Verify an element is a leaf of a Merkle tree given the proof

fn iter(&self) -> MerkleTreeIter<'_, E, I, T>

Return an iterator that iterates through all element that are not forgotten

impl<E, H, I, const ARITY: usize, T> PartialEq for MerkleTree<E, H, I, ARITY, T>

where E: Element + PartialEq, H: DigestAlgorithm<E, I, T> + PartialEq, I: Index + PartialEq, T: NodeValue + PartialEq,

fn eq(&self, other: &MerkleTree<E, H, I, ARITY, T>) -> 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<E, H, I, const ARITY: usize, T> Serialize for MerkleTree<E, H, I, ARITY, T>

where E: Element + CanonicalSerialize + CanonicalDeserialize, H: DigestAlgorithm<E, I, T>, I: Index + CanonicalSerialize + CanonicalDeserialize, T: NodeValue,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<E, H, I, const ARITY: usize, T> Eq for MerkleTree<E, H, I, ARITY, T>

where E: Element + Eq, H: DigestAlgorithm<E, I, T> + Eq, I: Index + Eq, T: NodeValue + Eq,

impl<E, H, I, const ARITY: usize, T> StructuralPartialEq for MerkleTree<E, H, I, ARITY, T>

where E: Element, H: DigestAlgorithm<E, I, T>, I: Index, T: NodeValue,