darkfi_sdk::crypto

Module 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§

Modules§

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§

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§