Function tree_hash::merkleize_padded

source · 
pub fn merkleize_padded(bytes: &[u8], min_leaves: usize) -> Hash256
Expand description

Merkleize bytes and return the root, optionally padding the tree out to min_leaves number of leaves.

Note: This function is generally worse than using the crate::merkle_root which uses MerkleHasher. We only keep this function around for reference testing.

First all nodes are extracted from bytes and then a padding node is added until the number of leaf chunks is greater than or equal to min_leaves. Callers may set min_leaves to 0 if no adding additional chunks should be added to the given bytes.

If bytes.len() <= BYTES_PER_CHUNK, no hashing is done and bytes is returned, potentially padded out to BYTES_PER_CHUNK length with 0.

CPU Performance

A cache of MAX_TREE_DEPTH hashes are stored to avoid re-computing the hashes of padding nodes (or their parents). Therefore, adding padding nodes only incurs one more hash per additional height of the tree.

Memory Performance

This algorithm has two interesting memory usage properties:

  1. The maximum memory footprint is roughly O(V / 2) memory, where V is the number of leaf chunks with values (i.e., leaves that are not padding). The means adding padding nodes to the tree does not increase the memory footprint.
  2. At each height of the tree half of the memory is freed until only a single chunk is stored.
  3. The input bytes are not copied into another list before processing.

Note: there are some minor memory overheads, including a handful of usizes and a list of MAX_TREE_DEPTH hashes as lazy_static constants.