Module darkfi_sdk::crypto::smt

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 🔒
• util
• wasmdb

Structs

• MemoryStorage
  An in-memory storage, useful for unit tests and smaller trees.
• Path
  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.
• SparseMerkleTree
  The Sparse Merkle Tree struct.

Constants

• EMPTY_NODES_FP
• SMT_FP_DEPTH

Traits

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

Functions

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

Type Aliases

• MemoryStorageFp
• PathFp
• PoseidonFp
• SmtMemoryFp