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

pull theStack wants to merge 1 commits into bitcoin:master from theStack:test-compressscript_uncompressed_p2pk_not_on_curve changing 1 files +33 −0

theStack commented at 3:22 PM on July 31, 2023: contributor

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

https://github.com/bitcoin/bitcoin/blob/44b05bf3fef2468783dcebf651654fdd30717e7e/src/compressor.cpp#L49-L50

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:

https://github.com/bitcoin/bitcoin/blob/44b05bf3fef2468783dcebf651654fdd30717e7e/src/compressor.cpp#L122-L129

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 commented at 3:22 PM on July 31, 2023: contributor



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.
DrahtBot added the label Tests on Jul 31, 2023
DrahtBot added the label Needs rebase on Aug 17, 2023
theStack force-pushed on Aug 18, 2023
DrahtBot removed the label Needs rebase on Aug 19, 2023
DrahtBot added the label CI failed on Oct 25, 2023
theStack force-pushed on Jan 6, 2024
DrahtBot removed the label CI failed on Jan 6, 2024
DrahtBot added the label CI failed on Jan 12, 2024
test: add script compression coverage for not-on-curve P2PK outputs 28287cfbe1
theStack force-pushed on Jan 22, 2024
DrahtBot removed the label CI failed on Jan 22, 2024
in src/test/compress_tests.cpp:140 in 28287cfbe1
```
 131 | @@ -131,4 +132,36 @@ BOOST_AUTO_TEST_CASE(compress_script_to_uncompressed_pubkey_id)
 132 |      BOOST_CHECK_EQUAL(out[0], 0x04 | (script[65] & 0x01)); // least significant bit (lsb) of last char of pubkey is mapped into out[0]
 133 |  }
 134 |  
 135 | +BOOST_AUTO_TEST_CASE(compress_p2pk_scripts_not_on_curve)
 136 | +{
 137 | +    XOnlyPubKey x_not_on_curve;
 138 | +    do {
 139 | +        x_not_on_curve = XOnlyPubKey(g_insecure_rand_ctx.randbytes(32));
 140 | +    } while (x_not_on_curve.IsFullyValid());
```
tdb3 commented at 1:26 AM on February 15, 2024:

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

cbergqvist commented at 9:48 AM on February 23, 2024:

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 commented at 12:04 AM on February 27, 2024:

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.
tdb3 commented at 1:27 AM on February 15, 2024: contributor

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

Test actions taken: Checkout the PR branch, built, ran all unit and functional tests (all passed).
cbergqvist approved
cbergqvist commented at 10:16 AM on February 23, 2024: contributor

ACK 28287cf!
marcofleon approved
marcofleon commented at 12:06 AM on February 27, 2024: contributor

Nicely done, ACK 28287cfbe18b6c468f76389e9f66bdcf2d00f8d1. 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.

Type	Reviewers
ACK	tdb3, cbergqvist, marcofleon, achow101

in src/test/compress_tests.cpp:159 in 28287cfbe1

 154 | +    bool done = CompressScript(script, out);
 155 | +    BOOST_CHECK_EQUAL(done, false);
 156 | +
 157 | +    // Check that compressed P2PK script with uncompressed pubkey that is not fully
 158 | +    // valid (i.e. x coordinate of the pubkey is not on curve) can't be decompressed
 159 | +    CompressedScript compressed_script(x_not_on_curve.begin(), x_not_on_curve.end());

davidgumberg commented at 1:59 AM on March 2, 2024:

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 commented at 1:28 PM on March 13, 2024: member

ACK 28287cfbe18b6c468f76389e9f66bdcf2d00f8d1
achow101 merged this on Mar 13, 2024
achow101 closed this on Mar 13, 2024
theStack deleted the branch on Mar 13, 2024
bitcoin locked this on Mar 13, 2025

Contributors

Labels

Linked (view graph)

#24628 rpc: dumptxoutset as sqlite file #27432 contrib: add tool to convert compact-serialized UTXO set to SQLite database

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

Code Coverage

Reviews

Conflicts