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.
>
One other thing we could do is reduce the maximum HTL. We reach the ideal
location pretty quickly; the main reason for a high HTL is to find stuff that
is not where it should be.
-------------- 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/eba7ae76/attachment.pgp>
