[messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

Michael Rogers:
> On 06/11/17 13:29, Ximin Luo wrote:
>> https://www.cs.rice.edu/~dwallach/pub/osdi2002.pdf
>>
>> This paper's description of the eclipse attack is as follows:
>>
>> "More precisely, routing updates from correct nodes point to a faulty node with
>> probability at least f whereas this probability can be as high as one for
>> routing updates from faulty nodes. Correct nodes receive updates from other
>> correct nodes with probability at most 1 − f and from faulty nodes with
>> probability at least f. Therefore, the probability that a routing table entry
>> is faulty after an update is at least (1 − f) × f + f × 1, which is greater
>> than f. This effect cascades with each subsequent update, causing the fraction
>> of faulty entries to tend towards one."
>>
>> This argument assumes that nodes have a (very) simple algorithm for selecting
>> their neighbours, one that is uniformly random over all offered neighbours. It
>> assumes that nodes are unable to use any other information to distinguish
>> between faulty vs good neighbours. Indeed, the paper you linked proposes
>> various more sophisticated algorithms to defend against the basic attack.
>>
>> I actually can't think of a selection algorithm that is less sophisticated than
>> "uniform random" and I think it's a bit unfair (and incorrect) to "write off"
>> all decentralised systems just because the simplest example one can think of,
>> has problems.
> 
> I don't think the attack in general depends on uniform random selection.
> That's just the easiest case to quantify. The attack applies to any
> system with the following properties: [..]
> 
> So if we're asking whether a system may be vulnerable to the attack, and
> it has the properties above, then we need to ask whether the system is
> doing something to produce that countervailing tendency. In other words,
> is it actively preventing the attack?
> 

Indeed, I noted that the specific simple attack "assumes that nodes are unable 
to use any other information to distinguish between faulty vs good neighbours.

There are various things you can do along those lines, and the paper you linked 
includes a defense that based on their analysis is moderately effective. I'm 
sure there are improvements to be made though.

>> Going back to the original issue (epistemic attacks against mixnets), the key
>> point AFAIU is to ensure that n ~= N. Whether this is achieved in a centralised
>> or decentralised way seems immaterial to me.
> 
> The question isn't really the size of the view, but how much overlap
> there is between the views of different users. Even if a user has some
> way to know the value of N in a decentralised system (which is a hard
> problem in its own right), how does she know whether the n ~= N nodes in
> her own view are also in other users' views?
> 

If n ~= N then the overlaps are much closer and you can follow the maths in the 
rest of the paper to see that the attack probabilities drop to very low.

> [..]
> 
> I'm not interested in writing off decentralised systems any more than
> you are, but there's a burden of proof here. Given the existence of a
> pretty broad class of attacks that only apply to decentralised systems,
> a decentralised system needs to show it's not vulnerable to those attacks.
> 

The attacks only work if the decentralised system literally makes no effort to
defend itself.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git