[tahoe-dev] [tahoe-lafs] #302: stop permuting peerlist, use SI as offset into ring instead?

[tahoe-lafs]

#302: stop permuting peerlist, use SI as offset into ring instead?
------------------------------------+---------------------------------------
 Reporter:  warner                  |           Owner:           
     Type:  task                    |          Status:  new      
 Priority:  major                   |       Milestone:  undecided
Component:  code-peerselection      |         Version:  0.7.0    
 Keywords:  repair newcaps newurls  |   Launchpad_bug:           
------------------------------------+---------------------------------------

Comment(by warner):

 Zooko suggested I add a note about the following idea which came up in
 tahoe-dev:

 Suppose an attacker gets to kill N servers of their choosing, and want to
 cause as much damage as possible. And suppose that there were far more
 than N servers in the grid, and we're using 1-of-N encoding. Now, if we're
 using the permuted-list algorithm, they could pick one file to completely
 kill (choose an arbitrary file, locate its servers, kill them all; boom,
 the file is dead). But killing two files is awfully hard: you'd have to be
 lucky and find two files that happen to permute to the same first N
 servers. I think the chance of killing a second file is like 1 over (M
 choose N), where M is the size of the grid: i.e., the number of
 permutations is huge.
 And of course killing a third file is that probability squared, etc.

 Whereas if you aren't using the permuted-list algorithm, and shares are
 placed on consecutive servers starting at the SI, the attacker can do a
 lot more damage. They just take out any N consecutive servers. They'll
 completely kill 1/M of the files on the grid (since there are only M total
 permutations in use, one for each server). And they'll kill all-but-one of
 the shares for another 2/M files (the two immediate neighbors), and all-
 but-two of another 2/M files, etc, in a sort of triangularly-shaped
 distribution.

 So I still think that permuted-list provides better properties.

-- 
Ticket URL: <http://allmydata.org/trac/tahoe/ticket/302#comment:9>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid