a scheme for cheating-resistant racing games

the general type of game this is for is single-player time-trial racing games. akin to defrag, trackmania, etc.

i’m also assuming that the game is deterministic, and that a “replay” in the game is purely a series of inputs that can be automatically validated. that’s not trivial work to do, but it’s not particularly difficult.

once you have a deterministic engine, then you already prevent cheating by doing things that are impossible.

the specific attack this is meant to protect against is “just make a TAS and replay it”, which was demonstrated in Malleo - Building an Undetectable Cheating Device for Mario Kart Wii. the solution used there depends on the code being closed source, which kinda fucking sucks, and is fragile against someone just putting in the effort to reimplement the game without the checks.

notably, this is not a probabilistic “just look at the inputs and see if they “look suspicious”“ method.

Servers Needed

Both kinds of servers here do exist already, so no additional setup is needed :)

Though a game community can of course set up additional servers of this type (which can then be used by any game).

The beacon and the timestamp server need to be trusted by whatever leaderboard you choose to submit to.

Randomness Beacon

The tweak value for a run here is provided by an Interoperable Randomness Beacon. This provides a random value every 60 seconds.

Timestamp Server

This is more commonly known. Just use RFC 3161 servers.

Scheme

When a client wants to do a run, it will first ask the Randomness Beacon for this minute’s random value. That will be used as a value to tweak the physics during the run (in a game-specific way). The whole (signed) response will be saved to be later included in the replay file.

The client will do the run. The physics tweaks are meant to be imperceptible for non-TASses, but butterfly-effect to desync a TAS.

Once the run is finished, the client makes an initial replay file. This contains all the data needed to verify the run, such as the full list of inputs and the map the run was performed on (or, at least, a hash of the map or a unique identifier). It also includes the full randomness beacon response, in order to pin down a time of when the run must have been started after.

Data that is not needed to verify the run should not go in this initial replay file. This includes the player name, any custom skins the player may be using, or anything else of the sort. This ensures that such data can be changed after a replay is made without invalidating it. No point in forcing a player to stick with a deadname for old replays when they could be rewritten :).

After that, the client will then hash then timestamp the initial replay file using a timestamping server. This pins down a time when the run must have been finished by.

Finally, the signed timestamp can be included into an outer replay file, along with any other metadata (player name, comments, skins) that don’t affect the validity of the run.

Privacy

The servers don’t directly receive any sensitive information.

The Randomness Beacon doesn’t get sent any user information, and its responses can be cached/proxied easily enough.

The Timestamp Server does get sent a hash of the replay file, so could correlate the IP that connected to it to a replay file, if that replay file is discovered in future. But it can be easily proxied.

Since signed documents for the start and end time are in the replay file (we assume the verifier knows the public keys for the servers), verification requires no network access.

This scheme does leak when the run was done. This is likely acceptable, especially since the common case of “do this, then upload it to a leaderboard server” also does that.

Attacks

There are some cheating methods that this cannot prevent.

Firstly, the limited resolution of the start/end time allows for playing in slow motion to some extent, or to rewind silently. Not a ton you can do about that. You still need to be a good player to set a great time in slow motion, and you can still look at the inputs (you need to play in slow motion and have natural-enough inputs)

A tool might be made that can play a track automatically. Doing this while also evading manual inspection, if you’re going for world records, seems unlikely, since the inputs will very likely look obviously wrong.

A crafted TAS might try to have inputs in such a way that it’s naturally resistant to desyncs. Maybe.

Someone might just be trying a TAS (or even a pool of TASes) every minute for a popular track, submitting whichever one happens to finish with a good time without desyncing badly enough. For this attack, changing every minute rather than every second is a benefit, since it means there’s less chances for an attacker to get lucky. It would be game-specific how well this works, but if the tweaks are done constantly, it seems unlikely that a TAS not designed for the specific tweak value could finish.

Hostile Randomness Beacons or Timestamp Servers can both completely remove the security here, by allowing a run to be started with a tweak that was known well in the past, or to backdate a run.

One mitigation could be to use multiple independent servers, and define the timestamped start/end time as the widest possible range. This isn’t too hard for Timestamp Servers, plenty of those exist, but Randomness Beacons are more obscure. (Though at least for Randomness Beacons, proving misbehavior is easier, because of the hash chaining property).

Downsides

The main downside of this method is that you can’t do a run completely offline. It is tolerant to very slow internet, but you do need some active internet connection, and the two servers involved (but not a game-specific leaderboard server!) need to be available.

I can’t think of a way to do this style of anticheat without requiring an internet connection. You can allow reasonably large margins so that clients can use cached beacons and timestamp a run when they get back online, but that would open up the possibility of just making a TAS in that time, or making a segmented run / playing in slow motion with rewinding.