Re: [Sks-devel] SKS apocalypse mitigation

[Andrew Gallagher]

Recent discussion has brought me back to thinking about Phil's
suggestion again.

On 25/03/18 03:37, Phil Pennock wrote:
> Treat items in Filtered as part of "what we have" for reconciliation to
> find the set difference.  That way you never request them.  Return HTTP
> "410 Gone" for attempts to retrieve things which are marked Filtered.
> That way clients don't try to authenticate and you just say "that might
> have once existed, but no longer does".  Include a custom HTTP header
> saying "SKS-Filtered: something".

I don't think we need the custom header - 410 might be sufficient.

> Then it's a policy change to not accept UATs and to mark them as things
> to be filtered out instead, and a clean-up tool to walk the existing DBs
> and decide what should be in Filtered.  There will be down-time of some
> extent, since SKS doesn't like sharing the DBs
Policy will have to be applied in multiple places. If the local
administrator changes a policy, then we have to walk the database as
above. If we receive a packet (either during catchup or via a
submission) that matches an existing policy, then we add the hash to the
blacklist (with an explanation) and throw away the packet. We also have
to be able to add and delete blacklist entries independently of general
policy.

It would be best if a running SKS was able to dynamically update its
blacklist and policy without having to shut down for maintenance. This
could be as simple as a config file that is reloaded on a schedule.

> An SKS version which understands "SKS-Filtered:" headers will add an
> entry to its own Filtered DB but _not_ delete stuff already in other
> DBs.  It should record "I've seen that some peers are unwilling to
> provide this to me, I can mark it as unavailable and include it in the
> set of things I won't request in future".

We need to distinguish between "things that we have blacklisted"
(authoritative) and "things that our peers have blacklisted" (cache).

The things that we have blacklisted locally (and presumably deleted) are
treated as present for recon, and "410 Gone" for requests.

The things that our peers have blacklisted (and previously returned 410
Gone for) are treated as present for recon *with that specific peer
only*, but otherwise not treated specially. If we don't have it and have
not locally blacklisted it, we should still request it from other peers
that are willing to serve it. If it violates our own policy then we
blacklist it locally. But we can't take our peer's word for that.

So the reconciliation process against "some-peer.net" operates against
the list of unique hashes from the set:

(SELECT hash FROM local_db) JOIN (SELECT hash FROM local_bl) JOIN
(SELECT hash FROM peer_bl_cache WHERE peer="some-peer.net")

(If we are in sync with "some-peer.net" then they will have generated
the same set, but with the local_bl and peer_bl_cache roles reversed)

But we only return 410 for incoming requests IFF they match:

(SELECT hash FROM local_bl)

If we receive 410 during catchup, then we add a new entry to the
peer_bl_cache: {hash: xxxxx, peer: "some-peer.net"}. All this should do
is ensure that recon against that particular peer stays in sync - it
should not affect the operation of recon with any other peer, nor of
incoming requests.

Since we are keeping a cache of peer blacklists, we have to allow for
cache invalidation. A remote peer might accidentally add a hash to its
blacklist, only to remove it later. We need to walk the peer_bl_cache at
a low rate in the background and HEAD each item just to make sure that
it still returns 410 - otherwise we clear that peer_bl_cache entry and
let it get picked up (if necessary) in the next recon.

I believe the above system should allow for recon to be maintained
separately between peer pairs whose blacklists differ, and for one
server to recon with multiple peers that all have differing blacklists.

---

The first, easier, issue with the above is bootstrapping.

Populating a new SKS server requires a dump of keys to be loaded. This
dump is assumed to be a close approximation to the full set of keys in
the distributed dataset. But with per-node policy restrictions, there is
no such thing as a "full set".

A new server populated by a dump from server A may not even be able to
recon with server A initially, because A's local_bl could be larger than
the maximum difference that the recon algorithm can handle. If A
included a copy of its local_bl with the dump, then the new server can
recon with A immediately. But only with A, because every server's
local_bl will be different.

This problem will extend to any two peers attempting to recon for the
first time. Without a local cache of each other's blacklists, the
difference between the datasets could easily be large enough to
overwhelm the algorithm.

There must therefore be a means of preseeding the local_bl_cache before
first recon with a new peer. This could be done by fetching a recent
blacklist dump from a standard location.

---

The second, harder, issue with the above is eventual consistency.

We assume that every peer will eventually see every packet at some
point. But it is entirely possible that all of my peers will put in
place policies against (say) photo-ids, and therefore I may never see a
photo-id that was not directly submitted to me - even if I have no such
policy myself. I am effectively firewalled behind my peers' policies.

Which then leads to pool consistency issues. If some peers are trapped
behind a policy firewall, not only will they have missing entries, they
may not ever *know* that they have missing entries. And this can break
in both directions simultaneously, as these peers may also contain extra
entries that the rest of the network will never see.

Without policies, indirect connectivity is sufficient for eventual
consistency. This leads to high latencies but is robust up to the point
of complete severance. But we can see that any policy that impedes the
flow of information across the network will potentially break eventual
consistency.

The only general solution is to alter the peering topology. We need to
get rid of membership restrictions for the pool. Any pool member should
be able to recon with any other pool member, ensuring that all members
see all hashes at least once. This would also have performance benefits
even if we don't implement policy blacklists.

-- 
Andrew Gallagher

signature.asc
Description: OpenPGP digital signature