Just some easy low-hanging fruit. It's complete overkill to use the RFC6979 RNG for our test randomness. Replace it with a modern non-cryptographic RNG with good properties. It's a few % speedup for me.
Given the internal naming of all these functions to be "testrand", I'm not concerned about the risk of someone using this for something that needs actual cryptographic randomness.
24 | 25 | -SECP256K1_INLINE static void secp256k1_testrand_seed(const unsigned char *seed16) { 26 | - secp256k1_rfc6979_hmac_sha256_initialize(&secp256k1_test_rng, seed16, 16); 27 | +SECP256K1_INLINE static uint32_t secp256k1_testrand32(void) { 28 | + /* RNG based on https://arxiv.org/abs/2004.06278, using two separate keys, and 29 | + * only using odd counters to avoid entropy loss of key1. */
It may be worth stressing in the comment that it's for tests only, for someone who runs grep RNG...
Agreed, I think it should say non-cryptographic RNG to match the comment at the start of testrand.h
Done.
I'm curious why you choose this specific Rng?
How does it compare to something like XoShiRo256++?
138 | @@ -109,7 +139,7 @@ static void secp256k1_testrand256_test(unsigned char *b32) { 139 | } 140 | 141 | static void secp256k1_testrand_flip(unsigned char *b, size_t len) { 142 | - b[secp256k1_testrand_int(len)] ^= (1 << secp256k1_testrand_int(8)); 143 | + b[secp256k1_testrand_int(len)] ^= (1 << secp256k1_testrand_bits(3));
(Not this PR) Looks like there's lots of calls to testrand_int with a power of two; if this is indeed a nontrivial speedup, should a future PR address all of them at once?
Done (in a separate commit).
Concept ACK
If tests taking a long time is an issue then I agree it's fine to use a faster but insecure sequence generator for tests. The specific choice of Squares seems a bit arbitrary but I don't have any particular reason to prefer another one.
I just tried to insert additional entropy in the RNG because we already have a 128-bit seed. Perhaps that's overkill though, and I should use the paper's RNG unmodified.
The reasoning is this: the existing function uses the same key variable twice. If I replace the second use with a different key, it shouldn't worsen anything. However, if the counter is even now then key1 * cnt loses (at least) one bit of entropy (multiply by even number modulo a power of 2 is not reversible), so to counter that, only use odd counters. Neither of those changes should meaningfully impact runtime.
To be clear: my belief is that with two keys, but without only-odd counters, the result is still at least as good as the one-key version. But with only-odd counters it's somewhat better still.
Thanks for clarifying!
I have a slight preference for using the paper's RNG unmodified (possibly with odd counters, which is compatible with the paper), but I don't have a stronger reason than "on principle you shouldn't modify it" 🙃 so feel free to decide either way.
First commit looks good. Nits on second commit:
secp256k1_testrand_int(2**N) -> secp256k1_testrand_bits(N) instead?testrand_flip still calls testrand_int(8)Wait, just double checking, how much speedup did you see? Here's what I got (% = M1 Mac, # = Linux VM):
% time ./tests
./tests 28.53s user 3.27s system 99% cpu 31.878 total
# time ./tests
real 1m8.177s user 1m8.050s sys 0m0.104s
# time valgrind ./tests 2
real 11m54.970s user 10m58.498s sys 0m56.142s
% time ./tests
./tests 30.23s user 3.26s system 98% cpu 33.852 total
# time ./tests
real 1m7.266s user 1m7.136s sys 0m0.112s
# time valgrind ./tests 2
real 11m49.739s user 10m53.123s sys 0m56.321s
Made a few changes:
On my Ryzen 5950X system, GCC 11.2.0, default config, ./tests:
155 | - seed16[4] ^= t >> 32; 156 | - seed16[5] ^= t >> 40; 157 | - seed16[6] ^= t >> 48; 158 | - seed16[7] ^= t >> 56; 159 | + if (frand == NULL || fread(&seed8, 1, sizeof(seed8), frand) != sizeof(seed8)) { 160 | + fprintf(stderr, "WARNING: could not read 8 bytes from /dev/urandom; falling back to insecure PRNG\n");
Nit: "falling back to time-based seed" since it's always an insecure PRNG?
ACK 6ee0f009ae4026aabf7bde654c1a18f940f9b4ea
Changed to using xoshiro256++. It's even (slightly) faster now, in my benchmarks.
Sorry for the many changes, I suspect I'm done now.
utACK 77a19750b46916b93bb6a08837c26f585bd940fa
Changed to using xoshiro256++. It's even (slightly) faster now, in my benchmarks.
and still trivial to review given https://prng.di.unimi.it/xoshiro256plusplus.c :)
ACK 77a19750b46916b93bb6a08837c26f585bd940fa
and still trivial to review given https://prng.di.unimi.it/xoshiro256plusplus.c :)
Yes :)
Timing (n=1 sample size) are indeed slightly faster than before:
% time ./tests
./tests 28.31s user 3.28s system 99% cpu 31.766 total
# time ./tests
real 1m3.644s user 1m3.485s sys 0m0.140s
# time valgrind ./tests 2
real 11m21.063s user 10m25.844s sys 0m54.987s
Post-Merge code review ACK 77a19750b46916b93bb6a08837c26f585bd940fa