On Wednesday 16 January 2008 13:56, Michael Rogers wrote: > On Jan 16 2008, Matthew Toseland wrote: > >If they are both local they'd both be HTL 10 iirc. > > Right, if they're both local they'll have the same HTL, which means if they > don't have the same HTL they can't both be local... so local traffic has > less traffic to hide in. > > > A simple weighted coin would generate very few > > timeouts: If we assume the data isn't found (typical on *long* requests), > > 2 seconds per hop seems a reasonable upper estimate, so there is a 0.2% > > chance that a request goes more than 60 hops and therefore causes a > > timeout... on the other hand we want it to generally respond in much less > > than that. > > That sounds good - and if it doesn't time out we'll get a reply of some > kind within 60 seconds so we can move on to another peer.
120 seconds in the current code. > > >> DNF after a short search isn't a big deal, we can always try again. > > > > True. But to the same node? And how do we detect this anyway? Simply by > > time? > > If we get a DNF from one peer we move on to the next - DNF is equivalent to > RNF because there's no hop counter. Hmmm, interesting. What are the ramifications? We lose the ability for an attacker to kill the request through a DNF, which is probably a good thing; he has to let it timeout (or use some other propagated failure). Overall a request should travel the same number of hops. And the code would be simpler. > > > Report the number of hops on a DNF? Is that safe? > > It's not safe and we don't know the number of hops anyway. > > > On either a DNF or a timeout, we'd like to route differently the next > > time, because both could be caused by a single malicious node attempting > > to censor a specific key. If short DNFs and timeouts are too common, this > > could be a problem. > > In the case of a DNF we can just move on to the next peer... in the case of > a timeout, maybe we should remember which peers we tried last time for a > few seconds (in other words failure tables)? > > > This again appears solvable: allow more than one request before blocking > > it - block the request only if there have been N requests over the > > timeout period. This is probably wise anyway, since Bad Things may have > > happened downstream. > > Sounds sensible - so one timeout or several DNFs will cause further > requests to block. We can work out the number of DNFs to tolerate using the > weight of the coin, eg if there's a 95% chance that at least one of the > requests travelled 10 hops downstream, then block further requests. Timeout should cause temporary rerouting of requests for that key yes. DNF is normal, and if we immediately move on to another node then there's no reason to worry about it. An attacker who uses a long delay will cause a timeout, even if it's not on that specific node... telling the branch that caused the timeout that there was a timeout seems rather convoluted, is it necessary? On the other hand, if we have full ULPRs as currently envisioned (and partly implemented), we'll want to reject requests with RecentlyFailed if we recently requested the same key and failed with a DNF. > > >> IMO it shouldn't be customisable. If some of the traffic flowing through > >> my node belongs to unusually paranoid or unusually confident people who > >> modify the weight of the coin, my anonymity is reduced even though I > >> stuck with the default. > > > >I was referring to tunnels IIRC. In terms of HTL, I agree. > > Ah, I see. We'll also need a way to decide when to terminate the tunnel (ie > switch from random routing to greedy routing) - I was thinking of a > weighted coin for that as well. > > > Okay, supposing we implement a simple weighted coin (say 10% > > probability). This would eliminate the *urgent* need for tunnels. > > I don't agree - replacing the hop counter without introducing tunnels might > actually make things worse: if we flip a separate coin for each request > then the attacker can quickly gather predecessor samples, even if each one > only provides a probability of 10%. Sure. > We could flip one coin per peer at > startup, The first problem you have to solve here is a familiar one: when you get a DNF, you need to throw the coin again, otherwise the request will visit every peer. I assume that throwing it randomly at the time would generate a predecessor sample, so we need to use the flag from the node we are sending it to instead of from the source after the first request?? Please read my message about trying all peers for the equivalent problem with HTL. > but then repeated requests will follow exactly the same path as > the original request unless we introduce failure tables. This happens with the current HTL system too: it is deterministic (with hidden constants), unless a node goes down, goes up, restarts, enters or leaves backoff. It is therefore not a disadvantage of a weighted coin approach to hops. If we route to a node and it returns too quickly, there is no problem, we route to another node, and if the network is well connected we'll get to the same target area soon enough. On a less well connected network, for example something very fragmented, it might be a problem. Is this an issue? If we route to a node and it gives us a timeout, that is bad. So we need some sort of failure tables logic to route around timeouts. "Failure tables" historically means two opposite things: Per-node failure tables: Track which keys each peer has recently failed for. Route to other peers. Maybe alternate, maybe try the top N/all nodes once in a given period. Failure tables: Kill requests which are likely to fail because they have recently failed. The ULPRs proposal / half-implementation currently does the latter, and a tiny bit of the former. It's a question of to what degree do we want to limit the load caused by continual retries, and to what degree do we want to shape it into an exhaustive search? Clearly we need to route differently next time if we get a timeout, if only to work around cancer nodes - on every hop, since any hop might be responsible for it. ULPRs' automatic propagation turns enough nodes searching into something like an exhaustive search, but if it's just one node continually requesting? Damping it out may be the best thing? The originator node doesn't drop locally originated requests, correct? > > > It would dramatically reduce the predecessor confidence, > > Yup, that's definitely worthwhile as long as we don't increase the number > of samples at the same time. Okay, so the proposal is: - Abolish HTL, replace with a per hop drop probability of 10%. (That may be too high - 5%?) - Treat DataNotFound identically to RouteNotFound. Since there is no HTL, in both cases we simply retry. - When a requestor receives a nonfatal error from a node, it considers whether to drop it by pretending that the node which just failed is the originator (without considering triage): we drop it if we would drop a request from that node. - When we get a timeout on a request from a specific node, we remember it and don't route that key to that node next time. - Request coalescing works as it does now, except that any request for a key matches with any request for a key because there is no HTL. ULPRs are also largely unchanged. Sound reasonable? > > Cheers, > Michael -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 189 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20080116/22e521e8/attachment.pgp>
