Support for Schnorr signatures and integration in SignatureCheckers (BIP 340)

This enables the schnorrsig module in libsecp256k1, adds the relevant types
and functions to src/pubkey, as well as in higher-level `SignatureChecker`
classes. The (verification side of the) BIP340 test vectors is also added.

7 files changed, 82 insertions, 6 deletions

diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index af8fd4912e..aef6e28118 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1522,6 +1522,12 @@ bool GenericTransactionSignatureChecker<T>::VerifyECDSASignature(const std::vect
 }
 
 template <class T>
+bool GenericTransactionSignatureChecker<T>::VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const
+{
+    return pubkey.VerifySchnorr(sighash, sig);
+}
+
+template <class T>
 bool GenericTransactionSignatureChecker<T>::CheckECDSASignature(const std::vector<unsigned char>& vchSigIn, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const
 {
     CPubKey pubkey(vchPubKey);
@@ -1544,6 +1550,30 @@ 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, ScriptError* serror) const
+{
+    assert(sigversion == SigVersion::TAPROOT);
+    // Schnorr signatures have 32-byte public keys. The caller is responsible for enforcing this.
+    assert(pubkey_in.size() == 32);
+    if (sig.size() != 64 && sig.size() != 65) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_SIZE);
+
+    XOnlyPubKey pubkey{pubkey_in};
+
+    uint8_t hashtype = SIGHASH_DEFAULT;
+    if (sig.size() == 65) {
+        hashtype = SpanPopBack(sig);
+        if (hashtype == SIGHASH_DEFAULT) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE);
+    }
+    uint256 sighash;
+    assert(this->txdata);
+    if (!SignatureHashSchnorr(sighash, *txTo, nIn, hashtype, sigversion, *this->txdata)) {
+        return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE);
+    }
+    if (!VerifySchnorrSignature(sig, pubkey, sighash)) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG);
+    return true;
+}
+
+template <class T>
 bool GenericTransactionSignatureChecker<T>::CheckLockTime(const CScriptNum& nLockTime) const
 {
     // There are two kinds of nLockTime: lock-by-blockheight
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index b739528f0f..e54243c8f0 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -7,12 +7,14 @@
 #define BITCOIN_SCRIPT_INTERPRETER_H
 
 #include <script/script_error.h>
+#include <span.h>
 #include <primitives/transaction.h>
 
 #include <vector>
 #include <stdint.h>
 
 class CPubKey;
+class XOnlyPubKey;
 class CScript;
 class CTransaction;
 class CTxOut;
@@ -176,6 +178,11 @@ public:
         return false;
     }
 
+    virtual bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptError* serror = nullptr) const
+    {
+        return false;
+    }
+
     virtual bool CheckLockTime(const CScriptNum& nLockTime) const
     {
          return false;
@@ -200,11 +207,13 @@ private:
 
 protected:
     virtual bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const;
+    virtual bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const;
 
 public:
     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn) : txTo(txToIn), 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, ScriptError* serror = nullptr) const override;
     bool CheckLockTime(const CScriptNum& nLockTime) const override;
     bool CheckSequence(const CScriptNum& nSequence) const override;
 };
diff --git a/src/script/script_error.cpp b/src/script/script_error.cpp
index 3b383393f9..9c49ced3ed 100644
--- a/src/script/script_error.cpp
+++ b/src/script/script_error.cpp
@@ -91,6 +91,12 @@ std::string ScriptErrorString(const ScriptError serror)
             return "Witness provided for non-witness script";
         case SCRIPT_ERR_WITNESS_PUBKEYTYPE:
             return "Using non-compressed keys in segwit";
+        case SCRIPT_ERR_SCHNORR_SIG_SIZE:
+            return "Invalid Schnorr signature size";
+        case SCRIPT_ERR_SCHNORR_SIG_HASHTYPE:
+            return "Invalid Schnorr signature hash type";
+        case SCRIPT_ERR_SCHNORR_SIG:
+            return "Invalid Schnorr signature";
         case SCRIPT_ERR_OP_CODESEPARATOR:
             return "Using OP_CODESEPARATOR in non-witness script";
         case SCRIPT_ERR_SIG_FINDANDDELETE:
diff --git a/src/script/script_error.h b/src/script/script_error.h
index 2978c147e1..c79a11a94b 100644
--- a/src/script/script_error.h
+++ b/src/script/script_error.h
@@ -66,6 +66,11 @@ typedef enum ScriptError_t
     SCRIPT_ERR_WITNESS_UNEXPECTED,
     SCRIPT_ERR_WITNESS_PUBKEYTYPE,
 
+    /* Taproot */
+    SCRIPT_ERR_SCHNORR_SIG_SIZE,
+    SCRIPT_ERR_SCHNORR_SIG_HASHTYPE,
+    SCRIPT_ERR_SCHNORR_SIG,
+
     /* Constant scriptCode */
     SCRIPT_ERR_OP_CODESEPARATOR,
     SCRIPT_ERR_SIG_FINDANDDELETE,
diff --git a/src/script/sigcache.cpp b/src/script/sigcache.cpp
index b9ba006e47..4a6e04f2eb 100644
--- a/src/script/sigcache.cpp
+++ b/src/script/sigcache.cpp
@@ -22,8 +22,9 @@ namespace {
 class CSignatureCache
 {
 private:
-     //! Entries are SHA256(nonce || signature hash || public key || signature):
-    CSHA256 m_salted_hasher;
+     //! Entries are SHA256(nonce || 'E' or 'S' || 31 zero bytes || signature hash || public key || signature):
+    CSHA256 m_salted_hasher_ecdsa;
+    CSHA256 m_salted_hasher_schnorr;
     typedef CuckooCache::cache<uint256, SignatureCacheHasher> map_type;
     map_type setValid;
     boost::shared_mutex cs_sigcache;
@@ -34,18 +35,30 @@ public:
         uint256 nonce = GetRandHash();
         // We want the nonce to be 64 bytes long to force the hasher to process
         // this chunk, which makes later hash computations more efficient. We
-        // just write our 32-byte entropy twice to fill the 64 bytes.
-        m_salted_hasher.Write(nonce.begin(), 32);
-        m_salted_hasher.Write(nonce.begin(), 32);
+        // just write our 32-byte entropy, and then pad with 'E' for ECDSA and
+        // 'S' for Schnorr (followed by 0 bytes).
+        static constexpr unsigned char PADDING_ECDSA[32] = {'E'};
+        static constexpr unsigned char PADDING_SCHNORR[32] = {'S'};
+        m_salted_hasher_ecdsa.Write(nonce.begin(), 32);
+        m_salted_hasher_ecdsa.Write(PADDING_ECDSA, 32);
+        m_salted_hasher_schnorr.Write(nonce.begin(), 32);
+        m_salted_hasher_schnorr.Write(PADDING_SCHNORR, 32);
     }
 
     void
     ComputeEntryECDSA(uint256& entry, const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubkey)
     {
-        CSHA256 hasher = m_salted_hasher;
+        CSHA256 hasher = m_salted_hasher_ecdsa;
         hasher.Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(&vchSig[0], vchSig.size()).Finalize(entry.begin());
     }
 
+    void
+    ComputeEntrySchnorr(uint256& entry, const uint256 &hash, Span<const unsigned char> sig, const XOnlyPubKey& pubkey)
+    {
+        CSHA256 hasher = m_salted_hasher_schnorr;
+        hasher.Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(sig.data(), sig.size()).Finalize(entry.begin());
+    }
+
     bool
     Get(const uint256& entry, const bool erase)
     {
@@ -97,3 +110,13 @@ bool CachingTransactionSignatureChecker::VerifyECDSASignature(const std::vector<
         signatureCache.Set(entry);
     return true;
 }
+
+bool CachingTransactionSignatureChecker::VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const
+{
+    uint256 entry;
+    signatureCache.ComputeEntrySchnorr(entry, sighash, sig, pubkey);
+    if (signatureCache.Get(entry, !store)) return true;
+    if (!TransactionSignatureChecker::VerifySchnorrSignature(sig, pubkey, sighash)) return false;
+    if (store) signatureCache.Set(entry);
+    return true;
+}
diff --git a/src/script/sigcache.h b/src/script/sigcache.h
index 49c6b192e9..00534f9758 100644
--- a/src/script/sigcache.h
+++ b/src/script/sigcache.h
@@ -7,6 +7,7 @@
 #define BITCOIN_SCRIPT_SIGCACHE_H
 
 #include <script/interpreter.h>
+#include <span.h>
 
 #include <vector>
 
@@ -49,6 +50,7 @@ public:
     CachingTransactionSignatureChecker(const CTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, bool storeIn, PrecomputedTransactionData& txdataIn) : TransactionSignatureChecker(txToIn, nInIn, amountIn, txdataIn), store(storeIn) {}
 
     bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const override;
+    bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const override;
 };
 
 void InitSignatureCache();
diff --git a/src/script/sign.h b/src/script/sign.h
index b77d26c0d7..a1cfe1574d 100644
--- a/src/script/sign.h
+++ b/src/script/sign.h
@@ -11,6 +11,7 @@
 #include <pubkey.h>
 #include <script/interpreter.h>
 #include <script/keyorigin.h>
+#include <span.h>
 #include <streams.h>
 
 class CKey;