From Digest to Floats

Every seed-based game in GFS 1.0 starts from the same raw material: a fraction f with 0 <= f < 1. Dice multiplies it by 10001, Roulette by 37, a shuffle by the number of cards still unplaced. This page is about where f comes from and how much it can be trusted as arithmetic. It assumes you know what the HMAC digest is. It doesn't assume you write JavaScript, and the short version fits in a sentence: cut the 32-byte digest into eight groups of four bytes, read each group as a big-endian unsigned integer, divide by 2³².

Eight Floats from One Digest

import { deriveDigest, digestToFloats, toHex } from '@galabet/fair';

const digest = await deriveDigest({
  serverSeed: '5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d',
  clientSeed: 'galabet',
  nonce: 42,
});

const view = new DataView(digest.buffer, digest.byteOffset, digest.byteLength);

digestToFloats(digest).forEach((float, i) => {
  const hex = toHex(digest.slice(i * 4, i * 4 + 4));
  const integer = view.getUint32(i * 4); // big-endian by default
  console.log(i, hex, String(integer).padStart(10), float, float === integer / 2 ** 32);
});

0 8fa8eae0 2410212064 0.5611712262034416 true
1 1ccd4312  483214098 0.11250704945996404 true
2 0b5028ac  189802668 0.044191877357661724 true
3 d55241e6 3578937830 0.8332863985560834 true
4 3f01343d 1057043517 0.24611212243326008 true
5 81935389 2173916041 0.506154271075502 true
6 da845788 3666106248 0.853581877425313 true
7 97a5fe39 2544238137 0.5923766030464321 true

Row 0 is the float behind the public Dice roll, and the Dice page follows it the rest of the way to 56.12. The other seven rows are what Dice throws away and what Plinko, Mines or a card shuffle would go on to use, in this order.

digestToFloats accepts a 32-byte array and nothing else. Any other length throws digest must be 32 bytes. The library's bytesToFloat is written as a sum, b0/256 + b1/256² + b2/256³ + b3/256⁴, and the last column shows it agrees with the integer form on all eight. The next section checks more than eight.

Exact in a Double

An IEEE 754 double has a 53-bit significand. A four-byte integer needs at most 32 of them, and dividing by a power of two only changes the exponent. So integer / 2**32 is not an approximation of the fraction. It is the fraction, and the conversion can be undone without loss.

The sum form is exact too, for a reason worth a line. Each of its four terms is a multiple of 2⁻³², and so is every partial sum, and all of them are below 1. A multiple of 2⁻³² below 1 fits in 32 bits. No addition ever has to round, which means the order of the additions can't matter and a port may use whichever form its language makes convenient.

That leaves 21 bits of headroom, and the mappers spend it. For an integer n below 2²¹, the product f * n needs at most 53 bits and is exact as well. So Math.floor(f * n) equals the pure integer calculation (integer * n) >> 32, not approximately but always. The example below checks all three claims on a million pseudo-random byte groups, using a small generator of its own so that the run is repeatable.

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

let state = 12345;
const nextByte = () => {
  state = (Math.imul(state, 1664525) + 1013904223) >>> 0;
  return state >>> 24;
};

const SAMPLES = 1_000_000;
let sameAsInteger = 0, roundTrips = 0, floorsAgree = 0;

for (let i = 0; i < SAMPLES; i++) {
  const [b0, b1, b2, b3] = [nextByte(), nextByte(), nextByte(), nextByte()];
  const integer = ((b0 << 24) | (b1 << 16) | (b2 << 8) | b3) >>> 0;
  const float = bytesToFloat(b0, b1, b2, b3);

  if (float === integer / 2 ** 32) sameAsInteger++;
  if (float * 2 ** 32 === integer) roundTrips++;
  if ([37, 52, 10001].every((n) => Math.floor(float * n) === Number((BigInt(integer) * BigInt(n)) >> 32n))) floorsAgree++;
}

console.log(sameAsInteger, roundTrips, floorsAgree);
console.log(bytesToFloat(0, 0, 0, 0), bytesToFloat(0, 0, 0, 1), bytesToFloat(255, 255, 255, 255));
console.log(2 ** 53 + 1 === 2 ** 53);

1000000 1000000 1000000
0 2.3283064365386963e-10 0.9999999997671694
true

The last line is the reason GFS stops at four bytes and doesn't take seven or eight for a finer float. Past 53 bits a double starts merging neighbouring integers, the conversion would round, and two ports could round differently. Four bytes is also a width that nearly every language can read in one call, getUint32 in JavaScript and int.from_bytes in Python, and it divides a SHA-256 output into a whole number of groups.

A caveat for ports. The exactness covers multiplying by an integer and flooring. Limbo divides by the float, and the order of its floating-point operations matters; the Limbo page deals with that. If your language has wide integers, doing the whole mapping in integers, as the Python on the Dice page does, avoids the question.

The Range Never Includes 1

The largest float is 1 − 2⁻³². For any n of 2³² or less, floor(f * n) therefore tops out at n - 1, and an index computed this way can't run off the end of a wheel, a board or a deck. No mapper needs a clamp.

The cost shows up at the other end of the design. A game that wants both ends of a closed range has to scale by one more than the obvious number, which is why Dice multiplies by 10001 to reach 100.00. And the resolution is finite: a single float can't address more than 2³² outcomes. Nothing in GFS 1.0 asks it to. Among the parameters inspectRecord accepts, the largest range a single float has to cover is Dice's 10,001. The shuffles use one float per swap over the items not yet placed, which is 416 at most, the first swap of an eight-deck shoe.

Scaling Without Modulo

The familiar way to turn random bytes into a number from 0 to 36 is byte % 37. It's worth being precise about what is wrong with it, because the usual one-line explanation ("modulo is biased") leaves out half the story. Here are both methods applied to every possible byte, then to every possible 32-bit value.

const POCKETS = 37;
const half = (counts, from, to) => counts.slice(from, to + 1).reduce((a, b) => a + b, 0);

const modulo = new Array(POCKETS).fill(0);
const scaled = new Array(POCKETS).fill(0);
for (let byte = 0; byte < 256; byte++) {
  modulo[byte % POCKETS]++;
  scaled[Math.floor((byte / 256) * POCKETS)]++;
}

console.log('one byte, % 37    ', modulo.join(''), ' low', half(modulo, 1, 18), 'high', half(modulo, 19, 36));
console.log('one byte, floor   ', scaled.join(''), ' low', half(scaled, 1, 18), 'high', half(scaled, 19, 36));

// Four bytes, counted exactly. Pocket k receives the integers v with floor(v * 37 / 2^32) = k.
const SPACE = 2n ** 32n;
const n = BigInt(POCKETS);
const ceilDiv = (a, b) => (a + b - 1n) / b;
const base = SPACE / n;
const extraModulo = [], extraScaled = [];
for (let k = 0n; k < n; k++) {
  if (k < SPACE % n) extraModulo.push(Number(k));
  if (ceilDiv((k + 1n) * SPACE, n) - ceilDiv(k * SPACE, n) > base) extraScaled.push(Number(k));
}

console.log('four bytes, base  ', base, 'remainder', SPACE % n);
console.log('four bytes, % 37  ', extraModulo.join(' '));
console.log('four bytes, floor ', extraScaled.join(' '));

one byte, % 37     7777777777777777777777777777777777666  low 126 high 123
one byte, floor    7777777777776777777777776777777777776  low 125 high 124
four bytes, base   116080197n remainder 7n
four bytes, % 37   0 1 2 3 4 5 6
four bytes, floor  0 5 10 15 21 26 31

Each digit in the first two lines is how many of the 256 byte values land in that pocket, pocket 0 on the left. Both methods give 34 pockets seven values and 3 pockets six. They have to: 256 things don't go into 37 boxes evenly, and no formula changes that. With one byte of input, the lucky pockets come up about 17% more often than the unlucky ones whichever method is used.

So the first defence is not the formula. It is the size of the input. With four bytes the base count is 116,080,197 per pocket and only 7 values are left over, so the most and least likely pockets differ by one part in 116 million. For a 52-card deck the figure is one part in 82,595,524, and for Dice it is one in 429,453.

The formula decides where the leftovers go. Modulo always hands them to the lowest results: pockets 0 to 6 in the four-byte case, 0 to 33 in the one-byte case, where a bet on 1 to 18 covers 126 byte values and a bet on 19 to 36 covers 123. Scaling and flooring spreads the leftovers through the range at even intervals, and the same two bets come out at 125 and 124. In the four-byte case the extra values fall on pockets 0, 5, 10, 15, 21, 26 and 31, three in each half of the layout. A bias that sits in one place can add up across a bet that covers that place. One that is spread out mostly cancels.

There's a third reason, less mathematical. floor(f * n) works for any n and for mappings that aren't integer ranges at all, such as Limbo's multiplier. One rule serves nine games and a port implements it once. The only % in @galabet/fair/games is in the card code, where it turns a card index into a rank and folds an eight-deck index back onto 52 labels. No float passes through it.

None of this makes the residue zero. Pocket 0 has one more 32-bit value behind it than pocket 36 does under either method. GFS accepts a bias of that size and states it; rejection sampling would remove it at the cost of a variable number of floats per result, which would make the cursor depend on the seeds.

deriveFloats and the Cursor

Games don't call digestToFloats. They ask deriveFloats(seeds, count) for the first count floats of a bet and let it fetch digests as needed: cursor 0 supplies floats 0 to 7, cursor 1 supplies 8 to 15, and so on.

import { deriveDigest, deriveFloats, digestToFloats } from '@galabet/fair';

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

const nine = await deriveFloats(seeds, 9);
const second = digestToFloats(await deriveDigest(seeds, 1));

console.log(nine.floats.length, nine.cursor);
console.log(nine.floats[8] === second[0]);
console.log((await deriveFloats(seeds, 16)).cursor, (await deriveFloats(seeds, 17)).cursor);

try {
  await deriveFloats(seeds, 0);
} catch (error) {
  console.log(error.message);
}

9 1
true
1 2
count must be a positive integer

Asking for nine floats costs a whole second digest, and seven of its floats go unused. They are discarded, never carried into the next bet, because the next bet has a different nonce and starts again at cursor 0.

The cursor that comes back is the highest cursor consumed, which is what a record stores. It is 1 for anything from 9 to 16 floats and becomes 2 at 17. Nonce and cursor has the per-game figures. count must be a positive integer is also the message a caller of play sees for a rows of 0 or a fraction, or a decks of 0, since those parameters end up as a float count. Other out-of-range values get the mapper's own message.

The Same Floats in Python

import hashlib
import hmac

server_seed = "5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d"
digest = hmac.new(server_seed.encode(), b"galabet:42:0", hashlib.sha256).digest()

for i in range(0, 32, 4):
    print(int.from_bytes(digest[i:i + 4], "big") / 2**32)

0.5611712262034416
0.11250704945996404
0.044191877357661724
0.8332863985560834
0.24611212243326008
0.506154271075502
0.853581877425313
0.5923766030464321

Compare these with the fourth column of the first example. They agree to the last digit, which isn't luck. Both languages hold the identical double, and both print the shortest decimal string that reads back as that double. A language that prints fewer digits by default, as C's %f does, still holds the right value. Compare the integers if you're unsure.

What the Floats Inherit from HMAC

The arithmetic on this page is exact, so whatever statistical quality the floats have is the quality of the bytes. GFS relies on HMAC-SHA256 behaving as a pseudo-random function: under an unknown key, each output bit is as likely 0 as 1 and unrelated to the others. That is a standard assumption about HMAC, and it is an assumption. The library doesn't test it and couldn't prove it.

What you can do is look. This takes 5,000 nonces, 40,000 floats, and averages each of the eight positions separately, since a flaw in the byte grouping would show up as one position behaving differently from the rest.

import { deriveDigest, digestToFloats } from '@galabet/fair';

const serverSeed = '5c1f7d3e8a2b4c6d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d';
const ROUNDS = 5000;
const sums = new Array(8).fill(0);

for (let nonce = 0; nonce < ROUNDS; nonce++) {
  const floats = digestToFloats(await deriveDigest({ serverSeed, clientSeed: 'galabet', nonce }));
  floats.forEach((float, i) => { sums[i] += float; });
}

console.log(sums.map((sum) => (sum / ROUNDS).toFixed(4)).join(' '));
console.log('expected 0.5000, standard error', (Math.sqrt(1 / 12) / Math.sqrt(ROUNDS)).toFixed(4));

0.5011 0.5039 0.5015 0.5028 0.5013 0.5020 0.4961 0.5023
expected 0.5000, standard error 0.0041

A uniform variable has a standard deviation of √(1/12), so the mean of 5,000 of them should sit within a few standard errors of 0.5. The furthest of the eight, 0.5039 and 0.4961, are each 0.0039 away, under one standard error. A test like this can expose a broken implementation. It can't certify a sound one, and it says nothing about whether an operator's server seed was random to begin with, which is a matter for the server seed page.