On Tuesday 12 Apr 2011 14:01:21 Matthew Toseland wrote:
> It has become clear that Freenet cannot support the volume of USK polling
> that Freetalk and other plugins are going to be putting it under.
>
> In particular: My node, with a 40KB/sec limit (and which is not a seednode),
> can send one bulk SSK request every 2.5 seconds, i.e. 1440 per hour.
>
> Currently the demand from a single USK subscription is:
> - 3 tries every half hour, for each of the 3 next slots. I.e. 18 requests per
> hour.
> - 3 tries for each of 4 slots to get the initial DBR.
> - 3 tries for each of 3 slots to confirm that the version returned by the DBR
> is current.
> - Possibly more than that if the DBR wasn't updated today or there have been
> multiple inserts today.
> - A few random probes every so often, which we could probably get rid of now
> we have DBR hints, but this has exponential backoff so is negligible long
> term anyway.
> - So a minimum of 21 requests plus 18 per hour. Of which, 9 plus 18 fail - so
> use very little bandwidth but go to a lot of nodes.
>
> Practically speaking, a largish chunk of my outgoing SSK request capacity is
> used just for updating bookmarks, and after 2 days it is still constantly
> sending requests for the Freetalk/WebOfTrust.
>
> How can we improve on this? It's true that Freetalk and WebOfTrust could
> probably do less polling, e.g. only poll directly trusted identities most of
> the time; FMS manages with a similar sized network. But even so, the capacity
> of my node works out to less than 80 USK subscriptions, which is almost
> certainly not enough. We need to improve this. We need a linear increase;
> making do with a capacity of a few hundred subscriptions on a WoT of
> thousands of identities is WebOfTrust's problem.
>
> REDUCE THE NUMBER OF FETCHES FOR EACH KEY:
> We could reduce the number of tries for each slot. The problem with that is
> that SSKs are routed very badly according to the statistics. It is
> conceivable that this is an artefact of fetching offered keys, although I
> have tried to exclude this. In any case we *could* reduce it to one fetch per
> key, especially if new load management improves routing and/or we find out
> that SSKs aren't routed so badly and it's just an artefact.
>
> QUENCH THE REQUESTS ON THE NETWORK:
> Since lots of nodes are requesting these keys, we can coalesce the requests,
> by detecting when we get a request when there are already 3 ULPR
> subscriptions, and if so, sending a RecentlyFailed rejection. This would be
> handled similarly to a DNF, except that it carries a notice that we can try
> again after a given period. This could reduce the number of hops these failed
> requests visit, meaning they complete faster and hopefully we can run more of
> them.
>
> ALLOW MORE REQUESTS:
> 1440 SSK requests at current usage is actually pretty low: around 2.5KB/sec
> *across the whole 24 hops*. We could increase the bulk threshold (caveat - we
> need to sort out load limiting vs link level congestion control first); it
> might be at the load limiting level. Or if that doesn't work, sorting out
> load management might help.
>
> MORE EFFICIENT REQUESTS:
> We could probably send just the routing key on SSK requests, saving a further
> 32 bytes on unsuccessful ones. This might be tricky with the datastore. We
> could probably coalesce bulk SSK requests for longer, avoiding some padding
> overhead.
>
> LIGHTWEIGHT PASSIVE REQUESTS:
> No longer Ultra-Lightweight Passive Requests! We could further enhance ULPRs
> into LPRs by for instance having the subscription persist indefinitely
> (subject to a longish limit say 6 hours), and notifying downstream when it is
> lost: when the node we are connected to disconnects, when a new one connects
> and we are no longer subscribed to the best node for the key etc. Then we can
> send requests only when we need to. One difficulty is this might open up a
> timing attack in some cases, as does anything where the data source sends
> back to the originator and the originator replies. Also there is a
> conceivable security issue, in that we are retaining information on who has
> asked for the key for longer. However the benefit could be large: We only
> need to send requests when we lose the subscription, which should hopefully
> be better than twice an hour.
>
> TRUE UPDATABLE KEYS:
> The simplest implementation of this is a public key, some sort of identifier
> (preferably not derivable from that used in the SSKs) and a plaintext edition
> number (possibly disguised by an initial offset, but need to avoid
> wrap-around). Requests continue until they run out of HTL and return the
> highest found edition, complete with signature. Some old proposals include a
> timestamp for optimisations; we could allow a few extra bytes for such
> extensions. These keys would be very, very small, although the pubkeys are
> huge; hopefully the pubkey cache will avoid having to send the pubkey in most
> cases, this is a much bigger gain here than it is with SSKs. Two difficulties
> are 1) keyspace black-holes i.e. some parts of the keyspace are less reliable
> than others, so relying solely on one key for updating a USK is bad; 2)
> attacks and incentives - with normal requests, the peer either returns the
> data or doesn't, if the latter we remember and route differently the next
> time; with an updatable key we might always reroute next time regardless
> since we can't tell whether there is a more recent edition; inserts have
> pretty much the same problem so this isn't necessarily a serious issue. We
> could improve on both by either using two separate TUKs or inserting the same
> TUK to two locations with a request-level flag (losing indistinguishability
> but gaining error correction); this was proposed as an alternative to MHKs on
> Freetalk some time back, and I think before that on the mailing list. We
> might fix the locations, or have them based on hashes, but we probably want
> to ensure they are not too close together. TUKs could be compatible with
> ULPR/LPR subscriptions (being deleted only after a disconnection or timeout),
> and with RecentlyFailed, so might avoid the need to actively poll for new
> editions via SSKs, but we would need to maintain a subscription to the TUK,
> preferably via multiple routes. Load limiting would allow a lot more TUKs
> than SSKs because the worst case transfer is much lower. The number of
> requests would be a bit lower (not necessarily a lot lower if we have to
> maintain two subscriptions mind you). Another security difficulty is two
> subscriptions might be correlated by conspiring peers, or by an attacker
> closing in; but there are much stronger attacks.
>
Note that this ("not enough capacity") is only true/relevant if either:
a) We care about how many requests are running. I.e. if we are over-capacity,
then the priorities involved will be swamped, and nothing at lower priority on
the same key type (SSK request, bulk) will run, or
b) We want to keep the ULPRs alive and therefore get a near-instant
notification when an update happens.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20110412/16bf0edb/attachment.pgp>
