JRFC 20 - Merkle DAG

When I hear "[Merkle Tree](https://en.wikipedia.org/wiki/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

``` go
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)