Technical solution to eliminate desync in single-player sessions

Disclaimer: The official word from GGG is that this system would require too many changes to their current code in order to work. This thread has been completely de-railed. Apparantly every member of the PoE community is a senior network engineer. I've done my best, and I wash my hands of this madness.



Original post:


I believe that desync can be eliminated in single-player sessions / instances of Path of Exile, which is an important first-step in solving desync. Baby steps are necessary to solve the overall desync problem, and the simplest place to start is in situations where other players are not involved.

Although PoE is a multiplayer game, there are many times that people play in single-player sessions. For example, a majority of the races are solo, and eliminating desync/lag in these races would greatly improve their feasibility.

Throughout this post I will include excellent quotes from community members that have provided good feedback on the topic. If you feel that you have something worthwhile to contribute, please PM me with what you would like to add to this main post.

I even wrote some C# code to demonstrate this entire system from end-to-end. It uses a deterministic seed to produce a simulation that can remain in sync and unhackable:
http://pastebin.com/raw.php?i=PpkzipAS

The 'ServerValidate()' function represents the code that would be on Path of Exile's server to validate the player's actions.


PoE is not an MMORPG, it's a fast-paced action RPG

The client currently acts as a 'thin client' which is continually streamed the game state from the server. The client's only responsibility is to render the game state and send input to the server. The client performs very little actual calculations, and instead relies almost 100% on the server to validate the game state. This means that the server is likely running an ongoing simulation of the game instance and is continually notifying the client of changes to the state based on prediction. Even introductions of small amounts of latency can cause desyncs (forcing the game client to the current authoritative game state).

This is the common MMORPG design pattern due to the number of connected clients that are simultaneously affecting the world state.


The game client should have the ability to process the game simulation without ongoing feedback from the server.

This is a hard pill to swallow. We have all been told time and time again that the client can never be 'trusted'. It MUST receive all game state from the server, otherwise cheating is possible!

During this post, I need you to forget everything you think you know about online game networking. The industry has made significant advances in synchronizing game states, even as far as securing peer to peer play.

I am going to explain how this is possible, so I hope you are ready for some technical mumbo-jumbo.


I need you to think about these three points:

1. The server should be a referee.

2. A referee observes the game.

3. The referee blows his whistle when there is a foul.



What is the server's -current- role?

Currently, the Path of Exile server acts as a gateway for all game actions/outcomes. It attempts to simulate your actions and invoke them in an isolated environment. In practice, this sounds great for an online game. After all, why would we want the CLIENT making any 'decisions' for the actual gameplay? If the client were just 'playing the game', it could do absolutely anything it wanted.

The truth is, due to Path of Exile's fast-paced play, 'desync' happens frequently due to the server/client disagreeing on the game state due to latency. This is because they are constantly passing messages back and forth, struggling to maintain a consistent understood 'state'.



The client must send it's state to the server in order for the server to save/validate anything that's actually happening

Okay, so yeah, my client actually has to tell the server what's going on. But couldn't I just tell it anything I wanted? Why couldn't I just make things up? How does it know that im doing the things I say im doing?


"
HellGauss wrote:
There is no need of a 'realtime' running of instance on the server. Nobody is playing on the server and enjoying the game. The server should only check that the command of the client are legit. It is not the server that is moving monster, it is the client/server shared algorithm that do that.



The server sends the client a 'seed' at the start of the session.

This is more or less a 'password' that both the client and server know. This seed is used by the client to generate pseudo-random numbers. The client must use this seed to run the game's simulation. As you play the game, this seed is continually generating numbers in a deterministic (reproducible) manner.



What is this magic 'seed'? How does it work?

The seed allows both the client and server to run the game simulation under a similar pretense. In other words, the seed governs what happens during the actual gameplay, and is used to deterministically generate psuedo-random numbers. This means that the server is able to produce a similar outcome as the client.

So what all is this seed used to generate?
- Combat damage calculations
- Chance to hit calculations
- Mob pathing



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.

Both the client and server run the same simulation using the same seed, so the server can replicate the exact pathing of the mob.


"
ScrotieMcB wrote:
Making monster behavior deterministic, while at the same time pseudorandom, would not be very exploitable to hacking, but it would prevent desync by keeping the client simulation a consistent one-ping-time ahead of the server's true copy of the gamestate. Monsters would be less laggy, more fluid, and combat would seem less disjointed.



My input is not deterministic, so how does the server know that the seed is accurate once my input is added into the mix?

Your input does not modify the seed, but your resulting actions do. Your snapshot provides the server with enough information to reproduce your actions. Therefore, the server knows how many times the seed has been 'rolled'.


Even though my client is using this 'seed', how does the server act as a referee?

The server's role is to observe the game and 'blow the whistle' if it finds that your actions violate the rules of Path of Exile. The client will continually stream a 'snapshot' of his game state/input to the server. The snapshot contains the information that the server needs to reproduce the scenario that the client says he performed.

For example, if I cast raise skeleton, and then attack a rhoa, my 'snapshot' may include the raise skeleton spell/location, and the action that I attacked a rhoa. The server will use this information to simulate the exact same actions and attempt to validate whether this 'move' was valid.


"
SkyCore wrote:
The way i see it: in the games current state there is a lot of back and forth communication between the client and the server, since the server is virtually always out of synch with the client they regularly dont agree, when this happens the server asserts the game state resulting in rubberbanding and such.
With the proposed model this is as a whole eliminated since the server is basing its calculation on what the client has already done, here the client asserts the game state at all times. except when cheating is detected via an impossible action reflected in a snapshot.




Okay, so it's like chess then. The client makes a move, and then the server checks to make sure the move was valid.

Online games like Path of Exile are a bit more complicated than chess, but the principle is right. The server's only role is to ensure that the client is not making 'moves' that grossly violate the deterministic seed. Additionally, it also validates that the move is acceptable in the first place. The important thing to note is that the client does not need to send a 100% accurate representation of the state if the server allows for some extremely minor leniency on the output. In other words, if the player says he did 1385 damage, but the server determined he actually did 1384.2 damage, leniency can be used.

However, the client DOES need to send enough information that the server can reproduce the number of 'rolls' required on the seed. This is important because the server uses the deterministic seed to validate each action against each ->timestamp<-.



What about speed hacks? Why can't I just tell the server I am in a different location?

The server performs a 'delta' of each snapshot you send it to determine the amount of time that has passed. This delta compares the 'timestamps' between your snapshots. It uses your movement speed against the delta to determine if that distance could have been traveled in that amount of time. In other words, since your last packet, how much time has passed? You can use this algorithm to determine if the player could have feasibly moved to a given location in a certain amount of time.



Why can't I just tell the server im standing still, while I am actually attacking and killing mobs? In other words, im 'buffering' a series of actions and not telling the server until im ready.

Every snapshot must include a timestamp, which is the time that you performed the action. In other words, the timestamp must actually match the time that you attacked a creature. If you are standing still, then the client must send packets to the server that says you are standing still.



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.



Okay, so what if I die and just refuse to tell the server what happened?

Failure to send the server a snapshot in a timely manner will result in a 'disconnect'.
Since the server maintains the snapshots you have been sending it, it will simulate the game using the last known snapshot and recognize that your character died.

It's also worth noting that there may need to be a 'log out' / 'town portal' timer with 1-2 seconds of delay in order to prevent hacks from predicting death and instantly 'escaping'.


What about looting and crafting? Couldn't I optimize the rolls to generate better loot?

All non-combat/pathing related functionality is 100% server side. In other words, after you send a packet to the server indicating that you have attacked a mob, it will validate that action. If the mob dies, then the server will generate loot for you.

The same goes for crafting. All crafting / upgrading occurs exclusively on the server.



Is this a form of 'offline play'?

Not at all. The client must remain connected to the server at all times in order to stream the snapshot data. The server will be saving it and provide an authoritative simulation only when the client disconnects or there is a lapse in data. There is no system that guarantees cheat prevention if the client is offline.


Will desync still exist? If so, when will it happen?

Desync will still happen in the following scenarios:

- Your latency is so high that the server thinks you disconnected.
- The snapshot you sent to the server does not match the expectations of the server. This should only happen in situations where the client is cheating.


Couldn't software be used to generate optimal outcomes for things like crit?

Due to how the deterministic seed is generating various permutations, it would be virtually impossible to reliably create favorable outcomes. As long as the server mandates that the client continually streams a snapshot, there will be an extremely small window for hack software to evaluate the seeded data.

There are exceptions however. In certain boss fights such as Brutus (one on one fights), there may not be enough seed generations to produce enough entropy. This means that software may be able to reduce the amount of times they take critical damage in one-on-one fights. However, I think this is a very rare occurrence and would require extremely sophisticated software.

I think players would gain more of an advantage with the fact that they could actually dodge Brutus/Vaal attacks without having to worry about desync/lag!

I call this sort of thing a 'roll hack', because the client is basically standing around and waiting for the 'right time' to perform an action. Ultimately, GGG can minimize this by tweaking the way seeds are rolled. Ultimately, this trick can provide subtle benefits to the hacker, but it will not grant them 'god mode' or 'better loot'.


"
syrioforel wrote:

What's worse: auto-logout "hack" at 25% health, or anti-Kole crit hack?

"
qwave wrote:
Haha, something tells me that if an anti-Kole crit hack manifested itself the community wouldn't say: "OMG PLEASE BRING BACK DESYNC, PEOPLE ARE FARMING KOLE"




You're wrong, im super smart and can make a hack that crits more frequently.

If GGG wants to further prevent these sort of 'roll hacks', they could easily use heuristics to align the player's output with the given values. In other words, if your critical strike chance is 3%, but your character is magically critically striking 70% of the time, they can use heuristics to identify a problem. They have a few options in this situation:

- They can require more frequent / detailed snapshots from this client.
- They can revert that client to using the current game system.
- They can re-sync the client and align their critical strike chance accordingly.


Are there any other pros/cons to this proposed system?

As a result of implementing this system, Path of Exile would also gain:

- A full combat log, which many have asked for! This is because the client would be responsible for generating snapshots.

- A replay system, which I also believe would be absolutely amazing. The snapshots themselves are more or less 'replays' that contain the snapshot data, allowing the game client to 'play them back' at a later time.

- Reduced bandwidth and costs. This is because the server would not need to continually process state data and send it back to the client. It would only need to evaluate the state once.

- Happier players and more revenue! The desync and lag has caused a lot of complaints from the community, especially on hardcore. I believe that by reducing the number of desync deaths, the playerbase will expand.


What happens if other players enter the instance? How can multiplayer desync be improved?

Once another player enters the zone, the server will need to immediately perform the authoritative game state check. Once multiplayer is a factor, the above solution is not optimal, and will need to revert to the current architectural approach.

This topic is not designed to address desync issues during multiplayer play. Synchronization in multiplayer scenarios is far more complex, and reflects the development team's current approach to the network architecture. This game was obviously meant for multiplayer, but many people play solo, especially when leveling up and during races. Personally, I believe that desync is -less- of an issue in multiplayer because there are other players to support you.



Can this even be implemented? Does the PoE engine support these types of changes?

That's up to GGG to decide. This synchronization system can run alongside their existing one. They need to provide the client with the ability to simulate the game, and then add an API call on the server for snapshot validation. Rhys_GGG has responded numerous times with critical feedback, and I have responded to each and every issue with a resolution. I believe that the proposal is evolving to a form that GGG should at least consider.

"
LogoOnPoE wrote:
The additional work on the server is unknown, but considering Rhys's responses, it's not an apparent problem. As I previously stated, unless Rhys comes and says that it's too much of an additional load, we cant assume that it's a reason to discard the idea.



To further support this proposal, a user named ungalunga has informed me that he had a similar idea back in May. Here is his post:
http://www.pathofexile.com/forum/view-thread/616/page/2#p3230716

Although it specifically targets offline play/replays, the concept is very similar. My approach mainly aimed at eliminating desync while still preventing cheats/hacks.

There is also a white paper which describes the technique to evaluate these snapshots to prevent cheating:
http://www.cs.cuhk.hk/~cslui/PUBLICATION/ms2008.pdf
Last edited by qwave on Nov 23, 2013, 5:52:45 PM
It isn't quite so easy for the server to magically recognize if someone was using speed/teleport hacks during their session, when you give the client full authority. The idea of being able to just roll back their stats wouldn't be so simple. You'd basically just be saying, "No desync in singleplayer, and its okay if you cheat too." which of course would give the edge to those cheating.
"Danger is like jello, there's always room for more."
http://www.twitch.tv/vejita00
Last edited by CliveHowlitzer on Nov 18, 2013, 12:33:11 AM
The server can easily take a snapshot of the character's state once they enter the instance.

The client continually sends snapshots to the server, which includes timestamps and seeds. The server does not validate this until -after- the client leaves the instance.

Therefore, the speed hacks would be detected after the player left the instance, which means the server could then flag the account and perform the rollback. Since the account was found cheating, the server could then perform a ban/review of the account. You can easily identify speed hacks because the snapshot log would indicate that the player moved from X position to Y position in Z time. Any discrepancy in the snapshot is unacceptable because the client does not experience latency when it is authoritative.

The problem is that the server is performing authoritative checks during the gameplay, which I feel is 100% unnecessary.
Last edited by qwave on Nov 18, 2013, 12:35:23 AM
"
qwave wrote:
II. Client should be a full authority during single player instances
No, it shouldn't. You don't trust the client to tell you which items were found, whether it died, or how much XP was earned. Trusting the client at all is just opening the door to item duping and turning ladder competitions into a farce.

I know desync sucks, but from a security perspective, full server authority is the only smart way to go.
"
qwave wrote:
The server can easily take a snapshot of the character's state once they enter the instance.

The client continually sends snapshots to the server, which includes timestamps and seeds. The server does not validate this until -after- the client leaves the instance.
What you are describing is just a reversal of the current roles. What would then happen when the server is experiencing desync? And if the answer to that question is in any way tolerant, what is to stop hackers from exploiting it by manufacturing desync?
When Stephen Colbert was killed by HYDRA's Project Insight in 2014, the comedy world lost a hero. Since his life model decoy isn't up to the task, please do not mistake my performance as political discussion. I'm just doing what Steve would have wanted.
Last edited by ScrotieMcB on Nov 18, 2013, 12:38:19 AM
"
No, it shouldn't. You don't trust the client to tell you which items were found, whether it died, or how much XP was earned. Trusting the client at all is just opening the door to item duping and turning ladder competitions into a farce.


Perhaps you didn't read my entire post. The client is only trusted to generate the snapshot. Once the player leaves the instance, the entire snapshot is reviewed authoritatively by the server. Item duping would not be possible. Experience/items could be held authoritative by the server. The timestamp/seed guarantees that the client's snapshots are generated accurately because the server can reproduce the exact simulation in a deterministic manner.



"
What you are describing is just a reversal of the current roles. What would then happen when the server is experiencing desync? And if the answer to that question is in any way tolerant, what is to stop hackers from exploiting it by manufacturing desync?


The server cannot experience 'desync'. It will receive a full snapshot of the game state and review it once the player leaves the instance. Hackers cannot manufacture desync because their client is authoritative and unable to desync.
Last edited by qwave on Nov 18, 2013, 12:40:21 AM
"
qwave wrote:
The timestamp/seed guarantees that the client's snapshots are generated accurately because the server can reproduce the exact simulation in a deterministic manner.
LOL no. Any communication from the client can be manufactured by hack instead of being legitimate, and any communication received by the client can be used by the hack to manufacture that communication.
When Stephen Colbert was killed by HYDRA's Project Insight in 2014, the comedy world lost a hero. Since his life model decoy isn't up to the task, please do not mistake my performance as political discussion. I'm just doing what Steve would have wanted.
"
LOL no. Any communication from the client can be manufactured by hack instead of being legitimate, and any communication received by the client can be used by the hack to manufacture that communication.


The server would identify the hack because the client could only cheat by generating data that is outside the scope of the deterministic seed. In other words, if your next hit is supposed to do 150 damage, and your hacked snapshot says you did 1000 damage, the server would be able to deterministically evaluate that this was not properly generated.

The main emphasis is that instead of doing constant checks for 'hacks', the state only needs to be evaluated once the player has left the instance (or another has entered)
Last edited by qwave on Nov 18, 2013, 12:44:32 AM
"
qwave wrote:
"
LOL no. Any communication from the client can be manufactured by hack instead of being legitimate, and any communication received by the client can be used by the hack to manufacture that communication.


The server would identify the hack because the client could only cheat by generating data that is outside the scope of the deterministic seed. In other words, if your next hit is supposed to do 150 damage, and your hacked snapshot says you did 1000 damage, the server would be able to deterministically evaluate that this was not properly generated.


What if the spell says I can deal between 100 and 300 damage and then I hack so that it always deals 300 damage and never 100 damage. How will the server know that I didn't tamper with the RNG rolls?

Analogously: how will the server know I didn't tamper with the RNG while crafting (gambling) in an instance?
This message was delivered by GGG defence force.
Last edited by mazul on Nov 18, 2013, 12:46:27 AM
"
What if the spell says I can deal between 100 and 300 damage and then I hack so that it always deals 300 damage and never 100 damage. How will the server know that I didn't tamper with the RNG rolls?


The snapshot you are generating must adhere to the deterministic seed that the server sent at the start of the instance. This means that each random number can be validated by the server. This is the mathematical nature of a random seed. In other words, your client would roll the same value that the server would roll using that seed.
"
mazul wrote:
"
qwave wrote:
"
LOL no. Any communication from the client can be manufactured by hack instead of being legitimate, and any communication received by the client can be used by the hack to manufacture that communication.


The server would identify the hack because the client could only cheat by generating data that is outside the scope of the deterministic seed. In other words, if your next hit is supposed to do 150 damage, and your hacked snapshot says you did 1000 damage, the server would be able to deterministically evaluate that this was not properly generated.


What if the spell says I can deal between 100 and 300 damage and then I hack so that it always deals 300 damage and never 100 damage. How will the server know that I didn't tamper with the RNG rolls?

Analogously: how will the server know I didn't tamper with the RNG while crafting (gambling) in an instance?



If I initialize two PRNG states with the same seed, they always produce the same values. If the server transmits the seed to the client, the server can verify that all RNG rolls the client reported back were the correct ones.

It seems like this would require a *very large amount* of logging to do what the OP suggests. Furthermore, if the random seed -> game state correspondence could be reverse engineered that would be very bad.
IGN: SplitEpimorphism

Report Forum Post

Report Account:

Report Type

Additional Info