Re: End to end mixminion rationalized, with compression and K-of-N

[Zooko <zooko@zooko.com>]

Summary: Zooko thinks Nick has an excellent point about failure correlation, 
but doesn't understand some of it.  Zooko gives more general advice from Mnet 
which may or may not apply to MixMinion.


> I'm guessing that most failures in a remailer network are not single
> packet failures, but rather server-level failures where a given server's
> unavailability causes all packets sent through that server to be delayed
> or dropped.  Thus, the number of packets doesn't matter so much as the
> number of paths. 

You're exactly right that Mnet's model is that packet failures are 
uncorrelated with one another, which makes both the "low end of the erasure 
code curve" problem (that I mentioned to you in an early private e-mail) and 
the "P^K problem" as bad as they can be.  The solution of using variable 
length packets is precisely in order to make failure of some of the data 
correlate.  (You lose all or none of a packet.)

So in Mnet it is a huge win to use variable length packets over chunking, 
because even if you have the same number of failed bytes in the system, they 
are now highly correlated in such a way that our erasure code can handle it.

I didn't realize that MixMinion fragments would mostly be sent along the same 
path(s).  I think you are right that this makes packet-level failures better 
correlated.  Hm.  But what you want is for *message* level failures to be 
well-correlated.  If you are going to lose 100 chunks out of 1000 chunks 
during one time period, you very much want to lose all 100 chunks from a 
single 100-chunk message, instead of losing one chunk each out of 100 
different messages!  

You write below that if the failures are path-level then only K, N, and the 
number of paths matter.  Does this mean that failures are well correlated 
within messages?  I don't really understand.


> Math time: If failures *are* packet-level, assuming a assuming a modest
> 90% success rate and an EXF of 1.5 or so, a 20-chunk (8960KB) message
> will arrive with 99.4% probability.  Success probability only drops
> below 99% when message size

What's EXF?

An interesting thing you might want to look at is to hold the failure rate 
right around K/M (where K is required packets and M is total packets), and 
then see how twiddling numchunks changes reliability-of-total-message.  This 
is what happened to Mojo Nation: reliability of individual packets turned out 
to be much more variable than we had thought, and on average was closer to K/M 
than to 0.9.  The chunking "compounded" this problem, effectively killing most 
of the files most of the time, instead of killing a few of the files all of 
the time.


> > The next generation data structure in Mnet will not do *any* chunking, which 
> > we can get away with by specifying variable-length and large packet sizes.
> 
> Actually, variable-length packet sizes were the first recommendation
> that Justin made to me; they're a great choice for non-anonymous
> systems.  Just hold K constant and let the packet size equal Len(Msg)/K.

Yeah, Justin (Chapweske) is partially responsible for convincing me of this in 
Mnet, along with Bram Cohen and Jukka Santala.

FWIW, the next version of Mnet will specify packets sizes of 2^N, and the user 
can of course add higher-layer padding on top of that padding.

 
Regards,

Zooko