4096 iterations tests a big mix of flag combination mixes,
and runs far faster than the previous 131072 nonrandom iterations.
The nonrandom approach was getting unsustainable as we are getting up
to 1<<20 in the flag bits (would be 1 million iters).
Details
- Reviewers
deadalnix - Group Reviewers
Restricted Project - Maniphest Tasks
- T527: Add Schnorr support to OP_CHECKSIG and OP_CHECKDATASIG
- Commits
- rSTAGINGe6ac0d1db5d5: sigencoding_tests : use pseudorandom generator for flag patterns
rABCe6ac0d1db5d5: sigencoding_tests : use pseudorandom generator for flag patterns
I've run this LCG in python to do histogramming & verify the
correct order. Also the iterations include a testpoint to make sure the LCG
is producing the expected sequence.
Diff Detail
- Repository
- rABC Bitcoin ABC
- Branch
- lcg_sigencoding_tests
- Lint
Lint Passed - Unit
No Test Coverage - Build Status
Buildable 4818 Build 7699: Bitcoin ABC Buildbot (legacy) Build 7698: arc lint + arc unit
Event Timeline
Does this hit enough flag combinations? See comments in the code..
Here is the Python code for doing a direct histogram of four-flag AND and four-flag NOR for every possible combination of four flags, producing the numbers mentioned in code comments:
#!/usr/bin/env python3 import numpy as np MAX = 2**64 - 1 def nextlcg(x): return (x * 6364136223846793005 + 1442695040888963407) & MAX # flags goes like: #0x14057b7e #0x1a08ee11 #0x9af67822 #.... # create 4D arrays 32x32x32x32... histand = np.zeros((32,32,32,32), dtype='uint32') histnor = np.zeros((32,32,32,32), dtype='uint32') state = 0 for i in range(4096): state = nextlcg(state) flags = state >> 32 flagbits = (np.array(list('{:032b}'.format(flags))) == '1') # use numpy array broadcasting hand = flagbits * flagbits[:,None] * flagbits[:,None,None] * flagbits[:,None,None,None] hnor = ~(flagbits + flagbits[:,None] + flagbits[:,None,None] + flagbits[:,None,None,None]) histand += hand histnor += hnor if i % 100 == 0: print(i, np.min(histand), np.min(histnor)) print('Minimums for 4096 iters: ', np.min(histand), np.min(histnor))
For bigger flag tuples, it gets hard to brute force like that but we can do probabilistic predictions based on poisson distribution. Lets say you're worried about a specific combination of M=7 flags occurring or not (flag3=True,flag20=False,...) -- the probability of this being missed is exp(-4096/2^M). The chance of hitting ALL possible variations of those 7 flags is about (1 - 2^M * exp(-4096/2^M)).
For 4096 this only gets to be a problem once we reach M=9 (17% chance that we missed one possible 9-flag combination, but, 99.97% chance of hitting a *given* 9-flag combination). With M=8 these numbers are ~10^-5 and 99.99999% respectively.
However if we are worried about missing one possible true/false variation of all *possible* M-flag sets, the probability is (32 choose M) * 2^M * exp(-4096/2^M). For M=8 we are guaranteed to miss some variations, With M=7 it is very unlikely (10^-5) that out of all ~3 million possible choices of 7 flags, and all 128 true/false variations of each of those flagsets, we would miss any.
This is great. I do thing that there are other tests that would benefit from this. I think we can shave off a lot of run time from the test suite while keeping the same runtime.
src/test/sigencoding_tests.cpp | ||
---|---|---|
183 ↗ | (On Diff #7086) | Update the state after picking a value, this ensure we test all zeros. |
188 ↗ | (On Diff #7086) | If you feel this is require,d it's probably better to encapsulate the generator in its own class and write tests for it. This is fairly unrelated to what is tested here. It also seems logical to do that because this is already the second place where this generator is used now. |
365 ↗ | (On Diff #7086) | dito |
370 ↗ | (On Diff #7086) | dito |
src/test/sigencoding_tests.cpp | ||
---|---|---|
183 ↗ | (On Diff #7086) | 👍 |
188 ↗ | (On Diff #7086) | Hmm true. I think the class is overkill at the moment but I'll make a separate boost test for this purpose. (My worry with this test is that maybe some architectures don't do the 64 bit multiplication wraparound correctly, and thus maybe get stuck into a small cycle) |
src/test/sigencoding_tests.cpp | ||
---|---|---|
101 | Put that in a header file (there is probably an existing one that can be leveraged for this.), Migrate the radix test to use it and make it have its own test. This can be done in its own diff or in that one. rename GetFlags and just do the advancing in there. Just call it next() or something. |
src/test/sigencoding_tests.cpp | ||
---|---|---|
18 ↗ | (On Diff #7107) | You can remove the comment. It's not up to this test to know how's the generator working. |
src/test/sigencoding_tests.cpp | ||
---|---|---|
18 ↗ | (On Diff #7107) | k |