Details

Reviewers

Group Reviewers

Restricted Project

Maniphest Tasks

T527: Add Schnorr support to OP_CHECKSIG and OP_CHECKDATASIG

Commits

rSTAGING4b626647fb93: add flags to VerifySignature and sigcache
rABC4b626647fb93: add flags to VerifySignature and sigcache

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

Lint Not Applicable

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 reviewer: deadalnix. · View Herald Transcript

Herald added a subscriber: schancel. · View Herald Transcript

markblundeberg mentioned this in D2353: API rename VerifySignature -> VerifySignatureECDSA.Jan 21 2019, 20:39

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

markblundeberg added a task: T527: Add Schnorr support to OP_CHECKSIG and OP_CHECKDATASIG.Jan 21 2019, 20:41

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

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

Harbormaster completed remote builds in B4621: Diff 6795.Jan 21 2019, 20:49

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.

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

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

Harbormaster completed remote builds in B4625: Diff 6800.Jan 21 2019, 23:49

markblundeberg mentioned this in D2347: API renames of script signature functions to mention ECDSA.Jan 22 2019, 00:03

markblundeberg added a child revision: D2377: add Schnorr support to VerifySignature via flag SCRIPT_ENABLE_SCHNORR.Jan 22 2019, 00:34

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

In D2373#53753, @deadalnix wrote:

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

In D2373#53771, @markblundeberg wrote:

In D2373#53753, @deadalnix wrote:

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.

In D2373#53777, @deadalnix wrote:
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.

In D2373#53971, @deadalnix wrote:

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

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

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

markblundeberg edited the test plan for this revision. (Show Details)

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

Harbormaster completed remote builds in B4713: Diff 6946.Jan 26 2019, 05:38

remove comment from code per earlier discussion

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

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

Harbormaster completed remote builds in B4714: Diff 6947.Jan 26 2019, 05:55

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.