Details

Reviewers

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

Summary

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).

Test Plan

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

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

markblundeberg created this revision.Feb 1 2019, 03:54

Herald added a reviewer: Restricted Project. · View Herald TranscriptFeb 1 2019, 03:54

Herald added a reviewer: deadalnix. · View Herald Transcript

Herald added a subscriber: schancel. · View Herald Transcript

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

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.

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Harbormaster completed remote builds in B4809: Diff 7086.Feb 1 2019, 04:09

markblundeberg added a task: T527: Add Schnorr support to OP_CHECKSIG and OP_CHECKDATASIG.Feb 1 2019, 15:57

markblundeberg mentioned this in D2469: Add SCRIPT_ENABLE_SCHNORR support to sigencoding.Feb 1 2019, 16:48

markblundeberg added a child revision: D2469: Add SCRIPT_ENABLE_SCHNORR support to sigencoding.Feb 1 2019, 16:53

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

This revision now requires changes to proceed.Feb 1 2019, 17:03

markblundeberg added inline comments.Feb 1 2019, 17:09

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)

ensure flags=00000...000 is done at start; rewrap LCG as class & separate test

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

deadalnix requested changes to this revision.Feb 1 2019, 17:43

deadalnix added inline comments.

src/test/sigencoding_tests.cpp
101 ↗	(On Diff #7096)	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.