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 <ymin...@cs.cornell.edu> > To: keyserver-list <pgp-keyserver-f...@flame.org> > > 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 > Sks-devel@nongnu.org > https://lists.nongnu.org/mailman/listinfo/sks-devel --- Ari Trachtenberg Assoc. Prof., Assoc. Grad. Chair, ECE trach...@bu.edu http://people.bu.edu/trachten _______________________________________________ Sks-devel mailing list Sks-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/sks-devel