Trait UniversalMerkleTreeScheme

pub trait UniversalMerkleTreeScheme: MerkleTreeScheme {
    type NonMembershipProof;
    type BatchNonMembershipProof;

    // Required methods
    fn update_with<F>(
        &mut self,
        pos: impl Borrow<Self::Index>,
        f: F,
    ) -> Result<LookupResult<Self::Element, (), ()>, MerkleTreeError>
       where F: FnOnce(Option<&Self::Element>) -> Option<Self::Element>;
    fn universal_lookup(
        &self,
        pos: impl Borrow<Self::Index>,
    ) -> LookupResult<&Self::Element, Self::MembershipProof, Self::NonMembershipProof>;
    fn non_membership_verify(
        commitment: impl Borrow<Self::Commitment>,
        pos: impl Borrow<Self::Index>,
        proof: impl Borrow<Self::NonMembershipProof>,
    ) -> Result<Result<(), ()>, MerkleTreeError>;

    // Provided methods
    fn update(
        &mut self,
        pos: impl Borrow<Self::Index>,
        elem: impl Borrow<Self::Element>,
    ) -> Result<LookupResult<Self::Element, (), ()>, MerkleTreeError> { ... }
    fn remove(
        &mut self,
        pos: impl Borrow<Self::Index>,
    ) -> Result<LookupResult<Self::Element, (), ()>, MerkleTreeError> { ... }
}

A universal merkle tree is abstracted as a random-access array or a key-value map. It allows manipulation at any given position, and has ability to generate/verify a non-membership proof.

Required Associated Types

type NonMembershipProof

Non membership proof for a given index

type BatchNonMembershipProof

Batch non membership proof

Required Methods

fn update_with<F>( &mut self, pos: impl Borrow<Self::Index>, f: F, ) -> Result<LookupResult<Self::Element, (), ()>, MerkleTreeError>

where F: FnOnce(Option<&Self::Element>) -> Option<Self::Element>,

Apply an update function f at a given position

• pos - zero-based index of the leaf in the tree
• f - the update function, None means the given leaf doesn’t exist or should be removed.
• returns - Err() if any error occurs internally. Ok(result) if the update is success or the given leaf is not in memory.

Example

merkle_tree.update_with(account, |balance| {
    Some(balance.cloned().unwrap_or_default().add(amount))
});

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

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(p) if the leaf position is empty along with a proof p. LookupResult::NotInMemory if the leaf position has been forgotten.

fn non_membership_verify( commitment: impl Borrow<Self::Commitment>, pos: impl Borrow<Self::Index>, proof: impl Borrow<Self::NonMembershipProof>, ) -> Result<Result<(), ()>, MerkleTreeError>

Verify an index is not in this merkle tree

• pos - zero-based index of the leaf in the tree
• proof - a merkle tree proof
• 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.

Provided Methods

fn update( &mut self, pos: impl Borrow<Self::Index>, elem: impl Borrow<Self::Element>, ) -> Result<LookupResult<Self::Element, (), ()>, MerkleTreeError>

Update the leaf value at a given position

• pos - zero-based index of the leaf in the tree
• elem - newly updated element
• returns - Err() if any error occurs internally or the given leaf is not in memory. Ok(result) if the update is success.

fn remove( &mut self, pos: impl Borrow<Self::Index>, ) -> Result<LookupResult<Self::Element, (), ()>, MerkleTreeError>

Remove a leaf at the given position

• pos - zero-based index of the leaf in the tree
• returns - Err() if any error occurs internally. Ok(result) if the update is success or the given leaf is not in memory.

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> UniversalMerkleTreeScheme for UniversalMerkleTree<E, H, I, ARITY, T>

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

type NonMembershipProof = MerkleTreeProof<T>

type BatchNonMembershipProof = ()