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

[Ari Trachtenberg]

One minor quibble ... the overall communication and runtime complexity are
*expected* linear in the number of differences m (strictly
speaking, logarithmic in the overall set size), and m log m
with high probability (to appear).  The algorithm also has a number
of nice properties (like quick restart) although a proper
implementation require some additional thought.

best,
        -Ari


On Nov 2, 2011, at 2:41 PM, John Clizbe wrote:

> 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
> 
> 
> 
> 
> 
> _______________________________________________
> Sks-devel mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/sks-devel

---
Ari Trachtenberg                   Assoc. Prof., Assoc. Grad. Chair, ECE
address@hidden                    http://people.bu.edu/trachten