Ethereum's Compact Merkle Trie (nervous.io)

I can't say much about the Compact Merkle Tree, but Merkle Trees generally have had widespread uses in databases[1] and filesystems[2]

[1] http://distributeddatastore.blogspot.com/2013/07/cassandra-u...

[2] https://blogs.oracle.com/bonwick/zfs-end-to-end-data-integri...

this kind of stuff = merkle trees? they're really awesome. I like to think of the whole class of things as "self-authenticating data structures".

for a list of uses for merkle trees: https://en.wikipedia.org/wiki/Merkle_tree#Uses

Merkle trees are used extensively in distributed computing. Here's an example: You have many instances serving assets of some kind replicated in several data centers. They are structured in an arbitrary number of branches with many assets in each branch:

  (root)
    |   \
  (foo)  (bar)---(baz)----[even_more_assets]
    |     |
    |  [many_more_assets]
    |
  [many_assets]

How do you make sure the asset trees in the instances are synced up, serving the same assets?

You could compare every bit across every instance, but that would be very inefficient. You could compare the hashes of all the assets at each node of the tree, but you would still end up making many unnecessary comparisons.

You can simply hash each node of the tree based on the hash of its child nodes / assets. This forms a Merkle tree. That way, you can simply compare the root hashes across instances, and if they match, then the whole asset tree must be the same. If they don't match, compare the hashes at the next level of the tree until you find the discrepancy, and sync the nodes / assets where the hashes don't match. Merkle trees can be a very powerful tool for reaching consensus quickly in distributed systems.

Not that weird of a coincidence, right? The words lisp and sputter are both related to speech, so I wasn't being overly creative when I came up with the name.

I wouldn't recommend using my incarnation of sputter just yet. It's not even close to being production-ready and it's purely interpreted right now and rather slow.