We could even send the insert twice in one insert: have a counter
ParallelInserts on an insert, then:
int newParallelInserts = 0;
for(int i=0;i<ParallelInserts;i++) {
if(rand() > 0.95)
newParallelInserts++;
}
If newParallelInserts is 0, terminate on that hop.
Obviously this is more state than simple weighted coin, which is bad - but it
should give less information than actually sending the request more than
once, because there's only one set of routing info.
0.95*0.95 is ~ 90%, so if PI started at 2, and 10% of the samples are at 2 and
90% at 1, we can conclude that we are 1 hop from the target. Likewise with
simple weighted coin, if we know the inserter is sending two inserts for
every block, and for 95% of keys we get two inserts and for 5% we get one, we
can draw the same conclusion.
Even weighted-coin-followed-by-HTL gives significantly better security than
the current scheme: against a global remote search, dramatically better
security because no nearestLoc. Against a local attacker, it's still better:
Weighted coin followed by HTL:
At 1 hop, 10% of requests have HTL 10 (rather than no HTL). If we get an HTL
10 request, we know the sender is not the originator.
Current scheme:
At 1 hop, 50% of requests have HTL 10 (rather than HTL 9). If we get HTL 9, we
know the sender is not the originator. If we get HTL 10, and nearestLoc is
*not* the same as the sender's, we know the sender is not the originator. If
it is, there is a 1 in (average # resets + 1) chance that the sender is the
originator.
So I propose to implement weighted-coin-followed-by-HTL. This should cause
very little disruption, as we won't have very short requests, in fact the
code changes would be very minor. We can always change it later on to for
example pure weighted coin (although I'm not convinced that will work well
for inserts).
On Wednesday 30 January 2008 10:54, Matthew Toseland wrote:
> 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:
<https://emu.freenetproject.org/pipermail/devl/attachments/20080130/6a371ebf/attachment.pgp>
