SKS synchronization

[Casey Marshall]

Support keyserver synchronization. Interoperate with SKS gossip protocols if practical.

[Casey Marshall (cmars)]

Yaron Minsky's explanation of the algorithm, from the early announcement of SKS in 2002:
https://lists.gnu.org/archive/html/sks-devel/2011-11/msg00014.html

Russ Cox explains Finite Fields & Reed-Solomon Coding, related to the math used in SKS recon, more accessible than the papers:
http://research.swtch.com/field

[Casey Marshall (cmars)]

More notes:

Polynomial representation of the keys is calculated within a finite field of integer Z(p). This is like doing an implicit (mod p) on every calculation. The p must be prime in order for the fundamentals of arithmetic to work properly in the finite field.

For the recon algorithm, this p would be a prime > 2**n, where n is the bit size of the keyring's digest. Not the fingerprint, but the *digest*, which captures the entire state of the key, all its signatures, subkeys, photo attrs, etc.

The evaluation points should be outside the range of values that could be keys, that bit of extra values > 2**n and <= p.

Building a polynomial is easy but time-consuming. For mongo, it'd be a "full collection scan". These values could be kept incrementally and indexed, which is I believe the SKS PTree..

Using the ratio of those polynomials to determine what keys you need is a rational function interpolation problem. This sounds pretty impressive but the gist I believe is that you connect the dots (interpolate) of those evaluation points, knowing something of the general shape and structure of the function (we know its a ratio, after all). Rational interpolation on ALGLIB: http://www.alglib.net/interpolation/rational.php

[Casey Marshall (cmars)]

In the above comment, "these values" would mean the result of the evaluation points, I think. And I suppose if the rational interpolation fails (couldn't connect the dots), you needed a bigger 'm' evaluation points to sync the databases.

[Casey Marshall (cmars)]

Working on the algorithm as a general reusable library in github.com/cmars/conflux.

[Casey Marshall (cmars)]

Development of recon has been generalized into a separate project, conflux (https://github.com/cmars/conflux). Once complete, conflux will be used to implement the recon protocol as it pertains to SKS interoperability.

[Casey Marshall (cmars)]

Full reconciliation achieved with conflux@8224bc7dcf739c99c211fec6e8e10838783dbfb5.