[freenet-dev] Moving to a simple coin was Re: Tunnels vs premix routing was Re: Vulnerability in inserting the manifest before finishing

[Matthew Toseland]

On Friday 18 January 2008 12:39, Michael Rogers wrote:
> On Jan 16 2008, Matthew Toseland wrote:
> >> We could flip one coin per peer at  
> >> startup, 
> 
> Sorry, I've realised this wouldn't work. Flipping a coin at startup can 
> only have two outcomes: drop all requests for that peer or drop none!

Is this a problem? Hmmm, yeah, I suppose it is - why route to the node if 
it'll just DNF? This also rules out weighted-coin-followed-by-HTL schemes.

In fact, any per-peer scheme like this is problematic, even the current 
HTL-10/HTL-1 decrementAtMax/decrementAtMin encourages nodes to avoid peers 
they know to decrement to get more hops.
> 
> Flipping one coin per request gives the attacker too many predecessor 
> samples, so I guess weighted coins aren't useful without tunnels or premix 
> routing.

Compared to the current scheme? Lets do the maths...

Current scheme:
- If HTL!=10 or nearestLoc!=prevLoc, the requestor is definitely NOT the 
originator (because requests cannot loop back on themselves). This is around 
15 out of 16 requests.
- Otherwise, predecessor sample with confidence = 1 in (avgResets+1).
- A positive sample: 75% chance this node is not the target.
- A negative sample: 100% chance this node is not the target.

How valuable are negative samples? If you are directly connected to the 
originator, you will *never* get a negative sample from it (assuming you can 
unambiguously identify the requests of interest).

If you are not directly connected to the originator, most of your samples will 
be negative, but the node that sends the most negative samples is probably 
the one you want to investigate next (get connected to his peers, remote root 
him if possible, etc). You will get some positive samples, but the volume of 
negative samples will establish with reasonable certainty that the originator 
is not the node in question.

Weighted coin:
- Always predecessor sample with confidence equal to pDrop (imho 10% pDrop is 
probably too high, 5% may be better on past experience, and is feasible in 
terms of timeouts).
- A single valid sample: 95% chance this node is not the target.
- No negative samples.

If we ignore the negative samples issue then clearly the weighted coin gives 
away more information: 16 weighted coin samples give a 44% chance the 
requestor is not the originator, versus 75% for one HTL-based positive 
sample. But the negative samples must be of significant value for both local 
and global searches. Without further analysis of the proportion of bocks in 
the file, the routing key, etc, neither will provide *proof* of origination.

So clearly both schemes are unacceptable! But the question of which is better 
remains unsolved IMHO.
> 
> Sorry about that,
> Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://emu.freenetproject.org/pipermail/devl/attachments/20080118/07332c64/attachment.pgp