Trait MerkleTreeScheme

pub trait MerkleTreeScheme: Sized {
    type Element: Element;
    type Index: Index;
    type NodeValue: NodeValue;
    type MembershipProof: MerkleProof<Self::NodeValue>;
    type BatchMembershipProof: Clone;
    type Commitment: NodeValue;

    const ARITY: usize;

    // Required methods
    fn height(&self) -> usize;
    fn capacity(&self) -> BigUint;
    fn num_leaves(&self) -> u64;
    fn commitment(&self) -> Self::Commitment;
    fn lookup(
        &self,
        pos: impl Borrow<Self::Index>,
    ) -> LookupResult<&Self::Element, Self::MembershipProof, ()>;
    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>;
    fn iter(
        &self,
    ) -> MerkleTreeIter<'_, Self::Element, Self::Index, Self::NodeValue>;
}

Basic functionalities for a merkle tree implementation. Abstracted as an accumulator for fixed-length array. Supports generating membership proof at a given position and verify a membership proof.

Required Associated Constants

const ARITY: usize

Tree ARITY

Required Associated Types

type Element: Element

Merkle tree element type

type Index: Index

Index type for this merkle tree

type NodeValue: NodeValue

Internal and root node value

type MembershipProof: MerkleProof<Self::NodeValue>

Merkle proof

type BatchMembershipProof: Clone

Batch proof

type Commitment: NodeValue

Merkle tree commitment

Required Methods

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

• pos - zero-based index of the leaf in the tree
• returns - Leaf value at the position along with a proof. LookupResult::EmptyLeaf if the leaf position is empty or invalid, LookupResult::NotInMemory if the leaf position has been forgotten.

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

• commitment - a merkle tree commitment
• pos - zero-based index of the leaf in the tree
• element - the leaf value
• proof - a membership proof for element at given pos
• returns - Ok(true) if the proof is accepted, Ok(false) if not. Err() if the proof is not well structured, E.g. not for this merkle tree.

fn iter( &self, ) -> MerkleTreeIter<'_, Self::Element, Self::Index, Self::NodeValue>

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

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

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

type Element = E

type Index = I

type NodeValue = T

type MembershipProof = MerkleTreeProof<T>

type BatchMembershipProof = ()

type Commitment = T

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

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

const ARITY: usize = ARITY

type Element = E

type Index = I

type NodeValue = T

type MembershipProof = MerkleTreeProof<T>

type BatchMembershipProof = ()

type Commitment = T

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

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

const ARITY: usize = ARITY

type Element = E

type Index = I

type NodeValue = T

type MembershipProof = MerkleTreeProof<T>

type BatchMembershipProof = ()

type Commitment = T