Struct fuchsia_merkle::MerkleTree

pub struct MerkleTree { /* private fields */ }

A MerkleTree contains levels of hashes that can be used to verify the integrity of data.

While a single hash could be used to integrity check some data, if the data (or hash) is corrupt, a single hash can not determine what part of the data is corrupt. A MerkleTree, however, contains a hash for every 8K block of data, allowing it to identify which 8K blocks of data are corrupt. A MerkleTree also allows individual 8K blocks of data to be verified without having to verify the rest of the data.

Furthermore, a MerkleTree contains multiple levels of hashes, where each level contains hashes of 8K blocks of hashes of the lower level. The top level always contains a single hash, the merkle root. This tree of hashes allows a MerkleTree to determine which of its own hashes are corrupt, if any.

Structure Details

A merkle tree contains levels. A level is a row of the tree, starting at 0 and counting upward. Level 0 represents the leaves of the tree which contain hashes of chunks of the input stream.

Each level consists of a hash for each 8K block of hashes from the previous level (or, for level 0, each 8K block of data). When computing a hash, the 8K block is prepended with a block identity.

A block identity is the binary OR of the starting byte index of the block within the current level and the current level index, followed by the length of the block. For level 0, the length of the block is 8K, except for the last block, which may be less than 8K. All other levels use a block length of 8K.

Implementations

impl MerkleTree

pub fn from_levels(levels: Vec<Vec<Hash>>) -> MerkleTree

Creates a MerkleTree from a well-formed tree of hashes.

A tree of hashes is well-formed iff:

• The length of the last level is 1.
• The length of every hash level is the length of the prior hash level divided by HASHES_PER_BLOCK, rounded up to the nearest integer.

pub fn root(&self) -> Hash

The root hash of the merkle tree.

pub fn from_reader(reader: impl Read) -> Result<MerkleTree, Error>

Creates a MerkleTree from all of the bytes of a Reader.

Examples

let data_to_hash = [0xffu8; 8192];
let tree = MerkleTree::from_reader(&data_to_hash[..]).unwrap();
assert_eq!(
    tree.root(),
    "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737".parse().unwrap()
);

Trait Implementations

impl AsRef<[Vec<GenericDigest<FuchsiaMerkleMarker>>]> for MerkleTree

fn as_ref(&self) -> &[Vec<Hash>]

Converts this type into a shared reference of the (usually inferred) input type.

impl Clone for MerkleTree

fn clone(&self) -> MerkleTree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for MerkleTree

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

Formats the value using the given formatter.

impl From<MerkleTreeBuilder> for MerkleTree

fn from(builder: MerkleTreeBuilder) -> Self

Converts to this type from the input type.

impl Hash for MerkleTree

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Ord for MerkleTree

fn cmp(&self, other: &MerkleTree) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized + PartialOrd,

Restrict a value to a certain interval.

impl PartialEq for MerkleTree

fn eq(&self, other: &MerkleTree) -> 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 PartialOrd for MerkleTree

fn partial_cmp(&self, other: &MerkleTree) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

This method tests less than (for self and other) and is used by the < operator.

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

This method tests less than or equal to (for self and other) and is used by the <= operator.

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

This method tests greater than (for self and other) and is used by the > operator.

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

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for MerkleTree

impl StructuralPartialEq for MerkleTree