[freenet-dev] How to deal with inserts with weighted coin?

[Matthew Toseland]

On Wednesday 30 January 2008 10:17, Matthew Toseland wrote:
> On Tuesday 29 January 2008 23:09, Michael Rogers wrote:
> > Matthew Toseland wrote:
> > > Of course it's safe. The average number of nodes visited will be 
1/pDrop. 
> Full 
> > > stop. End of story. Because DNFs are fatal.
> > 
> > Shit, you're right, I see what you mean now. :-) Sorry about that.
> 
> So weighted coin rulez! Great.
> 
> One more concern: what about inserts? With a simple weighted coin, some data 
> will be inserted very shallowly. We won't retry the insert in response to 
> failure, because it will succeed. We could send the insert two or three 
> times? Weighted coin followed by an HTL countdown would give away more 
> information than just weighted coin (although the difference is marginal, 
65% 
> vs 64% for 10 positive 10 negative vs 20 positive), and privacy is 
especially 
> important for inserts.

How much of a problem are negative samples here? I.e. the samples from the 
countdown phase? They tell an attacker that the nodes sending them are 
*definitely not* the originator. On average they should all be at the 
specialised end of the request, so they shouldn't tell the attacker very much 
that he doesn't already know from the keys. However because of probabilistic 
drop, many of them will be much closer to the originator, and can help the 
attacker to quickly eliminate possible originators once he is close to it.

Generally in Freenet there is a preference for security over performance, as 
long as the cost is reasonable. So lets go with weighted coin, and see if 
it's feasible to get acceptable performance:

Do we just have to send the insert twice (or more)?

The probability of the insert going 6 hops or less is 
0.05+0.05*0.95+0.05*0.95^2+... = 0.264. If we send it twice there is a 7% 
chance of failure, if we send it 3 times there is a 1.8% chance of failure. 
7% is certainly acceptable for splitfiles (26% isn't - well, it's pushing 
it!). On a 0.5-scale network with good topology 7 hops ought to be sufficient 
(iirc most successes took around that on 0.5).

For 10 hops or less it is 0.422, so 18% for twice, 7% for 3 times, 3% for 4 
times, 1.3% for 5 times.

The other problem is if it *is* too short, it won't reach the store, it will 
only be in the cache, because it won't reach any permanent storage location.

Maybe we could return the number of nodes which added the data to the store 
(not the cache) with the InsertReply as a diagnostic? Obviously it could be 
spoofed, so we can't use it for actual routing decisions (e.g. retrying until 
it's stored on enough nodes is out!), but it might be an interesting stat. 
Would it be safe?

What would be the performance cost of sending an insert 3 times? If we assume 
that on average an insert goes 20 hops right now (it might be more than that, 
we need probe requests), sending the insert twice would reduce performance by 
a factor of two... :( Combined with the fact that it looks like inserts are 
much faster than they ought to be right now because of a stats bug, this 
could be bad...

A more extravagant option would be to keep on inserting the block until we can 
fetch it through a separate tunnel - a kind of insert verification protocol.
> > 
> > Cheers,
> > 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/20080130/ef6564bf/attachment.pgp