Better randomness test for secp256k1_rand_bits

[sipa]

[gmaxwell]

Still too twitchy: I am able to observe failures. FWIW, generally checks out fine, and I confirmed it catches some obscure bugs I tried adding.

[gmaxwell]

Can we go forward with this but disable the testing RNG tests by default and make running them part of our release process? I don't like the possibility of spurious failures for users, even if we make it much lower.

98% of the value of this is catching boneheaded mistakes like changes that make the RNG return all zero or all even values. :P

[real-or-random]

For reference / easier testing:

test count = 1
random seed = 4d1bd7716e4f3a7b9a5442833b305b83
src/tests.c:562: test condition failed: ((~x[m][shift]) << (64 - (1 << usebits))) == 0
[1]    7866 abort (core dumped)  ./tests 1 4d1bd7716e4f3a7b9a5442833b305b83

This is at fa3301713549d118e57ebe6551d062903ddd6b63.

[real-or-random]

Here's a more recent one on 67a429f31fd3d1b37c5365cc58b70588b8645d62, posting this here because the other seed may not work any longer

test count = 64
random seed = 4211e70b4eef2c4554bedfdbe4015501
src/tests.c:560: test condition failed: ((~x[m][shift]) << (64 - (1 << usebits))) == 0

FAIL tests (exit status: 134)

[gmaxwell]

Can I suggest that this be changed so that it runs the randomness tests with a static seed? This way it won't cause spurious failures for users, but will still likely catch bugs introduced by changes to the rng?

[real-or-random]

You mean run the current tests with a static seed? Or simply add some known-output tests then to detect any change in the rng (and maybe run them first in the test suite)?

[gmaxwell]

Current test with a static seed. just for the RNG tests. People tend to copy-paste new responses when a non-normative function changes, so known responses really are only just "this changed" tests-- useful to that extent but don't replace tests that check invariants.

If the RNG is changed then then it might trigger a spurious failure with the static seed but then the author can check it out and increment the seed if its appropriate to just suppress .

What I want to avoid is the current situation where it passes 99.99% of the time but then fails randomly for some user, but otherwise not change anything.

[markblundeberg]

FWIW if my math is right, the current test succeeds with 99.984% chance. https://gitlab.com/bitcoin-cash-node/bitcoin-cash-node/-/issues/208#note_457729449

Fixed seed sounds like a nice idea.

An alternative idea: Increase the rounds so that each call to run_rand_bits actually has a one-in-a-billion overall failure rate (or whichever target is desired).

A possible improvement: build an actual counting histogram (up to 27 * 6 * 64 bins), rather than a binary "appeared at least once"-ogram. The counts will follow a binomial distribution. Check if counts exceed min/max limits, and make those limits generous enough for the desired failure rate.

• Example 1: 2176 rounds for the usebits=6 cases, and check that 0 < count < 89. Gives 3e-15 failure rate per bin, and thus overall failure rate of 2e-10 from all the usebits=6 tests.
• Example 2: 9600 rounds for the usebits=6 case, giving an avg of 9600/64 = 150 counts per bin, and check that 46 < count < 254 (symmetrical about the avg). 4e-15 failure rate per bin, and thus overall failure rate of 6e-10 from all the usebits=6 tests.
• The much faster 1,2,3,4, and 5-bit tests can in turn have parameters chosen to each have ~1e-10 failure rate, hence the total failure rate of run_rand_bits will be about one-in-a-billion.