Struct diem_jellyfish_merkle::node_type::InternalNode

pub struct InternalNode { /* private fields */ }

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.

Implementations

impl InternalNode

pub fn new(children: HashMap<Nibble, Child>) -> Self

Creates a new Internal node.

pub fn hash(&self) -> HashValue

pub fn serialize(&self, binary: &mut Vec<u8>) -> Result<()>

pub fn deserialize(data: &[u8]) -> Result<Self>

pub fn child(&self, n: Nibble) -> Option<&Child>

Gets the n-th child.

pub fn generate_bitmaps(&self) -> (u16, u16)

Generates existence_bitmap and leaf_bitmap as a pair of u16s: child at index i exists if existence_bitmap[i] is set; child at index i is leaf node if leaf_bitmap[i] is set.

pub fn get_child_with_siblings( &self, node_key: &NodeKey, n: Nibble ) -> (Option<NodeKey>, Vec<HashValue>)

Gets the child and its corresponding siblings that are necessary to generate the proof for the n-th child. If it is an existence proof, the returned child must be the n-th child; otherwise, the returned child may be another child. See inline explanation for details. When calling this function with n = 11 (node b in the following graph), the range at each level is illustrated as a pair of square brackets:

    4      [f   e   d   c   b   a   9   8   7   6   5   4   3   2   1   0] -> root level
           ---------------------------------------------------------------
    3      [f   e   d   c   b   a   9   8] [7   6   5   4   3   2   1   0] width = 8
                                 chs <--┘                        shs <--┘
    2      [f   e   d   c] [b   a   9   8] [7   6   5   4] [3   2   1   0] width = 4
                 shs <--┘               └--> chs
    1      [f   e] [d   c] [b   a] [9   8] [7   6] [5   4] [3   2] [1   0] width = 2
                         chs <--┘       └--> shs
    0      [f] [e] [d] [c] [b] [a] [9] [8] [7] [6] [5] [4] [3] [2] [1] [0] width = 1
    ^                chs <--┘   └--> shs
    |   MSB|<---------------------- uint 16 ---------------------------->|LSB
 height    chs: `child_half_start`         shs: `sibling_half_start`

Trait Implementations

impl Arbitrary for InternalNode

Computes the hash of internal node according to JellyfishTree data structure in the logical view. start and nibble_height determine a subtree whose root hash we want to get. For an internal node with 16 children at the bottom level, we compute the root hash of it as if a full binary Merkle tree with 16 leaves as below:

  4 ->              +------ root hash ------+
                    |                       |
  3 ->        +---- # ----+           +---- # ----+
              |           |           |           |
  2 ->        #           #           #           #
            /   \       /   \       /   \       /   \
  1 ->     #     #     #     #     #     #     #     #
          / \   / \   / \   / \   / \   / \   / \   / \
  0 ->   0   1 2   3 4   5 6   7 8   9 A   B C   D E   F
  ^
height

As illustrated above, at nibble height 0, 0..F in hex denote 16 chidren hashes. Each # means the hash of its two direct children, which will be used to generate the hash of its parent with the hash of its sibling. Finally, we can get the hash of this internal node.

However, if an internal node doesn’t have all 16 chidren exist at height 0 but just a few of them, we have a modified hashing rule on top of what is stated above:

1. From top to bottom, a node will be replaced by a leaf child if the subtree rooted at this node has only one child at height 0 and it is a leaf child.
2. From top to bottom, a node will be replaced by the placeholder node if the subtree rooted at this node doesn’t have any child at height 0. For example, if an internal node has 3 leaf children at index 0, 3, 8, respectively, and 1 internal node at index C, then the computation graph will be like:

  4 ->              +------ root hash ------+
                    |                       |
  3 ->        +---- # ----+           +---- # ----+
              |           |           |           |
  2 ->        #           @           8           #
            /   \                               /   \
  1 ->     0     3                             #     @
                                              / \
  0 ->                                       C   @
  ^
height
Note: @ denotes placeholder hash.

type Parameters = ()

The type of parameters that arbitrary_with accepts for configuration of the generated Strategy. Parameters must implement Default.

type Strategy = BoxedStrategy<InternalNode>

The type of Strategy used to generate values of type Self.

fn arbitrary_with(_args: ()) -> Self::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self). The strategy is passed the arguments given in args.

fn arbitrary() -> Self::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self).

impl Clone for InternalNode

fn clone(&self) -> InternalNode

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for InternalNode

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl From<InternalNode> for HashMap<Nibble, Child>

fn from(node: InternalNode) -> Self

Converts to this type from the input type.

impl<V> From<InternalNode> for Node<V>

fn from(node: InternalNode) -> Self

Converts to this type from the input type.

impl PartialEq<InternalNode> for InternalNode

fn eq(&self, other: &InternalNode) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for InternalNode

impl StructuralEq for InternalNode

impl StructuralPartialEq for InternalNode