Struct MerkleNonInclusionProof 

pub struct MerkleNonInclusionProof<L> { /* private fields */ }

Available on crate feature unstable only.

A non-inclusion proof for a tree built over sorted leaves.

The proof shows that a target leaf does not appear in the tree by presenting its two neighbours in sorted order (with their inclusion proofs) and asserting left < target < right.

Edge cases:

• For an empty tree, both neighbours are None and index is 0; any target is automatically non-included.
• When the target sorts before every leaf, left_leaf is None, right_leaf is the first leaf, and index is 0.
• When the target sorts after every leaf, right_leaf is None and left_leaf is the right-most leaf in the tree (which is detected via MerkleProof::is_right_most during verification).

Implementations

impl<L> MerkleNonInclusionProof<L>

pub fn new( index: usize, left_leaf: Option<(L, MerkleProof)>, right_leaf: Option<(L, MerkleProof)>, ) -> Self

Construct a proof directly from its parts. Mostly useful for reconstructing a proof from out-of-band data; the usual way to produce a proof is MerkleTree::compute_non_inclusion_proof.

pub fn index(&self) -> usize

The position where target would be inserted to keep the leaf list sorted.

pub fn left_leaf(&self) -> Option<&(L, MerkleProof)>

The left neighbour leaf and its inclusion proof, if any.

pub fn right_leaf(&self) -> Option<&(L, MerkleProof)>

The right neighbour leaf and its inclusion proof, if any.

impl<L> MerkleNonInclusionProof<L>

where L: Serialize,

pub fn verify_proof_by_key<K, F>( &self, root: &Node, target_key: &K, key_of: F, ) -> Result<(), MerkleError>

where K: Ord + ?Sized, F: Fn(&L) -> &K,

Verify that no leaf whose projected key equals target_key appears in the tree whose root is root, where each leaf is projected to its comparison key via key_of.

The bracketing inequalities are evaluated on key_of(leaf) instead of on the whole leaf, which is useful when the tree’s leaves carry more than just the field that the caller wants to prove absent (e.g. an ObjectReference tree where the natural question is “is any leaf with this object id present?”).

Soundness depends on the tree being sorted by an order whose projection through key_of is monotonic — that is, all leaves sharing the same key must be contiguous in the sorted leaf list. This is the analogue of the sorted-leaf invariant on verify_proof; the caller is responsible for it, since the verifier cannot inspect the rest of the tree.

impl<L> MerkleNonInclusionProof<L>

where L: Ord + Serialize,

pub fn verify_proof(&self, root: &Node, target: &L) -> Result<(), MerkleError>

Verify that target is not in the tree whose root is root.

Thin wrapper over verify_proof_by_key with the identity projection — the leaf itself is its own key.

Trait Implementations

impl<L: Clone> Clone for MerkleNonInclusionProof<L>

fn clone(&self) -> MerkleNonInclusionProof<L>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<L: Debug> Debug for MerkleNonInclusionProof<L>

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

Formats the value using the given formatter.

impl<L: PartialEq> PartialEq for MerkleNonInclusionProof<L>

fn eq(&self, other: &MerkleNonInclusionProof<L>) -> 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<L: Eq> Eq for MerkleNonInclusionProof<L>

impl<L> StructuralPartialEq for MerkleNonInclusionProof<L>