Better randomness test for secp256k1_rand_bits #367

1. 
   sipa commented at 9:49 pm on December 12, 2015: contributor
2. sipa force-pushed on Dec 12, 2015
3. sipa force-pushed on Dec 12, 2015
4. Better randomness test for secp256k1_rand_bits 843f0b79c6
5. sipa force-pushed on Dec 12, 2015
6. 
   gmaxwell commented at 7:30 pm on December 19, 2015: contributor

   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.
7. 
   gmaxwell commented at 10:18 pm on December 16, 2016: contributor

   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

8. sipa cross-referenced this on Apr 12, 2019 from issue unit test failure in Core PR 15796 by instagibbs
9. 
   real-or-random commented at 11:16 am on June 8, 2019: contributor

   For reference / easier testing:

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

   This is at fa3301713549d118e57ebe6551d062903ddd6b63.

10. 
    real-or-random commented at 6:29 pm on July 28, 2020: contributor

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

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

11. 
    gmaxwell commented at 0:13 am on July 29, 2020: contributor

    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?
12. 
    real-or-random commented at 4:52 am on July 29, 2020: contributor

    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)?
13. 
    gmaxwell commented at 6:00 am on July 29, 2020: contributor

    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.

14. 
    markblundeberg commented at 11:49 am on December 1, 2020: none

    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.
15. real-or-random cross-referenced this on Nov 21, 2022 from issue Conditionally include `stdio.h` and `stdlib.h` by tcharding
16. 
    sipa commented at 4:03 pm on May 8, 2023: contributor

    Closing this. Our RNG has been replaced with a well-analyzed existing one (xoshiro256++), which doesn’t really need this kind of testing.

    Going to open another PR that replaces these tests with static test vectors from xorshiro256++.

17. sipa closed this on May 8, 2023

    ---

18. real-or-random cross-referenced this on Jul 17, 2023 from issue subtree: update libsecp256k1 to latest master by fanquake

Contributors
sipa gmaxwell real-or-random markblundeberg