[messaging] Namecoin

[Trevor Perrin]

Namecoin is a naming system based on Bitcoin, with some similarity to
"transparency" ideas we've discussed.

I'll try to summarize it, then discuss its potential for public key
distribution.


Background on Bitcoin and Namecoin
---
The Namecoin "blockchain" is distinct from the Bitcoin blockchain, but
it's basically the same data structure.  Many Bitcoin miners use
"merged mining" to search for Bitcoin and Namecoin blocks
simultaneously.

A Bitcoin or Namecoin "blockchain" is a sequence of Merkle Trees (or
"blocks").  The root hash of each tree is based on the root hash of
the previous, so the trees are linked.  This structure was proposed
for timestamping by Bayer-Haber-Stornetta [1] and others in early 90s.
The idea was a Timestamp Authority (TSA) would collect things people
want timestamped (e.g. inventions) into a tree, then publish the
latest root hash at intervals (e.g. in the newspaper).

You can efficiently prove your "thing" was included in a published
root hash, and that later root hashes include earlier root hashes.
The TSA can't forge these proofs, and if published hashes are widely
witnessed then the TSA doesn't need to be trusted (all it could do is
refuse to publish).

Similar structures have been proposed for certificates and revocation
(Naor-Nissim [2] and related; Certificate Transparency and related).

You get to Bitcoin by:
 1) Having the TSA only timestamp valid "money" transactions between public keys
 2) Having entities solve proof-of-work problems to "mine" money
 3) Replacing the TSA with miners who choose the next block via the
proof-of-work problem

You get to Namecoin by allowing entities to "spend" some "money" in a
transaction that registers a name and a small amount of data (< 1 KB)
to a public key.  The public key can be used to replace the data (and
public key), and an update must be performed every several months or
the registration expires.


Analysis
---
We've discussed the idea of a transparency log where example.com
publishes the mapping ("bob at example.com", bob's public key) [3].  If
this mapping is changed monitors will notify Bob, and Alice can check
an efficient proof that the latest mapping was published.

Namecoin differs in a couple ways:
 1)  With a Namecoin-type log (call it an "immutable mapping" log?),
only Bob is allowed to change the mapping for his name, after
registration.
 2)  Namecoin is a centralized namespace dependent on Bitcoin, not
just a log that different parties could run.

(1) means Namecoin-type logs probably can't be used with existing
namespaces, since existing service providers probably don't want to
surrender control over their names.  But these logs might be a good
way to assign a new name to a public key (e.g. an alternative to
fingerprints).  Bob just has to check that his name was registered, he
doesn't have to worry about changes after that.

(2) means Namecoin *definitely* can't be used with existing
namespaces, as there's a single global namespace and anyone could
register any names.  It also means we're tied to this blockchain and
its quirks, and the only way to get names is to buy them via Namecoin,
which seems like a poor user experience at the moment.


State of software
---
There are some projects claiming to do something with Namecoin, but
everything I could find looks pretty raw - there doesn't seem to be a
"killer app" yet.  Greg Slepak has DNSChain [4], which looks up
Namecoin entries so you don't need your own copy of the blockchain
(currently 2 GB).  Interestingly it doesn't provide Merkle Tree proofs
that the entries match widely published root hashes.  The argument is
you should just query a trusted DNSChain server.

I don't see anyone else using proofs either.  I'm a little surprised
by that, since that seems like the main point of this datastructure.
Curious if anyone has an explanation.


Summary
---
I think the idea of an "immutable mapping" log for names => public
keys is interesting.  I'm not sure the need for everyone to use a
single such log that's tied to Bitcoin.  It seems like a service
provider that lets you register an immutable name for your public key
in its transparency log would provide the same value in a simpler way,
without the centralization.

Trevor

[1] http://en.wikipedia.org/wiki/Linked_timestamping
[2] http://www1.cs.columbia.edu/~locasto/projects/crlcc/naor98certificate.pdf
[3] https://moderncrypto.org/mail-archive/messaging/2014/000226.html
[4] https://github.com/okTurtles/dnschain