Sometimes-Recurse Shuffle

>>> import hashlib
>>> hashlib.sha256(b"test0").digest()[0] & 1
1
>>> hashlib.sha256(b"test1").digest()[0] & 1
1
>>> hashlib.sha256(b"test2").digest()[0] & 1
0
>>> hashlib.sha256(b"test3").digest()[0] & 1
1

this way, you generate deterministic coinflips

so we do this for a couple rounds

if the outcome of the coinflip is 1, we swap i = i2

if the outcome is 0, we don't

conceptually, in each round we randomly make pairs in the array, and randomly swap them or not

but we never track the position of other elements!

and the more rounds we do, the better our randomness gets

Cᴏɴᴏʀ O'Bʀɪᴇɴ

8:32 PM

huh

orlp

now, this algorithm is called swap-or-not

for reasons I don't fully understand (read the paper), this only mixes around half the cards after log(N) rounds, and is not sufficient

(err, I started using 'cards' suddenly there, but you know what I mean)

but it does uniformly randomly separate the elements in the left half and right half

so what the algorithm does as a final step, if after all the rounds i < N/2, we recurse, and do the whole thing again, but with limit N/2

Maltysen

@orlp I don't understand how this lets you not have P in memory

orlp

gist.github.com/orlp/33535eefce782a59e185e4a971cda1a3

this is an ugly implementation I made in Python

prf_under_n returns a deterministic pseudorandom number under n, given its inputs

prf_coinflip returns a deterministic pseudorandom coinflip, given its inputs

you'd replace those with something more appropriate

@Maltysen do you understand how the pairings are made without P in memory?

Maltysen

@orlp ohhh, so you just keep a list of the pairings, i see now

orlp

@Maltysen not even a list of the pairings

a list of the numbers R that generates the pairings

e.g. for N = 8

if R = 5

0 pairs with (5 - 0) % 8 = 5

1 pairs with (5 - 1) % 8 = 4

2 pairs with (5 - 2) % 8 = 3

3 pairs with (5 - 3) % 8 = 2

4 pairs with (5 - 4) % 8 = 1

5 pairs with (5 - 5) % 8 = 0

6 pairs with (5 - 6) % 8 = 7

7 pairs with (5 - 7) % 8 = 6

see how the pairing is symmetric?

and how you can always compute the other pair from just knowing the current number?

Maltysen

8:43 PM

yeah

orlp

all right

so let's say I give you i = 2

and we're doing currently a round with R = 5

you compute i2 = (R - i) % N = 3

now you do a deterministic, but pseudorandom coinflip

if the coinflip turns out to be 0, we don't swap, so i stays the same

if the coinflip turns out to be 1, there was a swap, so i = i2

@Maltysen the crucial part is, we determine the coinflip based on max(i, i2)

and because the i <-> i2 thing is symmetric, the max is the same for either of them

@Maltysen the crux is rather than making the shuffle locations really random, we use a simple sort-of-random method, but then conditionally apply it

Maltysen

i see

orlp

and by repeatedly doing that we get a high quality random permutation

Maltysen

this is cool

orlp

and you can do that individually for every element

Cᴏɴᴏʀ O'Bʀɪᴇɴ

8:51 PM

^^

orlp

in log(n) time and space (per element)

but really, read these slides: ec14.compute.dtu.dk/talks/20.pdf

you can skip the first 7 pages if you're not into crypto

@Maltysen so, if you abstract away the prf_under_n and prf_coinflip pseudo-rng building blocks, this is the algorithm:

def f(n, p, N=10**18):
    if N == 1:
        return n

    round_keys = [prf_under_n(N, p, r) for r in range(7 * math.ceil(math.log(N, 2)))]
    for r, K in enumerate(round_keys):
        n2 = (K - n) % N
        if prf_coinflip(max(n, n2), p, r):
            n = n2

    if n < N // 2:
        return f(n, p, N // 2)

    return n

which, to me, is elegant

Maltysen

nice

orlp

@Maltysen btw, is it clear what prf_coinflip does?

Maltysen

@orlp yeah

it takes a "seed" and gives you a random bit

orlp

@Maltysen the crucial part is that the seed is dependent on 1. p, 2. the round key and 3. max(i, i2)

the result of this is that all coinflips are independent

which is... rather important :)

Cᴏɴᴏʀ O'Bʀɪᴇɴ

9:05 PM

Now I can't say I didn't learn anything interesting today.

Transcript for

Sometimes-Recurse Shuffle