# Module darkfi_sdk::crypto::smt

source · ## Expand description

Sparse Merkle Tree implementation This file provides a native implementation of the Sparse Merkle tree data structure.

A Sparse Merkle tree is a type of Merkle tree, but it is much easier to
prove non-membership in a sparse Merkle tree than in an arbitrary Merkle
tree. For an explanation of sparse Merkle trees, see:
`<https://medium.com/@kelvinfichter/whats-a-sparse-merkle-tree-acda70aeb837>`

In this file we define the `Path`

and `SparseMerkleTree`

structs.
These depend on your choice of a prime field F, a field hasher over F
(any hash function that maps F^2 to F will do, e.g. the poseidon hash
function of width 3 where an input of zero is used for padding), and the
height N of the sparse Merkle tree.

The path corresponding to a given leaf node is stored as an N-tuple of pairs of field elements. Each pair consists of a node lying on the path from the leaf node to the root, and that node’s sibling. For example, suppose

```
a
/ \
b c
/ \ / \
d e f g
```

is our Sparse Merkle tree, and `a`

through `g`

are field elements stored at
the nodes. Then the merkle proof path `e-b-a`

from leaf `e`

to root `a`

is
stored as `[(d,e), (b,c)]`

## §Terminology

**level**- the depth in the tree. Type:`u32`

**location**- a`(level, position)`

tuple**position**- the leaf index, or equivalently the binary direction through the tree with type`F`

.**index**- the internal index used in the DB which is`BigUint`

. Leaf node indexes are calculated as`leaf_idx = final_level_start_idx + position`

.**node**- either the leaf values or parent nodes`hash(left, right)`

.

## Re-exports§

`pub use util::Poseidon;`

## Modules§

- empty 🔒

## Structs§

- An in-memory storage, useful for unit tests and smaller trees.
- The path contains a sequence of sibling nodes that make up a Merkle proof. Each sibling node is used to identify whether the merkle root construction is valid at the root.
- The Sparse Merkle Tree struct.

## Constants§

## Traits§

- Pluggable storage backend for the SMT. Has a minimal interface to put, get, and delete objects from the store.

## Functions§

- A function to generate empty hashes with a given
`default_leaf`

.