Technical solution to eliminate desync in single-player sessions

I had edited my post to ask for exactly that =)

Tearing apart qwave's insistence on trusting the client gets boring. So let's change it up by defending deterministic simulations instead.

"

MeltingPoint wrote:

"

qwave wrote:

So wait, you're telling me that this 'seed' will ensure that a mob's AI works in the same manner on the client as on the server?

Yes, mob pathing occurs as a result of the deterministic seed being passed into the mob's artificial intelligence procedures.

I want to make sure we're clear here. Some definitions:

Seed = A value used to 'start' a Random Number Generator
Random Number = A value pulled from a Random Number Generator

In it's current incarnation, a Seed is sent once to start the Random Number Generator off. We are left with 2 possibilities for mob pathing/AI

1) All mobs use the Seed as their Pathing/AI generation.
2) All mobs use a Random Number as their Pathing/AI generation.

In 1) that would mean all mobs, or at the very least, all mobs of the same type/class, will behave the same. If you've found a way to use one Seed on the same mobs, and have a different outcome, you've essentially broken the point of the seed.

In 2) that would mean that each timestep/snapshot, a mob gets a new random number for it's pathfinding/AI, how can this result in fluid motion? How is it any different from coin flipping to determine movement?

Although your definitions are kind of correct, I think you don't understand them in enough detail.

A random number generator, in computing, is very rarely truly random (there are a few exceptions, but they all involve getting the numbers from nature somehow; for example, random.org uses a static electricity sensor, which obviously measures static electricity and uses the readings as output). Generally random number generators are pseudorandom, which means they appear random, and can be used in lieu of (expensive) true randomness with essentially the same results, but in truth are deterministic, meaning that, over an extremely large sample, eventually the numbers would start to repeat themselves; naturally, all pseudorandom generators have patterns so amazingly long that this is not practical.

In other words, a pseudorandom number generator — the type computer programs use — isn't rolling a die; instead, it's using a pre-established list of die rolls, and reading them off one by one. This gives the appearance of random while still allowing the computer program to stick to its standard M.O. of only doing exactly what it's told.

What is a seed? It's a position on the list of die rolls. When a computer program (or a person) has both a pseudorandom number generator and the seed, the randomness is now gone; you know exactly which rolls are coming, in what order. The next roll is a 1, then the next roll is a 5, and so on. With the seed, a random number generator stops being random and starts being utterly, flawlessly predictable.

The whole point of this is that the client program knows the seed, but the user doesn't (unless he's hacking). Thus, to the user, monsters would still have some degree of unpredictability in their actions; but, to the client, everything would follow a preset simulation of pure logic.

The only problem with this is exposing the seed to hacking. So the question becomes: what is this seed used for? If the answer to that is simply "having the Rhoa decide whether or not to charge you," then that's not that amazing; if it's "having Dominus decide whether or not to use the Touch of God" then that's a little more interesting, but there's also Miscreations in the same level, probably using the same seed, so it would get hard for the hack to manage it because it would also have to factor in your movements and how they change RNG iteration (moving from one die roll to the next) in terms of the logic of all monsters.



*yawn*

"

qwave wrote:

The timestamp cannot be spoofed because it uses the seed generated by the actions at that exact time.

The hack can use the same seed, because the hack can trace all actions.

ScrotieMcB: I writing am the code for this full system right now. It will prove that you cannot modify the packet, and that the server can detect any sort of cheats, speed hack, etc.

You are not understanding how the seed is used in conjunction with the timestamp. The code will explain it in more detail.

"

ScrotieMcB wrote:

*yawn*

"

qwave wrote:

But hackers can just modify the timestamp to any value that they want! Therefore the server has to believe whatever the client tells them

The server can detect modified timestamps because the timestamp is encrypted using the current deterministic seed random number based on the state of the game. This is called 'signing' the packet. The timestamp and seed is used as a signature.

In other words, the server will only be able to read the packet if it can decrypt that packet using the exact deterministic seed that your client had at the time of creation.

So basically, if your character attacks a Rhoa and then raises some skeletons, the deterministic seed will be at a specific value at that exact time.

Therefore, it is impossible for the client to forge the timestamp, because it uses the deterministic seed to 'sign' the timestamp.

The hack also has the seed, and can track uses of it (both alleged and real) to know precisely which number to encrypt with.

Let me break this down for you real slow.

Starting from before the Path of Exile client even launches, and ending after the client closes, a hack can view any and every network communication the client receives, send any message to the server which it wishes, prevent any outgoing message from the client, or perform essentially any process which the client could (encryption, decryption, iteration). Therefore, no form of encryption can ever secure the client against local (e.g. not man-in-the-middle) hacks. Any keys which the client has, a hack can also have; same with any seed, any counting process, any analysis of data.

The ability of a local hack to spoof the client is limitless. In fact, the client can't even prove that it is the client. (Do you really believe that the ability to solve captcha proves you are human?)

You say to forget what we know. You say the client can be trusted. Sorry, but no. We can't even trust that what we think is the client, is actually the client. Nothing will ever solve this, ever; even token-based authentication can be spoofed.

While you've actually kind of converted me in terms of deterministic simulations, you have not, nor will ever, convince me that trusting the client is a good thing. Because it really, really isn't.

Physical control of a system is total control of a system.

I am not sure if this could be possible, but I'll give it a try.

So, what is this client, you ask? Well, abstractly speaking, I would say it is the pair <program,player> that occurs when the player executes the PoE.exe .
But "hacks", have total access to the physical data of PoE, and can simulate any interaction a player can have with the process and code. If a player moves the mouse and clicks the screen, there exists hacks that simulate that mouse move and click. If a player types a key, there are hacks that simulate that key press.
In terms of the program, the hacks can get access to the source code, and any configuration file. We can assume that will happen (at least after some time, the hacker has to decrypt files, figure out protocols, etc). Thus, the hacker has access to all the code, knows exactly how everything works in the client, and how the client-server relationship works, at least from the point of view of the client. He can also make tests and know exactly what each client network request/response does to the game.
So basically, any hacker can create a new pair <simulated_program,simulated_player>, therefore the hacker can simulate the client, or what the server thinks of the client.

Up until this point, I have to agree. The conclusion of this is indeed never trust the client at all, since ANYTHING that the server can consider comes from a client, can come from a simulated one.

But this depends on the server recognizing the client as that <program,player> pair. Maybe if we could define it in some other way, this could be averted?

There's one example that crosses my mind: runtime environment.
The "client" executes in a process in the machine, but does so in a specific runtime environment. This could be native code running normally (is stored in memory, is executed by CPU), or it could be bytecode running in some virtual machine like JVM, etc.
Now this could add a new dimension to the previous "definition" of a client. Perhaps, it could be possible to define a runtime environment where PoE runs, so that no "hack" can run in the same environment as this one. Or perhaps, this runtime environment could be defined in a way that the PoE program can be uniquely identified, and the "hacks" are identified in a different manner. Let's say this identification is an "RTE_id" number.
Now, we can say that, PoE, running in a specific runtime environment, by a specific player, defines a tuple <RTE_id,program,player>. This new tuple is the one that defines the client. The server knows this tuple identifies the client. Now, can it be simulated by hacks? Well, we know the "program" and "player" parts can be simulated, but because the hacks can't manipulate the runtime environment they are running in, and they are identified by a "RTE_hack_id" number, then any hack will be, at most, identified as a <RTE_hack_id,simulated_program,simulated_player> tuple.
The program can be simulated, the player can be simulated, but not the runtime environment authentication. Thus, the client is not simulated, thus with the proper authentication, the server can trust the client.


I know this seems too abstract and maybe nonsensical, but that's because it HAS to be vague, without introducing other technical aspects (like network, etc), since that would just complicate things.

Basically, define a lower-level entity that acts as the "trust advisor", that can define if the client can be trusted or not. The hacks or hacker won't be able to manipulate this lower-level entity (won't have sufficient OS permissions, etc), so he can't access anything about it, or manipulate it into "simulating" the client.

I kind of think this may be impossible...but I'm not an expert on this subject. Could something like this be possible to do? In some operative system, in some computer architectural pattern, in any way? If it can be done in at least one way, that's a start. Obviously if it's something complicated (like maybe creating an OS from scratch just for PoE :P ) it won't be viable at all and GGG obviously won't be able to do it, but at least theoretically it could be done, and with time and effort...who knows? Maybe we could get there.

"

qwave wrote:

ScrotieMcB: I writing am the code for this full system right now. It will prove that you cannot modify the packet, and that the server can detect any sort of cheats, speed hack, etc.

You are not understanding how the seed is used in conjunction with the timestamp. The code will explain it in more detail.

I won't accept a proof until you post a paper with the formal specification of the problem, and prove using a proof assistant that your code follows that specification!

:P

Yeah "proof" is a strong word. The code itself doesn't prove anything, you'd have to prove it step by step yourself :P

The code will simulate a combat scenario using this system. It will show that the server can validate all of the client's actions, and detect ANY sort of change to the packet and timestamp.

"

ScrotieMcB wrote:

RNGs

Thanks ScrotieMcB, I certainly don't want to offend the only other person in this conversation, but I understand well enough what a RNG is, what a seed is, and how they are used.

If you would bear with me, a coin is a random number generator (in its own way). If movement is BASED on that coin flip, say forwards and backwards, how do I tell a mob to chase a character.

Mob.Position = MoveTo(Character.Position)

Function MoveTo(pos as Point) {
If (CoinFlip() == 1) {
move towards the player
}else{
move away from player
}

Imagine this mob on screen, it would be jittering back and forth trying to reach you!

That's the part I can't wrap my head around, using a constantly changing value to control the mobs movement is...difficult to say the least.

MeltingPoint, mob pathing only needs to use the random number once. It doesn't keep using it. It gets seeded like everything else.

"

qwave wrote:

MeltingPoint, mob pathing only needs to use the random number once. It doesn't keep using it. It gets seeded like everything else.

So all mobs use the same seed?

No, each mob generates it's own seed once.