Incremental Merkle Tree

https://docs.rs/incrementalmerkletree/latest/
Admin
This project provides documentation for an Incremental Merkle Tree implementation.
Tokens:54,335
Snippets:545
Trust Score:9.1
Update:4 months ago
Show doc for...
Tokens:
Raw
### Find Common Ancestor of Addresses (Example 2)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the common ancestor of two addresses. This example demonstrates a scenario where the common ancestor is at Level 2.

```rust
assert_eq!(
            Address::from_parts(Level(0), 12).common_ancestor(&Address::from_parts(Level(0), 15)),
            Address::from_parts(Level(2), 3)
        );
```

--------------------------------

### Find Common Ancestor of Addresses (Example 5)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the common ancestor of two addresses. This example shows a case where the common ancestor is at Level 1.

```rust
assert_eq!(
            Address::from_parts(Level(0), 14).common_ancestor(&Address::from_parts(Level(0), 15)),
            Address::from_parts(Level(1), 7)
        );
```

--------------------------------

### Find Common Ancestor of Addresses (Example 1)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the common ancestor of two addresses. This example shows a case where the common ancestor is at Level 2.

```rust
assert_eq!(
            Address::from_parts(Level(0), 9).common_ancestor(&Address::from_parts(Level(2), 2)),
            Address::from_parts(Level(2), 2)
        );
```

--------------------------------

### Find Common Ancestor of Addresses (Example 6)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the common ancestor of two addresses. This example demonstrates a scenario where the common ancestor is at Level 5.

```rust
assert_eq!(
            Address::from_parts(Level(0), 15).common_ancestor(&Address::from_parts(Level(0), 16)),
            Address::from_parts(Level(5), 0)
        );
```

--------------------------------

### Find Common Ancestor of Addresses (Example 3)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the common ancestor of two addresses. This example shows a case where the common ancestor is at Level 2.

```rust
assert_eq!(
            Address::from_parts(Level(0), 13).common_ancestor(&Address::from_parts(Level(0), 15)),
            Address::from_parts(Level(2), 3)
        );
```

--------------------------------

### Find Common Ancestor of Addresses (Example 4)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the common ancestor of two addresses. This example demonstrates a scenario where the common ancestor is at Level 2.

```rust
assert_eq!(
            Address::from_parts(Level(0), 13).common_ancestor(&Address::from_parts(Level(0), 14)),
            Address::from_parts(Level(2), 3)
        );
```

--------------------------------

### Construct MerklePath from Parts

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Constructs a MerklePath directly from a vector of path elements and a starting position. Ensures the number of path elements matches the tree depth.

```rust
pub fn from_parts(path_elems: Vec<H>, position: Position) -> Result<Self, ()> {
        if path_elems.len() == usize::from(DEPTH) {
            Ok(MerklePath {
                path_elems,
                position,
            })
        } else {
            Err(())
        }
    }
```

--------------------------------

### Any Trait Implementation for T

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.PathFiller.html

Demonstrates the implementation of the Any trait for any type T, providing a method to get the TypeId of an object.

```rust
fn type_id(&self) -> TypeId
```

--------------------------------

### Address Common Ancestor Finding

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Provides examples of finding the common ancestor address between two different addresses in the Merkle tree.

```rust
assert_eq!(Address::from_parts(Level(2), 1).common_ancestor(&Address::from_parts(Level(3), 2)), Address::from_parts(Level(5), 0));
assert_eq!(Address::from_parts(Level(2), 2).common_ancestor(&Address::from_parts(Level(1), 7)), Address::from_parts(Level(3), 1));
assert_eq!(Address::from_parts(Level(2), 2).common_ancestor(&Address::from_parts(Level(1), 6)), Address::from_parts(Level(3), 1));
assert_eq!(Address::from_parts(Level(2), 2).common_ancestor(&Address::from_parts(Level(2), 2)), Address::from_parts(Level(2), 2));
assert_eq!(Address::from_parts(Level(2), 2).common_ancestor(&Address::from_parts(Level(0), 9)), Address::from_parts(Level(2), 2));
```

--------------------------------

### Get Position Range Start

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the minimum leaf position contained within the subtree rooted at this address. Useful for range queries.

```rust
pub fn position_range_start(&self) -> Position
```

--------------------------------

### CloneToUninit for Level

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Level.html

An experimental, nightly-only API for performing copy-assignment to uninitialized memory.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
Performs copy-assignment from `self` to `dest`.

### Method
`clone_to_uninit`

### Parameters
- `self`: An immutable reference to the Level instance.
- `dest`: A raw pointer to the destination memory location.

### Safety
This function is unsafe as it involves direct memory manipulation. The caller must ensure that `dest` is valid for writes and that the memory is uninitialized.
```

--------------------------------

### Get Start of Position Range Contained by Address

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Returns the minimum leaf position index covered by the tree rooted at this address. Useful for range queries.

```rust
pub fn position_range_start(&self) -> Position {
    (self.index << self.level.0).into()
}
```

--------------------------------

### CloneToUninit for T

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Provides the `clone_to_uninit` method for cloning to an uninitialized memory location. This is an experimental nightly-only API.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
Performs copy-assignment from `self` to `dest`. This is a nightly-only experimental API.

### Parameters
- `dest` (*mut u8): A mutable pointer to the destination memory location.

### Safety
This function is unsafe as it operates on raw pointers and assumes `dest` is valid and sufficiently large.
```

--------------------------------

### Merkle Path Root Calculation

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Illustrates how to construct a Merkle path from parts and then calculate the root hash by providing a leaf value.

```rust
let path: MerklePath<String, 3> = MerklePath::from_parts(
            vec!["a".to_string(), "cd".to_string(), "efgh".to_string()],
            Position(1),
        )
        .unwrap();

        assert_eq!(path.root("b".to_string()), "abcdefgh".to_string());

        let path: MerklePath<String, 3> = MerklePath::from_parts(
            vec!["d".to_string(), "ab".to_string(), "efgh".to_string()],
            Position(2),
        )
        .unwrap();

        assert_eq!(path.root("c".to_string()), "abcdefgh".to_string());
```

--------------------------------

### Get Full Position Range Contained by Address

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Returns a `Range` struct representing the start (inclusive) and end (exclusive) of leaf positions covered by this address. Ideal for iterating over contained leaves.

```rust
pub fn position_range(&self) -> Range<Position> {
    Range {
        start: self.position_range_start(),
        end: self.position_range_end(),
    }
}
```

--------------------------------

### clone_to_uninit

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/witness/struct.IncrementalWitness.html

This is a nightly-only experimental API. It performs copy-assignment from self to a mutable pointer destination.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
Performs copy-assignment from `self` to `dest`.

### Method
`unsafe fn`

### Parameters
#### Path Parameters
- **dest** (*mut u8) - Required - The mutable pointer to copy the data to.

### Note
This is a nightly-only experimental API.
```

--------------------------------

### Get Witness Addresses for Position

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Position.html

Provides an iterator over the node addresses required to build a witness for the current position. It starts with the leaf's sibling and ends with the ancestor's sibling needed for a root at the specified level.

```rust
pub fn witness_addrs( &self, root_level: Level, ) -> impl Iterator<Item = (Address, Source)>
```

--------------------------------

### Creating an Incremental Witness from a CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/witness.rs.html

Shows how to initialize an IncrementalWitness using an existing CommitmentTree. Returns None if the tree is empty, as there would be no position to witness.

```rust
pub fn from_tree(tree: CommitmentTree<H, DEPTH>) -> Option<Self> {
    (!tree.is_empty()).then(|| IncrementalWitness {
        tree,
        filled: vec![],
        cursor_depth: 0,
        cursor: None,
    })
}
```

--------------------------------

### Frontier Initialization and Validation

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

Tests the `from_parts` constructor for `Frontier`, checking valid and invalid combinations of index, parent, and children.

```rust
#[test]
fn frontier_from_parts() {
    assert!(super::Frontier::<(), 1>::from_parts(0.into(), (), vec![]).is_ok());
    assert!(super::Frontier::<(), 1>::from_parts(1.into(), (), vec![()]).is_ok());
    assert!(super::Frontier::<(), 1>::from_parts(0.into(), (), vec![()]).is_err());
}
```

--------------------------------

### Construct Address from Parts

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Creates a new Address instance using its level and index. This is a fundamental way to initialize an address.

```rust
pub fn from_parts(level: Level, index: u64) -> Self
```

--------------------------------

### PathFiller Methods

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.PathFiller.html

Provides methods to create and interact with a PathFiller instance.

```APIDOC
## Struct PathFiller

Available on **crate feature`legacy-api`** only.

```rust
pub struct PathFiller<H> { /* private fields */ }
```

### Methods

#### `empty()`

Creates a new, empty `PathFiller`.

- **Returns**: `Self` (a new `PathFiller` instance)

#### `new(queue: VecDeque<H>)`

Creates a new `PathFiller` with the given queue of elements.

- **Parameters**:
  - `queue` (VecDeque<H>): The initial queue of elements.
- **Returns**: `Self` (a new `PathFiller` instance)

#### `next(&mut self, level: Level) -> H`

Retrieves the next element from the `PathFiller` at the specified level.

- **Parameters**:
  - `level` (Level): The level at which to retrieve the next element.
- **Returns**: `H` (the next element)
```

--------------------------------

### Frontier::take

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Consumes the Frontier instance and returns the underlying Option<NonEmptyFrontier>, allowing for ownership transfer.

```APIDOC
## Frontier::take

### Description
Consumes this wrapper and returns the underlying `Option<NonEmptyFrontier>`.

### Method
`take(self) -> Option<NonEmptyFrontier<H>>`

### Returns
- `Option<NonEmptyFrontier<H>>`: The underlying Option<NonEmptyFrontier>.
```

--------------------------------

### Address Methods

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Provides an overview of the methods available for the Address struct, including construction, navigation, and relationship queries.

```APIDOC
## Address Struct

The address of a node of the Merkle tree. When `level == 0`, the index has the same value as the position.

### Methods

#### `from_parts(level: Level, index: u64) -> Self`
Construct a new address from its constituent parts.

#### `above_position(level: Level, position: Position) -> Self`
Returns the address at the given level that contains the specified leaf position.

#### `level(&self) -> Level`
Returns the level of the root of the tree having its root at this address.

#### `index(&self) -> u64`
Returns the index of the address. The index of an address is defined as the number of subtrees with their roots at the address’s level that appear to the left of this address in a binary tree of arbitrary height > level * 2 + 1.

#### `parent(&self) -> Address`
The address of the node one level higher than this in a binary tree that contains this address as either its left or right child.

#### `sibling(&self) -> Address`
Returns the address that shares the same parent as this address.

#### `children(&self) -> Option<(Address, Address)>`
Returns the immediate children of this address.

#### `is_ancestor_of(&self, addr: &Self) -> bool`
Returns whether this address is an ancestor of the specified address.

#### `common_ancestor(&self, other: &Self) -> Self`
Returns the common ancestor of `self` and `other` having the smallest level value.

#### `contains(&self, addr: &Self) -> bool`
Returns whether this address is an ancestor of, or is equal to, the specified address.

#### `position_range_start(&self) -> Position`
Returns the minimum value among the range of leaf positions that are contained within the tree with its root at this address.

#### `position_range_end(&self) -> Position`
Returns the (exclusive) end of the range of leaf positions that are contained within the tree with its root at this address.

#### `max_position(&self) -> Position`
Returns the maximum value among the range of leaf positions that are contained within the tree with its root at this address.

#### `position_range(&self) -> Range<Position>`
Returns the end-exclusive range of leaf positions that are contained within the tree with its root at this address.

#### `context(&self, level: Level) -> Either<Address, Range<u64>>`
Returns either the ancestor of this address at the given level (if the level is greater than or equal to that of this address) or the range of indices of root addresses of subtrees with roots at the given level contained within the tree with its root at this address otherwise.

#### `position_cmp(&self, pos: Position) -> Ordering`
Returns whether the tree with this root address contains the given leaf position, or if not whether an address at the same level with a greater or lesser index will contain the specified leaf position.

#### `is_left_child(&self) -> bool`
Returns whether this address is the left-hand child of its parent.

#### `is_right_child(&self) -> bool`
Returns whether this address is the right-hand child of its parent.

#### `current_incomplete(&self) -> Address`

#### `next_incomplete_parent(&self) -> Address`

#### `next_at_level(&self) -> Address`
Increments this address’s index by 1 and returns the resulting address.
```

--------------------------------

### NonEmptyFrontier Manipulation and Querying

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.NonEmptyFrontier.html

Methods for appending leaves, generating roots, and constructing witnesses.

```APIDOC
## `impl<H: Hashable + Clone> NonEmptyFrontier<H>`

### `append(&mut self, leaf: H)`

Append a new leaf to the frontier, and recompute ommers by hashing together full subtrees until an empty ommer slot is found.

### `root(&self, root_level: Option<Level>) -> H`

Generate the root of the Merkle tree by hashing against empty subtree roots.

### `witness<F>(&self, depth: u8, complement_nodes: F) -> Result<Vec<H>, Address>`

where F: Fn(Address) -> Option<H>,

Constructs a witness for the leaf at the tip of this frontier, given a source of node values that complement this frontier. If the `complement_nodes` function returns `None` when the value is requested at a given tree address, the address at which the failure occurs will be returned as an error.
```

--------------------------------

### Any for T

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Provides the `type_id` method to get the `TypeId` of an object.

```APIDOC
## fn type_id(&self) -> TypeId

### Description
Gets the `TypeId` of `self`.

### Parameters
None

### Returns
- `TypeId`: The type identifier of the object.
```

--------------------------------

### Creating and Updating an Incremental Witness

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/witness.rs.html

Demonstrates how to create an IncrementalWitness from a CommitmentTree and how to append new commitments to both the tree and the witness, ensuring they remain synchronized.

```rust
use incrementalmerkletree::{
    frontier::{CommitmentTree, testing::TestNode},
    witness::IncrementalWitness,
    Position
};

let mut tree = CommitmentTree::<TestNode, 8>::empty();

tree.append(TestNode(0));
tree.append(TestNode(1));
let mut witness = IncrementalWitness::from_tree(tree.clone()).expect("tree is not empty");
assert_eq!(witness.witnessed_position(), Position::from(1));
assert_eq!(tree.root(), witness.root());

let next = TestNode(2);
tree.append(next.clone());
witness.append(next);
assert_eq!(tree.root(), witness.root());
```

--------------------------------

### Get tree size

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Returns the total size of the Merkle tree that this frontier represents.

```rust
pub fn tree_size(&self) -> u64
```

--------------------------------

### PathFiller Implementations

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.PathFiller.html

Provides implementations for the PathFiller struct, including methods for creating an empty PathFiller, initializing it with a queue, and retrieving the next element at a given level.

```rust
pub fn empty() -> Self
```

```rust
pub fn new(queue: VecDeque<H>) -> Self
```

```rust
pub fn next(&mut self, level: Level) -> H
```

--------------------------------

### Get Leaf Node of CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Returns an optional reference to the leaf node of the CommitmentTree.

```rust
pub fn leaf(&self) -> Option<&H>
```

--------------------------------

### Address Equality and Partial Ordering

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Methods for checking equality and partial ordering between Address instances.

```APIDOC
## fn eq(&self, other: &Address) -> bool

Tests for `self` and `other` values to be equal, and is used by `==`.

### Method
`eq`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Address` - The second address.

### Returns
- `bool` - `true` if the addresses are equal, `false` otherwise.
```

```APIDOC
## fn ne(&self, other: &Rhs) -> bool

Tests for `!=`.

### Method
`ne`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Rhs` - The second address.

### Returns
- `bool` - `true` if the addresses are not equal, `false` otherwise.
```

```APIDOC
## fn partial_cmp(&self, other: &Address) -> Option<Ordering>

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

### Method
`partial_cmp`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Address` - The second address.

### Returns
- `Option<Ordering>` - An `Ordering` if the values can be compared, `None` otherwise.
```

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

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

### Method
`lt`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Rhs` - The second address.

### Returns
- `bool` - `true` if `self` is less than `other`, `false` otherwise.
```

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

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

### Method
`le`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Rhs` - The second address.

### Returns
- `bool` - `true` if `self` is less than or equal to `other`, `false` otherwise.
```

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

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

### Method
`gt`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Rhs` - The second address.

### Returns
- `bool` - `true` if `self` is greater than `other`, `false` otherwise.
```

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

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

### Method
`ge`

### Parameters
- **self**: `&Address` - The first address.
- **other**: `&Rhs` - The second address.

### Returns
- `bool` - `true` if `self` is greater than or equal to `other`, `false` otherwise.
```

--------------------------------

### Get Right Node of CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Returns a reference to the optional right node of the CommitmentTree.

```rust
pub fn right(&self) -> &Option<H>
```

--------------------------------

### Get NonEmptyFrontier Leaf

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.NonEmptyFrontier.html

Returns a reference to the leaf value most recently added to the frontier.

```rust
pub fn leaf(&self) -> &H
```

--------------------------------

### Arbitrary Frontier Strategy

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

Creates a Proptest strategy for generating `Frontier` instances with a specified minimum size and an arbitrary node strategy. It populates the frontier by appending nodes.

```rust
pub fn arb_frontier<H: Hashable + Clone + Debug, T: Strategy<Value = H>, const DEPTH: u8>(
        min_size: usize,
        arb_node: T,
    ) -> impl Strategy<Value = Frontier<H, DEPTH>> {
        assert!((1 << DEPTH) >= min_size + 100);
        vec(arb_node, min_size..(min_size + 100)).prop_map(move |v| {
            let mut frontier = Frontier::empty();
            for node in v.into_iter() {
                frontier.append(node);
            }
            frontier
        })
    }
```

--------------------------------

### Creating and Updating an IncrementalWitness

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/witness/struct.IncrementalWitness.html

Demonstrates how to create an IncrementalWitness from a CommitmentTree, append new nodes to both the tree and the witness, and verify their roots.

```rust
use incrementalmerkletree::{
    frontier::CommitmentTree,
    witness::IncrementalWitness,
    Position
};
use incrementalmerkletree::frontier::testing::TestNode;

let mut tree = CommitmentTree::<TestNode, 8>::empty();

tree.append(TestNode(0));
tree.append(TestNode(1));
let mut witness = IncrementalWitness::from_tree(tree.clone()).expect("tree is not empty");
assert_eq!(witness.witnessed_position(), Position::from(1));
assert_eq!(tree.root(), witness.root());

let next = TestNode(2);
tree.append(next.clone());
witness.append(next);
assert_eq!(tree.root(), witness.root());
```

--------------------------------

### Get Left Node of CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Returns a reference to the optional left node of the CommitmentTree.

```rust
pub fn left(&self) -> &Option<H>
```

--------------------------------

### IncrementalWitness Methods

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/witness/struct.IncrementalWitness.html

This section details the publicly available methods for interacting with the IncrementalWitness struct.

```APIDOC
## Struct IncrementalWitness<H, const DEPTH: u8>

An updatable witness to a path from a position in a particular `CommitmentTree`.
Appending the same commitments in the same order to both the original `CommitmentTree` and this `IncrementalWitness` will result in a witness to the path from the target position to the root of the updated tree.

Available on **crate feature`legacy-api`** only.

### `fn from_tree(tree: CommitmentTree<H, DEPTH>) -> Option<Self>`

Creates an `IncrementalWitness` for the most recent commitment added to the given `CommitmentTree`.
Returns `None` if `tree` is empty (and thus there is no position to witness).

### `fn invalid_empty_witness() -> Self`

Creates an invalid empty `IncrementalWitness`. This constructor is provided for backwards compatibility with the encodings of `zcashd` `IncrementalWitness` values; that type permits multiple distinct encodings of the same witness state, and in some cases it is necessary to create an empty witness and then append leaves in order to obtain the encoded forms produced by `zcashd` (and which we must reproduce in order to demonstrate interoperability with `zcashd` test vectors.) This should not be used except in a testing context.

### `fn from_parts( tree: CommitmentTree<H, DEPTH>, filled: Vec<H>, cursor: Option<CommitmentTree<H, DEPTH>>, ) -> Option<Self>`

Constructs an `IncrementalWitness` from its parts.
Returns `None` if the parts do not form a valid witness, for example if all of the parts are empty (and thus there is no position to witness).

### `fn tree(&self) -> &CommitmentTree<H, DEPTH>`

Returns the underlying `CommitmentTree`.

### `fn filled(&self) -> &Vec<H>`

Returns the filled portion of the witness.

### `fn cursor(&self) -> &Option<CommitmentTree<H, DEPTH>>`

Returns the cursor of the witness.

### `fn witnessed_position(&self) -> Position`

Returns the position of the witnessed leaf node in the commitment tree.

### `fn tip_position(&self) -> Position`

Returns the position of the last leaf appended to the witness.

### `fn append(&mut self, node: H) -> Result<(), ()>`

Tracks a leaf node that has been added to the underlying tree.
Returns an error if the tree is full.

### `fn root(&self) -> H`

Returns the current root of the tree corresponding to the witness.

### `fn path(&self) -> Option<MerklePath<H, DEPTH>>`

Returns the current witness, or None if the tree is empty.

### `fn clone(&self) -> IncrementalWitness<H, DEPTH>`

Returns a copy of the value.

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

Performs copy-assignment from `source`.
```

--------------------------------

### Consume frontier to get option

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Consumes the Frontier wrapper and returns the underlying Option<NonEmptyFrontier>.

```rust
pub fn take(self) -> Option<NonEmptyFrontier<H>>
```

--------------------------------

### Get Size of CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Returns the total number of leaf nodes currently present in the CommitmentTree.

```rust
pub fn size(&self) -> usize
```

--------------------------------

### MerklePath::from_parts Constructor

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.MerklePath.html

Constructs a MerklePath directly from a vector of hash elements and a position. Returns a Result indicating success or failure.

```rust
pub fn from_parts(path_elems: Vec<H>, position: Position) -> Result<Self, ()>
```

--------------------------------

### Get Parent Nodes of CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Returns a reference to the vector containing the parent nodes of the CommitmentTree.

```rust
pub fn parents(&self) -> &Vec<Option<H>>
```

--------------------------------

### Get Parent Address

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Calculates the address of the parent node. This is useful for navigating up the Merkle tree structure.

```rust
pub fn parent(&self) -> Address
```

--------------------------------

### Address Comparison Methods

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Provides methods for comparing Address instances, including standard comparison and ordering.

```APIDOC
## fn cmp(&self, other: &Address) -> Ordering

This method returns an `Ordering` between `self` and `other`.

### Method
`cmp`

### Parameters
- **self**: `&Address` - The first address to compare.
- **other**: `&Address` - The second address to compare.

### Returns
- `Ordering` - An ordering between `self` and `other`.
```

```APIDOC
## fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

### Method
`max`

### Parameters
- **self**: `Self` - The first address.
- **other**: `Self` - The second address.

### Returns
- `Self` - The maximum of the two addresses.
```

```APIDOC
## fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

### Method
`min`

### Parameters
- **self**: `Self` - The first address.
- **other**: `Self` - The second address.

### Returns
- `Self` - The minimum of the two addresses.
```

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

Restrict a value to a certain interval.

### Method
`clamp`

### Parameters
- **self**: `Self` - The value to clamp.
- **min**: `Self` - The minimum allowed value.
- **max**: `Self` - The maximum allowed value.

### Returns
- `Self` - The clamped value.
```

--------------------------------

### Getting the most recently appended leaf

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

The `leaf` method returns a reference to the leaf value currently held by the frontier.

```rust
pub fn leaf(&self) -> &H {
    &self.leaf
}
```

--------------------------------

### Getting the position of the most recently appended leaf

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

The `position` method returns the current position of the frontier's leaf.

```rust
pub fn position(&self) -> Position {
    self.position
}
```

--------------------------------

### CloneToUninit Trait Implementation (Nightly)

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.MerklePath.html

An experimental nightly-only API for performing copy-assignment from a cloned value to uninitialized memory.

```rust
impl<T> CloneToUninit for T
where T: Clone,
```

```rust
unsafe fn clone_to_uninit(&self, dest: *mut u8)
```

--------------------------------

### Get non-empty frontier reference

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Returns a reference to the inner NonEmptyFrontier if the frontier is not empty, otherwise returns None.

```rust
pub fn value(&self) -> Option<&NonEmptyFrontier<H>>
```

--------------------------------

### Level Partial Ordering Comparison

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Level.html

Compares two Level instances and returns an Option<Ordering> if a comparison is possible. Used for partial ordering checks.

```rust
fn partial_cmp(&self, other: &Level) -> Option<Ordering>
```

--------------------------------

### Get NonEmptyFrontier Ommer Hashes

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.NonEmptyFrontier.html

Provides a slice of the past hashes required for constructing a witness for the latest leaf.

```rust
pub fn ommers(&self) -> &[H]
```

--------------------------------

### Frontier::fmt

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Formats the Frontier instance for debugging purposes using the given formatter.

```APIDOC
## Frontier::fmt

### Description
Formats the value using the given formatter.

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

### Parameters
#### Path Parameters
- `f` (&mut Formatter<'_>) - The formatter to use.

### Returns
- `Result`: A Result indicating success or failure of the formatting operation.
```

--------------------------------

### Convert Position to Address

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Converts a Position into an Address at level 0. This is a common conversion when starting from a leaf position.

```rust
impl From<Position> for Address {
    fn from(p: Position) -> Self {
        Address {
            level: 0.into(),
            index: p.into(),
        }
    }
}
```

--------------------------------

### Getting the list of past hashes (ommers)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

The `ommers` method returns a slice containing the hashes required for witness construction.

```rust
pub fn ommers(&self) -> &[H] {
    &self.ommers
}
```

--------------------------------

### Get Maximum Position

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the maximum leaf position contained within the subtree rooted at this address. Complements `position_range_start`.

```rust
pub fn max_position(&self) -> Position
```

--------------------------------

### Position Methods

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Provides various utility methods for `Position`, including checking child status, determining root level, counting past ommers, and verifying subtree completeness.

```APIDOC
## Position Methods

### Description
Provides utility methods for the `Position` type, which represents the position of a leaf in a Merkle tree.

### Methods

#### `is_right_child()`
- **Description**: Returns `true` if the position refers to the right-hand child of a subtree with its root at level 1.
- **Signature**: `pub fn is_right_child(&self) -> bool`

#### `root_level()`
- **Description**: Returns the minimum possible level of the root of a binary tree containing at least `self + 1` leaves.
- **Signature**: `pub fn root_level(&self) -> Level`

#### `past_ommer_count()`
- **Description**: Returns the number of cousins and/or ommers required to construct an authentication path to the root of a Merkle tree that has `self + 1` leaves.
- **Signature**: `pub fn past_ommer_count(&self) -> u8`

#### `is_complete_subtree(root_level: Level)`
- **Description**: Returns `true` if the binary tree having `self` as the position of the rightmost leaf contains a perfect balanced tree with a root at `root_level` that contains the aforesaid leaf.
- **Signature**: `pub fn is_complete_subtree(&self, root_level: Level) -> bool`
- **Parameters**:
  - **root_level**: `Level` - The level of the root to check against.
```

--------------------------------

### Get Sibling Address

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the address of the sibling node, which shares the same parent. Essential for Merkle proof generation and verification.

```rust
pub fn sibling(&self) -> Address
```

--------------------------------

### Frontier::clone_from

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Performs copy-assignment from a source Frontier instance to the current one.

```APIDOC
## Frontier::clone_from

### Description
Performs copy-assignment from `source`.

### Method
`clone_from(&mut self, source: &Self)`

### Parameters
#### Path Parameters
- `source` (&Self) - The source Frontier to copy from.
```

--------------------------------

### Create Empty CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Creates a new, empty CommitmentTree. This is a basic constructor for initializing an empty tree structure.

```rust
pub fn empty() -> Self
```

--------------------------------

### Get Address Index

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the index of the address within its level. The index is defined by the count of preceding subtrees at the same level.

```rust
pub fn index(&self) -> u64
```

--------------------------------

### Get Address Level

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Retrieves the level of the Merkle tree root associated with this address. The level indicates the depth in the tree.

```rust
pub fn level(&self) -> Level
```

--------------------------------

### TryFrom<Position> for usize

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Position.html

Provides functionality to convert a Position into a usize. It defines the error type for conversion failures and the `try_from` method to perform the conversion.

```APIDOC
## impl TryFrom<Position> for usize

### Description
Provides functionality to convert a Position into a usize. It defines the error type for conversion failures and the `try_from` method to perform the conversion.

### Type `Error`
- **Type**: `TryFromIntError`
- **Description**: The type returned in the event of a conversion error.

### Method `try_from`
- **Signature**: `fn try_from(p: Position) -> Result<Self, Self::Error>`
- **Description**: Performs the conversion from a Position to a usize.
```

--------------------------------

### Get dynamic memory usage

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Calculates and returns the amount of memory dynamically allocated for ommer values within the frontier.

```rust
pub fn dynamic_memory_usage(&self) -> usize
```

--------------------------------

### Constructing a new frontier with a leaf at position 0

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

Use `NonEmptyFrontier::new` to create a frontier with a single leaf. The leaf is automatically assigned position 0 and has no ommers.

```rust
pub fn new(leaf: H) -> Self {
    Self {
        position: 0.into(),
        leaf,
        ommers: vec![],
    }
}
```

--------------------------------

### Get Children Addresses

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Retrieves the immediate children of the current address, if they exist. Returns an Option containing a tuple of two addresses.

```rust
pub fn children(&self) -> Option<(Address, Address)>
```

--------------------------------

### Get Next Address at Level

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Increments the index of the current address by one at its level and returns the new address. Useful for sequential traversal.

```rust
pub fn next_at_level(&self) -> Address
```

--------------------------------

### NonEmptyFrontier Methods

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.NonEmptyFrontier.html

Methods for creating and accessing data within a NonEmptyFrontier.

```APIDOC
## `NonEmptyFrontier<H>`

A `NonEmptyFrontier` is a reduced representation of a Merkle tree, containing a single leaf value, along with the vector of hashes produced by the reduction of previously appended leaf values that will be required when producing a witness for the current leaf.

### `new(leaf: H) -> Self`

Constructs a new frontier with the specified value at position 0.

### `from_parts(position: Position, leaf: H, ommers: Vec<H>) -> Result<Self, FrontierError>`

Constructs a new frontier from its constituent parts.

### `into_parts(self) -> (Position, H, Vec<H>)`

Decomposes the frontier into its constituent parts.

### `position(&self) -> Position`

Returns the position of the most recently appended leaf.

### `leaf(&self) -> &H`

Returns the leaf most recently appended to the frontier.

### `ommers(&self) -> &[H]`

Returns the list of past hashes required to construct a witness for the leaf most recently appended to the frontier.
```

--------------------------------

### Get Current Root of CommitmentTree

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.CommitmentTree.html

Returns the current root hash of the CommitmentTree. Requires the Hashable and Clone traits for the generic type H.

```rust
pub fn root(&self) -> H
```

--------------------------------

### MerklePath StructuralPartialEq Implementation

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.MerklePath.html

Enables structural equality comparison for MerklePath.

```rust
impl<H, const DEPTH: u8> StructuralPartialEq for MerklePath<H, DEPTH>
```

--------------------------------

### TryFrom<usize> for Position

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Position.html

Enables the conversion of a usize into a Position. It specifies the error type for potential conversion issues and includes the `try_from` method for executing the conversion.

```APIDOC
## impl TryFrom<usize> for Position

### Description
Enables the conversion of a usize into a Position. It specifies the error type for potential conversion issues and includes the `try_from` method for executing the conversion.

### Type `Error`
- **Type**: `TryFromIntError`
- **Description**: The type returned in the event of a conversion error.

### Method `try_from`
- **Signature**: `fn try_from(sz: usize) -> Result<Self, Self::Error>`
- **Description**: Performs the conversion from a usize to a Position.
```

--------------------------------

### Get Maximum Position Contained by Address

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Calculates the maximum leaf position index within the range covered by this address. Useful for boundary checks.

```rust
pub fn max_position(&self) -> Position {
    self.position_range_end() - 1
}
```

--------------------------------

### Get Current Root of the Witness Tree

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/witness.rs.html

Retrieves the current root hash of the Merkle tree represented by the witness. This is useful for verifying the integrity of the tree.

```rust
pub fn root(&self) -> H {
        self.tree.root_at_depth(DEPTH, self.filler())
    }
```

--------------------------------

### witness

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

Constructs a MerklePath to the leaf at the tip of this frontier, given a source of node values that complement this frontier. If the complement_nodes function returns None when the value is requested at a given tree address, the address at which the failure occurs will be returned as an error.

```APIDOC
## witness

### Description
Constructs a `MerklePath` to the leaf at the tip of this frontier. It requires a function that provides complementary node values. If the provided function fails to supply a node at a required address, an error is returned.

### Method
`witness<F>(&self, complement_nodes: F) -> Result<Option<MerklePath<H, DEPTH>>, Address>`

### Parameters
#### Closure `complement_nodes`
- `Fn(Address) -> Option<H>`: A function that takes a tree `Address` and returns an `Option<H>` representing the hash at that address, or `None` if it cannot be provided.

### Returns
- `Result<Option<MerklePath<H, DEPTH>>, Address>`: Returns `Ok(Some(MerklePath))` if successful, `Ok(None)` if the frontier is empty, or an `Err` containing the `Address` where the `complement_nodes` function failed.
```

--------------------------------

### Get Next Incomplete Parent Address

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Calculates the address of the next parent that is considered incomplete. Used in algorithms dealing with partially formed trees.

```rust
pub fn next_incomplete_parent(&self) -> Address
```

--------------------------------

### VZip<V> for T Implementation

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/enum.Marking.html

This implementation provides a `vzip` method for type `T`, which returns a value of type `V`. This is applicable when `V` is a `MultiLane` of `T`, suggesting a mechanism for zipping or combining multiple lanes of data.

```APIDOC
## impl<V, T> VZip<V> for T

### Description
Enables zipping operations for type `T` into a multi-lane structure `V`.

### Methods
- `vzip(self) -> V`: Returns a `V` (a MultiLane of `T`) by zipping the current instance.
```

--------------------------------

### Get Position Range

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the end-exclusive range of leaf positions covered by the subtree rooted at this address. Provides a complete view of the contained leaves.

```rust
pub fn position_range(&self) -> Range<Position>
```

--------------------------------

### Address Context Calculation

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Shows how to determine the context of an address relative to a specific level, returning either a range or another address.

```rust
assert_eq!(Address::from_parts(Level(3), 1).context(Level(0)), Either::Right(Range { start: 8, end: 16 }));
assert_eq!(Address::from_parts(Level(3), 4).context(Level(5)), Either::Left(Address::from_parts(Level(5), 1)));
```

--------------------------------

### Get Minimum Root Level for Position

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Position.html

Calculates the minimum possible level for a Merkle tree root that can contain at least `self + 1` leaves.

```rust
pub fn root_level(&self) -> Level
```

--------------------------------

### Implement CloneToUninit Trait for NonEmptyFrontier

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.NonEmptyFrontier.html

Implements the nightly-only experimental CloneToUninit trait for NonEmptyFrontier.

```rust
unsafe fn clone_to_uninit(&self, dest: *mut u8)
```

--------------------------------

### Construct MerklePath witness

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Constructs a MerklePath to the leaf at the frontier's tip, using a provided function for complement nodes. Returns an error with the address of failure if complement nodes are not found.

```rust
pub fn witness<F>( &self, complement_nodes: F, ) -> Result<Option<MerklePath<H, DEPTH>>, Address> where F: Fn(Address) -> Option<H>
```

--------------------------------

### Get Current Incomplete Address

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the current address, potentially representing an incomplete part of the tree structure. Specific usage depends on tree state.

```rust
pub fn current_incomplete(&self) -> Address
```

--------------------------------

### Frontier::try_from

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/frontier/struct.Frontier.html

Attempts to convert a NonEmptyFrontier into a Frontier. Returns an error if the conversion fails.

```APIDOC
## Frontier::try_from

### Description
Performs the conversion from `NonEmptyFrontier` to `Frontier`.

### Method
`try_from(f: NonEmptyFrontier<H>) -> Result<Self, FrontierError>`

### Parameters
#### Path Parameters
- `f` (NonEmptyFrontier<H>) - The NonEmptyFrontier to convert.

### Returns
- `Result<Self, FrontierError>`: A Result containing the Frontier instance on success, or a FrontierError on failure.
```

--------------------------------

### Get Position Range End

Source: https://docs.rs/incrementalmerkletree/latest/incrementalmerkletree/struct.Address.html

Returns the exclusive end of the leaf position range contained within the subtree rooted at this address. Used for defining ranges.

```rust
pub fn position_range_end(&self) -> Position
```

--------------------------------

### Address Struct Documentation

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Documentation for the `Address` struct, representing the address of a node in the Merkle tree. It includes methods for construction, retrieving node information, and navigating the tree structure.

```APIDOC
## Address Struct

The address of a node of the Merkle tree. When `level == 0`, the index has the same value as the position.

### Methods

*   `from_parts(level: Level, index: u64) -> Self`: Construct a new address from its constituent parts.
*   `above_position(level: Level, position: Position) -> Self`: Returns the address at the given level that contains the specified leaf position.
*   `level(&self) -> Level`: Returns the level of the address.
*   `index(&self) -> u64`: Returns the index of the address. The index of an address is defined as the number of subtrees with their roots at the address's level that appear to the left of this address in a binary tree of arbitrary height > level * 2 + 1.
*   `parent(&self) -> Address`: Returns the address of the node one level higher than this in a binary tree that contains this address as either its left or right child.
*   `sibling(&self) -> Address`: Returns the address that shares the same parent as this address.
*   `children(&self) -> Option<(Address, Address)>`: Returns the immediate children of this address. Returns `None` if the current level is 0.
*   `is_ancestor_of(&self, addr: &Self) -> bool`: Returns whether this address is an ancestor of the specified address.
```

--------------------------------

### Get End of Position Range Contained by Address

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/lib.rs.html

Returns the exclusive end of the leaf position range covered by the tree rooted at this address. Useful for range queries.

```rust
pub fn position_range_end(&self) -> Position {
    ((self.index + 1) << self.level.0).into()
}
```

--------------------------------

### Arbitrary CommitmentTree Strategy (Legacy API)

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/frontier.rs.html

Generates a Proptest strategy for `CommitmentTree` using the legacy API. It populates the tree and resizes parents to match the depth.

```rust
pub fn arb_commitment_tree<H: Hashable + Clone + Debug, T: Strategy<Value = H>, const DEPTH: u8>(
        min_size: usize,
        arb_node: T,
    ) -> impl Strategy<Value = CommitmentTree<H, DEPTH>> {
        assert!((1 << DEPTH) >= min_size + 100);
        vec(arb_node, min_size..(min_size + 100)).prop_map(move |v| {
            let mut tree = CommitmentTree::empty();
            for node in v.into_iter() {
                tree.append(node).unwrap();
            }
            tree.parents.resize_with((DEPTH - 1).into(), || None);
            tree
        })
    }
```

--------------------------------

### Getting the Witnessed Position

Source: https://docs.rs/incrementalmerkletree/latest/src/incrementalmerkletree/witness.rs.html

Retrieves the position of the leaf node that the witness is currently tracking within the commitment tree. Assumes the tree size is within supported limits.

```rust
pub fn witnessed_position(&self) -> Position {
    Position::try_from(self.tree.size() - 1)
        .expect("Commitment trees with more than 2^64 leaves are unsupported.")
}
```
Tokens:
Raw