This post refers to my game, CubeDance, and its predecessor BlockMatrix (no longer available). Give CubeDance a play at cube.dance!

I built CubeDance mostly last year, in 2022, but am finally posting about it because I set up my blog.

The origin of the game

The game started as a project I built back in 2019. At the time, it was called BlockMatrix.

It used a library I made called Canvax for rendering and representing game entities for collision detection.

Deciding to revisit BlockMatrix

It’s concerning how much games rely on client-side anti-cheat these days. It’s a cat-and-mouse game between anti-cheat makers and game cheaters, and anti-cheats keep getting closer and closer to ring 0, resulting in tangible security issues for users.

My impression is that games use client-side anti-cheat because creating game-tailored server-side anti-cheat costs engineer hours while off-the-shelf client-side anti-cheats are straightforward to add to otherwise unsecured games.

So I had the fun idea to make a reasonably well-secured game using a strong server-side anti-cheat which reproduces submitted games.

And I decided to do so by making some upgrades to BlockMatrix, and to put it to the test by adding a public-facing leaderboard.

Building a deterministic game

Creating a deterministic (seeded) pseudorandom float64 generator

To generate pseudorandom float64 values for the game from a seed, I first implemented PseudorandomReader (implementing io.Reader) which would:

1. Initialize an XChaCha20 stream cipher by SHA3-512ing the provided seed to create a key and nonce. (This isn’t intended to stretch the seed and isn’t a substitute for using securely generated high-entropy seeds.)
2. When read from, encrypt zeroes (i.e. XOR the keystream with zeroes, outputting the keystream.)

Then, using the PseudorandomReader, a wrapper could be created specifically for compatibility with rand.Source, so we can generate pseudorandom values such as float64s. The wrapper is called PseudorandomSource.

I put the implementations for PseudorandomReader and PseudorandomSource into a library, gopherng.

Here’s how the library can be used to generate float64s by creating a rand.Rand from a PseudorandomSource:

1
2
3
4
5
6
7
8
9

// Create PseudorandomSource with a seed. Use a random high-entropy seed
// in most real use cases.
s := gopherng.NewSource([]byte{1, 2, 3, 4, 5, /* ... */})

// Create a rand.Rand from the Source.
r := rand.New(s)

fmt.Println(r.Float64())
// => 0.7124063346129034

Encapsulating the game

In the original game, game state was kept in the global scope. For this project, my goal was to fully encapsulate the game.

This involved creating a Game class which looked vaguely like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Game represents a CubeDance game. It has an internally maintained
// state.
class Game {
    // Initialize a Game with the given properties.
    constructor (width, height, randomValues, metadata)

    // Run a game tick with the given held keys.
    tick (heldKeys)

    // Render the current game state using the provided Canvax renderer.
    render (renderer)

    // Export the game initialization parameters and player behaviors.
    export()
}

The Game class has a state property including score and other game details like living entities.

Most of the original code was put into the tick function (or related functions) and the constructor without much modification at all.

I will explain the use of the metadata constructor argument soon.

During the game, the Game instance keeps track of player key presses (start tick and end tick) in order to provide them in the game export. The game export includes the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// GameExport represents all information about a CubeDance game,
// allowing it to be simulated.
type GameExport struct {
    Version      int          `json:"v"`
    Width        int          `json:"w"`
    Height       int          `json:"h"`

    // Ticks is the number of ticks for which the game ran. (This is
    // validated on the server.)
    Ticks        int          `json:"t"`

    // RVCount is the number of random values generated originally for
    // the game.
    RVCount      int          `json:"rvc"`

    // Initialized is the time at which the game was initialized.
    Initialized  time.Time    `json:"i"`

    // Events is a slice of of GameEvent (key presses), which includes
    // key, start tick, and end tick.
    Events       []*GameEvent `json:"e"`

    // Metadata is sent by the server and is sent back when submitting
    // a game.
    Metadata     []byte       `json:"m"`
}

Why not give the client the seed?

You might notice that the export doesn’t appear to include the game seed and that the Game constructor accepts an argument randomValues (which is indeed a list of pseudorandom values).

The seed is actually included in the Metadata field, but is encrypted and not visible to the client.

I ended up going this route for two reasons:

Firstly, the JavaScript SubtleCrypto library only offered hash functions as async functions, and async is contagious. I didn’t want the tick function to become async because that would complicate running the simulation on the server (which is done using a library providing V8 bindings for Go).

I looked to figure out if this was possible, and when I searched things like “js call async function synchronously”, I mostly saw people recommending propagating async/await forward rather than actually answering the question. It seemed inefficient to get around this limitation so I decided to go the way I did.

And secondly, there may be security considerations involved with making the seed available. See the discussion on cherry picking game initializations for more details on this.

Bucketing the random values provided

Originally I was imagining a competitive mode to CubeDance where there would be a daily-resetting random game seed and leaderboard, so all players are on an equal footing and competing to get the best score in the same exact game (same enemy spawn locations, same powerups, etc). I didn’t implement this feature, but I wanted to support it.

Inside the original game code were a bunch of calls to Math.random(), which generates a pseudorandom float value. But now we are given a list of random values.

One option was to simply create a helper function to get the next random value from a single random value (RV) bucket stored in the Game instance. This has a flaw though: depending on the order of RV-consuming events of different types (enemy spawn vs powerup spawn, for example), the game can become completely different, especially if different types of RV requesters need different numbers of RVs.

I decided to put the RVs into buckets for each discrete game event that uses RVs, solving this problem.

Adding simulation helper functions

Additionally, I added some helper functions to the game.js file (where the Game class was located) to help with simulating the game, including one like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// simGame runs a game simulation, returning the created Game after it
// ends.
export const simGame = (exp) => {
    const g = new Game(exp.w, exp.h, exp.rv, {}, /*...*/)

    for (let i = 0; i <= exp.t; i++) {
        // Determine pressed keys at the current tick.

        const keysPressed = exp.keystrokes
            .filter((e) => e.startTick <= i && e.endTick > i)
            .map((e) => e.key)

        g.tick(keysPressed)

        if (g.state.ended) {
            break
        }
    }

    return g
}

This simulation function creates a Game using the initialization options from the given export, then calls tick() until the game ends, for each tick determining which keys were pressed according to the export and providing those.

When the function returns, the game has ended (or at least the expected tick count was reached), so we can use the returned Game’s state to determine the verified score and other game properties (on the server.)

Additionally, I added another simulation function which takes a renderer argument as well. This one is used to render game replays for the leaderboard!

Adding a time limit

To prevent simGame from simulating a potentially very large of ticks wherein the player does nothing, a gameplay change was made.

A limit was added on inactive time, ending the game if the player doesn’t collect a point, collect a powerup, or destroy an enemy for a while. The timeout time is determined dynamically depending on the number of enemies present.

Building the game for use in backend

Bundling the game for frontend was pretty straightforward using Webpack.

For backend use (as a library) I used Rollup to bundle the Game class JavaScript, the simGame function mentioned earlier, and dependencies such as Canvax into a standalone JavaScript library.

This library is called on the server by running it in a V8 context.

Implementing the backend

I wanted to store previous games and build the leaderboard from games in the database, so I decided the server would simulate all received games and save the verified results.

Initializing a game

The server needs to provide the random seed for the RNG and also the fixed properties that should be consistent across games, such as width and height.

This is the data I had the server return to the frontend in response to game initialization requests:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// GameInit represents initialization data for a CubeDance Game.
type GameInit struct {
    Width    int       `json:"w"`
    Height   int       `json:"h"`

    // RVs includes the random float64 values for the game.
    RVs      []float64 `json:"rv"`

    // Metadata is the encrypted metadata blob provided by the server
    // with verified game information.
    Metadata []byte    `json:"m"`
}

The metadata is where things get more interesting.

I decided not to store a game in the backend until it is later submitted to the server, so I added information just for the server’s use to the encrypted metadata.

Here is the metadata struct:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

type GameMetadata struct {
    // GameID is the pre-determined random UUID for the game.
    GameID            []byte    `json:"gid"`

    // Seed is the randomly generated seed for the game's random
    // generator.
    Seed              []byte    `json:"s"`
    
    // RandomValuesCount is the number of random values included in the
    // game init response.
    RandomValuesCount int       `json:"rvc"`

    Width             int       `json:"w"`
    Height            int       `json:"h"`

    // Additional fields for later use, including the timestamp of game
    // initialization and more.
}

Some of these fields are later used by the server when storing a completed game in the database.

When initializing a game, a GameMetadata is generated, serialized as JSON, and then encrypted and authenticated with XChaCha20-Poly1305 using a random nonce.

The ciphertext and nonce are then serialized to JSON and base64’d in the final GameInit response.

The GameInit data is returned to the client and is enough to get a game started, even when the GameMetadata data is kept secret.

On cherry picking of game initializations

The game initialization endpoint is rate limited to make mass generation of random values in order to cherry pick a game matching specific qualifications a bit slower.

There may be more room for improvement here. One thought is that cherry picking could be prevented by continuously verifying the gameplay (similarly to how we do in the submit endpoint below, but also tracking the consumption of RVs) and providing random values for each RV bucket as needed and only if all conditions are met:

1. The correct amount of time has elapsed, according to the simulated game’s tick count.
2. The game has indeed consumed all RVs provided thus far and immediately needs more, or the number of unconsumed provided RVs has dwindled to some threshold.

We can verify condition 2 by adding a new RV request method to Game, with signature getRVs(bucket) and a new simulation function for determining RV need, simGameVerifyRVNeed(exp, getRVs, ...) where getRVs(bucket) is a function returning RVs for the requested bucket.

The simulation function will work as follows:

1. Simulate the game thus far (until the current tick is reached or the game ends), requesting RVs as needed.
2. If the simulation runs out of RVs, end the game.
3. Return the remaining RV count and number of RVs consumed for each bucket as a map.

Using this simulation function, the server can verify RV consumption and return the correct RVs needed.

This would be a pretty good solution to this issue, because someone would need to be playing the game in order to be provided with additional RVs to keep playing.

Submitting a game

The client submits a game by sending a game submit message:

1
2
3
4

struct {
    Score      int                  `json:"score"`
    GameExport *gamedata.GameExport `json:"x"`
}

The server evaluates the provided game export approximately like so:

1. Decrypt the game metadata and confirm that the values in the provided GameExport align with it.
2. Generate RVs for the game from the seed in the metadata and set the RVs in the GameExport.
3. Create a v8go Context in a new Isolate.
4. Evaluate the Rollup-bundled version of the Game class and simGame function (as described above) so they exist in the Context.
5. Convert the GameExport into a v8go Value.
6. Call simGame with the export.
7. Inspect properties of the returned game state object as needed, specifically returning score, tick count, and whether the game ended.

It will then save the game according to the game ID included in the game’s metadata, and if the verified score is leaderboard-qualifying, let the client know so it can add a name to its leaderboard entry.

Importantly, saving the game according to the game ID in its GameMetadata makes it trivial to prevent submitting a game more than once.

Trying it out with valid and cheated games

You might wonder why the Score field is in the game submit message. I added it not because that is considered in any way during game submission, but because I wanted to log it to see when anyone tried to claim an incorrect score.

Here’s what a legitimate game log looks like:

1
2
3
4

2023/10/11 03:51:32 Got game gid:e7a77c03...
    score:11 (claim 11),
    ticks: 1931 (claim: 1930),
    ended:true

Note that the actual score (score) and claimed score (claim) are equal.

Now for an illegitimate game log:

1
2
3
4

2023/10/11 03:56:12 Got game gid:21701c95...
    score:1 (claim 12),
    ticks: 214 (claim: 1894),
    ended:true

For this illegitimate game, I modified the Game implementation on the client so that the player could only be eliminated by an enemy if the score was greater than 10. I then played, running into an enemy after scoring 1 point, and due to the local change I didn’t lose and was able to keep playing.

The server simulated the game and ended it earlier than I did, with an actual score of 1 versus my claimed score of 12, because it was running my inputs against the official version of the game.

So this worked successfully and keeps cheaters off the leaderboard! (See limitations below.)

Limitations

In addition to the areas for consideration mentioned above, there are some types of attacks against the game that aren’t (fully or at all) prevented currently:

• Time dilation and retakes: The potential to dilate time and/or retake parts of a game can likely be prevented by checking the game generation timestamp in the GameMetadata against the submission time on game submission to make sure the time taken is reasonable considering the tick count and standard game tick rate.
• Player assist / AI player: Automated detection of assistance (for example, automated movements canceling out velocity) may be possible, but requires additional consideration. This is an issue all games, even those using client-side anti-cheat, may face.
• Game initialization farming / cherry picking: An adversary could spam the game initialization endpoint with requests, cherry picking a game initialization which has favorable random values. This is partially mitigated by rate limiting, and additional options for improvement are discussed above.

Congratulations to Vadim Pelyushenko (Discord: _jarl) for successfully using time dilation in order to win the CubeDance CTF I hosted earlier this year!

Result

Importantly and fundamentally, we know that games on the leaderboard are valid (including initialization parameters) and that their scores are accurate! This is an effective start towards securing the game!