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: <>

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

        /   \
       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)]


  • 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).




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



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


  • A function to generate empty hashes with a given default_leaf.

Type Aliases§