P2P network hiding positions?

Question

I have been working on a P2P architecture for secure gaming and I have divided the problem into five sub-problems:

• Unlawful modification of sent game state
• Accurately drop cheaters
• Agreeing on a game state
• Avoiding "look ahead" cheat
• Hiding sensitive information from opponents

The first four I have pretty much all solved but it is the last one which I am having trouble with.

Before I go into details I just want to ask if there's anything I've missed in my list of making a "cheat proof" p2p network. I am not interested in cheats such as using aimbots, I am only interested in making the p2p network as secure as a centralized server.

So in my effort so far on hiding sensitive information I've focused on the position of players in a game where the position of your opponent should not always be known. The problem then becomes how to determine if you should send you position to your opponent without knowing the position of your opponent.

I have ruled out methods such as the opponent sending multiple false positions for you to compare yours too since your opponent can easily abuse such a system since he will get your position if one of the false positions happened to be "visible" from your position.

The method I have been focusing on one in which you receive a "visual field" from your opponent and can thereby determine if you should send your position or not. This is however a problem in games such as League of Legends where the visual field of your opponent is also highly sensitive information. I have tried to solve this by transforming the visual field using a singular matrix meaning you cannot go from the transformed version of the visual field back to the original version, but since it is a linear transformation you can still figure out if your position is inside the visual field or not.

This does not however work perfectly, the exact visual field cannot be restored after transformation, but information about the "slopes" in the visual field (the visual field is constructed by several lines, and the slope of each line can be determined) can be restored and this can be used to relatively inexpensively reconstruct the original visual field.

In essence, what I need is a function which can determine if a position is "visible" or not, and reconstructing this function/visual field has to be so computationally demanding that once you are done reconstructing the visual field it is no longer relevant for the game in action. Is there any super smart person out there who happens to know of such a method?

Edit People seam kind of confused about the whole "vision field" so I aim to give a more detailed explanation here. The vision field consists groups of a set of lines, you can easily check if a position is inside one of these groups by just checking which side of the line your position is, if it's on the same side for all lines in that group you know it's inside that group and thus inside the vision field.

The information being sent however is not this line, but a transformation of the line and the transformation (2 by 2 singular a matrix), you can still check which side of the line your position is on by first transforming it using the transformation you received and comparing that value to the transformed line. The key here is that the transformation is singular, meaning it is impossible to find an inverse to go back to the original line. However it is possible to determine the slope of the line which makes reconstructing the line by just checking on which side of the transformed line a lot of points lie until you have pinpointed the origin of the line a lot computationally cheaper than if you did not know the slope of the line.

What I am looking for is a method for determining if a point is inside of an area, where reconstructing the area from the method is either impossible (which I doubt exists since you can always brute force it) or very computationally heavy.

Answer 1

I think that even if you had an irreversible algorithm for a vision field, people could still gain advantage by calculating if nearby points to them would result in an intersection of that location and an opponents visual field would intersect. In a bad case (of a large enough vision field to map ratio) you could calculate by process of elimination the exact point of your enemy.

I think instead maybe all connected peers should announce which part of the map they are in, to determine if it possible if they can see each other or not. First split the map into 2x2 or 2x2x2 if the 3rd dimension is important. Then everyone tells each other if they are in 1,0 1,1 0,1 or 0,0. If they are not in the same quadrant, their conversation is over until next check. This protects their exact location. If they exist in the same quadrant, they will split this space up into 4 new quads, and continue until they determine that they are close enough to be seen by each other.

Of course there are problems with the borders of the quadrants, but it should be solvable by additional queries to neighboring quadrants.

Answer 2

Don't take this as a definitive answer, the topic is really broad (I won't be suprised if someone flag your question infact).

You can solve it by using some players as server, and when a player is used as server it cannot participate in the game of players that are actually playing that server.

If your game is not too demanding you could as well run multiple servers from the same player machine (of course that would be useful, since not all players can run as server due to NAT problems, thanks you IPv6!!).

The main problem here is that since a random player will be used as server, there's a slight chance it will be a "compromised" player or that it will pass the simulation to a "compromised" player, allowing sensitive information to be passed on (well, in reality at that point the server could send arbitrary data and force the win anyway).

If you use a central server to check authorizations and logins then you could allow to organize games better and to ban players easily (however that would no longer be a pure P2P network).

You could also divide the world into slices and compute a hash of the visible slices, but this could be easily tricked, the most common visible slices will allow to build a table of hashes pretty quickly.

To me your question is like trying to search for a cryptographic function. The test should be quick, but brute force should be slow..

The simplest thing that comes to my mind (also related to my work) is to use some quick vision recognition algorithm (Augmented reality-like).

If you manage to make a quick "snapshot" of your location (similiar to slices), than can be recognized only when placed around something visible then you are going to have it. Especially if there are timed elements in the map that allow to generate quick throw away recognition patterns.

However, even if such algorithms become pretty fast even on mobile, I don't think those will be fast enough for a First Person shooter.

Also if you make them too fast, you will have fake positives! And a player can anyway create a game that try some "Common visuals" so that one of the visuals match positive to the feature detection algorithm.

I will not be surprised the only possible solution to your problem would be possible in Quantum Computing, and within some years someone publish a paper prooving that intrinsic limit in P2P networks.

Answer 3

When you say 'Hiding sensitive information from opponents', you mean you want to avoid people with packet sniffers from listening to your traffic and getting info about your game?

If so, there's an easy answer to this; most AAA games (and certainly console games) use encryption. In fact, its so common that many of the networking middlewares used in games already have packet encryption built-in.

Usually it works like this: When you open a connection to another machine, before the socket becomes active, a Key exchange happens. I know that on XBox it used to be Diffie-Hellman key exchange; I've no idea if they still use it now. Then once you have your keys, all data sent is encrypted using the keys and unencrypted on receipt. If someone uses a sniffer to read your packets, they will look like gibberish and it's unlikely they can decrypt them since they don't have the keys. (Advanced hackers may be able to get them by accessing the process memory of the running game, but that is rare and unlikely.)

The only exception to the encryption rule is VoiceChat data; by law in the US, voice chat must be sent in-the-clear so that the CIA can listen in if they want to. Consoles usually provide a way to tag voice data so that it's not encrypted.