Struct 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 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 for InternalNode

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

Tests for self and other values to be equal, and is used by ==.

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

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

impl Eq for InternalNode

impl StructuralPartialEq for InternalNode