Merkle Tree

Merkle Tree

A Merkle tree is a way of hashing a large number of “chunks” of data together,

• which relies on splitting the chunks into buckets, 
• where each bucket contains only a few chunks, 
• then taking the hash of each bucket and repeating the same process, 
• continuing to do so until the total number of hashes remaining becomes only one: the root hash.

The most common form of Merkle tree is the binary Merkle tree, where a bucket always consists of two adjacent chunks or hashes.

The efficiency comes from peers not needing to know so much.

For example, we have been sent a block and the required “uncle” hashes by an untrusted peer. We don’t have any other verified blocks, but we need to verify the integrity of the block we’ve been sent.

To do this, we utilize the Merkle Proofs.

A Merkle proof consists of a block, the trusted root hash of the tree, and the “branch” consisting of all of the hashes(uncles) going up along the path from the chunk to the root.

Calculating the missing nodes in the Merkle tree by hashing the descendants(the sent block and its uncle hashes) will eventually yield an untrusted hash representing all the blocks. This untrusted root hash can then be compared to our trusted root hash to decide whether to keep the block or not.

In this process, we don't have to know the unknown hashes make up the tree, because those nodes in the tree are covered by the "uncle" nodes.

Merkle DAG

A directed acyclic graph whose objects are linked to each other (usually just by their hash), where the hash(object) includes all hash(linked_object). This gives the Merkle DAG useful properties:

• integrity check a root hash, and know all children are ok too
• deduplication of common children
• can content address all the nodes in the data structure
• can reveal single path from node to a root with adjacent hashes(uncle hashes) and prove object must be in dag.

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/
https://bmcorser.github.io/2014/12/22/merkle-dag.html
https://github.com/ErikBjare/merkle
https://github.com/jimjh/merkle-trees-impl