Module diem_jellyfish_merkle::node_type

source ·
Expand description

Node types of JellyfishMerkleTree

This module defines two types of Jellyfish Merkle tree nodes: InternalNode and LeafNode as building blocks of a 256-bit JellyfishMerkleTree. InternalNode represents a 4-level binary tree to optimize for IOPS: it compresses a tree with 31 nodes into one node with 16 chidren at the lowest level. LeafNode stores the full key and the value associated.

Structs

  • Child
    Each child of InternalNode encapsulates a nibble forking at this node.
  • InternalNode
    Represents a 4-level subtree with 16 children at the bottom level. Theoretically, this reduces IOPS to query a tree by 4x since we compress 4 levels in a standard Merkle tree into 1 node. Though we choose the same internal node structure as that of Patricia Merkle tree, the root hash computation logic is similar to a 4-level sparse Merkle tree except for some customizations. See the CryptoHash trait implementation below for details.
  • LeafNode
    Represents an account.
  • NodeKey
    The unique key of each node.

Enums