Privacy and bandwidth preserving key update mechanism

Hey there,

I'd like to discuss and think through a feature that I think is very important for Hagrid: A privacy-preserving and performant key update mechanism.

First, some background:

It is desirable for openpgp implementations to regularly refresh all known keys, to notice when a key is revoked, gets new subkeys, etc. However, this use case is not considered at all in the traditional HKP API. So what implementations do to refresh a key is that they download the full key by fingerprint, and merge it into their local copy. This is then done for all keys following some schedule, for example OpenKeychain refreshes all keys over a time span of three days.

So, if keys should be updated every time span X, then within each X and for each key Y:

• the client does one HTTP roundtrip
• the client reveals to the keyservers that it is interested in Y
• the client downloads and processes a full copy of Y

If we look past what we're primed to consider state of the art in OpenPGP, this mechanism is hilariously bad, in terms of privacy, performance, and traffic it causes. On keys.o.o we get about 10 requests per second on average, almost all of which are update schedules of this kind (from Enigmail and OpenKeychain). I would wager that 99% or more of those deliver no actual updates.