Merge bitcoin/bitcoin#24105: Optimize CHECKSIGADD Script Validation

cfa575266bc0198574a82e8e386040e969b05dea Optimize CHECKSIGADD Script Validation (Jeremy Rubin)

Pull request description:

  This is a mild validation improvement that improves performance by caching some signature data when you have a Taproot script fragment that uses CHECKSIGADD Multisignatures with sighash single. In some basic testing I showed this to have about a 0.6% speedup during block validation for a block with a lot of CHECKSIGADDs, but that was with the entirety of block validation so the specific impact on the script interpreter performance should be a bit more once you subtract things like coin fetching. If desired I can produce a more specific/sharable bench for this, the code I used to test was just monkey patching the existing taproot tests since generating valid spends is kinda tricky. But it's sort of an obvious win so I'm not sure it needs a rigorous bench, but I will tinker on one of those while the code is being reviewed for correctness.

  The overhead of this approach is that:

  1. ScriptExecutionData is no longer const
  2. around 32 bytes of extra stack space
  3. zero extra hashing since we only cache on first use

ACKs for top commit:
  sipa:
    utACK cfa575266bc0198574a82e8e386040e969b05dea
  MarcoFalke:
    review ACK cfa575266bc0198574a82e8e386040e969b05dea
  jonatack:
    ACK cfa575266bc0198574a82e8e386040e969b05dea
  theStack:
    Code-review ACK cfa575266bc0198574a82e8e386040e969b05dea

Tree-SHA512: d5938773724bb9c97b6fd623ef7efdf7f522af52dc0903ecb88c38a518b628d7915b7eae6a774f7be653dc6bcd92e9abc4dd5e8b11f3a995e01e0102d2113d09

4 files changed, 18 insertions, 11 deletions

diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index 95ffe40a74..07b44971b7 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1500,7 +1500,7 @@ static bool HandleMissingData(MissingDataBehavior mdb)
 }
 
 template<typename T>
-bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache, MissingDataBehavior mdb)
+bool SignatureHashSchnorr(uint256& hash_out, ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache, MissingDataBehavior mdb)
 {
     uint8_t ext_flag, key_version;
     switch (sigversion) {
@@ -1568,9 +1568,12 @@ bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata
     // Data about the output (if only one).
     if (output_type == SIGHASH_SINGLE) {
         if (in_pos >= tx_to.vout.size()) return false;
-        CHashWriter sha_single_output(SER_GETHASH, 0);
-        sha_single_output << tx_to.vout[in_pos];
-        ss << sha_single_output.GetSHA256();
+        if (!execdata.m_output_hash) {
+            CHashWriter sha_single_output(SER_GETHASH, 0);
+            sha_single_output << tx_to.vout[in_pos];
+            execdata.m_output_hash = sha_single_output.GetSHA256();
+        }
+        ss << execdata.m_output_hash.value();
     }
 
     // Additional data for BIP 342 signatures
@@ -1692,7 +1695,7 @@ bool GenericTransactionSignatureChecker<T>::CheckECDSASignature(const std::vecto
 }
 
 template <class T>
-bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror) const
+bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror) const
 {
     assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT);
     // Schnorr signatures have 32-byte public keys. The caller is responsible for enforcing this.
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index 2a28f1a2d3..cf1953ad22 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -11,6 +11,7 @@
 #include <span.h>
 #include <primitives/transaction.h>
 
+#include <optional>
 #include <vector>
 #include <stdint.h>
 
@@ -215,6 +216,9 @@ struct ScriptExecutionData
     bool m_validation_weight_left_init = false;
     //! How much validation weight is left (decremented for every successful non-empty signature check).
     int64_t m_validation_weight_left;
+
+    //! The hash of the corresponding output
+    std::optional<uint256> m_output_hash;
 };
 
 /** Signature hash sizes */
@@ -244,7 +248,7 @@ public:
         return false;
     }
 
-    virtual bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const
+    virtual bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const
     {
         return false;
     }
@@ -272,7 +276,7 @@ enum class MissingDataBehavior
 };
 
 template<typename T>
-bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache, MissingDataBehavior mdb);
+bool SignatureHashSchnorr(uint256& hash_out, ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache, MissingDataBehavior mdb);
 
 template <class T>
 class GenericTransactionSignatureChecker : public BaseSignatureChecker
@@ -292,7 +296,7 @@ public:
     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {}
     bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
-    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override;
+    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override;
     bool CheckLockTime(const CScriptNum& nLockTime) const override;
     bool CheckSequence(const CScriptNum& nSequence) const override;
 };
@@ -313,7 +317,7 @@ public:
         return m_checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion);
     }
 
-    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
+    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
     {
         return m_checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror);
     }
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 8e08448480..371a937bc8 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -542,7 +542,7 @@ class DummySignatureChecker final : public BaseSignatureChecker
 public:
     DummySignatureChecker() {}
     bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override { return true; }
-    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror) const override { return true; }
+    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror) const override { return true; }
 };
 const DummySignatureChecker DUMMY_CHECKER;
 
diff --git a/src/test/fuzz/signature_checker.cpp b/src/test/fuzz/signature_checker.cpp
index deffe26b17..f6c591aca4 100644
--- a/src/test/fuzz/signature_checker.cpp
+++ b/src/test/fuzz/signature_checker.cpp
@@ -34,7 +34,7 @@ public:
         return m_fuzzed_data_provider.ConsumeBool();
     }
 
-    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
+    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
     {
         return m_fuzzed_data_provider.ConsumeBool();
     }