April 07, 2024

Mental Poker Part 6: Shuffling Implementation

For an overview on Mental Poker, see Mental Poker Part 0: An Overview. Other articles in this series: https://vladris.com/writings/index.html#mental-poker. In the previous post in the series we covered the state machine we use to implement game logic.

We now have all the pieces in place to look at a card shuffling algorithm. Shuffling cards in a game of Mental Poker is one of the key innovations for this type of zero-trust games. We went over the cryptography aspects of shuffling in Part 1.

Let's review the algorithm:

At this point the cards are shuffled. In order to play, Alice and Bob also need the capability to look at individual cards. In order to enable this, the following steps must happen:

If Alice wants to look at a card, she asks Bob for his key for that card. For example, if Alice draws the first card, encrypted with \(K_{A_1}\) and \(K_{B_1}\), she asks Bob for \(K_{B_1}\). If Bob sends her \(K_{B_1}\), she now has both keys to decrypt the card and look at it. Bob still can't decrypt it because he doesn't have \(K_{A_1}\).

This way, as long as both Alice and Bob agree that one of them is supposed to see a card, they exchange keys as needed to enable this.

Implementation

While we covered the algorithm before, we didn't have the infrastructure in place to implement this. We now do.

Types

We'll start by describing our shuffle actions. As we just saw in the above recap, we have 2 steps:

type ShuffleAction1 = BaseAction & { type: "Shuffle1"; deck: string[] };
type ShuffleAction2 = BaseAction & { type: "Shuffle2"; deck: string[] };

We only need to pass around the deck of cards (encrypted or not), so we extend the BaseAction type (which includes ClientId and type) to pin the type and add the deck.

We need more data in the context though:

type ShuffleContext = {
    clientId: string;
    deck: string[];
    imFirst: boolean;
    keyProvider: KeyProvider;
    commonKey?: SRAKeyPair;
    privateKeys?: SRAKeyPair[];
};

We need to know our clientId, whether we are first or second in the turn order, we need a keyProvider to generate encryption keys, a commonKey (that's for the first encryption step) and privateKeys (for the second encryption step). We'll use the context later on, when we stich everything together. Before that, let's look at the basic shuffling functions.

Shuffling primitives

First, we need a function that shuffles an array:

function shuffleArray<T>(arr: T[]): T[] {
    let currentIndex = arr.length,  randomIndex;
  
    while (currentIndex > 0) {
  
      randomIndex = Math.floor(Math.random() * currentIndex);
      currentIndex--;
  
      [arr[currentIndex], arr[randomIndex]] = [arr[randomIndex], arr[currentIndex]];
    }
  
    return arr;
};

We won't go into the details of this, as it's a generic shuffling function, not specific to Mental Poker, but a required piece.

Let's look at the two shuffling steps next. First step, in which we shuffle and encrypt all cards with the same key:

async function shuffle1(keyProvider: KeyProvider, deck: string[]): Promise<[SRAKeyPair, string[]]> {
    const commonKey = keyProvider.make();

    deck = shuffleArray(deck.map((card) => SRA.encryptString(card, commonKey)));

    return [commonKey, deck];
};

The shuffle1() function takes a keyProvider, a deck, and returns a promise of a shuffled deck plus the key used to encrypt it.

The function is pretty straight-forward: we generate a new key, we encrypt each card with it, then we shuffle the deck. We return the key and the now shuffled and encrypted deck.

Both players need to perform the first step, after which both Alice and Bob have encrypted the deck with \(K_A\) and \(K_B\) respectively, so neither knows the order of the cards.

The next step, according to our algorithm, is for each player to decrypt the deck with their key and encrypt each card individually with a unique key:

async function shuffle2(commonKey: SRAKeyPair, keyProvider: KeyProvider, deck: string[]): Promise<[SRAKeyPair[], string[]]> {
    const privateKeys: SRAKeyPair[] = [];

    deck = deck.map((card) => SRA.decryptString(card, commonKey));

    for (let i = 0; i < deck.length; i++) {
        privateKeys.push(keyProvider.make());
        deck[i] = SRA.encryptString(deck[i], privateKeys[i]);
    }

    return [privateKeys, deck];
}

shuffle2() is also fairly straight-forward. It takes the commonKey from step 1, a keyProvider, and the encrypted deck.

First, it decrypts all cards using the commonKey (note the cards are still encrypted by the other player). Next, it uses the keyProvider to generate a key for each card, and encrypts each card with the key. The function returns the private keys generated, and the re-encrypted deck.

We now have all the basics in place. Here's how we put it all together:

Shuffling state machine

Here is the state machine that describes the shuffling steps:

function makeShuffleSequence() {
    return sm.sequence([
        sm.local(async (queue: IQueue<ShuffleAction1>, context: ShuffleContext) => {
            if (!context.imFirst) {
                return;
            }

            [context.commonKey, context.deck] = await shuffle1(context.keyProvider, context.deck);

            await queue.enqueue({
                type: "Shuffle1",
                clientId: context.clientId,
                deck: context.deck,
            });
        }),
        sm.transition(async (action: ShuffleAction1, context: ShuffleContext) => {
            if (action.type !== "Shuffle1") {
                throw new Error("Invalid action type");
            }

            context.deck = action.deck;
        }),
        sm.local(async (queue: IQueue<ShuffleAction1>, context: ShuffleContext) => {
            if (context.imFirst) {
                return;
            }

            [context.commonKey, context.deck] = await shuffle1(context.keyProvider, context.deck);

            await queue.enqueue({
                type: "Shuffle1",
                clientId: context.clientId,
                deck: context.deck,
            });
        }),
        sm.transition(async (action: ShuffleAction1, context: ShuffleContext) => {
            if (action.type !== "Shuffle1") {
                throw new Error("Invalid action type");
            }

            context.deck = action.deck;
        }),
        sm.local(async (queue: IQueue<ShuffleAction2>, context: ShuffleContext) => {
            if (!context.imFirst) {
                return;
            }

            [context.privateKeys, context.deck] = await shuffle2(context.commonKey!, context.keyProvider, context.deck);

            await queue.enqueue({
                type: "Shuffle2",
                clientId: context.clientId,
                deck: context.deck,
            });
        }),
        sm.transition(async (action: ShuffleAction2, context: ShuffleContext) => {
            if (action.type !== "Shuffle2") {
                throw new Error("Invalid action type");
            }

            context.deck = action.deck;
        }),
        sm.local(async (queue: IQueue<ShuffleAction2>, context: ShuffleContext) => {
            if (context.imFirst) {
                return;
            }

            [context.privateKeys, context.deck] = await shuffle2(context.commonKey!, context.keyProvider, context.deck);

            await queue.enqueue({
                type: "Shuffle2",
                clientId: context.clientId,
                deck: context.deck,
            });
        }),
        sm.transition(async (action: ShuffleAction2, context: ShuffleContext) => {
            if (action.type !== "Shuffle2") {
                throw new Error("Invalid action type");
            }

            context.deck = action.deck;
        })
    ]);
}

Note we are limiting this to a 2-player game, though we can easily generalize to more players if needed.

This is a longer function so let's break it down:

At this point, both players performed the first step of the shuffle, so the deck is encrypted with \(K_A\) And \(K_B\) and neither players knows the turn order. We move on to the second step of the shuffle, where each player calls shuffle2() to decrypt the deck and re-encrypt each individual card. Again, depending on whether we are first or not, we take action or wait:

A helper function to run this state machine given an async queue:

async function shuffle(
    clientId: string,
    turnOrder: string[],
    sharedPrime: bigint,
    deck: string[],
    actionQueue: IQueue<BaseAction>,
    keySize: number = 128 // Key size, defaults to 128 bytes
): Promise<[SRAKeyPair[], string[]]> {
    if (turnOrder.length !== 2) {
        throw new Error("Shuffle only implemented for exactly two players");
    }

    const context: ShuffleContext = { 
        clientId, 
        deck, 
        imFirst: clientId === turnOrder[0],
        keyProvider: new KeyProvider(sharedPrime, keySize)
    };
    
    const shuffleSequence = makeShuffleSequence();

    await sm.run(shuffleSequence, actionQueue, context);

    return [context.privateKeys!, context.deck];
}

We need our clientId, the turn order (whether we go first or not), a shared large prime (to seed other encryption keys), an unshuffled deck, a queue, and, optionally, a keySize.

From the input, we create a ShuffleContext with the required data, then we generate the state machine by calling the function we discussed previously, and we run the state machine using the given actionQueue and generated context.

We return the private keys with which we encrypted each individual card, and the shuffled and encrypted deck.

Notes on performance

Shuffling a full deck of 52 cards with large enough key sizes gets noticeably slow. Note that we need to generate an encryption key for each card, which involves searching for large prime numbers. The more secure we want the encryption to be, the larger the number of bits we want in the key, the longer it takes to find a key.

This can be mitigated with some loading/progress UI while shuffling. For the demo discard game in mental-poker-toolkit, I used a smaller deck (only cards from 9 to A) and a smaller key size (64 bits).

When implementing a game, it might be a good idea to start generating encryption keys asynchronously as soon as possible - note though that the players need to agree on a shared large prime before key generation can begin.

Summary

In this post we looked at an implementation of card shuffling.

The Mental Poker Toolkit is here. This post covered card shuffling, which is implemented in the primitives package in shuffle.ts.