test: add script compression coverage for not-on-curve P2PK outputs #28193

theStack · 2023-07-31T15:22:04Z

This PR adds unit test coverage for the script compression functions {Compress,Decompress}Script in the special case of uncompressed P2PK outputs (scriptPubKey: OP_PUSH65 <0x04 ....> OP_CHECKSIG) with pubkeys that are not fully valid, i.e. where the encoded point is not on the secp256k1 curve. For those outputs, script compression is not possible, as the y coordinate of the pubkey can't be recovered (see also call-site of IsToPubKey):

bitcoin/src/compressor.cpp

Lines 49 to 50 in 44b05bf

    
           pubkey.Set(&script[1], &script[66]); 
        
           return pubkey.IsFullyValid(); // if not fully valid, a case that would not be compressible

Likewise, for a compressed script of an uncompressed P2PK script (i.e. compression ids 4 and 5) where the x coordinate is not on the curve, decompression fails:

bitcoin/src/compressor.cpp

Lines 122 to 129 in 44b05bf

    
           case 0x04: 
        
           case 0x05: 
        
               unsigned char vch[33] = {}; 
        
               vch[0] = nSize - 2; 
        
               memcpy(&vch[1], in.data(), 32); 
        
               CPubKey pubkey{vch}; 
        
               if (!pubkey.Decompress()) 
        
                   return false;

Note that the term "compression" is used here in two different meanings (though they are related), which might be a little confusing. The encoding of a pubkey can either be compressed (33-bytes with 0x02/0x03 prefixes) or uncompressed (65-bytes with 0x04 prefix). On the other hand there is also compression for whole output scripts, which is used for storing scriptPubKeys in the UTXO set in a compact way (and also for the dumptxoutset result, accordingly). P2PK output scripts with uncompressed pubkeys get compressed by storing only the x-coordinate and the sign as a prefix (0x04 = even, 0x05 = odd). Was diving deeper into the subject while working on #27432, where the script decompression of uncompressed P2PK needed special handling (see also #24628 (comment)).

Trivia: as of now (block 801066), there are 13 uncompressed P2PK outputs in the UTXO set with a pubkey not on the curve (which obviously means they are unspendable).

DrahtBot · 2023-07-31T15:22:07Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	tdb3, cbergqvist, marcofleon, achow101

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

No conflicts as of last run.

tdb3

Good work increasing unit test robustness. Looks good to me. Only a nit was observed. Author's choice for nit inclusion/exclusion.
ACK for 28287cf.

Test actions taken:
Checkout the PR branch, built, ran all unit and functional tests (all passed).

tdb3 · 2024-02-15T01:26:23Z

src/test/compress_tests.cpp

+    XOnlyPubKey x_not_on_curve;
+    do {
+        x_not_on_curve = XOnlyPubKey(g_insecure_rand_ctx.randbytes(32));
+    } while (x_not_on_curve.IsFullyValid());


nit: Looks like the approach employed is to pick a random X value until one is found that is not on the curve. What is the rationale for using randomness, rather than choosing a fixed X value that is not on the curve (e.g. fd0473a380ddf239accbc31770fcc6e64096930eaa8bc57c10f5868f3596fe1e)? Seems like the other tests in the test file use randomness as well (e.g. GenerateRandomKey()), so maybe I'm missing something. Selecting a known invalid X value would technically increase test repeatability and consistency of test execution performance (although all of the 10 runs executed locally resulted in no more than a handful of X-picking attempts before finding an invalid X value, so performance is hardly a concern here).

If I'm not overlooking something, slightly less than half of the 32-byte space is valid X coordinates on the curve, so random selection would seem to have a negligible risk of starvation in finding an off-curve X value.
https://bitcoin.stackexchange.com/questions/55196/is-there-a-point-on-the-secp256k1-curve-for-any-given-x-coordinate

I also lean towards preferring a const/constexpr containing an always-invalid X-only-pubkey. Adding some logging in the loop and running the tests a bunch of times does show that we usually finds an invalid key on the first or second attempt. (This confirms the answer in the Stack Exchange link above). Only once over ~50 runs did it try 6 times.

(MakeNewKeyWithFastRandomContext() in orphanage_tests also uses .randbytes(32) but that's for calculating private keys which don't have invalid values (except possibly 0?). GenerateRandomKey() is also for private keys.)

Using random values adds robustness which is nice. However, given that there are 13 real cases in the UTXO set, incorporating a couple of those as constants could work and add reproducibility for this test. I think it's up to the author ultimately, either way works.

cbergqvist

ACK 28287cf!

cbergqvist · 2024-02-23T09:48:00Z

src/test/compress_tests.cpp

+    XOnlyPubKey x_not_on_curve;
+    do {
+        x_not_on_curve = XOnlyPubKey(g_insecure_rand_ctx.randbytes(32));
+    } while (x_not_on_curve.IsFullyValid());


I also lean towards preferring a const/constexpr containing an always-invalid X-only-pubkey. Adding some logging in the loop and running the tests a bunch of times does show that we usually finds an invalid key on the first or second attempt. (This confirms the answer in the Stack Exchange link above). Only once over ~50 runs did it try 6 times.

(MakeNewKeyWithFastRandomContext() in orphanage_tests also uses .randbytes(32) but that's for calculating private keys which don't have invalid values (except possibly 0?). GenerateRandomKey() is also for private keys.)

marcofleon

Nicely done, ACK 28287cf. Built the PR branch, ran the unit and functional tests, everything passed.

To further validate the changes, I executed some small mutation tests checking the robustness of the test. Here's the summary:

Altering the Initial Byte of pubkey_raw: Changed the initial byte from 4 to 2 (and tried 3), testing the assumption that the script specifically handles uncompressed pubkeys not on the curve. As expected, the test failed, validating the test's accuracy in identifying uncompressed pubkeys.

Making the Pubkey Fully Valid: Modified the generation of x_not_on_curve to produce fully valid pubkeys. The test failed, showing its ability to differentiate between compressible and non-compressible pubkeys based on curve validity.

Forcing CompressScript and DecompressScript to Succeed: Introduced changes to make these functions return true regardless of the actual input. The test identified these forced successes as incorrect outcomes, indicating their reliability in catching improper script (de)compression behaviors.

Altering the Script Size Check: Changed the expected script size to an incorrect value (68U instead of 67U). The test failed, highlighting its precision in validating script size expectations.

The new unit test robustly identifies and responds correctly to various edge cases. It's effective in handling script compression/decompression for uncompressed P2PK outputs with invalid pubkeys. Everything looks good to me.

davidgumberg · 2024-03-02T01:59:11Z

src/test/compress_tests.cpp

+
+    // Check that compressed P2PK script with uncompressed pubkey that is not fully
+    // valid (i.e. x coordinate of the pubkey is not on curve) can't be decompressed
+    CompressedScript compressed_script(x_not_on_curve.begin(), x_not_on_curve.end());


Would it be good idea to change the Decompress test below to use CompressedScript out

Or maybe instead to validate the assumption that compressed_script == out here?

achow101 · 2024-03-13T13:28:53Z

ACK 28287cf

DrahtBot added the Tests label Jul 31, 2023

This was referenced Aug 9, 2023

wallet: Use CTxDestination in CRecipient instead of just scriptPubKey #28246

Merged

Break up script/standard.{h/cpp} #28244

Merged

Silent Payments: Implement BIP352 #28122

Draft

DrahtBot added the Needs rebase label Aug 17, 2023

theStack force-pushed the test-compressscript_uncompressed_p2pk_not_on_curve branch from f17ad2f to 4f2f66f Compare August 18, 2023 23:28

DrahtBot removed the Needs rebase label Aug 19, 2023

DrahtBot added the CI failed label Oct 25, 2023

theStack force-pushed the test-compressscript_uncompressed_p2pk_not_on_curve branch from 4f2f66f to 3cc5328 Compare January 6, 2024 21:15

DrahtBot added CI failed and removed CI failed labels Jan 6, 2024

test: add script compression coverage for not-on-curve P2PK outputs

28287cf

theStack force-pushed the test-compressscript_uncompressed_p2pk_not_on_curve branch from 3cc5328 to 28287cf Compare January 22, 2024 12:39

DrahtBot removed the CI failed label Jan 22, 2024

tdb3 reviewed Feb 15, 2024

View reviewed changes

cbergqvist approved these changes Feb 23, 2024

View reviewed changes

marcofleon approved these changes Feb 27, 2024

View reviewed changes

davidgumberg reviewed Mar 2, 2024

View reviewed changes

achow101 merged commit ef6329f into bitcoin:master Mar 13, 2024

theStack deleted the test-compressscript_uncompressed_p2pk_not_on_curve branch March 13, 2024 15:21

bitcoin locked and limited conversation to collaborators Mar 13, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

test: add script compression coverage for not-on-curve P2PK outputs #28193

test: add script compression coverage for not-on-curve P2PK outputs #28193

Uh oh!

theStack commented Jul 31, 2023

Uh oh!

DrahtBot commented Jul 31, 2023 •

edited

Loading

Uh oh!

tdb3 left a comment

Uh oh!

tdb3 Feb 15, 2024 •

edited

Loading

Uh oh!

cbergqvist Feb 23, 2024

Uh oh!

marcofleon Feb 27, 2024

Uh oh!

cbergqvist left a comment

Uh oh!

cbergqvist Feb 23, 2024

Uh oh!

marcofleon left a comment •

edited

Loading

Uh oh!

davidgumberg Mar 2, 2024 •

edited

Loading

Uh oh!

achow101 commented Mar 13, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

	pubkey.Set(&script[1], &script[66]);
	return pubkey.IsFullyValid(); // if not fully valid, a case that would not be compressible

	case 0x04:
	case 0x05:
	unsigned char vch[33] = {};
	vch[0] = nSize - 2;
	memcpy(&vch[1], in.data(), 32);
	CPubKey pubkey{vch};
	if (!pubkey.Decompress())
	return false;

test: add script compression coverage for not-on-curve P2PK outputs #28193

test: add script compression coverage for not-on-curve P2PK outputs #28193

Uh oh!

Conversation

theStack commented Jul 31, 2023

Uh oh!

DrahtBot commented Jul 31, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage

Reviews

Conflicts

Uh oh!

tdb3 left a comment

Choose a reason for hiding this comment

Uh oh!

tdb3 Feb 15, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cbergqvist Feb 23, 2024

Choose a reason for hiding this comment

Uh oh!

marcofleon Feb 27, 2024

Choose a reason for hiding this comment

Uh oh!

cbergqvist left a comment

Choose a reason for hiding this comment

Uh oh!

cbergqvist Feb 23, 2024

Choose a reason for hiding this comment

Uh oh!

marcofleon left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

davidgumberg Mar 2, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 commented Mar 13, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

DrahtBot commented Jul 31, 2023 •

edited

Loading

tdb3 Feb 15, 2024 •

edited

Loading

marcofleon left a comment •

edited

Loading

davidgumberg Mar 2, 2024 •

edited

Loading