Randomise partition assignment to equally-full deadlines

[anorth]

Randomise the assignment of a partition to a new deadline among equally-full candidates. This randomisation should be seeded from chain randomness. We're seeking a really simple pseudo-random shuffle here, it's not first order security-critical. A Fiestel network may work, but is probably way overkill. A simple seeded PRNG that we can implement directly is probably sufficient.

[Stebalien]

I talked with @whyrusleeping about this and he says it's a "nice to have". I'll look into it if there's nothing else of higher priority. I'll look into #266.

[Stebalien]

I'm debating between two options.

1. Use a simple random offset. That is, assign to random deadline X, then X+1, etc.
2. Permute the deadlines.

The random offset is nice because it's really simple, and easy to test. However, we could still end up with "runs" of deadlines with partitions. Draft PR: #1054.

The permutation is nice and random, but doing it requires:

• A random number generator (not something I'd like to write at this point).
• Repeatedly asking the chain for randomness with different seeds (slow?).
• Repeatedly asking the chain to hash something (slow?).
• Stingy use of entropy.

I'm currently going with "stingy use of entropy", but it's a bit nasty. TL;DR: we (theoretically) need log2(48!) = 202 bits of entropy to permute the 48 deadlines. We have 256 bits of entropy. I can squeeze out enough entropy for a Fisher-Yates shuffle by:

1. Taking 6 bits for each of the first 16 elements.
2. 5 bits for the next 16 elements.
3. 4 bits for the next 8 elements.
4. 3 bits for the next 4 elements.
5. 2 bits for the next 2 elements.
6. 1 bit for the final swap.

This takes 225 bits (because I'm not stingy enough to try to use fractional bits).

The question is, is this worth it? Here's the proposed code for this "stingy" permutation algorithm:

func deadlinePermutation(randomness abi.Randomness) [WPoStPeriodDeadlines]int {
	var deadlines [WPoStPeriodDeadlines]int
	for i := range deadlines {
		deadlines[i] = i
	}
	randBits := uint(randomness[0])
	randomness = randomness[1:]
	remaining := 8
	for i := uint(0); i < uint(len(deadlines)-1); i++ {
		reqBits := bits.Len(uint(len(deadlines)) - i - 1)
		rand := uint(0)
		if remaining < reqBits {
			rand = randBits << (reqBits - remaining)
			randBits = uint(randomness[0])
			randomness = randomness[1:]
			reqBits -= remaining
			remaining = 8
		}
		remaining -= reqBits
		rand = randBits & ^((^uint(0)) << reqBits)
		randBits >>= reqBits

		j := rand + i
		deadlines[i], deadlines[j] = deadlines[j], deadlines[i]
	}
	return deadlines
}

[Stebalien]

(I can probably also implement the above with big.Int for some added sanity)

[Stebalien]

I talked about this with @nicola, and it's not important for security so we're going to drop it.

[Stebalien]

@anorth would you like me to leave this open as a future improvement?

[anorth]

Thanks! I'll re-open and move this to our "later" pipeline so we have your snippet above easily to hand if we decide to do this. I concur it's not important in the near term.