[Note for 2017-09-18 release: it seems in light of recent events with
gab.ai the DNS chokepoint hazard is less theoretical than I had
thought, so I am releasing some of my partially finished notes toward
a possible solution.  It is an unfortunate irony of history that the
defense of our network against infrastructural centralization hazards
becomes more urgent in connection with such distasteful people; if
they were in a position of sufficient cultural influence to do so,
they'd surely censor ten times as aggressively.]

Objective:
----------

Protocol participants communicate amongst themselves to learn a set of
transactions applying to one or more domain suffixes to which they subscribe.
For each domain under that suffix for which a homestead and zero or more
transfer of ownership transactions exist, they must resolve any conflicts
among the transfers of ownership in such a way as to be consistent and to
converge to global agreement in bounded time, so that all protocol
participants agree on an owner's public key for each domain.  Then they
may merge together DNS record transactions signed by the owner's public key
to construct a zone file, which can be supplied to a bind instance to
resolve names under the subscribed suffixes.

Scalability:

 - This is a protocol that requires each participant to store full
   transaction history for domains they care about resolving, and for
   any peer which wishes to construct a full zone file will need every
   domain, so enumeration should be possible.

 - Well, almost.  If a domain lapses and is re-homesteaded, it would be
   safe for participants to discard the earlier, lapsed chain of ownership.

 - I believe this is much less problematic than in the case of bitcoin,
   because the typical domain changes hands infrequently.  If this is
   used the way existing domain registrars are, I believe the typical
   domain will have only a homestead record and keepalives on the order
   of once every few years transferring ownership to the same set of
   keys.  It should be reasonable to expect on the order of, say, a 128-
   byte transaction per five years of history per active domain.

 - Per Verisign [1], there are about 127M domains in .com and .net, with
   an increase of about 5% year-over-year (i.e., net increase of 6.1M
   domains), with 8.2M registrations in one quarter.  Extrapolate to 32.8M
   new registrations per year, and conclude there were 26.7M non-renewed
   expirations, for a domain life expectancy of about 4.5 years.

 - So, if we have a 128-byte transaction every time someone homesteads a
   new domain or every five years thereafter as a keepalive, we generate
   3.9G per year of new registration transactions at the scale of the current
   registrar system, and per name we have a 20% probability per year to need
   a keepalive, and a 50% probability to actually execute it generates a
   somewhat longer life expectancy than the current system.  That would
   lead to about 12.7M 128-byte keepalives annually, or about 1.5G of them.
   In total, annual transaction traffic would be 5.4G, or about 184 bytes/
   second.

 - The assumptions in the preceding paragraph lead to Poisson-distributed
   domain ages, with 384 bytes of transaction history for the typical
   domain.  The total size of the transaction set needed to the full
   domain<->owner key table will be about 45.5G.

 - What about bringing up new nodes?  Hopefully by the time this ever gets
   pushed to those extremes the disk space requirements will be reasonable,
   but it could still be days to download that much with moderately near-
   future tech.

Unresolved:

 - Timestamps in TAI or UTC?  Need to compute lengths of intervals potentially
   in the far future accurately for proof of work.

   - Maybe a few leap seconds don't matter and we can just define a length
     metric that pretends they aren't there.

(peer, domain) relations:
-------------------------

Each peer (participant in the transaction exchange protocol), shall have
one of the following states with respect to each name:

 * Seeder

   - This peer stores the full transaction history for the domain and can
     serve it to others; it would like to be informed of any new transactions.

 * Seeker

   - This peer knows some transactions but isn't sure it has the whole
     history; it's trying to become a seeder and would like to be informed
     of any new transactions

 * Ignorant

   - This peer has no transactions for this name and hasn't looked.  It is a
     nonparticipant in the protocol with respect to this name.

 * Unbeliever

   - This peer has sought transactions for this name and found none; it
     believes the name is unused.

Transaction types:
------------------

Transaction IDs shall be SHA-256 hashes over serialized transactions with
all signature fields replaced with zeroes.

Origin of transaction chain for domain suffix (ORIGIN transaction):

 - Domain suffix
 - Random nonce
   - So that in the case of conflicting uses of a domain suffix
     (e.g. internal domains), the transaction IDs will be unique.
 - [optional/maybe reference to origin of chain / ownership transaction plus
    signature for suffix, to enable recursive application?]

Homestead transaction for domain (HOMESTEAD transaction):

 - Transaction ID of ORIGIN
 - A name which is a valid DNS label per RFC 1035
   - That is, 1-63 case-insensitive letters, digits or a '-'
 - valid_after and valid_until timestamps, with valid_after < valid_until
 - A list of N_k >= 1 owner public keys
   - TODO choice of crypto algorithm?  Support for multiple algorithms?
 - Integer valued thresholds n_zone, n_transfer such that
   1 <= n_zone <= N_k and 1 <= n_transfer <= N_k
 - A proof of work to slow mass namesquatting
   - TODO define the proof of work scheme
   - The difficulty should be proportional to the duration of claim
     valid_until - valid_after; to ensure it is possible to compute this
     duration exactly, timestamps should be in TAI, not UTC.

Transfer transaction:

 - Transaction ID of origin and of homestead or previous transfer
   - A list of N_k > 1 owner public keys, threshold parameters as in
     the homestead transaction

Abandon transaction?

BIG INTERESTING UNKNOWN:
------------------------

 - Given multiple independent homesteads for a name, or a multiple transfer,
   equivalent to a double-spend in a cryptocurrency, how do we reach consensus
   on ordering?

 - This is the problem a blockchain solves, but note that transactions can
   only conflict here when they are for the same name; the space of
   transactions partitions in a huge number of independent ordering domains,
   each with very tiny volume and forgiving latency demands.  There must be
   a way to exploit this to be more efficient than a blockchain and avoid
   quadratic scaling or requiring all nodes to store every transaction.

 - This is why approaches like Namecoin or Ethereum-based systems are
   inappropriate; they have no notion of transactions being commutative and
   force everything to be a total order.  I'm hoping for something much
   more lightweight here.

Usage:
------

Once a database mapping names to owner key sets exists, the rest is trivial.
We can complete the system with a distributed hash table; domain owners publish
zone file fragments containing NS, A/AAAA and DNSSEC records for their names,
signed with their keys.  Since these all come from a single administrative
entity per name, we can disambiguate order with a sequence number and have no
need to use a blockchain or whatever more lightweight construction we use for
the owner public keys themselves.

We can consider at least the following types of implementation:

 - Full node that tries to learn all possible names for a particular origin
   transaction; this can then, e.g., generate a zone file to be supplied to
   an external name server

 - Local DNS server or resolver library that tries to discover and cache
   history for a particular name on first access

Adoption strategy:
------------------

Alternative name systems have historically been hamstrung by network effects;
what good is a name no one can resolve?  Why should I take the trouble to set
up someone's weird new DNS gateway to resolve a handful of names?  To that
end, I propose operation as a third-level domain in full node mode.  A
conventional DNS server can expose the content of distributed registrar
database to naive DNS clients, thus making names immediately useful.  It
doesn't fully gain the trust or censorship-resistance advantages for those
clients, since such a server operator can potentially be pressured, although
the presence of the distributed registrar for comparison would make anything
of that nature immediately transparent.

Then, for aware clients, we gain a censorship resistant name system, but we
also gain a trustworthy DNSSEC root.  Adding a record type parallel to SSHFP
for certificate fingerprints would then suffice to provide the equivalent of
domain validation-level certificates and significantly lessen the CA problem.
Finally, for domain operators we can provide freedom from privacy hazards
such as WHOIS Accuracy [2].

[1] https://www.verisigninc.com/assets/domain-name-report-april2014.pdf
[2] https://www.easydns.com/blog/2014/01/21/icann-unleashes-deadliest-ddos-attack-vector-of-2014/