Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Swap-or-not shuffle #563

Closed
vbuterin opened this issue Feb 3, 2019 · 3 comments
Closed

Swap-or-not shuffle #563

vbuterin opened this issue Feb 3, 2019 · 3 comments
Labels
general:RFC Request for Comments

Comments

@vbuterin
Copy link
Contributor

vbuterin commented Feb 3, 2019

For historical background see #323

Dan Boneh recommended in discussions that we consider the swap-or-not method for shuffling.

Here is the paper: https://link.springer.com/content/pdf/10.1007%2F978-3-642-32009-5_1.pdf

Especially see the "generalized domain" algorithm on page 3.

Here's an implementation:

def hash(x): return blake2s(x).digest()[:32]

def values_at_position(n, positions, seed, precompute=False):
    values = positions[::]
    for round in range(32):
        if precompute:
            hashvalues = b''.join([
                hash(seed + round.to_bytes(1, 'big') + i.to_bytes(4, 'big'))
                for i in range((n + 255) // 256)
            ])
        pivot = int.from_bytes(hash(seed + round.to_bytes(1, 'big')), 'big') % n
        if precompute:
            def permute(pos):
                flip = (pivot - pos) % n
                maxpos = max(pos, flip)
                bit = (hashvalues[maxpos // 8] >> (maxpos % 8)) % 2
                return flip if bit else pos
        else:
            def permute(pos):
                flip = (pivot - pos) % n
                maxpos = max(pos, flip)
                h = hash(seed + round.to_bytes(1, 'big') + (maxpos // 256).to_bytes(4, 'big'))
                byte = h[(maxpos % 256) // 8]
                bit = (byte >> (maxpos % 8)) % 2
                return flip if bit else pos

        values = [permute(v) for v in values]
    return values

def swap_or_not_shuffle(values, seed):
    return [values[i] for i in values_at_position(len(values), list(range(len(values))), seed, True)]

def swap_or_not_shuffle_partial(values, seed, count):
    return [values[i] for i in values_at_position(len(values), list(range(count)), seed, False)]

It passes basic statistical tests for shuffling 9 elements. It seems to have all of the desired properties that we want (including being invertible: just run the rounds in reverse order), and is only slightly slower than the prime shuffle .

@djrtwo
Copy link
Contributor

djrtwo commented Feb 3, 2019

So simple!

To enumerate the "desired properties":

  • Provably (close to) uniform
  • Ability to compute P(x) in O(1)
  • Ability to compute P_inverse(x) in O(1)

@hwwhww hwwhww added the general:RFC Request for Comments label Feb 3, 2019
vbuterin added a commit that referenced this issue Feb 6, 2019
@djrtwo
Copy link
Contributor

djrtwo commented Feb 8, 2019

closed via #576

@JustinDrake
Copy link
Collaborator

JustinDrake commented Feb 23, 2019

Possibly relevant paper from Eurocrypt https://eprint.iacr.org/2018/1011.pdf

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
general:RFC Request for Comments
Projects
None yet
Development

No branches or pull requests

4 participants