When I hear "Merkle Tree", I think this:

But only this. A more generalized version of a merkle tree, where non-leaf nodes also contain data, is significantly different. Sometimes "Like Git" or "Like a blockchain" or "Like ZFS" works, but sometimes not. (@davidad probably feels the same way too). And since most of the time I mean a DAG, not a strict Tree, we might as well redefine. In interest of convenient future referencing, let's state the definition that has emerged through the use of "Merkle Trees" in various systems here. If someone has a better one (or can point me to the formal name of this thing that I didn't know about...) please post it below!

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 (efficient!)
• deduplication of common children
• can content address all the nodes in the datastructure
• can reveal single path from node to a root (with adjacent hashes) and prove object must be in dag.

Example

Sample git tree object:

> git cat-file -p master^{tree}
040000 tree 1a4f07485d009e5220a5fa34a9ef74b4269e5725    bam
100644 blob 5716ca5987cbf97d6bb54920bea6adde242d87e6    bar
100644 blob 76018072e09c5d31c8c6e3113b8aa0fe625195ca    baz

Sample git blob named 5716ca5987cbf97d6bb54920bea6adde242d87e6

> git cat-file -p 1a4f07485d009e5220a5fa34a9ef74b4269e5725
bar

Examples in practice

• ZFS blocks
• Bitcoin Blockchain
• Git version history DAG (it's not a tree!)
• All "standard" binary Merkle Trees (like diagram above).

Example in Code

type Hash []byte

type Hashable interface {
  Hash() Hash
}

type Directory struct {
  Entries map[string]Hash  // Files or Directories
}

func (d *Directory) Hash() Hash {
  hash := new hash.Sha256()
  for (var k, v in range(d.Entries)) {
    hash.Write(k)
    hash.Write(v)
  }
  return hash.Digest()
}

func (d *Directory) Add(h Hashable) {
  d.Entries[h.Hash()] = h
}

type File struct {
  Data []byte
}

func (f *File) Hash() Hash {
  hash := new hash.Sha256()
  hash.Write(f.Data)
  return hash.Digest()
}

var allObjects Directory

(Disclaimer: I haven't run this. For illustration only)