# Module darkfi_sdk::crypto::smt

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;`

## 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.

## 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`.