[Sks-devel] Fwd: How SKS works (was Re: SKS: The synchronizing keyserver)

[John Clizbe]

This may prove useful to the present discussion

-------- Original Message --------
Subject: How SKS works (was Re: SKS: The synchronizing keyserver)
Date: Fri, 27 Sep 2002 07:42:11 -0400
From: Yaron M. Minsky <address@hidden>
To: keyserver-list <address@hidden>

I've gotten some questions as to how the reconciliation algorithm itself
works.  It's not the simple divide-and-check algorithm that has been
mentioned on this list before, although there is a divide and conquer
algorithm in there somewhere.  You can get a detailed description of how
it works from the papers listed on sks.sourceforge.net, but I'll give a
brief description below.

NOTE: you don't need to understand this to use SKS.

Warning, the following assumes a basic understanding of finite fields
and polynomials and rational functions over finite fields.

The problem can be abstracted as follows:  consider two hosts A and B
with sets S_A and S_B, where the sets consist of fixed length
bitstrings.  (in our case, S_A and S_B contain the 128-bit hashes of A
and B's keys)   Further, assume that A and B know that the number of
elements not shared by S_A and S_B is no more than some number m.

The basic result is that A and can send B a message of size roughly m,
and from that message, B can determine exactly which elements differ
between A nd B.

Here's how it works.  First, think of the elements of S_A and S_B as
elements in some finite field.  We define the
_characteristic_polynomial_ of a set {x_1,x_2,...,x_n} to be the
following polynomial in Z:

    (Z-x_1) * (Z-x_2) * .... * (Z - x_n)

In other words, Chi(S), the characteristic polynomial of set S, is
basically the simplest polynomial whose roots are the elements of S.  By
factoring the characteristic polynomial of a set, you can recover the
contents of the set.

The key observation is that if you look at the ratio Chi(S_A)/Chi(S_B),
all the terms corresponding to elements that are in both S_A and S_B are
in both the numerator and denominator, and so they cancel out.  As a
result, what you're left with is the following rational function:

    Chi(S_A - S_B)
    --------------
    Chi(S_B - S_A)

Given that rational function, you could factor the numerator to find the
elements that A has and B doesn't, and the denominator to find the
elements that B does and A doesn't.

So, the only remaining question is, how do we actually get our hands on
this rational function?  After all, A can't send Chi(S_A) to B, since
Chi(S_A) is every bit as big as S_A.

The trick is to use rational function interpolation.  A can _evaluate_
it's polynomial Chi(S_A) at a collection of m agreed-upon evaluation
points, and sends those to B.  B evaluates Chi(S_B) at the same m
points, and divides those values from the ones that A sent.  Now B has
the values of Chi(S_A)/Chi(S_B) at m points, and assuming that the size
of the difference is no more than m, B can interpolate the rational
function.

That's the basic algorithm, but it's not the whole story.  There are
some other details I've omitted from the description of the above
algorithm, in particular how you deal with the case where you don't know
the size of the difference.  And the above algorithm is too
computationally intensive, and so it's used as the basis of a
divide-and-conquer algorithm, leading to an algorithm where both the
communication and computational costs are linear in the size of the
differences between the two sets.

y


Yaron M. Minsky wrote:
> I'd like to announce the release of a new keyserver, SKS.  I've been 
> quietly working on SKS for the last few months, and it's now in a stage 
> where I think it's together enough to get some feedback on.
> 
> You might wonder why we need a new keyserver at all.  After all, the 
> existing keyservers do a pretty good job, and there are some actively 
> developed keyservers (namely CKS) that are getting better all the time. 
>  But SKS is meant to address one big weakness shared by all of the 
> existing PGP keyservers -- replication.  Current keyservers rely on a 
> not-terribly-reliable flooding-based approach.   Keys often fail to get 
> distributed everywhere, and the only current way to repair these 
> differences is to periodically exchange full database dumps.
> 
> SKS takes a very different approach to replication.  Instead of using 
> the kind of flooding approach adopted by PKS, SKS works by directly 
> comparing the databases and discovering and repairing whatever 
> differences are found.  SKS uses some newly developed algorithms for 
> making the comparison between databases extremely efficient.  In 
> particular, the cost of reconciling a pair of keyservers is proportional 
> to the number of keys that differ between them, rather than the size of 
> the overall database.  That means reconcilation is cheap enough to be 
> done often. By having hosts periodically reconcile with other randomly 
> selected hosts, updates are quickly "gossiped" throughout the system. 
> The resulting system is simple to administer, and the replication is 
> extremely robust.
> 
> You can also try querying one of the two publicly-reachable SKS servers. 
>  The web pages for querying those servers are at:
> 
>   http://sks.dnsalias.net/
>         -and-
>   http://sks.dnsalias.net/other_sks.html
> 
> (yes, the web pages are hosted on the same server, but the actual sks 
> servers that the querying is done on are in different places.)
> 
> You can get more information about SKS, including some links to papers 
> describing the reconciliation protocols at:
> 
>     http://sks.sourceforge.net
> 
> and you can download the first release from:
> 
>     http://sourceforge.net/projects/sks
> 
> Any key succesfully submitted to one keyserver should appear on the 
> other within about a minute.
> 
> I'd love to get some feedback from the community.  And eventually, I'd 
> like to find a few brave souls who would be willing to run a few copies 
> of SKS to build a kind of proto-SKS network.   SKS is still new and is 
> not ready for production.  But I'm very committed to getting it there.
> 
> Yaron