Struct NodeIndex

pub struct NodeIndex { /* private fields */ }

Address to an arbitrary node in a binary tree using level order form.

The position is represented by the pair (depth, pos), where for a given depth d elements are numbered from $0..(2^d)-1$. Example:

depth
0             0
1         0        1
2      0    1    2    3
3     0 1  2 3  4 5  6 7

The root is represented by the pair $(0, 0)$, its left child is $(1, 0)$ and its right child $(1, 1)$.

Implementations

impl NodeIndex

pub const fn new(depth: u8, value: u64) -> Result<NodeIndex, MerkleError>

Creates a new node index.

Errors

Returns an error if the value is greater than or equal to 2^{depth}.

pub const fn new_unchecked(depth: u8, value: u64) -> NodeIndex

Creates a new node index without checking its validity.

pub fn from_elements( depth: &BaseElement, value: &BaseElement, ) -> Result<NodeIndex, MerkleError>

Creates a node index from a pair of field elements representing the depth and value.

Errors

Returns an error if:

• depth doesn’t fit in a u8.
• value is greater than or equal to 2^{depth}.

pub const fn root() -> NodeIndex

Creates a new node index pointing to the root of the tree.

pub const fn sibling(self) -> NodeIndex

Computes sibling index of the current node.

pub const fn left_child(self) -> NodeIndex

Returns left child index of the current node.

pub const fn right_child(self) -> NodeIndex

Returns right child index of the current node.

pub const fn parent(self) -> NodeIndex

Returns the parent of the current node. This is the same as Self::move_up(), but returns a new value instead of mutating self.

pub const fn build_node(&self, slf: Word, sibling: Word) -> [Word; 2]

Builds a node to be used as input of a hash function when computing a Merkle path.

Will evaluate the parity of the current instance to define the result.

pub const fn to_scalar_index(&self) -> u64

Returns the scalar representation of the depth/value pair.

It is computed as 2^depth + value.

pub const fn depth(&self) -> u8

Returns the depth of the current instance.

pub const fn value(&self) -> u64

Returns the value of this index.

pub const fn is_value_odd(&self) -> bool

Returns true if the current instance points to a right sibling node.

pub const fn is_root(&self) -> bool

Returns true if the depth is 0.

pub fn move_up(&mut self)

Traverses one level towards the root, decrementing the depth by 1.

pub fn move_up_to(&mut self, depth: u8)

Traverses towards the root until the specified depth is reached.

Assumes that the specified depth is smaller than the current depth.

pub fn proof_indices(&self) -> impl ExactSizeIterator + use<>

Return an iterator of the indices required for a Merkle proof of inclusion of a node at self.

This is exclusive on both ends: neither self nor the root index are included in the returned iterator.

Trait Implementations

impl Clone for NodeIndex

fn clone(&self) -> NodeIndex

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for NodeIndex

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

Formats the value using the given formatter.

impl Default for NodeIndex

fn default() -> NodeIndex

Returns the “default value” for a type.

impl Deserializable for NodeIndex

fn read_from<R>(source: &mut R) -> Result<NodeIndex, DeserializationError>

where R: ByteReader,

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into Self, and returns the result.

fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>

Attempts to deserialize the provided bytes into Self and returns the result.

impl Display for NodeIndex

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

Formats the value using the given formatter.

impl<const DEPTH: u8> From<LeafIndex<DEPTH>> for NodeIndex

fn from(value: LeafIndex<DEPTH>) -> NodeIndex

Converts to this type from the input type.

impl Hash for NodeIndex

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

where __H: Hasher,

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 Ord for NodeIndex

fn cmp(&self, other: &NodeIndex) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for NodeIndex

fn eq(&self, other: &NodeIndex) -> 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 PartialOrd for NodeIndex

fn partial_cmp(&self, other: &NodeIndex) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Serializable for NodeIndex

fn write_into<W>(&self, target: &mut W)

where W: ByteWriter,

Serializes self into bytes and writes these bytes into the target.

fn to_bytes(&self) -> Vec<u8>

Serializes self into a vector of bytes.

fn get_size_hint(&self) -> usize

Returns an estimate of how many bytes are needed to represent self.

impl<const DEPTH: u8> TryFrom<NodeIndex> for LeafIndex<DEPTH>

type Error = MerkleError

The type returned in the event of a conversion error.

fn try_from( node_index: NodeIndex, ) -> Result<LeafIndex<DEPTH>, <LeafIndex<DEPTH> as TryFrom<NodeIndex>>::Error>

Performs the conversion.

impl Copy for NodeIndex

impl Eq for NodeIndex

impl StructuralPartialEq for NodeIndex