Keno

To draw ten numbers from forty, the library shuffles all forty, keeps the first ten and sorts them. With the public inputs below, that's 7, 10, 11, 17, 22, 26, 28, 32, 33 and 36.

Holding a Keno record? result is the list of drawn numbers, smallest first. Your hits are the numbers on your ticket that are also in that list. What the hits paid is the site's own table and isn't part of the record. The verifier will tell you whether the list came from the seeds, and for most readers that's the whole job. One warning before you go: the record doesn't keep the order the numbers came out in. More on that below.

How the Draw Is Calculated

The shuffle is Fisher-Yates, run from the back.

1. Write the numbers 0 to 39 in a row.
2. Stand on the last position, 39. Take the next float, multiply it by 40 and floor it. That gives a position from 0 to 39. Swap the two entries.
3. Step down to position 38 and repeat with the next float, multiplying by 39 this time. Keep going until position 1, where the multiplier is 2.
4. Take the first draws entries, add 1 to each so they run from 1 to 40, and sort them.

Position 0 has nothing left to swap with, so forty entries need 39 floats. A digest holds eight. That makes five digests, cursors 0 to 4, with the fortieth float read and thrown away.

import { deriveFloats } from '@galabet/fair';
import { keno, shuffle } from '@galabet/fair/games';

const seeds = {
  serverSeed: '5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d',
  clientSeed: 'galabet',
  nonce: 42,
};

const { floats, cursor } = await deriveFloats(seeds, 39);
console.log(floats.length, cursor);

const row = shuffle(floats, 40).map((entry) => entry + 1);
console.log(row.slice(0, 10).join(' '), '|', row.slice(10).join(' '));
console.log(keno(floats).join(' '));

39 4
28 33 17 32 11 26 36 10 7 22 | 39 8 25 37 1 34 3 29 35 24 40 4 21 38 27 12 6 15 19 16 13 14 20 30 18 9 31 2 5 23
7 10 11 17 22 26 28 32 33 36

Everything left of the bar is the draw. The last line is the same ten numbers after sorting, and that's what play returns and what goes in the record.

Why the Full Shuffle Runs

The shuffle can't stop after ten swaps, because the ten entries you keep are the last to settle. Each step fixes the position it's standing on and can still reach into any position below it, so entries 0 to 9 stay open to a swap until the walk arrives at them, and the walk starts at the far end. All 39 swaps happen whether you want ten numbers or one.

So draws can't make a round cheaper. It can't change the shuffle either.

import { play } from '@galabet/fair';

const serverSeed = '5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d';

for (const draws of [1, 5, 10]) {
  const { result, cursor, floats } = await play({ game: 'keno', serverSeed, clientSeed: 'galabet', nonce: 42, params: { draws } });
  console.log(`draws ${String(draws).padStart(2)}  floats ${floats.length}  cursor ${cursor}  ${result.join(' ')}`);
}

draws  1  floats 39  cursor 4  28
draws  5  floats 39  cursor 4  11 17 28 32 33
draws 10  floats 39  cursor 4  7 10 11 17 22 26 28 32 33 36

Five draws is a subset of ten, because draws only decides how much of the front of the row to keep. draws: 40 is legal too, and returns every number from 1 to 40 on every round, which tells you nothing. The test vectors include it anyway, along with 1 and 10.

Draw Order Is Not Preserved

The shuffle put 28 first, then 33, then 17. The result opens with 7, 10, 11. Sorting happens inside keno, so a record holds a set of numbers written smallest first, and nothing in it says which came out before which.

If your game reveals balls one at a time, the sequence on screen is presentation. You can recompute the shuffled row from the seeds, as the example above does, and animate in that order if you like. The record won't back it up, and neither verifyRecord nor the verifier page ever looks at it. A player can't use a record to show that 28 was the first ball out, and a rule that depends on order, a first-ball bonus for instance, has nothing to stand on.

The reverse mistake is storing the unsorted list as result. That record fails, and the verifier's difference line reads result[0]: recorded 28, calculated 7. Store what play gave you.

Counting Hits

import { play } from '@galabet/fair';

const { result: drawn } = await play({
  game: 'keno',
  serverSeed: '5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d',
  clientSeed: 'galabet',
  nonce: 42,
});

const hits = (ticket) => ticket.filter((number) => drawn.includes(number));

console.log(hits([3, 7, 11, 19, 28, 40]));
console.log(hits([7, 7, 7]).length);

[ 7, 11, 28 ]
3

That's application code, and the second line is why a ticket needs validating before it gets this far: whole numbers, 1 to 40, no repeats. The library never sees a ticket. It doesn't know how many numbers a player may pick or what three hits out of six is worth.

The demo's pay table is KENO_TABLE in apps/api/src/demo/rules.ts, with one row for each ticket size from 1 to 10 numbers, always against a ten-number draw. Ten hits on a ten-number ticket pays 100. There are 847,660,528 ways to choose ten numbers from forty, and that ticket needs one of them. Worked out against the exact odds, the rows return between 98.96% and 99.04% depending on ticket size. The Keno game page prints the table beside the chance of each hit count. If you ever edit a pay table, keep a note of which version settled each bet. The Wheel page has the reason.

Distribution

Each number should turn up in a quarter of all ten-number draws. Over 20,000 nonces that's 5,000 appearances apiece.

import { play } from '@galabet/fair';

const serverSeed = '5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d';
const rounds = 20000;
const seen = new Array(41).fill(0);

for (let nonce = 0; nonce < rounds; nonce++) {
  const { result } = await play({ game: 'keno', serverSeed, clientSeed: 'galabet', nonce });
  for (const number of result) seen[number]++;
}

const counts = seen.slice(1);
const least = Math.min(...counts);
const most = Math.max(...counts);
console.log(`least drawn: ${counts.indexOf(least) + 1}, ${least} times`);
console.log(`most drawn: ${counts.indexOf(most) + 1}, ${most} times`);
console.log(`expected spread: about ${Math.sqrt(rounds * 0.25 * 0.75).toFixed(0)} either side of ${rounds / 4}`);

least drawn: 35, 4868 times
most drawn: 6, 5185 times
expected spread: about 61 either side of 5000

Number 6 is 185 over, which is three times the expected spread and far enough out to check. We checked two ways.

Watching forty counters at once makes a large miss on one of them much likelier than it would be on a single counter. We simulated this same experiment 1,000 times with an ordinary random shuffle in place of the seeds, and in 104 of those runs some number finished at least 185 away from 5,000. About one run in ten, then.

We also extended the real run to 100,000 nonces. Number 6 came back to 25,095 against an expected 25,000, inside a spread of 137, and the most-drawn number became 14. An excess that belonged to the algorithm would have grown with the sample. This one shrank.

The arithmetic does have a real unevenness, far too small to show up in a count like this. The first swap spreads 4,294,967,296 floats over 40 positions, and that doesn't divide, so 16 positions get 107,374,183 floats and the other 24 get 107,374,182. That's about one part in 107 million.

Porting the Shuffle

import hashlib
import hmac
import json


def keno(server_seed, client_seed, nonce, draws=10):
    values = []
    for cursor in range(5):
        message = f"{client_seed}:{nonce}:{cursor}".encode()
        digest = hmac.new(server_seed.encode(), message, hashlib.sha256).digest()
        values += [int.from_bytes(digest[i:i + 4], "big") for i in range(0, 32, 4)]

    row = list(range(40))
    for step, i in enumerate(range(39, 0, -1)):
        j = values[step] * (i + 1) >> 32
        row[i], row[j] = row[j], row[i]
    return sorted(entry + 1 for entry in row[:draws])


print(keno("5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d", "galabet", 42))

with open("vectors/gfs-1.0.json", encoding="utf-8") as file:
    vectors = [v for v in json.load(file)["games"] if v["game"] == "keno"]

matched = sum(keno(v["serverSeed"], v["clientSeed"], v["nonce"], v["params"]["draws"]) == v["result"] for v in vectors)
print(f"{matched} of {len(vectors)} Keno vectors match")

[7, 10, 11, 17, 22, 26, 28, 32, 33, 36]
336 of 336 Keno vectors match

values[step] * (i + 1) >> 32 is floor(float × (i + 1)) with no float in it. A 32-bit value times 40 at most fits in 38 bits, so nothing rounds in either form and the two always agree. What it must not become is value % (i + 1). That's a different shuffle.

What else has to match? The walk runs from 39 down to 1, not up from 0. Floats are used in stream order across all five digests, float 0 for the first swap. And the final sort compares numbers. JavaScript's bare sort() compares strings, so [7, 10, 11].sort() comes back as [10, 11, 7], and the library passes a comparator to avoid that.

A word on those 336 vectors. They're split evenly over draws of 1, 10 and 40, and all 112 of the draws: 40 rounds expect the numbers 1 to 40, which a port with no shuffle at all would also produce. The other 224 are the ones doing the work.

Errors

The verifier accepts the same range for draws, 1 to 40. Seed and nonce errors are shared by every game and are listed on the Dice page.