Try to share Merkle tree code about keytransparency HOT 2 CLOSED

Differences:

• The Google implementation currently does not support empty epochs.
• The Google implementation returns a codes.NotFound error when a lookup hits an empty branch rather than returning a proof of absence
• The Google implementation doesn't allow changing an existing value (returns codes.AlreadyExists).
• The Yahoo implementation persists everything (in LevelDB) rather than keeping things in memory.
• The Yahoo implementation currently doesn't know about epochs. Instead, it has a concept of "snapshots", which are immutable past version of the tree. You can create a new snapshot from an existing snapshot by calling Snapshot.BeginModification(), which gives you a NewSnapshot, on which you can call Set a bunch of times, and then finally call Flush to get a modified Snapshot out along with the LevelDB WriteBatch that makes the necessary changes. Each snapshot has a unique uint64 identifier, which won't correspond to epoch numbers. Thus, each epoch needs to store a snapshot number internally. (The reason I did this was to increase modularity and make simpler abstractions: the tree is just a standard fully persistent data structure (https://en.wikipedia.org/wiki/Persistent_data_structure#Fully_persistent), and each epoch contains a reference to the tree snapshot.) I already have a layer mapping epoch numbers to snapshots numbers implemented, so I could just use something like that on the Google side as well as long as the API works.

from keytransparency.

• Empty epochs support: refer to #50 [CLOSED].
• Proof of absence: refer to #58.
• Changing existing values: refer to #62 [CLOSED].

from keytransparency.