script/sign: avoid duplicated signature verification after signing (+introduce signing benchmarks)

theStack commented at 4:30 pm on November 21, 2023: contributor

This PR is a small performance improvement on the SignTransaction function, which is used mostly by the wallet (obviously) and the signrawtransactionwithkey RPC. The lower-level function ProduceSignature already calls VerifyScript internally as last step in order to check whether the signature data is complete: https://github.com/bitcoin/bitcoin/blob/daa56f7f665183bcce3df146f143be37f33c123e/src/script/sign.cpp#L568-L570

If and only if that is the case, the complete field of the SignatureData is set to true accordingly and there is no need then to verify the script after again, as we already know that it would succeed.

This leads to a rough ~20% speed-up for SignTransaction for single-input ECDSA or Taproot transactions, according to the newly introduced SignTransaction{ECDSA,Taproot} benchmarks:

0$ ./src/bench/bench_bitcoin --filter=SignTransaction.*

without commit 18185f4f578b8795fdaa75926630a691e9c8d0d4:

ns/op	op/s	err%	total	benchmark
185,597.79	5,388.00	1.6%	0.22	`SignTransactionECDSA`
141,323.95	7,075.94	2.1%	0.17	`SignTransactionSchnorr`

with commit 18185f4f578b8795fdaa75926630a691e9c8d0d4:

ns/op	op/s	err%	total	benchmark
149,757.86	6,677.45	1.4%	0.18	`SignTransactionECDSA`
108,284.40	9,234.94	2.0%	0.13	`SignTransactionSchnorr`

Note that there are already signing benchmarks in the secp256k1 library, but SignTransaction does much more than just the cryptographical parts, i.e.:

calculate the unsigned tx’s PrecomputedTransactionData if necessary
apply Solver on the prevout scriptPubKey, fetch the relevant keys from the signing provider
perform the actual signing operation (for ECDSA signatures, that could be more than once due to low-R grinding)
verify if the signatures are correct by calling VerifyScript (more than once currently, which is fixed by this PR)

so it probably makes sense to also have benchmarks from that higher-level application perspective.

DrahtBot commented at 4:31 pm on November 21, 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	furszy, glozow, 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.

theStack force-pushed on Nov 21, 2023

DrahtBot added the label CI failed on Nov 21, 2023

DrahtBot removed the label CI failed on Nov 21, 2023

DrahtBot added the label CI failed on Nov 28, 2023

achow101 commented at 2:53 pm on November 28, 2023: member

Concept ACK

theStack force-pushed on Nov 29, 2023

theStack commented at 12:31 pm on November 29, 2023: contributor

Rebased on master, CI should be green now (there was a silent merge conflict in the benchmark due to a change in the COutPoint ctor interface, see #28922).

DrahtBot removed the label CI failed on Nov 29, 2023

fanquake requested review from sipa on Nov 30, 2023

luke-jr commented at 1:32 am on December 5, 2023: member

Does this reduce our safety against memory corruption or similar?

theStack commented at 4:45 pm on December 5, 2023: contributor

Does this reduce our safety against memory corruption or similar?

I don’t think so, at least I don’t see how verifying a created signature twice in a row has any benefit over doing it only once.

DrahtBot added the label CI failed on Jan 16, 2024

theStack force-pushed on Jan 22, 2024

in src/bench/sign_transaction.cpp:26 in 30aa0fa78a outdated

21+
22+static void SignTransactionSingleInput(benchmark::Bench& bench, InputType input_type)
23+{
24+    ECC_Start();
25+
26+    FillableSigningProvider keystore;

furszy commented at 1:42 pm on January 22, 2024:

Would suggest to use FlatSigningProvider instead (see #28307). It will also save you one extra GetScriptForDestination call per created key.

theStack commented at 2:47 pm on January 26, 2024:

Have to admit that I’m lacking knowledge here about the concrete differences between FillableSigningProvider and FlatSigningProvider, especially about the possible benefits of the latter in this PR. AFAIR, I chose the fillable provider as it provides a nice interface (.AddKey()), which the flat one doesn’t. The following patch works:

 0diff --git a/src/bench/sign_transaction.cpp b/src/bench/sign_transaction.cpp
 1index 8cb5e63882..8bd2ecbcd0 100644
 2--- a/src/bench/sign_transaction.cpp
 3+++ b/src/bench/sign_transaction.cpp
 4@@ -23,7 +23,7 @@ static void SignTransactionSingleInput(benchmark::Bench& bench, InputType input_
 5 {
 6     ECC_Start();
 7 
 8-    FillableSigningProvider keystore;
 9+    FlatSigningProvider keystore;
10     std::vector<CScript> prev_spks;
11 
12     // Create a bunch of keys / UTXOs to avoid signing with the same key repeatedly
13@@ -31,7 +31,9 @@ static void SignTransactionSingleInput(benchmark::Bench& bench, InputType input_
14         CKey privkey;
15         privkey.MakeNewKey(/*fCompressed=*/true);
16         CPubKey pubkey = privkey.GetPubKey();
17-        keystore.AddKey(privkey);
18+        CKeyID key_id = pubkey.GetID();
19+        keystore.keys.emplace(key_id, privkey);
20+        keystore.pubkeys.emplace(key_id, pubkey);
21 
22         // Create specified locking script type
23         CScript prev_spk;

Is there anything more that could be changed? I don’t see how it makes the derivation of the outpoint scriptPubKey (needed for the map of coins) any easier, as I still need the individual GetScriptForDestination calls dependend on the locking script type.

furszy commented at 7:06 pm on January 26, 2024:

Have to admit that I’m lacking knowledge here about the concrete differences between FillableSigningProvider and FlatSigningProvider, especially about the possible benefits of the latter in this PR.

FillableSigningProvider is just the legacy class and contains legacy scripts limitations (thus #28307). It does not affect the current form of this PR but, because this benchmark uses segwit v0 and v1 outputs, it could cause issues in the future.

Is there anything more that could be changed? I don’t see how it makes the derivation of the outpoint scriptPubKey (needed for the map of coins) any easier, as I still need the individual GetScriptForDestination calls dependend on the locking script type.

I never said that it was going to make derivation easier. I Just said that it will also save you an extra GetScriptForDestination call per script.

 0diff --git a/src/bench/sign_transaction.cpp b/src/bench/sign_transaction.cpp
 1--- a/src/bench/sign_transaction.cpp	(revision 90469c8b7c1cd1d88134f6837914552792cbef49)
 2+++ b/src/bench/sign_transaction.cpp	(date 1706283907363)
 3@@ -23,15 +23,16 @@
 4 {
 5     ECC_Start();
 6 
 7-    FillableSigningProvider keystore;
 8-    std::vector<CScript> prev_spks;
 9+    FlatSigningProvider keystore;
10 
11     // Create a bunch of keys / UTXOs to avoid signing with the same key repeatedly
12     for (int i = 0; i < 32; i++) {
13         CKey privkey;
14         privkey.MakeNewKey(/*fCompressed=*/true);
15         CPubKey pubkey = privkey.GetPubKey();
16-        keystore.AddKey(privkey);
17+        CKeyID key_id = pubkey.GetID();
18+        keystore.keys.emplace(key_id, privkey);
19+        keystore.pubkeys.emplace(key_id, pubkey);
20 
21         // Create specified locking script type
22         CScript prev_spk;
23@@ -40,7 +41,7 @@
24         case InputType::P2TR:   prev_spk = GetScriptForDestination(WitnessV1Taproot(XOnlyPubKey{pubkey})); break;
25         default: assert(false);
26         }
27-        prev_spks.push_back(prev_spk);
28+        keystore.scripts.insert({CScriptID{prev_spk}, prev_spk});
29     }
30 
31     // Simple 1-input tx with artificial outpoint
32@@ -50,15 +51,16 @@
33     unsigned_tx.vin.emplace_back(prevout);
34 
35     // Benchmark.
36-    int iter = 0;
37+    auto it = keystore.scripts.begin();
38     bench.minEpochIterations(100).run([&] {
39         CMutableTransaction tx{unsigned_tx};
40         std::map<COutPoint, Coin> coins;
41-        CScript prev_spk = prev_spks[(iter++) % prev_spks.size()];
42+        const CScript& prev_spk = it->second;
43         coins[prevout] = Coin(CTxOut(10000, prev_spk), /*nHeightIn=*/100, /*fCoinBaseIn=*/false);
44         std::map<int, bilingual_str> input_errors;
45         bool complete = SignTransaction(tx, &keystore, coins, SIGHASH_ALL, input_errors);
46         assert(complete);
47+        if (++it == keystore.scripts.end()) it = keystore.scripts.begin();
48     });
49 
50     ECC_Stop();

theStack commented at 0:50 am on January 27, 2024:

FillableSigningProvider is just the legacy class and contains legacy scripts limitations (thus #28307). It does not affect the current form of this PR but, because this benchmark uses segwit v0 and v1 outputs, it could cause issues in the future.

Ok, good to know.

I never said that it was going to make derivation easier. I Just said that it will also save you an extra GetScriptForDestination call per script.

Took me a while now to understand what exactly you mean, after looking deeper in what happens in FillableSigningProvider::AddKey() and realizing that leads to an indirect GetScriptForDestination call. I initially assumed that you talk about needing less GetScriptForDestination calls directly in the benchmark preparation loop (i.e. “save” interpreted in the sense of less code from me, rather than less run-time overhead), which would have surprised me.

I’m still confused on why we would want/need to fill the .scripts of the FlatSigningProvider though. Aren’t those only relevant for spends where redeem scripts are involved, i.e. P2(W)SH? Your proposed patch uses the .scripts map of the provider instead of an array to store the prev_spks, but that map is never accessed inside SignTransaction.

I’ve changed the PR to take use of FlatSigningProvider (and GenerateRandomKey for privkey instantiation, which wasn’t available in master back then), but didn’t fill the .scripts map as it seems not necessary for the script types tested here.

DrahtBot removed the label CI failed on Jan 22, 2024

willcl-ark added the label Wallet on Jan 24, 2024

willcl-ark added the label Tests on Jan 24, 2024

willcl-ark added the label Resource usage on Jan 24, 2024

theStack force-pushed on Jan 27, 2024

DrahtBot added the label CI failed on Apr 4, 2024

DrahtBot removed the label CI failed on Apr 4, 2024

achow101 requested review from achow101 on Apr 9, 2024

achow101 requested review from furszy on Apr 9, 2024

achow101 commented at 5:29 pm on April 15, 2024: member

ACK 3a3ccf00f0bb6b6450dcf859982cdb40bb06f475

achow101 removed review request from achow101 on Apr 15, 2024

furszy commented at 10:17 pm on April 17, 2024: member

Code ACK 3a3ccf00f0b

DrahtBot added the label CI failed on May 12, 2024

DrahtBot commented at 2:51 pm on May 12, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/20920916767

bench: add benchmark for `SignTransaction` 080089567c

script/sign: avoid duplicated signature verification after signing

`ProduceSignature` already calls `VerifyScript` internally as last step in
order to check whether the signature data is complete. If and only if that is
the case, the `complete` field of the `SignatureData` is set accordingly and
there is no need then to verify the script after again, as we already know that
it would succeed.

This leads to a rough ~20% speed-up for `SignTransaction` for single-input
ECDSA or Taproot inputs, according to the `SignTransaction{ECDSA,Taproot}`
benchmarks.

fe92c15f0c

theStack force-pushed on May 12, 2024

theStack commented at 4:08 pm on May 12, 2024: contributor

Rebased on master, which was necessary due to the removal of ECC_{Start,Stop} from the key header in #29252. The ECC_Context RAII wrapper is used now instead (like done in commit 28905c1a64a87a56f16aea8a4d23dea7eec9ca59). Re-review should be trivial.

DrahtBot removed the label CI failed on May 12, 2024

furszy commented at 10:49 pm on May 12, 2024: member

utACK fe92c15f0c44

DrahtBot requested review from achow101 on May 12, 2024

glozow commented at 4:55 pm on July 15, 2024: member

light review ACK fe92c15f0c44d1405b9048306736bd0eae868506

Not super familiar with this area, did some code review to try to make sure the VerifyScript in ProduceSignature and end of SignTransaction have the same arguments, and complete can’t e.g. be from a DummySignatureChecker. AFAICT the MutableTransactionSignatureCreator::Checker() and TransactionSignatureChecker(...) here should be equivalent.

achow101 commented at 8:01 pm on July 16, 2024: member

ACK fe92c15f0c44d1405b9048306736bd0eae868506

achow101 merged this on Jul 16, 2024

achow101 closed this on Jul 16, 2024

hebasto added the label Needs CMake port on Jul 16, 2024

theStack deleted the branch on Jul 16, 2024

hebasto commented at 12:44 pm on July 24, 2024: member

Ported to the CMake-based build system in https://github.com/hebasto/bitcoin/pull/280.

hebasto removed the label Needs CMake port on Jul 24, 2024

script/sign: avoid duplicated signature verification after signing (+introduce signing benchmarks) #28923

Code Coverage

Reviews

Conflicts