[Freedombox-discuss] assigned numbers without ICANN
Thomas Lord
lord at emf.net
Fri Apr 29 02:08:34 UTC 2011
Allocating Assigned Routing Numbers
in a Distributed and Decentralized Way
NEED FOR AN OVERLAY NETWORK
Programs for Freedomboxes can not assume that each box has a
stable IP address. Boxes are most often likely to lack both a
fixed IP and a DNS hostname. Many boxes are also likely to be
connected behind highly restrictive firewalls.
Nevertheless, using some kind of "overlay network", we wish to
establish point-to-point communication between freedomboxes.
ROUTING ADDRESSES FOR THE OVERLAY NETWORK
This document is about how to allocate IP-like addresses for
routing in the overlay network, without needing an ICANN-style
central authority.
A routing address is similar to an IP address. It...
* is a logical name for a network node
* is globally unique
* has a specific owner
* is transferable to a new owner (and new network node)
* can be comfortably written on a small slip of paper
* can be memorized, if need be
* is reasonably secure (hard to forge or steal)
* is the address used by (overlay) network routing
That's like an IP address but there are also differences:
* A routing address looks different. A typical routing address:
0a9jj39f7a
* Routing addresses are allocated in a distributed and
decentralized process - there is no central authority like
ICANN.
* Routing addresses don't break down into nets and subnets
like IP addresses. A routing address has two parts:
0a9 jj39f7a
^^^ -------
| |
| timeslot id
|
timestamp (approximate time of creation)
(What those parts mean is explained later.)
ASSUMPTIONS
This document describes how routing addresses come to be
assigned, transfered, etc. The design includes some
assumptions:
* "Users" control their own freedomboxes.
* Many boxes sit behind an ISP firewall, have no assigned host
name, and have no fixed IP address.
* Some users are "admins"
* Admins have servers that aren't behind an overly restrictive
firewall. They normally have at least an assigned hostname
and ideally a fixed IP address.
* Admins have more technical knowledge than is required of
non-admin users. For example, admins can cooperate with one
another to maintain a federated cryptographic "web of
trust". Not all users have to be adept at such things.
* Admins help other users to connect to the freedombox overlay
network (over the Internet). Admin servers are hubs for
tunneling and for routing to Freedombox users that sit
behind firewalls on the net.
* There is no central "admin authority". Admins compete.
Admins do not need permission to become admins, but
admins who cooperate and federate with other admins
make both sides more effective and valuable. In the
admin business, a good and well earned reputation means
a lot.
* Each user uses the services of one or more admins who that
user trusts. This trust is mutually revokable. Most
non-techie freedombox users will need to "sign on" with one
or more admins to get the full benefit of the box.
* Trust between user and admin is made manifest by an exchange
of keys. The admin and the user each create new key pairs
and exchange public keys. Either can revoke trust in the
other by simply disregarding their own keys and their
counter-party's public key.
* All nodes on the overlay network can guess or compute the
current time relative to GMT to an accuracy of within 12
hours.
In the system described here, if a user wants a new routing
address, he sends a message to his admins. This document
explains the routing address allocation protocol.
THE ANATOMY OF A ROUTING ID
All of the routing IDs we'll talk about here are written
as 10 character numbers in base 36 (more than 51 and less
than 52 bits).
The system is extensible and longer and differently structured
routing IDs are possible. Extensions are not discussed here.
This:
0a9jj39f7a
is a sample routing ID. It breaks down into three parts:
0a9jj39f7a
|
the year offset
0a9jj39f7a
||
the time unit offset
0a9jj39f7a
|||||||
the time-slot ID
Every routing ID is "created" (conceptually speaking) at a
specific time. The time of its creation is recorded in the
year offset and time unit offset of the routing ID.
0a9jj39f7a
|
the year offset relative to 2011
2011 + 0 base 36 = 2011
This ID was created in 2011.
Next is the time unit. The year is divided up into
time units. (The last time unit within a year is shorter
than the others. Some years are shorter than others.)
0a9jj39f7a
||
the time unit offset
((a9 base 36) / (zz base 36)) * 8784 hours
~= 2503 hours (a bit more than 104 days)
This ID was created on the 104th day of the year.
So the timestamp:
0a9 ~= 14 April 2011 07:00 (GMT)
The timestamp clock advances slightly faster than once
per 7 hours.
The final 7 digits are the time-slot ID:
0a9jj39f7a
|||||||
the time-slot ID
In concept, when the timestamp clock advances, all routing ids
with that timestamp and ANY time-slot ID are "created". They
weren't available for allocation before that but then they
are. IDs of a certain tick of the timestamp clock can only be
allocated within the next to ticks of that clock. A routing
ID that hasn't been claimed in 14 hours (within a 12 hour
measure) won't ever be claimed.
Every seven hours roughly, the number of routing IDs "created"
is:
36^7 = 78,364,164,096 ~= 2^36.2
DEEDS FOR ROUTING IDS
For every routing ID that is owned by someone,
there is a cryptographic document called the "deed" for
that routing ID.
Users create brand new deeds when they (successfully) allocate
a new routing ID. Deeds are periodically updated for the
purposes of renewal, transfer, cancelation and some forms of
alteration.
Valid deeds are "recorded" in a decentralized way. As many
admins as possible keep complete or partial records of all
currently valid deeds (and, optionally, a history of those
records).
Deeds begin life as a simple email-like text file.
Routing ID Claim
Timestamp: 0a9
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key goes here ]
STEP 1: OBTAINING A TICKET
To claim a name, a user asks an admin for a claim ticket.
In return, the admin provides something like this:
Claim ticket: 0146458n00 0a99ke8ij2
The first part of the claim ticket ("0146458n00") is itself a
routing address. It is a routing address belonging to the
admin. The second part of the claim ticket is a timestamped
random number (timestamp "0a9" in this case, random number
"99ke8ij2").
This ticket gives the user a limited time ability to claim
some name in the indicated time slot ("0a9" in this case).
STEP 2: WRITING A CLAIM
This explains how to write a claim for a routing
address. Merely writing the claim doesn't
secure the ID -- this is just the first "paperwork"
step.
The user, given the claim ticket, fills out a deed,
as in the earlier example.
Routing ID Claim
Timestamp: 0a9
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key goes here ]
The user then signs the document, using the
corresponding private key:
Routing ID Claim
Timestamp: 0a9
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key ]
------------------
[ self signature of above ]
The user performs a cryptographic hash on the
document (so far), and appends that:
Routing ID Claim
Timestamp: 0a9
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key ]
------------------
[ self signature of the above ]
[ hash of the above in base 36 ]
The first seven characters of the hash are the time-slot ID of
the claimed routing ID. For example, if the hash is:
Lljk28nsdf8867y234hnaoyuyptnn
the first seven characters:
Lljk28n
are combined with the timestamp:
0a9
to create a routing ID:
0a9Lljk28n
SEALING A CLAIM
To "seal" a claim is to encrypt it temporarily, later
publishing the encryption key as a proof of work.
To seal a deed, a user generates a new key pair. Call this
the "seal keys".
A deed, which initially looks something like this:
Routing ID Claim
Timestamp: 0a9
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key ]
[ self signature of the above ]
Hash of above: Lljk28nsdf8867y234hnaoyuyptnn
is encrypted for the public seal key:
[encrypted routing ID claim]
To that the user appends the claimed ID and the
public seal key and claim ticket:
[encrypted routing ID claim]
[public seal key]
ID: 0a9Lljk28n
Claim ticket: 0146458n00 0a99ke8ij2
Then signs it for the public key in the claim itself
and finally for the seal key:
[encrypted routing ID claim]
ID: 0a9Lljk28n
Claim ticket: 0146458n00 0a99ke8ij2
[ claim key signature ]
[ seal key signature ]
STEP 3: SUBMITTING A CLAIM (the short form)
The user transmits the sealed claim to one or more of his
trusted admins.
I'll describe the details of what the admins do among
themselves later. For now, just assume that:
Within about 48 hours, those admins send a reply either
denying the claim, or giving tentative acceptance. A denial
might say:
Sorry, your request to claim
0a9Lljk28n
didn't work out. The reason is [....]
A claim might be rejected because it isn't timely (a timestamp
too far in the past or future).
A claim might be rejected for having an invalid claim ticket.
A claim might be rejected if the admins are having trouble
processing claims.
A claim might be rejected if something goes wrong and,
mysteriously, there are millions of attempts to register the
exact some ID, all at once.
Of course, a claim must be rejected if it is cryptographically
invalid (or unvalidated for too long).
A tentative acceptance, on the other hand, would say
something like:
Your tentative claim for 0a9Lljk28n
has been registered. Please complete
your claim within 12 hours.
or:
Your tentative claim for 0a9Lljk28n
has been registered but there is a problem.
5 competing claims for the same ID have
also been registered.
If you would like to try to complete your claim, please
respond within 12 hours. If two or more valid claims
are registered, none of them is deemed valid.
STEP 4: COMPLETING A CLAIM
To complete a tentative claim, a user (the user's software)
sends back to the admin (and anyone else) the PRIVATE seal
key, signed with the public claim key.
Using that key, any admin (or other user) who has a copy of
the sealed claim:
[encrypted routing ID claim]
ID: 0a9Lljk28n
Claim ticket: 0146458n00 0a99ke8ij2
[ claim key signature ]
[ seal key signature ]
can now decrypt the encrypted part:
Timestamp: 0a9
Keyword: freedombox
Owner Name: Anonymous
Contact Info: n/a
Claim ticket: 0146458n00 0a99ke8ij2
Notes: scratch ID for testing
[ public key ]
------------------
[ self signature of the above ]
[ hash of the above in base 36 ]
ID: 0a9Lljk28n
Claim ticket: 0146458n00 0a99ke8ij2
[ claim key signature of sealed form ]
[ seal key signature ]
and can verify that the final lines (from "hash of the above"
onwards) matches the preceeding material.
If only one user successfully completes a claim, the domain is
his. If none more more than one successfully complete a claim
for the same ID, none of those claims succeed.
RENEWALS
Deeds don't remain valid forever: they must be renewed
periodically.
Deeds are renewed by displaying knowledge of their current
claim key, and providing a (presumably new) replacement
claim key.
To renew a claim:
First, a new claim ticket is obtained from a trusted admin:
Claim ticket: 0146458n00 0b69e8ix83
Then, a user generates a key pair and appends the new key and
the new claim ticket:
[deed needing renewal]
Claim key: [new public key]
Claim ticket: 0146458n00 0b69e8ix83
and then signs it using the new and previous claim key:
[deed needing renewal]
Claim key: [new public key]
Claim ticket: 0146458n00 0b69e8ix83
[ signature using new key ]
[ signature using old key ]
This is sent to admin or admins and the federation of
admins either recognizes the renewal or sends up
red flags (for admins to sort out) about why renewal
should be denied.
TRANSFERS
The transfer of a routing ID uses the same protocol as a
renewal. The new public key and the new key signature
are provided by the party acquiring the routing ID. The
final old key signature is provided by the party relinquishing
the routing ID.
BACKING UP: ADMINS DO WHAT NOW?
In the above I explained claim, renewal and transfer
transactions in overview but left out the hard part: What
exactly do admins do to make that magic happen? The
remaining sections explain that.
THE ADMIN PUBLIC LOGS
Admins within a federation maintain a collective set of "news
feeds" which are publicly broadcast (in any mode that is
convenient). Each admin (identified by his own routing ID)
publishes a log of administrative actions taken at that admin
node.
For example, when a user submits a claim:
[encrypted routing ID claim]
ID: 0a9Lljk28n
Claim ticket: 0146458n00 0a99ke8ij2
[ claim key signature ]
[ seal key signature ]
the admin can append a (conventional) timestamp and his own
signature:
[encrypted routing ID claim]
ID: 0a9Lljk28n
Claim ticket: 0146458n00 0a99ke8ij2
[ claim key signature ]
[ seal key signature ]
Admin posted: <timestamp>
Claim ticket: 0146458n00 0a99ke8ij2
[ admin public key ]
[ admin signature ]
and post that to his public log feeds.
A "federation of admins" is a group of admins who have a means
by which to agree among themselves (and convince others) just
what, "officially", a given admin's log feed contained at a
particular tick of the routing ID timestamp clock. The
timestamp clock ticks almost once in 7 hours and, after every
few ticks, there is widespread and cryptographically
documented consensus within the federation about the contents
of the logs those few ticks before.
RECONCILING (Part 1)
After a user submits a sealed claim to one or more admins, it
gets broadcast as part of the admin logs.
Once the official logs of that period are fixed, the outcome
of claim submissions is deterministic. If a user's claimed ID
is unique among claims, then tentatively accept it. If there
were suprising competing claims, tenatively accept but with a
duplicate request warning. Otherwise, reject the claim.
Anyone who can see a verifiable copy of the logs can be
confident in the status of the user's claim.
RECONCILING (Part 2)
A tenatively accepted user (with or without duplicate request
warnings) replies by revealing the private seal key. This is
forward by the admin(s) to the admin logs of the federation.
After another "settling out period" to reach consensus on the
new contents of the logs, the validity of the private seal key
and of the entire claim can be tested by anyone who cares to
review the logs.
Admins who agree that a successful claim is valid attest, sign
and post such notice to their logs.
RENEWALS AND TRANSFERS
Happen similarly to initial claim reconciliations.
ROUTING TO ROUTING IDs
How exactly routing IDs are used in overlay network routing is
left for later. This is just about the hard-enough-on-its-own
problem of how to allocate from and manage the namespace of
routing ids.
-t
More information about the Freedombox-discuss
mailing list