[][src]Struct libra_jellyfish_merkle::node_type::InternalNode

pub struct InternalNode { /* fields omitted */ }

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[src]

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

Creates a new Internal node.

pub fn hash(&self) -> HashValue[src]

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

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

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

Gets the n-th child.

pub fn generate_bitmaps(&self) -> (u16, u16)[src]

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>)
[src]

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[src]

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. Read more

type Strategy = BoxedStrategy<Self>

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

impl Clone for InternalNode[src]

impl Debug for InternalNode[src]

impl Eq for InternalNode[src]

impl From<InternalNode> for Node[src]

impl From<InternalNode> for HashMap<Nibble, Child>[src]

impl PartialEq<InternalNode> for InternalNode[src]

impl StructuralEq for InternalNode[src]

impl StructuralPartialEq for InternalNode[src]

Auto Trait Implementations

impl RefUnwindSafe for InternalNode

impl Send for InternalNode

impl Sync for InternalNode

impl Unpin for InternalNode

impl UnwindSafe for InternalNode

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<T> Pointable for T

type Init = T

The type for initializers.

impl<T> Same<T> for T

type Output = T

Should always be Self

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

impl<V, T> VZip<V> for T where
    V: MultiLane<T>,