Naming service specification, version 1.0

Specification of the Naming Service for the I2P Network
Version 1.0
August 8, 2003


Contents
--------
1. Introduction
2. Data structures
3. Message structures
4. Setup of a naming server
5. How clients interact with a naming server
6. How naming servers interact with other naming servers
7. Conclusion and plans for the future

================================================================================


1. Introduction

As currently specified in the I2P Network Specification, communication between
two destinations on the network can occur only if one destination knows how to
contact the other. In other words, the first destination must know the second's
hash of the destination to communicate. This information has to be given to the
first destination before communication can occur. What if the destination is
not known, but a user of the I2P network knows that he or she wants to contact
a certain person and establish an instant messaging session?

The naming service (NS) application, running over the I2P network, solves this
problem. If user X wants to speak with user Y via Instant Messenger, user X's
IM client would look up user Y in a name server (the destination running the
naming service application), and obtain user X's contact information. If user
Y does not have IM capability, the NS would inform user X of this fact. Users
(or entities, rather) who want to simplify being contacted by others would, at
their option, register an entity name with a name server, which others could
use to look them up. Now, instead of having to type in user Y's destination
hash, user X could type in simply "user Y:im" as the destination to connect to.

The naming service, as specified below, has several capabilities. Entities
can register with it, add services they provide to their records, and modify
or delete these records. Records are signed with the entity's public key so
that only the entity establishing the record is able to modify it.

The entity establishing a record is responsible for updating the record if the
record changes. Other entities can search for whether that entity's record
exists, what services it provides, and whether it provides a particular service.


2. Data structures

The messages that clients and naming servers issue are described in sections 4
and 5 of this specification. This section specifies the formats and data types
for data structures used by the naming service software. Named constants that
appear in this section are all integers.

The two main structures the ServerInfo and EntityInfo structure, containing
records for naming servers and the entities who registered with a naming
server, respectively. The structures are as follows. The sizes of the data
members of the structures are those described in the I2P Network Specification.
All time information is specified in the UTC timezone (universal time), and
has the format "Aug 06 2003 01:23:45"--three letters for the month, two for the
day, four for the year, etc.

ServerInfo
   versionNumber - integer indicating the naming service's version
   lastUpdated - the time of last modification
   hashDest - hash of the server's destination
   pubKey - the server's public key

Service
   type - named constant (see below) indicating the type of service
   contact - hash of the destination providing this service for an entity

EntityInfo
   name - the entity's name, a string of 1-32 characters
   pubKey - public key for modifying the record
   lastUpdated - the time of last modification (set by naming service)
   numServices - number of service structures in the list of services
   service[1] - Service structure 1 (for example, for IM service)
   ...
   service[numServices] - last Service structure

The constants for the services recognized by the naming service are the
following. These are used in querying whether an entity provides a given
service. In this version, a query containing numbers other than these is
erroneous, and is discarded. In future versions, higher numbers can be used to
indicate other services over the I2P network.

1 = Instant Messaging (IM)
2 = File Transfer Protocol (FTP)
3 = Internet Relay Chat (IRC)
4 = World Wide Web (WWW)

All the incoming messages to a naming service are called requests, and all
outgoing messages are called responses. The naming service maintains a request
queue for dealing with incoming messages. In this version of the naming service
a simple first-in-first-out queue is used for messages, whatever their source.
The numer of requests handled is configurable. When the naming service starts
operating, it handles x requests at once (the number is read in from a settings
file). When requests arrive, it adds them to the queue before processing them.
The queue grows as necessary until a limit (also configurable) is reached.
After the limit on the number of requests handled is reached, if the queue is
full the server responds to new requests in one of two ways. If it does not
know about any other naming servers, it responds with a ResponseServerBusy
message. Otherwise, it respons with a ResponseUseAnotherServer message (if the
request came from a client), giving the client another server to query. The
formats for these messages are described below.

The naming service also maintains a log file. It does not log queries, but
does log when entity records are added or updated and when it lears about
other naming servers or when those servers update their information. The log
format is "[timestamp] [message]". The timestamp has the format described above
and the message can be one of the following (or can have more detail). The log
file should be named ns_log.txt.

"Entity [x] added"
"Entity [x] information updated"
"Server [x] added"
"Server [x] information updated"

The constants for the message types recognized by the naming service are the
following. The messages, described below, are divided into two categories:
client-server and server-server messages. Also, the messages are categorized as
requests to a server or responses from a server.

0 = Request
1 = Response
2 = RequestAddClient
3 = RequestAddServer
4 = RequestAddService
5 = RequestClientAdded
6 = RequestClientExists
7 = RequestClientUpdated
8 = RequestDeleteService
9 = RequestEntityInformation
10 = RequestModifyService
11 = RequestServerAdded
12 = RequestServerExists
13 = RequestServerInformation
14 = RequestServerUpdated
15 = ResponseAddApproved
16 = ResponseAddPending
17 = ResponseAddRejected
18 = ResponseChangedRecord
19 = ResponseClientDNE
20 = ResponseClientExists
21 = ResponseEntityInformation
22 = ResponseEntityList
23 = ResponseEntityService
24 = ResponseServerBusy
25 = ResponseServerDNE
26 = ResponseServerExists
27 = ResponseServerInformation
28 = ResponseUseAnotherServer


3. Message structures

All of the request and response messages derive from two base classes for
messages, Request and Response. The request messages for querying the naming
service about entities do not have to be signed by the sender, but those for
adding and mofidying records do. All of the response messages are signed by
the originating naming service with its public key. Please note that as far
as the I2P network is concerned, all of the messages below are data in I2P
message payloads.

The list of message structures and their fields follows. All of the Response*
messages derive from the Response message class, and all the Request* messages
derive from the Request message class. Thus, the fields in them are additional
to the fields in the Response and Request message classes/structures. All of
the signature fields in the structures below are signatures of the rest of
the message. For example, the ResponseServerBusy structure contains the field
reason in addition to the fields in the Response structure. They are omitted
because they are redundant.

Request - generic request message, not actually sent to servers
   msgType - type of message, an integer from the list above
   src - hash of the destination of the sender of the request
   time - timestamp of the time when the message was issued; see format above

Response
   msgType - type of message, an integer from the list above
   time - timestamp of the time when the message was issued; see format above
   signature - signature of the rest of the message

RequestAddClient
   signature - signature of the rest of the fields with entity's private key
   name - case-sensitive name of the entity to be added to naming service
   key - public key for the entity

RequestAddServer
   signature - signature of the rest of the fields with server's private key
   key - public key for the server

RequestAddService
   signature - signature of the rest of the fields with the entity's private key
   name - name of the entity for which to act
   service - Service data structure describing the service to add

RequestClientAdded
   signature - signature of the following field with naming server's private key
   info - EntityInfo structure for the entity added

RequestClientExists
   signature - signature of the server making the query, made with private key
   id - random integer identifying this request
   name - name (case-sensitive) of the entity to look up

RequestClientUpdated
   signature - signature of the following field with naming server's private key
   info - updated EntityInfo structure for an entity

RequestDeleteService
   signature - signature of the rest of the fields with the entity's private key
   name - name of the entity for which to act
   service - Service data structure to delete from the entity's record

RequestEntityInformation
   query - string specifying what information is sought; it is case-sensitive

RequestModifyService
   signature - signature of the rest of the fields with the entity's private key
   name - name of the entity for which to act
   service - Service data structure for the service to modify

RequestServerAdded
   dest - hash of the destination to send information to
   key - public key for the new server just added

RequestServerExists
   signature - signature of the server making the query, made with private key
   id - random integer identifying this request
   dest - hash of the destination for the server to look up
   key - public key of the server to look up

RequestServerInformation
   [no additional fields]

RequestServerUpdated
   signature - signature of the following field with naming server's private key
   dest - hash of the new destination for that naming server

ResponseAddApproved
   hash - hash of the destination of the entity or server to add

ResponseAddPending
   hash - hash of the destination of the entity or server to add

ResponseAddRejected
   hash - hash of the destination of the entity or server to add

ResponseChangedRecord
   hash - hash of the destination of the entity or server with changed record

ResponseClientDNE
   id - number of the request for which this is a response

ResponseClientExists
   id - number of the request for which this is a response

ResponseEntityInformation
   info - an EntityInfo data structure with the information for an entity 

ResponseEntityList
   service - type of service requested in the query
   numFound - number of entities found providing a given service; could be zero
   name[1] - name of first entity providing the service
   dest[1] - that entity's destination hash for the service
   ...
   name[numFound] - this list is only returned if 1 or more entities were found
   dest[numFound]

ResponseEntityService
   name - name of the entity for which the request was made
   service - service type in the request
   dest - hash of the destination to contact for that service

ResponseServerBusy
   reason - string explaining why server cannot fulfill a request

ResponseServerDNE
   id - number of the request for which this is a response

ResponseServerExists
   id - number of the request for which this is a response

ResponseServerInformation
   info - a ServerInfo data structure with information for the naming server

ResponseUseAnotherServer
   dest - hash of that server's destination
   key - public key for that server


4. Setup of a naming server

A naming server is the destination to which clients (and other naming servers)
connect. The naming service is the software application running on that server.
The software processes and responds to requests from clients and other servers.
Naturally, the software needs to perform setup before it can process requests.

The first part of the setup is to establish a destination and publish its lease
on the I2P network. Assuming the naming service operator also administers an
I2P router, the router needs to be set up first. Then, the naming service
software, which is really a type of I2P client, sets up a destination and
publishes a destination lease with the router. After this step, the naming
server can be connected to. It sends and receives data using the format given
in the I2P network specification.

The second part of the setup is reading in settings from a file. The file will
be named ns_prefs.txt, and will contain settings of the form "name=value", one
setting per line. Comments (beginning with "#") and blank lines will be ignored.
The naming service application will load the settings whenever it is run. This
file should be protected from viewing by the public; it should not be world
readable. A sample file appears below.

privateKey=
publicKey=
minRequests=10
maxRequests=50
logFile=filename      # Location of the file to log service's actitities to.
peer=0123456789abcdef # Sample hash of another name server's destination.
key=12983740          # Sample public key of the name server above.
peer=fedcba9876543210
key = qwepioruq

The file contains the private key and the public key values as the first two
entries. If the entries are blank, as in this sample, the public/private key
pair should be generated and written to the file. The next two settings control
the size of the request queue. The minRequests setting's value controls the
size of the queue when the server starts, and maxRequests controls the maximum
size of the queue (see the queue's description in section 2). The log file's
location on the hard drive is the next setting. The settings after that are the
list of naming servers this naming server knows about; their destinations'
hashes and public keys are added to the settings file as this naming server
learns about other naming servers on the I2P network.

After reading the settings and generating the public and private keys (if
necessary), the naming service application awaits requests to process from
clients or other naming service applications on the I2P network. Please note
that this keypair is separate from the public key of the destination on the I2P
network where the service runs. The destination can change its lease or obtain
a new one, but the service can persist and be identified by the combination of
its destination and public key.

When sending responses to requests from clients or other naming servers, the
naming service software will sign all messages. This is to prevent forging
entries from that server and to prevent man-in-the-middle attacks. When
receiving messages with signatures in them, the service will always check
signatures and discard messages whose signatures do not validate.


5. How clients interact with a naming server

Clients contact naming servers for two purposes, generally speaking. These
purposes are to add or update an entity record to the naming service or to
obtain information about another entity. But first, they may wish to obtain
a naming server's public key, to check other messages from it for validity.
This is done with a RequestServerInformation message. The response is either a
ResponseServerInformation message or a ResponseServerBusy message, in which
case the client will have to try again.

To request information about another entity, the client will send a message of
the type RequestEntityInformation. It will send a query as part of that
message consisting of two fields, separated by a colon. The first part is the
entity name to look up information for; the second is the service(s) to
search for. For example, "userx:www" is a valid query; so is "*:irc", which
asks for all entities providing the irc service; "userx:*" asks for all
information available on userx. Clients are not allowed to make the "*:*"
query, and it will be discarded.

The server's response varies, depending on the query issued to it and on the
number of queries it is processing. If its local router has detected abuse,
it will respond with a ResponseServerBusy message. Otherwise, if its queue of
requests is full, it will respond with a ResponseUseAnotherServer message,
giving the server information for another server to query. If the query is
of the type "user:*", it will return a ResponseEntityInformation message, with
all the information for that entity. If the query is of the type "userx:www",
it will return a ResponseEntityService message, containing the information for
only that entity and service. For the "*:irc" type of query, the message
returned is ResponseEntityList, with a list of destination hashes for IRC
providers. These responses can contain empty lists and empty information data
structures if nothing was found.

The other task that clients can perform is to register themselves with a naming
service, and update that information by adding or modifying their records. To
begin registration, a client will send a RequestAddClient message. This message
will contain the entity name to add, the client's public key and hash of
destination, and will be signed by the client's private key. The server will
respond with a ResponseAddPending message to the client, or ResponseServerBusy
if it is under attack. It will then synchronize with other servers, as the next
section describes, and will determine whether the entity name has already been
registered. If it has not, the client will receive a ResponseAddApproved message
from the service shortly after making the request. After that, the entity name
has been registered. The ResponseAddRejected message indicates that the entity
name already has been registered by someone else.

After registering, the client can add, delete, or mofidy services in its record
with the naming service. The messages to do so can be sent to any naming server
since servers propagate updates to the record. The messages are, respectively,
RequestAddService, RequestModifyService, and RequestDeleteService. The messages
will contain the entity name for which to perform these operations, and will
be signed by the entity's private key. The service must validate the requests,
and perform no actions if the signature does not verify using the entity's
public key.


6. How naming servers interact with other naming servers

The naming service application running on any given naming server cannot serve
the requests of all possible clients. That is why it interacts with other naming
service applications running on other naming servers. It is, in essence, a
distributed application. So naming servers need to interact with each other,
and they do so by sending messages to each other. The cases in which naming
servers need to send messages are when a naming server joins the network of
naming servers, when its information (destination and in later versions possibly
the public key) changes, when an entity is registered with a naming server, and
when an entity's information is updated. In the network of naming servers, each
naming server knows about all the other naming servers.

When a naming server wants to join the network, it will need to know the hash
of the destination for one of the servers already in the network. It first
needs to obtain the server's public key, by sending a RequestServerInformation
message. The response is either a ResponseServerInformation message or a
ResponseServerBusy message, in which case the server will have to try again at
another time. After obtaining the public key of the server to which it will
make the request to join the network, the new server sends a RequestAddServer
message, with its hash of the destination and public key, signed by its private
key. The server then broadcasts a RequestServerExists query to every other
server on the list. It waits for a reasonable amount of time, and if some of
the servers do not respond, it assumes the entry does not exist on their lists.
The other servers respond with ResponseServerExists if the server is in their
lists, and ResponseServerDNE if not. If any of the other servers responds with
a ResponseServerExists message, the new server is sent a ResponseAddRejected
message indicating it will not be added. Otherwise, after receiving the other
servers' responses, it responds to the new server with a ResponseAddApproved
message. Each RequestServerExists message has a unique ID number, so that the
server can discard response messages with that ID number if it rejects the
addition of the new server.
 
After the new server is added, it needs to be integrated into the network of
naming servers. The server that approved the addition then broadcasts to every
server in the network a RequestServerAdded message, indicating the server whose
list of servers needs to be populated. Every server then sends its own
information in a ResponseServerInformation message to the new server, which
builds a list of servers from these messages. The new server now needs to obtain
the data about entities that it will send to clients. It picks a random server
and sends it a RequestEntityInformation with a query of "*:*". That server then
sends it a number of ResponseEntityInformation messages for every registered
entity it knows about. The new server receives this information, and after it
receives all these messages it knows about every entity. It can now serve
client requests.

The new server in the network can give its information to entities to use it
as their naming server. It can also rely on eventually being contacted. When one
of the other naming servers sends a ResponseUseAnotherServer message, it now
has a chance of being the server clients are told to contact, and it will
process the clients' requests.

When an entity attempts to register itself with the network of naming servers,
the process is similar to that of a server joining the network. The entity
sends a RequestAddClient message, and the naming server responds with a
ResponseAddPending message. It then broadcasts a RequestClientExists query to
the other naming servers. Similarly to the description above, it will respond
to the entity with a ResponseAddRejected (if any other naming server responds
with a ResponseClientExists message) or ResponseAddApproved (if all the other
servers respond with a ResponseClientDNE message). After the addition of the
entity is approved, the server that approved the addition broadcasts a
RequestClientAdded message with the entity's information. The other servers do
not respond to this message, but add the entity to their lists of entities.

When an entity wishes to add, modify, or delete a service in the list of
services it provides, it sends an appropriate message to the naming service. If
the naming service responds with a ResponseUseAnotherServer message or with a
ResponseServerBusy message, the client should try again. If it receives no
response, then its signature was wrong, and the message was discarded. When a
change in the record is successful, the naming service does two things. First,
it replies to the entity/client with a ResponseChangedRecord message. Second,
it broadcasts a RequestClientUpdated message to the other servers with the
changed record. They do not respond, but change their records for that entity.

Finally, if a naming service has had its naming server under attack for some
time, it may wish to change its destination to avoid future attacks. In this
case, it will need to broadcast a RequestServerUpdated message to the other
servers, signed with its private key. The servers should each respond with a
ResponseChangedRecord message after processing the update.


7. Conclusion and plans for the future

This version omits certain suggestions that have been made on this mailing list
and in IIP discussions. These ideas will likely be incorporated in future
versions of the naming service. One idea is using a Resource Description
Framework (see http://www.w3.org/RDF) together with the naming service. As I
am not familiar with RDF at this time, I have not included it in this
specification. Another idea is having Certificate Authorities (CAs) that sign
entity entries when entities are registered with naming servers. A possible
implementation of this idea is to have trusted naming servers that other
naming servers connect to; these servers handle entity additions and sign
entity entries. This idea is omitted for now, so as not to complicate the
design at this stage. Yet another idea I have been given is to have clients
pay with HashCash for using the naming servers. It may make sense to add this
capability at a later stage, though I think that free naming servers will make
users of the I2P network not want to use the ones where payment is required.
Finally (although this is my own suggestion), perhaps name servers should
periodically check that other servers are still operating (ping them somehow)
to detect a name server that is no longer in service.

If this document contains any errors, unclear wording, or omissions, please
let me know. I also welcome your suggestion for improving the naming service
described in this specification. I will correct the errors in version 1.1 of
this specification. My plan is to make the corrections, publish version 1.1 of
the naming service specification, then implement the naming service software.
If this specification needs to be revised again (with version 1.2) before it
can be implemented, then I will do so. The naming service capabilities described
in the sections of this document above will be coded first, then the
capabilities in the paragraph above will be gradually added.