Cryptography: Peer-to-peer gaming disconnection protection

This is more of a crypto/algorithm than a programming question, so feel free to tell me to go elsewhere if this is inappropriate here.

I'm wondering if there is a solution for the "disconnection problem": Two peers A and B talk to each other, and it should be an offence for either peer to sever the connection. Is it possible to prove that a disconnection was caused by a specific party?

Of course, if the two were connected with a direct line, then there would be no way to define a responsible party for the loss of connection. So we must include some ambient network, and define as disconnected the party who loses connection to some third "arbitrator" node in the network. However, if A wanted to disconnect, he could selectively block only the connection to B, while maintaining communication with the arbitrator.

Is there a cryptograp开发者_运维问答hic solution by which A and B continuously exchange keepalives which they also forward to the arbitrator which ensures that it is always possible to tell who caused a deliberate disconnect?

I think that such protocol it it impossible.

Lets say that that you have connection

     arbiter
       /\
      /  \
     /    \
    /      \
   /        \
 peerA --- peerB

And now one of the peers cut away peerA -- peerB link.

Before disconnection there could be all possible situation. (A send data to B, or B received or B->A or something third.)

Since there is no more A <-> B link you are not able to tell who break connection. Both parties can claim that

a) they send last packet
b) they did not receive packet

Point is that when A<-->B link is gone, you are not able to tell who break it, because it might be even some third party in the middle.

One practical solution gets on my mind is, that once this happens, you reroute all traffic from arbiter which now acts as proxy. Both parties in the meantime sends trace route to each others and sends results to arbiter. Even if this fails and cheater implements faking ICMP packets this cheating method will not work and they will abandon this cheating method sooner or later. In worst case you will have to reroute some traffic and act as a router but you might be able to statistically trace cheaters and make proper actions against them.

I'm not an expert but since all is a bit quiet here I thought I would point to where I would start. Its possible that what I write is no good but at least it gets the ball rolling.

It seems to me that detecting a disconnect is the same class of problem as detecting an error generally. (presumably there is no "disconnect signal" so we are trying to detect when someone pulls the plug out). I feel this falls in the subject of noisy channel coding theory. I am not an expert at this but I have a good book on the subject.

David MacKay's

Information theory, Inference and Learning algorithms.

It is available for free online viewing on the Author's website (with permission of the publisher) so you can judge whether it is helpful or not yourself without paying any money.

For this particular problem you might want to look up the Repeat Accumulate codes (chap 49 - you don't need to read the 48 chapters before this). You send repeat of each bit of the signal that you want to send but the permute them with a random (but fixed) key. You then to checksums on the permuted signal.

So, if the central server used different keys for each user - I would have thought that they could detect who introduced the error of disconnecting mid-signal (by pulling their plug out - for example).

That's how I would start - but I am not an expert.

Tom