Repository: bitcoin/bitcoin (language: cpp)

Issue:
Add Taproot support to libconsensus
In preparation for the potential Taproot soft fork, libconsensus should be updated to support verifying Taproot scripts.

There are two changes I see as necessary:

- Add a VERIFY_TAPROOT flag
- Change the API to support passing in spent outputs (bitcoinconsensus_verify_script_with_spent_outputs?)


Discussion / hints:

Fix patch:
diff --git a/doc/release-notes-123.md b/doc/release-notes-123.md
new file mode 100644
index 0000000000000..fffd211f37125
--- /dev/null
+++ b/doc/release-notes-123.md
@@ -0,0 +1,5 @@
+Tools and Utilities
+---
+
+- A new `bitcoinconsensus_verify_script_with_spent_outputs` function is available in libconsensus which optionally accepts the spent outputs of the transaction being verified.
+- A new `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT` flag is available in libconsensus that will verify scripts with the Taproot spending rules.
\ No newline at end of file
diff --git a/doc/shared-libraries.md b/doc/shared-libraries.md
index 147e2237115ec..07aee46f0bbf8 100644
--- a/doc/shared-libraries.md
+++ b/doc/shared-libraries.md
@@ -11,13 +11,14 @@ The interface is defined in the C header `bitcoinconsensus.h` located in `src/sc
 
 #### Version
 
-`bitcoinconsensus_version` returns an `unsigned int` with the API version *(currently `1`)*.
+`bitcoinconsensus_version` returns an `unsigned int` with the API version *(currently `2`)*.
 
 #### Script Validation
 
-`bitcoinconsensus_verify_script` returns an `int` with the status of the verification. It will be `1` if the input script correctly spends the previous output `scriptPubKey`.
+`bitcoinconsensus_verify_script`, `bitcoinconsensus_verify_script_with_amount` and `bitcoinconsensus_verify_script_with_spent_outputs` return an `int` with the status of the verification. It will be `1` if the input script correctly spends the previous output `scriptPubKey`.
 
 ##### Parameters
+###### bitcoinconsensus_verify_script
 - `const unsigned char *scriptPubKey` - The previous output script that encumbers spending.
 - `unsigned int scriptPubKeyLen` - The number of bytes for the `scriptPubKey`.
 - `const unsigned char *txTo` - The transaction with the input that is spending the previous output.
@@ -26,6 +27,28 @@ The interface is defined in the C header `bitcoinconsensus.h` located in `src/sc
 - `unsigned int flags` - The script validation flags *(see below)*.
 - `bitcoinconsensus_error* err` - Will have the error/success code for the operation *(see below)*.
 
+###### bitcoinconsensus_verify_script_with_amount
+- `const unsigned char *scriptPubKey` - The previous output script that encumbers spending.
+- `unsigned int scriptPubKeyLen` - The number of bytes for the `scriptPubKey`.
+- `int64_t amount` - The amount spent in the input
+- `const unsigned char *txTo` - The transaction with the input that is spending the previous output.
+- `unsigned int txToLen` - The number of bytes for the `txTo`.
+- `unsigned int nIn` - The index of the input in `txTo` that spends the `scriptPubKey`.
+- `unsigned int flags` - The script validation flags *(see below)*.
+- `bitcoinconsensus_error* err` - Will have the error/success code for the operation *(see below)*.
+
+###### bitcoinconsensus_verify_script_with_spent_outputs
+- `const unsigned char *scriptPubKey` - The previous output script that encumbers spending.
+- `unsigned int scriptPubKeyLen` - The number of bytes for the `scriptPubKey`.
+- `int64_t amount` - The amount spent in the input
+- `const unsigned char *txTo` - The transaction with the input that is spending the previous output.
+- `unsigned int txToLen` - The number of bytes for the `txTo`.
+- `UTXO *spentOutputs` - Previous outputs spent in the transaction. `UTXO` is a struct composed by `const unsigned char *scriptPubKey`, `unsigned int scriptPubKeySize` (the number of bytes for the `scriptPubKey`) and `unsigned int value`.
+- `unsigned int spentOutputsLen` - The number of bytes for the `spentOutputs`.
+- `unsigned int nIn` - The index of the input in `txTo` that spends the `scriptPubKey`.
+- `unsigned int flags` - The script validation flags *(see below)*.
+- `bitcoinconsensus_error* err` - Will have the error/success code for the operation *(see below)*.
+
 ##### Script Flags
 - `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_NONE`
 - `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_P2SH` - Evaluate P2SH ([BIP16](https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki)) subscripts
@@ -34,6 +57,7 @@ The interface is defined in the C header `bitcoinconsensus.h` located in `src/sc
 - `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKLOCKTIMEVERIFY` - Enable CHECKLOCKTIMEVERIFY ([BIP65](https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki))
 - `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKSEQUENCEVERIFY` - Enable CHECKSEQUENCEVERIFY ([BIP112](https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki))
 - `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_WITNESS` - Enable WITNESS ([BIP141](https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki))
+- `bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT` - Enable TAPROOT ([BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki), [BIP342](https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki))
 
 ##### Errors
 - `bitcoinconsensus_ERR_OK` - No errors with input parameters *(see the return value of `bitcoinconsensus_verify_script` for the verification status)*
@@ -42,9 +66,12 @@ The interface is defined in the C header `bitcoinconsensus.h` located in `src/sc
 - `bitcoinconsensus_ERR_DESERIALIZE` - An error deserializing `txTo`
 - `bitcoinconsensus_ERR_AMOUNT_REQUIRED` - Input amount is required if WITNESS is used
 - `bitcoinconsensus_ERR_INVALID_FLAGS` - Script verification `flags` are invalid (i.e. not part of the libconsensus interface)
+- `bitcoinconsensus_ERR_SPENT_OUTPUTS_REQUIRED` - Spent outputs are required if TAPROOT is used
+- `bitcoinconsensus_ERR_SPENT_OUTPUTS_MISMATCH` - Spent outputs size doesn't match tx inputs size
 
 ### Example Implementations
 - [NBitcoin](https://github.com/MetacoSA/NBitcoin/blob/5e1055cd7c4186dee4227c344af8892aea54faec/NBitcoin/Script.cs#L979-#L1031) (.NET Bindings)
 - [node-libbitcoinconsensus](https://github.com/bitpay/node-libbitcoinconsensus) (Node.js Bindings)
 - [java-libbitcoinconsensus](https://github.com/dexX7/java-libbitcoinconsensus) (Java Bindings)
 - [bitcoinconsensus-php](https://github.com/Bit-Wasp/bitcoinconsensus-php) (PHP Bindings)
+- [rust-bitcoinconsensus](https://github.com/rust-bitcoin/rust-bitcoinconsensus) (Rust Bindings)
\ No newline at end of file
diff --git a/src/script/bitcoinconsensus.cpp b/src/script/bitcoinconsensus.cpp
index 4fab481b39894..71005cfb6eeec 100644
--- a/src/script/bitcoinconsensus.cpp
+++ b/src/script/bitcoinconsensus.cpp
@@ -72,14 +72,34 @@ static bool verify_flags(unsigned int flags)
 
 static int verify_script(const unsigned char *scriptPubKey, unsigned int scriptPubKeyLen, CAmount amount,
                                     const unsigned char *txTo        , unsigned int txToLen,
+                                    const UTXO *spentOutputs, unsigned int spentOutputsLen,
                                     unsigned int nIn, unsigned int flags, bitcoinconsensus_error* err)
 {
     if (!verify_flags(flags)) {
         return set_error(err, bitcoinconsensus_ERR_INVALID_FLAGS);
     }
+
+    if (flags & bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT && spentOutputs == nullptr) {
+        return set_error(err, bitcoinconsensus_ERR_SPENT_OUTPUTS_REQUIRED);
+    }
+
     try {
         TxInputStream stream(PROTOCOL_VERSION, txTo, txToLen);
         CTransaction tx(deserialize, stream);
+
+        std::vector<CTxOut> spent_outputs;
+        if (spentOutputs != nullptr) {
+            if (spentOutputsLen != tx.vin.size()) {
+                return set_error(err, bitcoinconsensus_ERR_SPENT_OUTPUTS_MISMATCH);
+            }
+            for (size_t i = 0; i < spentOutputsLen; i++) {
+                CScript spk = CScript(spentOutputs[i].scriptPubKey, spentOutputs[i].scriptPubKey + spentOutputs[i].scriptPubKeySize);
+                const CAmount& value = spentOutputs[i].value;
+                CTxOut tx_out = CTxOut(value, spk);
+                spent_outputs.push_back(tx_out);
+            }
+        }
+
         if (nIn >= tx.vin.size())
             return set_error(err, bitcoinconsensus_ERR_TX_INDEX);
         if (GetSerializeSize(tx, PROTOCOL_VERSION) != txToLen)
@@ -89,18 +109,34 @@ static int verify_script(const unsigned char *scriptPubKey, unsigned int scriptP
         set_error(err, bitcoinconsensus_ERR_OK);
 
         PrecomputedTransactionData txdata(tx);
+
+        if (spentOutputs != nullptr && flags & bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT) {
+            txdata.Init(tx, std::move(spent_outputs));
+        }
+
         return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), &tx.vin[nIn].scriptWitness, flags, TransactionSignatureChecker(&tx, nIn, amount, txdata, MissingDataBehavior::FAIL), nullptr);
     } catch (const std::exception&) {
         return set_error(err, bitcoinconsensus_ERR_TX_DESERIALIZE); // Error deserializing
     }
 }
 
+int bitcoinconsensus_verify_script_with_spent_outputs(const unsigned char *scriptPubKey, unsigned int scriptPubKeyLen, int64_t amount,
+                                    const unsigned char *txTo        , unsigned int txToLen,
+                                    const UTXO *spentOutputs, unsigned int spentOutputsLen,
+                                    unsigned int nIn, unsigned int flags, bitcoinconsensus_error* err)
+{
+    CAmount am(amount);
+    return ::verify_script(scriptPubKey, scriptPubKeyLen, am, txTo, txToLen, spentOutputs, spentOutputsLen, nIn, flags, err);
+}
+
 int bitcoinconsensus_verify_script_with_amount(const unsigned char *scriptPubKey, unsigned int scriptPubKeyLen, int64_t amount,
                                     const unsigned char *txTo        , unsigned int txToLen,
                                     unsigned int nIn, unsigned int flags, bitcoinconsensus_error* err)
 {
     CAmount am(amount);
-    return ::verify_script(scriptPubKey, scriptPubKeyLen, am, txTo, txToLen, nIn, flags, err);
+    UTXO *spentOutputs = nullptr;
+    unsigned int spentOutputsLen = 0;
+    return ::verify_script(scriptPubKey, scriptPubKeyLen, am, txTo, txToLen, spentOutputs, spentOutputsLen, nIn, flags, err);
 }
 
 
@@ -113,7 +149,9 @@ int bitcoinconsensus_verify_script(const unsigned char *scriptPubKey, unsigned i
     }
 
     CAmount am(0);
-    return ::verify_script(scriptPubKey, scriptPubKeyLen, am, txTo, txToLen, nIn, flags, err);
+    UTXO *spentOutputs = nullptr;
+    unsigned int spentOutputsLen = 0;
+    return ::verify_script(scriptPubKey, scriptPubKeyLen, am, txTo, txToLen, spentOutputs, spentOutputsLen, nIn, flags, err);
 }
 
 unsigned int bitcoinconsensus_version()
diff --git a/src/script/bitcoinconsensus.h b/src/script/bitcoinconsensus.h
index f2f2ff8686eee..a202b5ba065c2 100644
--- a/src/script/bitcoinconsensus.h
+++ b/src/script/bitcoinconsensus.h
@@ -31,7 +31,7 @@
 extern "C" {
 #endif
 
-#define BITCOINCONSENSUS_API_VER 1
+#define BITCOINCONSENSUS_API_VER 2
 
 typedef enum bitcoinconsensus_error_t
 {
@@ -41,6 +41,8 @@ typedef enum bitcoinconsensus_error_t
     bitcoinconsensus_ERR_TX_DESERIALIZE,
     bitcoinconsensus_ERR_AMOUNT_REQUIRED,
     bitcoinconsensus_ERR_INVALID_FLAGS,
+    bitcoinconsensus_ERR_SPENT_OUTPUTS_REQUIRED,
+    bitcoinconsensus_ERR_SPENT_OUTPUTS_MISMATCH
 } bitcoinconsensus_error;
 
 /** Script verification flags */
@@ -53,11 +55,19 @@ enum
     bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKLOCKTIMEVERIFY = (1U << 9), // enable CHECKLOCKTIMEVERIFY (BIP65)
     bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKSEQUENCEVERIFY = (1U << 10), // enable CHECKSEQUENCEVERIFY (BIP112)
     bitcoinconsensus_SCRIPT_FLAGS_VERIFY_WITNESS             = (1U << 11), // enable WITNESS (BIP141)
+    bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT             = (1U << 17), // enable TAPROOT (BIPs 341 & 342)
     bitcoinconsensus_SCRIPT_FLAGS_VERIFY_ALL                 = bitcoinconsensus_SCRIPT_FLAGS_VERIFY_P2SH | bitcoinconsensus_SCRIPT_FLAGS_VERIFY_DERSIG |
                                                                bitcoinconsensus_SCRIPT_FLAGS_VERIFY_NULLDUMMY | bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKLOCKTIMEVERIFY |
-                                                               bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKSEQUENCEVERIFY | bitcoinconsensus_SCRIPT_FLAGS_VERIFY_WITNESS
+                                                               bitcoinconsensus_SCRIPT_FLAGS_VERIFY_CHECKSEQUENCEVERIFY | bitcoinconsensus_SCRIPT_FLAGS_VERIFY_WITNESS |
+                                                               bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT
 };
 
+typedef struct {
+    const unsigned char *scriptPubKey;
+    unsigned int scriptPubKeySize;
+    int64_t value;
+} UTXO;
+
 /// Returns 1 if the input nIn of the serialized transaction pointed to by
 /// txTo correctly spends the scriptPubKey pointed to by scriptPubKey under
 /// the additional constraints specified by flags.
@@ -70,6 +80,11 @@ EXPORT_SYMBOL int bitcoinconsensus_verify_script_with_amount(const unsigned char
                                     const unsigned char *txTo        , unsigned int txToLen,
                                     unsigned int nIn, unsigned int flags, bitcoinconsensus_error* err);
 
+EXPORT_SYMBOL int bitcoinconsensus_verify_script_with_spent_outputs(const unsigned char *scriptPubKey, unsigned int scriptPubKeyLen, int64_t amount,
+                                    const unsigned char *txTo        , unsigned int txToLen,
+                                    const UTXO *spentOutputs, unsigned int spentOutputsLen,
+                                    unsigned int nIn, unsigned int flags, bitcoinconsensus_error* err);
+
 EXPORT_SYMBOL unsigned int bitcoinconsensus_version();
 
 #ifdef __cplusplus


Test patch:
diff --git a/src/test/fuzz/script_bitcoin_consensus.cpp b/src/test/fuzz/script_bitcoin_consensus.cpp
index fcd66b234e147..846389863d289 100644
--- a/src/test/fuzz/script_bitcoin_consensus.cpp
+++ b/src/test/fuzz/script_bitcoin_consensus.cpp
@@ -28,4 +28,23 @@ FUZZ_TARGET(script_bitcoin_consensus)
     }
     (void)bitcoinconsensus_verify_script(random_bytes_1.data(), random_bytes_1.size(), random_bytes_2.data(), random_bytes_2.size(), n_in, flags, err_p);
     (void)bitcoinconsensus_verify_script_with_amount(random_bytes_1.data(), random_bytes_1.size(), money, random_bytes_2.data(), random_bytes_2.size(), n_in, flags, err_p);
+
+    std::vector<UTXO> spent_outputs;
+    std::vector<std::vector<unsigned char>> spent_spks;
+    if (n_in <= 24386) {
+        spent_outputs.reserve(n_in);
+        spent_spks.reserve(n_in);
+        for (size_t i = 0; i < n_in; ++i) {
+            spent_spks.push_back(ConsumeRandomLengthByteVector(fuzzed_data_provider));
+            const CAmount value{ConsumeMoney(fuzzed_data_provider)};
+            const auto spk_size{static_cast<unsigned>(spent_spks.back().size())};
+            spent_outputs.push_back({.scriptPubKey = spent_spks.back().data(), .scriptPubKeySize = spk_size, .value = value});
+        }
+    }
+
+    const auto spent_outs_size{static_cast<unsigned>(spent_outputs.size())};
+
+    (void)bitcoinconsensus_verify_script_with_spent_outputs(
+            random_bytes_1.data(), random_bytes_1.size(), money, random_bytes_2.data(), random_bytes_2.size(),
+            spent_outputs.data(), spent_outs_size, n_in, flags, err_p);
 }
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 94656b229ed30..624d0b2c129f6 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -1637,6 +1637,37 @@ BOOST_AUTO_TEST_CASE(bitcoinconsensus_verify_script_invalid_flags)
     BOOST_CHECK_EQUAL(err, bitcoinconsensus_ERR_INVALID_FLAGS);
 }
 
+/* Test bitcoinconsensus_verify_script returns spent outputs required err */
+BOOST_AUTO_TEST_CASE(bitcoinconsensus_verify_script_spent_outputs_required_err)
+{
+    unsigned int libconsensus_flags{bitcoinconsensus_SCRIPT_FLAGS_VERIFY_TAPROOT};
+    const int nIn{0};
+
+    CScript scriptPubKey;
+    CScript scriptSig;
+    CScriptWitness wit;
+
+    scriptPubKey << OP_EQUAL;
+    CTransaction creditTx{BuildCreditingTransaction(scriptPubKey, 1)};
+    CTransaction spendTx{BuildSpendingTransaction(scriptSig, wit, creditTx)};
+
+    CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+    stream << spendTx;
+
+    bitcoinconsensus_error err;
+    int result{bitcoinconsensus_verify_script_with_spent_outputs(scriptPubKey.data(), scriptPubKey.size(), creditTx.vout[0].nValue, UCharCast(stream.data()), stream.size(), nullptr, 0, nIn, libconsensus_flags, &err)};
+    BOOST_CHECK_EQUAL(result, 0);
+    BOOST_CHECK_EQUAL(err, bitcoinconsensus_ERR_SPENT_OUTPUTS_REQUIRED);
+
+    result = bitcoinconsensus_verify_script_with_amount(scriptPubKey.data(), scriptPubKey.size(), creditTx.vout[0].nValue, UCharCast(stream.data()), stream.size(), nIn, libconsensus_flags, &err);
+    BOOST_CHECK_EQUAL(result, 0);
+    BOOST_CHECK_EQUAL(err, bitcoinconsensus_ERR_SPENT_OUTPUTS_REQUIRED);
+
+    result = bitcoinconsensus_verify_script(scriptPubKey.data(), scriptPubKey.size(), UCharCast(stream.data()), stream.size(), nIn, libconsensus_flags, &err);
+    BOOST_CHECK_EQUAL(result, 0);
+    BOOST_CHECK_EQUAL(err, bitcoinconsensus_ERR_SPENT_OUTPUTS_REQUIRED);
+}
+
 #endif // defined(HAVE_CONSENSUS_LIB)
 
 static std::vector<unsigned int> AllConsensusFlags()
@@ -1685,12 +1716,29 @@ static void AssetTest(const UniValue& test)
         PrecomputedTransactionData txdata;
         txdata.Init(tx, std::vector<CTxOut>(prevouts));
         CachingTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, true, txdata);
+
+#if defined(HAVE_CONSENSUS_LIB)
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << tx;
+        std::vector<UTXO> utxos;
+        utxos.resize(prevouts.size());
+        for (size_t i = 0; i < prevouts.size(); i++) {
+            utxos[i].scriptPubKey = prevouts[i].scriptPubKey.data();
+            utxos[i].scriptPubKeySize = prevouts[i].scriptPubKey.size();
+            utxos[i].value = prevouts[i].nValue;
+        }
+#endif
+
         for (const auto flags : ALL_CONSENSUS_FLAGS) {
             // "final": true tests are valid for all flags. Others are only valid with flags that are
             // a subset of test_flags.
             if (fin || ((flags & test_flags) == flags)) {
                 bool ret = VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr);
                 BOOST_CHECK(ret);
+#if defined(HAVE_CONSENSUS_LIB)
+                int lib_ret = bitcoinconsensus_verify_script_with_spent_outputs(prevouts[idx].scriptPubKey.data(), prevouts[idx].scriptPubKey.size(), prevouts[idx].nValue, UCharCast(stream.data()), stream.size(), utxos.data(), utxos.size(), idx, flags, nullptr);
+                BOOST_CHECK(lib_ret == 1);
+#endif
             }
         }
     }
@@ -1702,11 +1750,28 @@ static void AssetTest(const UniValue& test)
         PrecomputedTransactionData txdata;
         txdata.Init(tx, std::vector<CTxOut>(prevouts));
         CachingTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, true, txdata);
+
+#if defined(HAVE_CONSENSUS_LIB)
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << tx;
+        std::vector<UTXO> utxos;
+        utxos.resize(prevouts.size());
+        for (size_t i = 0; i < prevouts.size(); i++) {
+            utxos[i].scriptPubKey = prevouts[i].scriptPubKey.data();
+            utxos[i].scriptPubKeySize = prevouts[i].scriptPubKey.size();
+            utxos[i].value = prevouts[i].nValue;
+        }
+#endif
+
         for (const auto flags : ALL_CONSENSUS_FLAGS) {
             // If a test is supposed to fail with test_flags, it should also fail with any superset thereof.
             if ((flags & test_flags) == test_flags) {
                 bool ret = VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr);
                 BOOST_CHECK(!ret);
+#if defined(HAVE_CONSENSUS_LIB)
+                int lib_ret = bitcoinconsensus_verify_script_with_spent_outputs(prevouts[idx].scriptPubKey.data(), prevouts[idx].scriptPubKey.size(), prevouts[idx].nValue, UCharCast(stream.data()), stream.size(), utxos.data(), utxos.size(), idx, flags, nullptr);
+                BOOST_CHECK(lib_ret == 0);
+#endif
             }
         }
     }