Page MenuHomePhabricator

add flags to VerifySignature and sigcache
ClosedPublic

Authored by markblundeberg on Jan 21 2019, 20:38.

Details

Summary

In preparation for overloading CHECKSIG et al to accept Schnorr
signatures, this changes VerifySignature so that it has knowledge of
SCRIPT_ flags.

The sigcache code (which memoizes VerifySignature positive results) has been
upgraded in accordance. In order that the cache does not fill up with
duplicate entries and cache misses occur due to distinct policy/consensus
flagsets, I have also added an explicit flag-invariants masking so that
irrelevant flag permutations can be ignored.

The order of parameters in sigcache's internal ComputeEntry has been also
changed to mirror the order in VerifySignature, as well as order of hashing.

Test Plan

Added testset for flag invariance/variance in cache. I played around with adding/removing flags to this test module (and sigcache.cpp) to see how it fails in both directions.

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

markblundeberg created this revision.Jan 21 2019, 20:38
Herald added a reviewer: Restricted Project. · View Herald TranscriptJan 21 2019, 20:38
Herald added a subscriber: schancel. · View Herald Transcript
deadalnix requested changes to this revision.Jan 21 2019, 20:44
deadalnix added inline comments.
src/script/interpreter.h
45 ↗(On Diff #6795)

It's not the responsibility of the script system to know what flags affect the validity of a signature, because it's not the responsibility of the script system to validate a signature.

src/script/sigcache.cpp
46 ↗(On Diff #6795)

It should be possible to push the flags directly. This is also this piece of code that seems to be in charge of picking and choosing the relevant flags to compute the key from.

This revision now requires changes to proceed.Jan 21 2019, 20:44
markblundeberg added inline comments.Jan 21 2019, 22:04
src/script/interpreter.h
45 ↗(On Diff #6795)

Ok.

src/script/sigcache.cpp
46 ↗(On Diff #6795)

If I just put &flags, it complains with "no known conversion for argument 1 from ‘uint32_t* {aka unsigned int*}’ to ‘const uint8_t* {aka const unsigned char*}".

Perhaps Write() should take void * instead of uint8_t * but I'm not going to make that change in this diff. :-)

moved invariant flags to sigcache.cpp, some comment modifications.

deadalnix requested changes to this revision.Jan 22 2019, 01:05

So the code looks good, but the new behavior is missing a test. You need to check that caching still works when flags like SCRIPT_VERIFY_MINIMALIF, but do hit a different key when SCRIPT_ENABLE_SCHNORR is passed.

src/script/interpreter.cpp
1474 ↗(On Diff #6800)

Remove. This is incorrect in the general case, but even if every single use of this was memoized, adding this comment comes in direct violation of liskov's substitution principle.

https://en.wikipedia.org/wiki/Liskov_substitution_principle

It is simply not the role of this piece of code to know if it is memoized or not. It's role it to check a signature.

This revision now requires changes to proceed.Jan 22 2019, 01:05

So the code looks good, but the new behavior is missing a test. You need to check that caching still works when flags like SCRIPT_VERIFY_MINIMALIF, but do hit a different key when SCRIPT_ENABLE_SCHNORR is passed.

Yes, I've been trying to think how to do this somehow. The only way to I can think of how to distinguish a correct cache hit from an unwanted cache miss would be to measure timing, or to add additional API that exposes the private cache. 🤔

src/script/interpreter.cpp
1474 ↗(On Diff #6800)

hmm, ok

So the code looks good, but the new behavior is missing a test. You need to check that caching still works when flags like SCRIPT_VERIFY_MINIMALIF, but do hit a different key when SCRIPT_ENABLE_SCHNORR is passed.

Yes, I've been trying to think how to do this somehow. The only way to I can think of how to distinguish a correct cache hit from an unwanted cache miss would be to measure timing, or to add additional API that exposes the private cache. 🤔

You'd expect there are some existing tests for the signature cache. but

$ grep -r ../src/test/ -e CachingTransactionSignatureChecker

returns nothing. This is rather concerning, but this absolutely require a test. The cache for script can be used as an example: https://reviews.bitcoinabc.org/source/bitcoin-abc/browse/master/src/test/txvalidationcache_tests.cpp

It's probably a good idea to write a test for it independent of this patch and then have the modified behavior only be added to the test in that patch.

You'd expect there are some existing tests for the signature cache. but

$ grep -r ../src/test/ -e CachingTransactionSignatureChecker

returns nothing. This is rather concerning, but this absolutely require a test. The cache for script can be used as an example: https://reviews.bitcoinabc.org/source/bitcoin-abc/browse/master/src/test/txvalidationcache_tests.cpp
It's probably a good idea to write a test for it independent of this patch and then have the modified behavior only be added to the test in that patch.

OK, this is possible to do but again it does require opening the API. Currently the sigcache is totally inaccessible. We can change src/script/sigcache.h so its resembles src/script/scriptcache.h , is that what you have in mind?

Out of curiosity I did some digging. The sigcache stuff dates back to 2012 and only came with a test of denial of service. Moved & renamed to CSignatureCache later that year.

The DoS test was later removed in 2014.

Just add friend class CSignatureCacheTest and define CSignatureCacheTest in the test and access whatever you want through it.

Just add friend class CSignatureCacheTest and define CSignatureCacheTest in the test and access whatever you want through it.

I don't understand, how does this help? There is only one private member on that class, which is an uninteresting bool.

rebased on new sigcache testing code (D2409) and added testset

markblundeberg edited the summary of this revision. (Show Details)Jan 26 2019, 05:24
markblundeberg edited the test plan for this revision. (Show Details)
markblundeberg edited the test plan for this revision. (Show Details)

remove comment from code per earlier discussion

markblundeberg added inline comments.Jan 27 2019, 01:58
src/script/sigcache.cpp
21 ↗(On Diff #6947)

note to self -- mentions "sighash.cpp" which is misspelled and needlessly self-referential here

deadalnix added inline comments.Jan 28 2019, 01:47
src/script/sigcache.cpp
60 ↗(On Diff #6947)

Why did you change the ordering ? I would keep the signature at the end as it is under user control.

src/test/sigcache_tests.cpp
30 ↗(On Diff #6947)

Pick a different name in the test and the code.

43 ↗(On Diff #6947)

This should probably be an explicit list.

markblundeberg added inline comments.Jan 28 2019, 21:02
src/script/sigcache.cpp
60 ↗(On Diff #6947)

Ordering was changed to follow the ordering of VerifySignature, which is getting memoized. But I can change it back if you prefer.

src/test/sigcache_tests.cpp
30 ↗(On Diff #6947)

ok

43 ↗(On Diff #6947)

I was thinking so, but, unfortunately it would look a bit ugly since it tests all the unnamed flags - (1U << 11) & (1U << 12) & (1U <<19) & (1U << 20) & ... & (1U << 31).

When I add SCRIPT_ENABLE_SCHNORR it will be listed explicitly, regardless.

deadalnix added inline comments.Jan 28 2019, 22:55
src/test/sigcache_tests.cpp
43 ↗(On Diff #6947)

Unnamed flags do not have a set behavior yet, so there is really not much of a point testing them.

rename test flagsets; remove unnamed flags from TEST_VARIANT_FLAGS

markblundeberg marked 3 inline comments as done.Jan 28 2019, 23:32
deadalnix added inline comments.Jan 29 2019, 00:05
src/script/sigcache.cpp
60 ↗(On Diff #6947)

Yes, I do think it is better to keep the signature at the end. H(msg || pubkey || flags || sig) for instance.

reordered hashing: fixed size args first, then pubkey, then signature

It may be cryptographically stronger to have the weird var-length user
supplied blob (the signature) at the end.

deadalnix accepted this revision.Jan 29 2019, 00:06
This revision is now accepted and ready to land.Jan 29 2019, 00:06
This revision was automatically updated to reflect the committed changes.