peoplecoin

  1// Package feistel implements the seeded shuffle that pairs the registry.
  2//
  3// Permute is a bijection on [0, N) built from a six-round Feistel network on
  4// k = ceil(log2 N) bits with cycle walking for results ≥ N, exactly as in the
  5// specification:
  6//
  7//	k = ceil(log2(N)); left_bits = floor(k/2); right_bits = k - left_bits
  8//	loop:
  9//	    L = index >> right_bits;  R = index & (2^right_bits - 1)
 10//	    for round = 0..5:
 11//	        mask = SHA256(seed ‖ uint8(round) ‖ uint64(R))[0..ceil(left_bits/8)]
 12//	        mask = mask >> (8*ceil(left_bits/8) - left_bits)
 13//	        R, L = L ⊕ mask, R
 14//	    result = (L << right_bits) | R
 15//	    if result < N: return result
 16//	    index = result
 17//
 18// The halves swap widths every round (the mask is always left_bits wide and
 19// is XORed into the low bits of whichever half is L); after the even number
 20// of rounds L is left_bits wide and R right_bits wide again, so the
 21// recombination is exact. Invert runs the rounds backwards.
 22//
 23// Pairs are adjacent positions in the shuffled order, 0↔1, 2↔3, …: the
 24// partner of index i is Invert(Permute(i) ⊕ 1). When N is odd the entry at
 25// shuffled position N−1 has no partner.
 26package feistel
 27
 28import (
 29	"crypto/sha256"
 30	"encoding/binary"
 31	"math/bits"
 32)
 33
 34const rounds = 6
 35
 36// widths returns k, left_bits and right_bits for a domain of size n.
 37func widths(n uint64) (k, left, right uint) {
 38	if n <= 1 {
 39		return 0, 0, 0
 40	}
 41	k = uint(bits.Len64(n - 1)) // ceil(log2 n)
 42	left = k / 2
 43	right = k - left
 44	return
 45}
 46
 47// mask is the round function: the first ceil(left/8) bytes of
 48// SHA256(seed ‖ round ‖ half) as a big-endian integer, right-shifted to
 49// left bits.
 50func mask(seed *[32]byte, round uint8, half uint64, left uint) uint64 {
 51	nbytes := (left + 7) / 8
 52	if nbytes == 0 {
 53		return 0
 54	}
 55	h := sha256.New()
 56	h.Write(seed[:])
 57	h.Write([]byte{round})
 58	var b [8]byte
 59	binary.BigEndian.PutUint64(b[:], half)
 60	h.Write(b[:])
 61	sum := h.Sum(nil)
 62	var m uint64
 63	for i := uint(0); i < nbytes; i++ {
 64		m = m<<8 | uint64(sum[i])
 65	}
 66	return m >> (8*nbytes - left)
 67}
 68
 69// Permute maps index ∈ [0, n) to its shuffled position. It panics if
 70// index ≥ n.
 71func Permute(index, n uint64, seed [32]byte) uint64 {
 72	if index >= n {
 73		panic("feistel: index out of range")
 74	}
 75	k, left, right := widths(n)
 76	if k == 0 {
 77		return index
 78	}
 79	rmask := uint64(1)<<right - 1
 80	for {
 81		l := index >> right
 82		r := index & rmask
 83		for round := uint8(0); round < rounds; round++ {
 84			m := mask(&seed, round, r, left)
 85			r, l = l^m, r
 86		}
 87		res := l<<right | r
 88		if res < n {
 89			return res
 90		}
 91		index = res
 92	}
 93}
 94
 95// Invert maps a shuffled position ∈ [0, n) back to its index. It panics if
 96// position ≥ n.
 97func Invert(position, n uint64, seed [32]byte) uint64 {
 98	if position >= n {
 99		panic("feistel: position out of range")
100	}
101	k, left, right := widths(n)
102	if k == 0 {
103		return position
104	}
105	rmask := uint64(1)<<right - 1
106	for {
107		l := position >> right
108		r := position & rmask
109		for round := rounds - 1; round >= 0; round-- {
110			m := mask(&seed, uint8(round), l, left)
111			l, r = r^m, l
112		}
113		res := l<<right | r
114		if res < n {
115			return res
116		}
117		position = res
118	}
119}
120
121// Partner returns the index paired with index this period, or false if it
122// is the odd one out. It panics if index ≥ n.
123func Partner(index, n uint64, seed [32]byte) (uint64, bool) {
124	p := Permute(index, n, seed) ^ 1
125	if p >= n {
126		return 0, false
127	}
128	return Invert(p, n, seed), true
129}