Changes between Initial Version and Version 3 of Ticket #753


Ignore:
Timestamp:
2009-07-11T10:25:36Z (15 years ago)
Author:
warner
Comment:

as before, I think I'd like to continue using "storage index" for what you're calling the "file identifier", but yeah split out "server selector" or "peer-selection index" or some similar term for the purpose of determining which servers you're going to be talking to. One way of describing this would be "we used to use the storage-index as the peer-selection index, but these days we put two separate values in the filecap".

I am also starting to think of these as separate concepts, but remember that we've yet to actually implement such a split.

Sylvan's concern was about availability: he considered a backup system to be broken if its design has a built-in probability of file unrecoverability. It's easier to see the problem if we set the encryption-key and hash lengths to infinity, but restrict the storage index to say four bits. Then upload two files, and try to download one of them.. you've got a 1/16 chance of getting a download failure because your two files had the same storage-index, you downloaded the wrong bits, and now they won't pass the integrity check.

Also, when we talk about this, we should be careful to distinguish between the failure modes of mutable files versus immutable files.. they're very distinct. And, collisions at different levels have very different consequences: if the storage index is too small, we'll get availability failures; if the immutable encryption key or mutable writekey is too small, we'll get confidentiality failures. I've been assuming that we'll keep the security parameters sufficiently large.. this ticket was specifically about the availability concerns resulting from a too-small storage index.

If we compress the filecap by deriving the storage-index from the writekey, then clearly we're limited by min(len(writekey),len(storage-index)).

Mostly I ticketed this issue because it's something I want to keep in mind as we design the next revision of the filecap format. If we don't already have a wiki page for it, I'll add one to organize our ideas.. I think they're currently spread across half a dozen tickets.

I updated the table in the description: I think 192-bit caps will let us have an effectively-infinite number of files (264) with an effectively-zero chance of collision (2-65).

[edited to fix trac markup]

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #753 – Description

    initial v3  
    3535from C. The table looks like:
    3636
    37 ||N||numfiles||prob(collision)||
    38 ||96||2**48||2**-1 (0.5)||
    39 ||96||2**40||2**-16||
    40 ||96||2**32||2**-32||
    41 ||96||2**24||2**-48||
    42 ||128||2**64||2**-1 (0.5)||
    43 ||128||2**56||2**-16||
    44 ||128||2**48||2**-32||
    45 ||128||2**32||2**-64||
    46 ||256||2**128||2**-1 (0.5)||
    47 ||256||2**96||2**-64||
     37||N||numfiles|| ||prob(collision)||
     38||96||2**48||->||2**-1 (0.5)||
     39||96||2**40||->||2**-17||
     40||96||2**32||->||2**-33||
     41||96||2**24||->||2**-49||
     42||128||2**64||->||2**-1 (0.5)||
     43||128||2**56||->||2**-17||
     44||128||2**48||->||2**-33||
     45||128||2**32||->||2**-65||
     46||192||2**96||->||2**-1||
     47||192||2**80||->||2**-33||
     48||192||2**64||->||2**-65||
     49||256||2**128||->||2**-1 (0.5)||
     50||256||2**96||->||2**-65||
    4851
    4952