\documentstyle[listing,fullpage,11pt]{report}

\def\tm{$^{\mbox{\footnotesize TM}}$}

\addtolength{\topmargin}{0.25in}
\addtolength{\oddsidemargin}{0.25in}
\addtolength{\evensidemargin}{0.25in}
\addtolength{\textheight}{-0.25in}
\addtolength{\textwidth}{-0.5in}

\parindent=0in
\parskip=\baselineskip

\author{Marc Horowitz}
\title{A PGP Public Key Server}

\begin{document}
\maketitle

\begin{abstract}

Existing key servers for Pretty Good Privacy\tm{} (PGP) use the PGP
program for key management.  PGP was not designed to handle large
keyrings, and as a result, performance of the existing key server
suffers badly.  In this paper, I describe the specification and design
of a new key server which does not depend on PGP for any of its
functions.  This new key server is a ``drop-in'' replacement for the
old key server, providing almost all of the same functionality via
both the e-mail and HTTP interfaces, with much improved performance.
Early testing of this server under simulated production conditions
demonstrates a performance increase of about two orders of magnitude
compared to the old server.  This increase is directly attributable to
storing the key database in hash tables and balanced trees instead of
a PGP format keyring.
\end{abstract}

\tableofcontents

\chapter{Background}
\section{PGP and the web of trust}

PGP, short for Pretty Good Privacy, is a widely used program for
performing public key authentication and encryption functions.  Unlike
most similar systems, which establish trust in terms of strict
certification hierarchies, PGP uses a concept known as a ``web of
trust'', in which any party can certify the identity of any other
party (in PGP parlance, ``sign their key'').  A signature on a key or
document can be trusted if, and only if, there is a path of signatures
between the verifier's key and the key used to make the signature in
question.  The number, shortness, and quality of such paths determine
how well the key, and therefore the signature, can be trusted.

While most public key heirarchies are based on formal, sometimes
legally binding notions of identity, the web of trust has no such
restrictions. This generality is part of what makes PGP popular.  PGP
keys exist for individuals, groups, organizations, network services,
and even pseudonyms and anonymous addresses.  Unfortunately, this
generality has its cost.  It is not always possible to verify a
signature made by an arbitrary key, or even to find the key.  Although
it is possible to advertise a key via traditional Internet mechanisms
such as {\tt .plan} files and World Wide Web home pages, this is not
always practical, since the key space does not map cleanly onto
traditional Internet naming.  There is no appropriate place for a
pseudonym operated through an anonymous remailer, for example.

\section{Key servers today}

To solve this problem, repositories of PGP public keys have been
established.  These PGP public key servers allow anyone to submit any
public keys and signatures, and to query this database.  The first
public key server was a simple email server which used the PGP program
to provide basic PGP functionality on a centrally stored keyring.
This server evolved and added features, including more advanced
searching and incremental updates between servers.  Interactive World
Wide Web interfaces followed.

However, all these systems have a substantial problem.  Today's key
servers manage over twenty thousand public keys, including over 28,000
associated signatures.  The PGP implementation was not designed to
manage extremely large databases of keys such as this.  As a result,
key server performance suffers badly.  Merging a large keyring into a
public key server database takes hours or even days.  The most common
operations takes between thirty and sixty seconds using the old
PGP-based key server.

\chapter{A new key server}

A new key server would solve many of the problems of the
first-generation key server.  Any new design should strive to meet the
following general requirements:
\begin{description}
\item[Compatibility] The server should behave like the existing
servers from the user's point of view.  Especially, no functionality
should be lost.
\item[Administration] Building and installing the server should be
simple.  Special privileges on the server should not be required for
day-to-day maintenance.
\item[Performance] Queries of all sorts should take a reasonable
amount of time to complete.
\item[Access] The server should be accessible via email and the World
Wide Web.  It should be able to create files for access by ftp.
\end{description}

\section{Functional specifications}

Since the old server uses the PGP program for keyring maintenance, the
old server's commands can be described in terms of the PGP commands
which are used to implement them.  This generates familiar output,
which is useful, but the keyring search and modify algorithms are
quite inefficient.  The functional specifications are intended to
describe a system with behavior similar to that of the old system,
with a few restrictions which allow for a more efficient
implementation.

\subsection{Searching}
\label{spec:searching}

The most user-visible change is that searches are no longer simple
string or regular expression matches against the user ID, because this
makes it impossible to search efficiently.  Instead, each user ID and
each search is divided up into ``words'', where a ``word'' is defined
as a run of consecutive alphanumeric characters of length greater than
one.  For a given search, all keys with a user ID which contains all
the words in the search are returned.  This means that searches for
part of a word, which would have succeeded before, will fail now, but
these kind of searches are very rare.\footnote{A week's worth of
statistics taken in early October, 1995, from the mail and HTTP
servers running on {\tt pgp.ai.mit.edu} indicate that this change will
only result in a difference in behavior for a very small number of
requests (less than 1 in 1000).} Optionally, the list of user ID's
returned can be limited to those which contain the search string
exactly, not just the words which make up the search string.  All
searches are case-insensitive.  Searches by key ID will remain
unchanged.

\subsection{Mail server}

The mail server accepts requests submitted via email, and delivers
replies to the originator of the message.  The subject header of the
message contains a command, and the body of the message contains data
if the command requires it.

\begin{description}
\item[{\tt ADD}] This command adds or updates keys in the key
database.  The body of the message should contain a keyring in
ASCII-armor format to be merged into the database.
\end{description}

The next three commands search in the key database for {\tt userid} as
described in section \ref{spec:searching} and email a response back to
the user based on the keys which match.  The option for exact matching
is used so that the new server behaves more like the old server.

\begin{description}
\item[{\tt INDEX userid}] The response is equivalent to that outputted
by {\tt pgp~-kv} on the matching keys.
\item[{\tt VERBOSE INDEX userid}] The response is equivalent to that
outputted by {\tt pgp~-kvv} on the matching keys.
\item[{\tt GET userid}] The response is equivalent to that outputted
by {\tt pgp~-kxa} on the matching keys.

%% The next three commands email a response back to the user based on the
%% entire key database.  In order to avoid iterating over the entire
%% database, the answer may be cached and therefore not completely
%% current.
%% \item[{\tt INDEX}] The response is equivalent to that outputted
%% by {\tt pgp~-kv} on the entire database.
%% \item[{\tt VERBOSE INDEX}] The response is equivalent to
%% that outputted by {\tt pgp~-kvv} on the entire database.
%% \item[{\tt GET}] The response is the entire database in keyring
%% format, uuencoded for transmission, and possibly split into multiple
%% messages.

\item[{\tt LAST num}] This command is like {\tt GET}, except that keys
which have been added or changed in the last {\tt num} days are
returned.
\end{description}

The {\tt MGET} command is no longer supported.  In a week's worth of
mail server logs, this command was only used 28 times, and all but
four of these were constant strings, which means that MGET had no
special effect.  Those which were not constant strings only used the
alternation (``{\tt |}'') regular expression operator.  In other
words, all of these queries could have been made with a few separate
GET requests.

\subsection{HTTP server}
\label{spec:web}

The new HTTP server accepts the same query parameters as the old HTTP
server; however, the semantics are slightly different, as described
here.  Two URI's should be implemented.

The first URI, {\tt /pks/lookup}, is for performing searches.  It
understands four different properties in its property list.  The {\tt
op} property can have three values.  If this value is {\tt index} or
{\tt vindex}, then the returned page is equivalent to that outputted
by {\tt pgp~-kv} or {\tt pgp~-kvv}, respectively, on the keys matched
by the value of the {\tt search} property, as described in section
\ref{spec:searching}.  In addition, if the {\tt fingerprint} property
has the value {\tt on}, then output is equivalent to that outputted by
{\tt pgp~-kvc} or {\tt pgp~-kvcv}, respectively.  If the {\tt op}
property has the value {\tt get}, then the returned page is equivalent
to that outputted by {\tt pgp~-kxa} on the keys matched by the value
of the {\tt search} property.  If the {\tt exact} property has the
value {\tt on}, then the search is restricted to exact matches as
described in section \ref{spec:searching}.

The second URI, {\tt /pks/add}, is for adding or changing keys in the
database.  It understands one property.  The {\tt keytext} property
contains the ASCII-armored PGP keyring to be merged into the database.

For an example of an HTML page which includes forms for making the
above queries, see Appendix \ref{commandhtml}.

\subsection{Replication}

It is desirable to have multiple key servers for performance and
reliability.  In order to avoid the latency associated with the slower
lines between countries and continents, key servers have been
established all over the world.  Some organizations separated from the
Internet by a firewall or a slow connection run their own key servers.
If the nearest server to a user becomes temporarily unavailable, the
user can use another key server to look up keys.

In order to have multiple key servers provide access to the same keys,
either users must send updates to all key servers, or the key servers
must share updates among themselves.  Since it is not reasonable to
expect users to know all the key servers which exist and are
operational, an incremental mechanism is available to propagate
updates between servers.  A user needs to send updates to just one
server, and the update will be spread to all the other key servers.

Each key server keeps a list of other key servers with which it shares
updates.  Whenever a key is added or changed by a user or by an
incremental from another key server, this change is propagated to all
the key servers in this list.  To keep the message from propagating
forever, each key server adds a header to the message to indicate that
it has seen the update, and should not be sent it again.  Incrementals
are implemented using one additional command in the mail server.
Users should never need to use this command.

\begin{description}
\item[{\tt INCREMENTAL}] This command is intended for inter-server
communication. It functions identically to {\tt ADD}, except that the
mail headers will be parsed for headers of the form {\tt
X-Keyserver-Sent:~email-address}.  The servers whose email addresses
are listed will be assumed to have seen the record already, and will
not be sent additional copies.  When a server sends an {\tt
INCREMENTAL} to another server, it should list all the servers which
were named when it received the message, and add itself.
\end{description}

\section{Architecture}

\subsection{Overview}

The design of the several programs which make up the new key server is
complicated by the very different access methods of email and HTTP.
Mail is by nature batched and non-interactive.  A mail request should
be relatively immune to system failures, network failures, etc.  HTTP
requests are by nature interactive.  If the host or network goes down,
it is acceptable to terminate the transaction in progress.

Unfortunately, the traditional means of handling batch and interactive
requests in a unix\tm{} environment are very different.  Batch requests
are usually accumulated in a queue, and the queue is run periodically.
Interactive requests usually result in a new process which handles the
request, then exits.  Multithreaded servers exist which use one thread
per interactive request instead of one process, but the principle is
the same.

The server must also deal with shared (read) and exclusive (write)
locks on the database.  Since none of the freely available database
libraries provide record locking facilities, the system must insure
that while the database is being updated, no other accesses are made
to the database, or corruption may occur.

Two solutions seem possible.  The first, more traditional system would
use several different programs to handle different kinds of access.
Whenever mail is received for the mail server, a short program would
insert the request in a queue.  Periodically, a program would run to
handle all the jobs in the queue.  A second program would run out of
inetd or as a CGI script run by a HTTP server to process HTTP
requests.  These latter two programs would both access the database
files directly to perform queries and updates, and perform locking
between them.  This is the approach which is used by existing key
servers.

The second, more sophisticated solution involves a more complex server
which is persistent and handles multiple mail and HTTP requests at the
same time, via a threaded or event-driven architecture.

My experience with network servers has shown that the first solution
is simpler and easier to implement, but suffers from reduced
performance.  Mail server users are at a disadvantage, since their
requests are not processed immediately upon receipt.  The potential
exists for many processes to be running at the same time, since there
would be one process for each concurrent HTTP request\footnote{This is
not a problem now, since the servers are only receiving about 350 HTTP
requests a day, but it is worth considering.}.  Since each request
starts a new process, caching information to make future queries
faster is difficult.

The second solution is harder to implement correctly, but is more
scalable.  Because resource consumption does not increase linearly
with the number of requests, many more requests can be handled.  No
interprocess locking is needed, because only one process will ever be
manipulating the database.  Also, the server can cache frequently-used
information to increase performance.  Since this solution has more
advantages (and is more interesting), I have used this approach.

\subsection{Database format}

The Berkeley db database library is used for all the databases.  This
library is freely available and portable, and is more versatile than
the dbm libraries which most vendors ship with their operating
systems.  In particular, it allows arbitrary sized keys and data, and
supports balanced trees in addition to hash tables.

The primary database is a hash table which indexes PGP key IDs into
PGP keys.  The key is a 32-bit integer corresponding to the key ID.
As used here, the key ID is the 32-bit ID which is used by the PGP
user interface, not the 64-bit ID which is used by the internal
structures.  The data is in the same format as a PGP keyring,
containing the public key for all keys with that key ID, and all
associated user ID's, signatures, and revocations.

Two secondary indexes into the primary database are kept.  The first
index is a hash table containing words as keys and a list of PGP key
IDs and key creation times as values.  The creation time is used to
disambiguate different keys with the same key ID.  This index is used
to to implement searches over the database as described in section
\ref{spec:searching}.  The list in the data of each entry in this
database is sorted by key creation time, with the most recent time
first.

The second index is a balanced tree containing times as keys and PGP
key IDs and creation times as values.  The value of each entry in the
database describes all the keys which were added or changed at the
time represented by the key.  This index is used to generate lists of
keys based on recency, such as a keyring consisting of all keys
changed in the last day.

Since all the information in the secondary indices is derived from
information in the primary database, if the secondary databases are
damaged or somehow become out of sync, they can be destroyed and
recreated.

\subsection{Main server}

The main server consists of four major parts.  The first part is the
multiplexor, which handles most of the input and output for the
server.  It deals with the multiple input and output streams of the
server, and ensures that no I/O request ever blocks.

The second part of the server is the database engine.  It manages the
underlying database which stores all the PGP keys, and the various
indexes which enable efficient searching.

The third part is the HTTP server.  This part receives HTTP requests
read from the client by the multiplexor, and converts them into calls
to the database engine.  The database engine's response is converted
into a HTTP reply, which is delivered to the client by the
multiplexor.

The last part is the unix domain socket server.  This is a more
controlled mechanism than HTTP for submitting commands to the key
server.  The most important task of this part is to handle email
messages.  Mail requests are parsed and converted into calls to the
database engine.  The database engine's response is converted into a
mail reply, which is delivered to a mail delivery agent by the
multiplexor.

\subsubsection{Multiplexor}

To support multiple input sources and output sinks, some sort of
multiplexing is necessary.  The server implements multiplexing with a
queue of inputs (file descriptors opened for reading) and a queue of
outputs (file descriptors opened for writing).  Using the select()
system call, the server can determine which members of the input queue
can be read without blocking, and which members of the output queue
can be written without blocking.

When new data is available for any of the input file descriptors, it
is passed to a function which processes the data.  When a full request
has been read, this function handles the request, creates a reply, and
queues it for output.  When any of the output file descriptors becomes
writeable, as much data as possible is written to it.  When all the
data which has been queued is written, a function is called to clean
up from the request, freeing memory or other resources.  The
multiplexor also handles errors, timeouts, and other exception
conditions.

The architecture of the server would be much simpler (this component
would be basically unnecessary) if multiple threads of execution were
used, but since threads are not widely available, using them is not a
good idea at this time.  The implementation uses abstractions which
should permit the event-driven architecture to be replaced with a
threaded architecture when a robust thread implementation is
available.  The logic of the server would still be event-based, but it
would then be possible to perform multiple computational tasks, such
as database searches, at the same time.

\subsubsection{Database engine}

The database engine manages all of the data in the PGP key server.  It
implements a small number of high-level operations on the database.
Functions implementing these operations are called by the mail and
HTTP servers.

Functions are provided to 
\begin{itemize}
\item Add a key to the database.
\item Extract an index based on a key ID or user ID.  The format of
the index will be the same as that generated by the PGP keyring view
functions.  The exact command equivalent will be determined by flags
to the function:

\begin{tabular}{|l|l|l|} \hline
verbose format?	& include fingerprint?	& PGP command equivalent \\ \hline
no		& no			& {\tt pgp~-kv} \\
yes		& no			& {\tt pgp~-kvv} \\
no		& yes			& {\tt pgp~-kvc} \\
yes		& yes			& {\tt pgp~-kvcv} \\ \hline
\end{tabular}

\item Extract keys based on key ID or user ID.
\item Extract keys added to the database since a given time.
\item Delete keys based on key ID or user ID.
\end{itemize}

Functions are also provided to create an empty database, open and
close the database, and write cached elements of the database to disk.

The functions which operate on a key ID or user ID accept a search
string.  If the string begins with {\tt 0x}, then the string will be
interpreted as a hexadecimal key ID.  Otherwise, the string will be
interpreted as a user ID search string as described in section
\ref{spec:searching}.  The functions which accept keys can be passed a
binary file, in the format PGP uses for keyring files, or an
ASCII-armored PGP key block, as produced by {\tt pgp~-kxa}.  Functions
which return keys return an ASCII-armored PGP key block.  When more
than one key or index entry is returned, the keys referred to are
sorted by time, with the most recently created keys first.  This
behavior differs from PGP, which lists the keys most recently added to
a keyring first.

\subsubsection{HTTP server}

The HTTP server listens for connections on a TCP port.  As connections
are accepted and data is passed in from the multiplexor, the server
interprets the data as HTTP requests.  The URI, query string, and body
from each request are parsed and converted to arguments for the
database engine.  The database engine performs the actual query, and
returns a textual reply.  This reply is marked up with HTML, and HTTP
headers are added.  The result is passed to the multiplexing code for
transmission back to the client.

\subsubsection{Unix domain socket server}

In order to provide a mechanism for controlling the running server,
the server listens for connections on a unix domain
socket.\footnote{Unix domain sockets are a mechanism for stream-based
IPC in unix.}

When a connection is received on the socket, lines containing commands
for the key server are read and parsed.  The first word of the line
describes the type of request.  The most frequently used type of
request is a mail request, indicated by the word {\tt mail}.  The rest
of the line gives a filename which contains a mail message for the PGP
mail server.  This file is opened and the headers are parsed to
construct a query for the database engine, and reply information for
the mail reply.  The database engine performs the actual query, and
returns a textual reply.  A short descriptive message is prepended to
the reply, and MIME headers are added for structure.  Finally, a mail
transfer agent (usually sendmail) is executed as a child process, and
the reply mail message is passed to the multiplexing code for output
to the mailer.  Once the output is complete, the input mail request
file is deleted.  If there is any error, the file is left in place so
an administrator can examine it.

The only other type of request is indicated by the word {\tt backup}.
This request causes the server to write any cached information to
disk, and make a copy of the database files.  This can be run
periodically to protect against catastrophic failures.

\chapter{Conclusions}

\section{Performance}

The new server was tested in a beta production environment for about
one week.  During this time, it has received about 32 mail requests
per day and 220 web requests per day on average.  Almost all of the
mail requests were add or incremental requests.  Of the HTTP requests,
6\% were add requests, 33\% were get requests, and 61\% were index or
vindex requests.  The requests to this server came from volunteers who
heard about the test server from announcements to mailing lists or
word-of-mouth.

During a one week sample period, the old server received about 97 mail
requests a day and 358 HTTP requests per day on average.  Of the mail
requests, 83\% were add or incremental requests, 14\% were get
requests, and the remaining 3\% were index or last requests.  Of the
HTTP requests, 8\% were add requests, 35\% were get requests, and 57\%
were index or vindex requests.

The new server's load in testing was almost half the old server's load
in production, with ratios of add requests, get requests, and index
requests about the same.  This makes the new server's statistics a
good basis for comparison to the old server's statistics.  The most
interesting basis for comparison of the two servers is performance.
Although there is no timing information available for the old HTTP
server, there is timing information available for the old mail server,
and since the database operations were performed by the same PGP
program, it is reasonable to assume that similar HTTP and mail queries
take about the same amount of time.  Figure \ref{timings} shows
average and median times for the old and new servers for different
kinds of requests.  For all kinds of requests, the new server is about
two orders of magnitude faster than the old server.

\begin{figure}
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|} \cline{2-7}
\multicolumn{1}{l|}{} & \multicolumn{2}{c|}{add} & \multicolumn{2}{c|}{get} &
\multicolumn{2}{c|}{index} \\
\multicolumn{1}{l|}{} &
average & median & average & median & average & median \\ \hline
old server & 169 & 183 & 38 & 15 & 53 & 29 \\ \hline
new server & 2.3 & 2 & 0.5 & $\dagger$ & 0.3 & $\dagger$ \\ \hline
\end{tabular}
\end{center}

{\small $^{\dagger}$ The median of get and index requests against the
new server was zero seconds, which is an artifact of the one second
granularity of the timing samples.  This indicates that most of the
requests took less than one second to process.}
\caption{Average and Median request times for the old and new PGP key
servers, in seconds.}
\label{timings}
\end{figure}

As the key database grows, this performance difference can be expected
to increase.  The PGP keyring format and search algorithms require
that all operations scan the database linearly until matches are
found, resulting in operations which are $O($number of keys$)$.  The
new key server database format allows all operations to be more
efficient.  Operations by key ID require only a single hash table
lookup, which is $O(1)$ in the number of keys in the database.
Operations by user ID, which include add and delete, are currently
$O($number of keys containing the words in the user ID$)$.  This can
be extremely small if searches are chosen carefully.  Even if
inefficient searches are used, both the order of the operation and the
associated constant factor are smaller in the new key server than the
old server.

The most common words appear in user ID's of about one third of all
the keys.  For each key with a user ID containinf a word, the new
server must read and process about 12 bytes, compared to the old
server, which must read and process about 400 bytes.  Multiplying
these two numbers together gives a constant factor for the new server
which is about 0.01 the constant factor of the old server.  This
factor corresponds to the two orders of magnitude observed performance
difference between the two servers. 

It is reasonable to expect the viable lifetime of the new server to
continue until the performance drops to the performance levels of the
old server today.  Based on the observations above, I would expect the
old key server's performance at twenty thousand keys to equal the new
key server's performance at about two million keys.  This is a
conservative estimate not accounting for other increases in
performance, due to faster hardware or other changes.  Due to the
extra overhead of the database formats and the extra indices, the new
key server does use about twice as much disk space as the old server.
This proportion should remain constant.

The increases in performance are a direct result of structuring the
database for efficient access to the common operations, rather than
simplicity of management as with the PGP implementation.  Of all the
aspects of the design, this is the single most important.  As long as
the PGP keyring format remains the same, efficient operation on large
keyrings will be impossible.

\section{Future Work}

The next level of performance increases can easily be obtained by
moving to a relational database model.  Well-designed relational
databases can perform the operations which are currently $O(n)$ in
$O(\log n)$ or $O(1)$ time.  With a database engine based on a good
relational database, the key server could be viable for any
conceivable number of keys.  With a relational database, it might also
become reasonable to store an index of word fragments to allow
efficient searches by parts of words.

As more people use PGP, the key servers will receive more requests,
and these requests will return more data.  The current key server
design multiplexes I/O with select(), but handles database requests
serially.  A single long request will cause all other requests to
block until the long request completes.  Replacing the event-driven
model with a threaded execution model will allow multiple database
requests to proceed in parallel, reducing the apparent latency when
the server load increases.  This change will require locking inside
the server in the form of mutexes, since the underlying database is
neither thread-safe nor does it support transactions.

Another useful change will come in the next version of the berkeley db
library, when transactions are supported.  Transaction support will
enable the server to recover from system crashes and other failures
which require a recovery from backup in the current design.  Using
transactions for operations requiring multiple database accesses will
prevent the secondary indexes from becoming inaccurate with respect to
the primary key database.

Finally, there are a number of issues in the key server which are
related to PGP itself.  PGP allows a key to have multiple user ID's
associated with it.  One of these keys is the primary user ID, which
is treated as a special case by PGP.  This special case adds
substantial complexity to the key server merge functions, as shown in
Appendix \ref{pseudocode}.  If PGP did not make this user ID special,
the server could be substantially simplified.  The other problem with
PGP which the key server implementation must address is the
non-uniqueness of key ID's.  PGP uses the least significant 64 bits of
the modulus as the key ID of a public key.  When a key is referred to,
such as in a signature, this key ID is what is stored.  There is
enough uniqueness in 63 bits (the least bit is always one) to have a
reasonable expectation that there will never be collisions.  However,
the user interface of PGP only exposes the least significant 32 bits
of the key ID.  The expectation of collisions is high enough at the
end of the expected life of the key server that it is prudent to have
code which can handle potential collisions.  There seems to be little
reason for PGP to make less than the entire key ID visible to the
user, since the potential collision problems seem to outweigh the
small inconvenience of larger key ID's.

\appendix

\chapter{Details of the database engine}
\label{pseudocode}

This appendix describes in pseudocode how the basic operations (add,
get, index, delete, since) of the key server are implemented.  The
code itself is more complex, since it has to deal with error checking
and the general overhead of C memory management.

\begin{tabbing}
\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\kill
add(keyring) ::= \\
\>	for key in keyring \\
\>	\>	dbkey = read-entry(key-db, keyid(key)) \\
\>	\>	if found then (key, newkeys) = merge-keys(dbkey, key) \\
\>	\>	write-entry(key-db, keyid(key), key) \\
\>	\>	for word in userids(key) \\
\>	\>	\>	keyid-list = read-entry(word-db, word) \\
\>	\>	\>	add-to-list(keyid-list, keyid(key)) \\
\>	\>	\>	write-entry(word-db, word, keyid-list) \\
\>	\>	end \\
\>	\>	write-entry(time-db, now, keyid(key)) \\
\>	\>	allnewkeys = allnewkeys + newkeys \\
\>	end \\
\>	return(allnewkeys) \\
\\
delete(keyid) ::= \\
\>	keyid-list = search(userid) \\
\>	for keyid in keyid-list \\
\>	\>	key = read-entry(key-db, keyid(key)) \\
\>	\>	for word in userids(key) \\
\>	\>	\>	keyid-list = read-entry(word-db, word) \\
\>	\>	\>	delete-from-list(keyid-list, keyid(key)) \\
\>	\>	\>	write-entry(word-db, word, keyid-list) \\
\>	\>	end \\
\>	\>	delete-entry(key-db, keyid(key)) \\
\>	end \\
\\
get(userid) ::= \\
\>	keyid-list = search(userid) \\
\>	for keyid in keyid-list \\
\>	\>	keyring = keyring + read-entry(key-db, keyid) \\
\>	end \\
\>	return(ascii-armor(keyring)) \\
\\
index(userid,verbose,fingerprint) ::= \\
\>	keyid-list = search(userid) \\
\>	for keyid in keyid-list \\
\>	\>	keyring = keyring + read-entry(key-db, keyid) \\
\>	end \\
\>	return(index(keyring,verbose,fingerprint)) \\
\\
since(time) ::= \\
\>	keyid-list = read-range(time-db, from time to end) \\
\>	for keyid in keyid-list \\
\>	\>	keyring = keyring + read-entry(key-db, keyid) \\
\>	end \\
\>	return(ascii-armor(keyring))
\end{tabbing}

The above pseudocode uses a few functions whose implementation is not
trivial.  These are defined here.

\begin{tabbing}
\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\kill
merge-keys(key1, key2) ::= \\
\>	output-key.modulus = key2.modulus \\
\>	output-key.exponent = key2.exponent \\
\>	if key1.primary-userid.name eq key2.primary-userid.name then \\
\>	\>	output-key.primary-userid.name = key2.primary-userid.name \\
\>	\>	output-key.primary-userid.sigs = \\
\>	\>	\>	merge-sigs(\=key1.primary-userid.sigs \\
\>	\>	\>	           \>key2.primary-userid.sigs) \\
\>	\>	output-key.secondary-userid-list =  \\
\>	\>	\>	merge-userids(\=key1.secondary-userid-list, \\
\>	\>	\>	              \>key2.secondary-userid-list) \\
\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\kill
\>	else \\
\>	\>	for userid in key1.secondary-userid-list \\
\>	\>	\>	if userid.name eq key2.primary-userid.name then \\
\>	\>	\>	\>	temp-userid = userid \\
\>	\>	\>	fi \\
\>	\>	end \\
\>	\>	delete-from-list(key1.secondary-userid-list, temp-userid) \\
\>	\>	output-key.primary-userid.name = key2.primary-userid.name \\
\>	\>	output-key.primary-userid.sigs = \\
\>	\>	\>	merge-sigs(\=temp-userid.sigs \\
\>	\>	\>	           \>key2.primary-userid.sigs) \\
\>	\>	output-key.secondary-userid-list =  \\
\>	\>	\>	merge-userids(\=key1.primary-userid, \\
\>	\>	\>	              \>key1.secondary-userid-list, \\
\>	\>	\>	              \>key2.secondary-userid-list) \\
\>	fi \\
\>	return(output-key) \\
\\
merge-userids(userid-list-1, userid-list-2) ::= \\
\>	for (userid-1, userid2) \=in (userid-list-1, userid-list-2) \\
\>	                        \>such that userid-1.name eq userid-2.name \\
\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\kill
\>	\>	output-userid.name = userid-2.name \\
\>	\>	output-userid.sigs = merge-sigs(userid-1.sigs, userid-2.sigs) \\
\>	\>	add-to-list(output-list, output-userid) \\
\>	end \\
\>	for userid-1 \=in userid-list-1 \\
\>	             \>such that userid-1.name not in userid-list-2 \\
\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\kill
\>	\>	add-to-list(output-list, userid-1) \\
\>	end \\
\>	for userid-2 \=in userid-list-2 \\
\>	             \>such that userid-2.name not in userid-list-1 \\
\hspace{3em}\=\hspace{3em}\=\hspace{3em}\=\kill
\>	\>	add-to-list(output-list, userid-2) \\
\>	end \\
\>	return(output-list) \\
\\
merge-sigs(sigs-list-1, sigs-list-2) ::= \\
\>	return(add-to-list(sigs-list-1, sigs-list-2)) \\
\\
search(userid) ::= \\
\>	if (is-keyid-format(userid)) return(userid) \\
\>	for word in userid \\
\>	\>	keyid-list = read-entry(word-db, word) \\
\>	\>	if (output-list is empty) \\
\>	\>	\>	output-list = keyid-list \\
\>	\>	else \\
\>	\>	\>	output-list = intersect(keyid-list, output-list) \\
\>	\>	fi \\
\>	end \\
\>	return(output-list)
\end{tabbing}

\chapter{Sample query form HTML}
\label{commandhtml}

{\small\listing{../../www/pks-commands.html}}

\chapter*{Acknowledgements}

I would like to thank Brian LaMacchia for his help at the beginning of
my project, when he provided me with logs from {\tt pgp.ai.mit.edu},
and at the end, when he installed my server for testing.  His feedback
on the software and on the paper was invaluable.  I would like to
thank Phil Zimmerman for making privacy available to the masses and
creating the need for a public key server.

\chapter*{References}

Aktins, Derek, et al.  {\em PGP Message Exchange Formats.}  IETF
Internet Draft, 1995.

Graff, Michael.  {\em PGP Keyserver Software}, version 2.5. Computer
software, 1995.

LaMacchia, Brian A. {\em Public Key Server Commands}.  World Wide Web
document, 1995.  

\end{document}
