diff options
Diffstat (limited to 'src/script')
-rw-r--r-- | src/script/descriptor.cpp | 4 | ||||
-rw-r--r-- | src/script/interpreter.cpp | 14 | ||||
-rw-r--r-- | src/script/interpreter.h | 5 | ||||
-rw-r--r-- | src/script/sign.cpp | 195 | ||||
-rw-r--r-- | src/script/sign.h | 9 | ||||
-rw-r--r-- | src/script/signingprovider.cpp | 13 | ||||
-rw-r--r-- | src/script/signingprovider.h | 4 | ||||
-rw-r--r-- | src/script/standard.cpp | 57 | ||||
-rw-r--r-- | src/script/standard.h | 46 |
9 files changed, 322 insertions, 25 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index 51cf8a7d62..84a8b06c5c 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -843,7 +843,9 @@ protected: XOnlyPubKey xpk(keys[0]); if (!xpk.IsFullyValid()) return {}; builder.Finalize(xpk); - return Vector(GetScriptForDestination(builder.GetOutput())); + WitnessV1Taproot output = builder.GetOutput(); + out.tr_spenddata[output].Merge(builder.GetSpendData()); + return Vector(GetScriptForDestination(output)); } bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, bool priv, bool normalized) const override { diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 3c3c3ac1a8..2dd173ee20 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -1420,7 +1420,7 @@ uint256 GetSpentScriptsSHA256(const std::vector<CTxOut>& outputs_spent) } // namespace template <class T> -void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent_outputs) +void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent_outputs, bool force) { assert(!m_spent_outputs_ready); @@ -1431,9 +1431,9 @@ void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent } // Determine which precomputation-impacting features this transaction uses. - bool uses_bip143_segwit = false; - bool uses_bip341_taproot = false; - for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) { + bool uses_bip143_segwit = force; + bool uses_bip341_taproot = force; + for (size_t inpos = 0; inpos < txTo.vin.size() && !(uses_bip143_segwit && uses_bip341_taproot); ++inpos) { if (!txTo.vin[inpos].scriptWitness.IsNull()) { if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.size() == 2 + WITNESS_V1_TAPROOT_SIZE && m_spent_outputs[inpos].scriptPubKey[0] == OP_1) { @@ -1478,8 +1478,8 @@ PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo) } // explicit instantiation -template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs); -template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs); +template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs, bool force); +template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs, bool force); template PrecomputedTransactionData::PrecomputedTransactionData(const CTransaction& txTo); template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo); @@ -1711,7 +1711,7 @@ bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const uns if (hashtype == SIGHASH_DEFAULT) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE); } uint256 sighash; - assert(this->txdata); + if (!this->txdata) return HandleMissingData(m_mdb); if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, *this->txdata, m_mdb)) { return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE); } diff --git a/src/script/interpreter.h b/src/script/interpreter.h index fa4ee83e04..ced5c28bc1 100644 --- a/src/script/interpreter.h +++ b/src/script/interpreter.h @@ -168,7 +168,7 @@ struct PrecomputedTransactionData PrecomputedTransactionData() = default; template <class T> - void Init(const T& tx, std::vector<CTxOut>&& spent_outputs); + void Init(const T& tx, std::vector<CTxOut>&& spent_outputs, bool force = false); template <class T> explicit PrecomputedTransactionData(const T& tx); @@ -260,6 +260,9 @@ enum class MissingDataBehavior FAIL, //!< Just act as if the signature was invalid }; +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); + template <class T> class GenericTransactionSignatureChecker : public BaseSignatureChecker { diff --git a/src/script/sign.cpp b/src/script/sign.cpp index da0092f9e3..65276f641f 100644 --- a/src/script/sign.cpp +++ b/src/script/sign.cpp @@ -11,13 +11,28 @@ #include <script/signingprovider.h> #include <script/standard.h> #include <uint256.h> +#include <util/vector.h> typedef std::vector<unsigned char> valtype; -MutableTransactionSignatureCreator::MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, int nHashTypeIn) : txTo(txToIn), nIn(nInIn), nHashType(nHashTypeIn), amount(amountIn), checker(txTo, nIn, amountIn, MissingDataBehavior::FAIL) {} +MutableTransactionSignatureCreator::MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, int nHashTypeIn) + : txTo(txToIn), nIn(nInIn), nHashType(nHashTypeIn), amount(amountIn), checker(txTo, nIn, amountIn, MissingDataBehavior::FAIL), + m_txdata(nullptr) +{ +} + +MutableTransactionSignatureCreator::MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData* txdata, int nHashTypeIn) + : txTo(txToIn), nIn(nInIn), nHashType(nHashTypeIn), amount(amountIn), + checker(txdata ? MutableTransactionSignatureChecker(txTo, nIn, amount, *txdata, MissingDataBehavior::FAIL) : + MutableTransactionSignatureChecker(txTo, nIn, amount, MissingDataBehavior::FAIL)), + m_txdata(txdata) +{ +} bool MutableTransactionSignatureCreator::CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& address, const CScript& scriptCode, SigVersion sigversion) const { + assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0); + CKey key; if (!provider.GetKey(address, key)) return false; @@ -26,13 +41,61 @@ bool MutableTransactionSignatureCreator::CreateSig(const SigningProvider& provid if (sigversion == SigVersion::WITNESS_V0 && !key.IsCompressed()) return false; - // Signing for witness scripts needs the amount. - if (sigversion == SigVersion::WITNESS_V0 && amount < 0) return false; + // Signing without known amount does not work in witness scripts. + if (sigversion == SigVersion::WITNESS_V0 && !MoneyRange(amount)) return false; + + // BASE/WITNESS_V0 signatures don't support explicit SIGHASH_DEFAULT, use SIGHASH_ALL instead. + const int hashtype = nHashType == SIGHASH_DEFAULT ? SIGHASH_ALL : nHashType; - uint256 hash = SignatureHash(scriptCode, *txTo, nIn, nHashType, amount, sigversion); + uint256 hash = SignatureHash(scriptCode, *txTo, nIn, hashtype, amount, sigversion, m_txdata); if (!key.Sign(hash, vchSig)) return false; - vchSig.push_back((unsigned char)nHashType); + vchSig.push_back((unsigned char)hashtype); + return true; +} + +bool MutableTransactionSignatureCreator::CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const +{ + assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT); + + CKey key; + { + // For now, use the old full pubkey-based key derivation logic. As it indexed by + // Hash160(full pubkey), we need to try both a version prefixed with 0x02, and one + // with 0x03. + unsigned char b[33] = {0x02}; + std::copy(pubkey.begin(), pubkey.end(), b + 1); + CPubKey fullpubkey; + fullpubkey.Set(b, b + 33); + CKeyID keyid = fullpubkey.GetID(); + if (!provider.GetKey(keyid, key)) { + b[0] = 0x03; + fullpubkey.Set(b, b + 33); + CKeyID keyid = fullpubkey.GetID(); + if (!provider.GetKey(keyid, key)) return false; + } + } + + // BIP341/BIP342 signing needs lots of precomputed transaction data. While some + // (non-SIGHASH_DEFAULT) sighash modes exist that can work with just some subset + // of data present, for now, only support signing when everything is provided. + if (!m_txdata || !m_txdata->m_bip341_taproot_ready || !m_txdata->m_spent_outputs_ready) return false; + + ScriptExecutionData execdata; + execdata.m_annex_init = true; + execdata.m_annex_present = false; // Only support annex-less signing for now. + if (sigversion == SigVersion::TAPSCRIPT) { + execdata.m_codeseparator_pos_init = true; + execdata.m_codeseparator_pos = 0xFFFFFFFF; // Only support non-OP_CODESEPARATOR BIP342 signing for now. + if (!leaf_hash) return false; // BIP342 signing needs leaf hash. + execdata.m_tapleaf_hash_init = true; + execdata.m_tapleaf_hash = *leaf_hash; + } + uint256 hash; + if (!SignatureHashSchnorr(hash, execdata, *txTo, nIn, nHashType, sigversion, *m_txdata, MissingDataBehavior::FAIL)) return false; + sig.resize(64); + if (!key.SignSchnorr(hash, sig, merkle_root, nullptr)) return false; + if (nHashType) sig.push_back(nHashType); return true; } @@ -92,6 +155,86 @@ static bool CreateSig(const BaseSignatureCreator& creator, SignatureData& sigdat return false; } +static bool CreateTaprootScriptSig(const BaseSignatureCreator& creator, SignatureData& sigdata, const SigningProvider& provider, std::vector<unsigned char>& sig_out, const XOnlyPubKey& pubkey, const uint256& leaf_hash, SigVersion sigversion) +{ + auto lookup_key = std::make_pair(pubkey, leaf_hash); + auto it = sigdata.taproot_script_sigs.find(lookup_key); + if (it != sigdata.taproot_script_sigs.end()) { + sig_out = it->second; + } + if (creator.CreateSchnorrSig(provider, sig_out, pubkey, &leaf_hash, nullptr, sigversion)) { + sigdata.taproot_script_sigs[lookup_key] = sig_out; + return true; + } + return false; +} + +static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, const CScript& script, std::vector<valtype>& result) +{ + // Only BIP342 tapscript signing is supported for now. + if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false; + SigVersion sigversion = SigVersion::TAPSCRIPT; + + uint256 leaf_hash = (CHashWriter(HASHER_TAPLEAF) << uint8_t(leaf_version) << script).GetSHA256(); + + // <xonly pubkey> OP_CHECKSIG + if (script.size() == 34 && script[33] == OP_CHECKSIG && script[0] == 0x20) { + XOnlyPubKey pubkey(MakeSpan(script).subspan(1, 32)); + std::vector<unsigned char> sig; + if (CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion)) { + result = Vector(std::move(sig)); + return true; + } + } + + return false; +} + +static bool SignTaproot(const SigningProvider& provider, const BaseSignatureCreator& creator, const WitnessV1Taproot& output, SignatureData& sigdata, std::vector<valtype>& result) +{ + TaprootSpendData spenddata; + + // Gather information about this output. + if (provider.GetTaprootSpendData(output, spenddata)) { + sigdata.tr_spenddata.Merge(spenddata); + } + + // Try key path spending. + { + std::vector<unsigned char> sig; + if (sigdata.taproot_key_path_sig.size() == 0) { + if (creator.CreateSchnorrSig(provider, sig, spenddata.internal_key, nullptr, &spenddata.merkle_root, SigVersion::TAPROOT)) { + sigdata.taproot_key_path_sig = sig; + } + } + if (sigdata.taproot_key_path_sig.size()) { + result = Vector(sigdata.taproot_key_path_sig); + return true; + } + } + + // Try script path spending. + std::vector<std::vector<unsigned char>> smallest_result_stack; + for (const auto& [key, control_blocks] : sigdata.tr_spenddata.scripts) { + const auto& [script, leaf_ver] = key; + std::vector<std::vector<unsigned char>> result_stack; + if (SignTaprootScript(provider, creator, sigdata, leaf_ver, script, result_stack)) { + result_stack.emplace_back(std::begin(script), std::end(script)); // Push the script + result_stack.push_back(*control_blocks.begin()); // Push the smallest control block + if (smallest_result_stack.size() == 0 || + GetSerializeSize(result_stack, PROTOCOL_VERSION) < GetSerializeSize(smallest_result_stack, PROTOCOL_VERSION)) { + smallest_result_stack = std::move(result_stack); + } + } + } + if (smallest_result_stack.size() != 0) { + result = std::move(smallest_result_stack); + return true; + } + + return false; +} + /** * Sign scriptPubKey using signature made with creator. * Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed), @@ -113,7 +256,6 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator case TxoutType::NONSTANDARD: case TxoutType::NULL_DATA: case TxoutType::WITNESS_UNKNOWN: - case TxoutType::WITNESS_V1_TAPROOT: return false; case TxoutType::PUBKEY: if (!CreateSig(creator, sigdata, provider, sig, CPubKey(vSolutions[0]), scriptPubKey, sigversion)) return false; @@ -175,6 +317,9 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator // Could not find witnessScript, add to missing sigdata.missing_witness_script = uint256(vSolutions[0]); return false; + + case TxoutType::WITNESS_V1_TAPROOT: + return SignTaproot(provider, creator, WitnessV1Taproot(XOnlyPubKey{vSolutions[0]}), sigdata, ret); } // no default case, so the compiler can warn about missing cases assert(false); } @@ -205,7 +350,6 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato bool solved = SignStep(provider, creator, fromPubKey, result, whichType, SigVersion::BASE, sigdata); bool P2SH = false; CScript subscript; - sigdata.scriptWitness.stack.clear(); if (solved && whichType == TxoutType::SCRIPTHASH) { @@ -238,10 +382,17 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato sigdata.scriptWitness.stack = result; sigdata.witness = true; result.clear(); + } else if (whichType == TxoutType::WITNESS_V1_TAPROOT && !P2SH) { + sigdata.witness = true; + if (solved) { + sigdata.scriptWitness.stack = std::move(result); + } + result.clear(); } else if (solved && whichType == TxoutType::WITNESS_UNKNOWN) { sigdata.witness = true; } + if (!sigdata.witness) sigdata.scriptWitness.stack.clear(); if (P2SH) { result.push_back(std::vector<unsigned char>(subscript.begin(), subscript.end())); } @@ -402,6 +553,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; } }; const DummySignatureChecker DUMMY_CHECKER; @@ -427,6 +579,11 @@ public: vchSig[6 + m_r_len + m_s_len] = SIGHASH_ALL; return true; } + bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* tweak, SigVersion sigversion) const override + { + sig.assign(64, '\000'); + return true; + } }; } @@ -476,6 +633,26 @@ bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, // Use CTransaction for the constant parts of the // transaction to avoid rehashing. const CTransaction txConst(mtx); + + PrecomputedTransactionData txdata; + std::vector<CTxOut> spent_outputs; + spent_outputs.resize(mtx.vin.size()); + bool have_all_spent_outputs = true; + for (unsigned int i = 0; i < mtx.vin.size(); i++) { + CTxIn& txin = mtx.vin[i]; + auto coin = coins.find(txin.prevout); + if (coin == coins.end() || coin->second.IsSpent()) { + have_all_spent_outputs = false; + } else { + spent_outputs[i] = CTxOut(coin->second.out.nValue, coin->second.out.scriptPubKey); + } + } + if (have_all_spent_outputs) { + txdata.Init(txConst, std::move(spent_outputs), true); + } else { + txdata.Init(txConst, {}, true); + } + // Sign what we can: for (unsigned int i = 0; i < mtx.vin.size(); i++) { CTxIn& txin = mtx.vin[i]; @@ -490,7 +667,7 @@ bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, SignatureData sigdata = DataFromTransaction(mtx, i, coin->second.out); // Only sign SIGHASH_SINGLE if there's a corresponding output: if (!fHashSingle || (i < mtx.vout.size())) { - ProduceSignature(*keystore, MutableTransactionSignatureCreator(&mtx, i, amount, nHashType), prevPubKey, sigdata); + ProduceSignature(*keystore, MutableTransactionSignatureCreator(&mtx, i, amount, &txdata, nHashType), prevPubKey, sigdata); } UpdateInput(txin, sigdata); @@ -502,7 +679,7 @@ bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, } ScriptError serror = SCRIPT_ERR_OK; - if (!VerifyScript(txin.scriptSig, prevPubKey, &txin.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, TransactionSignatureChecker(&txConst, i, amount, MissingDataBehavior::FAIL), &serror)) { + if (!VerifyScript(txin.scriptSig, prevPubKey, &txin.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, TransactionSignatureChecker(&txConst, i, amount, txdata, MissingDataBehavior::FAIL), &serror)) { if (serror == SCRIPT_ERR_INVALID_STACK_OPERATION) { // Unable to sign input and verification failed (possible attempt to partially sign). input_errors[i] = "Unable to sign input, invalid stack size (possibly missing key)"; diff --git a/src/script/sign.h b/src/script/sign.h index a1cfe1574d..b4e7318892 100644 --- a/src/script/sign.h +++ b/src/script/sign.h @@ -11,13 +11,13 @@ #include <pubkey.h> #include <script/interpreter.h> #include <script/keyorigin.h> +#include <script/standard.h> #include <span.h> #include <streams.h> class CKey; class CKeyID; class CScript; -class CScriptID; class CTransaction; class SigningProvider; @@ -31,6 +31,7 @@ public: /** Create a singular (non-script) signature. */ virtual bool CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& keyid, const CScript& scriptCode, SigVersion sigversion) const =0; + virtual bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const =0; }; /** A signature creator for transactions. */ @@ -40,11 +41,14 @@ class MutableTransactionSignatureCreator : public BaseSignatureCreator { int nHashType; CAmount amount; const MutableTransactionSignatureChecker checker; + const PrecomputedTransactionData* m_txdata; public: MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, int nHashTypeIn = SIGHASH_ALL); + MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData* txdata, int nHashTypeIn = SIGHASH_ALL); const BaseSignatureChecker& Checker() const override { return checker; } bool CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& keyid, const CScript& scriptCode, SigVersion sigversion) const override; + bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const override; }; /** A signature creator that just produces 71-byte empty signatures. */ @@ -64,8 +68,11 @@ struct SignatureData { CScript redeem_script; ///< The redeemScript (if any) for the input CScript witness_script; ///< The witnessScript (if any) for the input. witnessScripts are used in P2WSH outputs. CScriptWitness scriptWitness; ///< The scriptWitness of an input. Contains complete signatures or the traditional partial signatures format. scriptWitness is part of a transaction input per BIP 144. + TaprootSpendData tr_spenddata; ///< Taproot spending data. std::map<CKeyID, SigPair> signatures; ///< BIP 174 style partial signatures for the input. May contain all signatures necessary for producing a final scriptSig or scriptWitness. std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> misc_pubkeys; + std::vector<unsigned char> taproot_key_path_sig; /// Schnorr signature for key path spending + std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> taproot_script_sigs; ///< (Partial) schnorr signatures, indexed by XOnlyPubKey and leaf_hash. std::vector<CKeyID> missing_pubkeys; ///< KeyIDs of pubkeys which could not be found std::vector<CKeyID> missing_sigs; ///< KeyIDs of pubkeys for signatures which could not be found uint160 missing_redeem_script; ///< ScriptID of the missing redeemScript (if any) diff --git a/src/script/signingprovider.cpp b/src/script/signingprovider.cpp index 9781ec32af..b80fbe22ce 100644 --- a/src/script/signingprovider.cpp +++ b/src/script/signingprovider.cpp @@ -44,6 +44,11 @@ bool HidingSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& inf return m_provider->GetKeyOrigin(keyid, info); } +bool HidingSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const +{ + return m_provider->GetTaprootSpendData(output_key, spenddata); +} + bool FlatSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const { return LookupHelper(scripts, scriptid, script); } bool FlatSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const { return LookupHelper(pubkeys, keyid, pubkey); } bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const @@ -54,6 +59,10 @@ bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) return ret; } bool FlatSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const { return LookupHelper(keys, keyid, key); } +bool FlatSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const +{ + return LookupHelper(tr_spenddata, output_key, spenddata); +} FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b) { @@ -66,6 +75,10 @@ FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvide ret.keys.insert(b.keys.begin(), b.keys.end()); ret.origins = a.origins; ret.origins.insert(b.origins.begin(), b.origins.end()); + ret.tr_spenddata = a.tr_spenddata; + for (const auto& [output_key, spenddata] : b.tr_spenddata) { + ret.tr_spenddata[output_key].Merge(spenddata); + } return ret; } diff --git a/src/script/signingprovider.h b/src/script/signingprovider.h index 76f31d2f6f..939ae10622 100644 --- a/src/script/signingprovider.h +++ b/src/script/signingprovider.h @@ -25,6 +25,7 @@ public: virtual bool GetKey(const CKeyID &address, CKey& key) const { return false; } virtual bool HaveKey(const CKeyID &address) const { return false; } virtual bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const { return false; } + virtual bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const { return false; } }; extern const SigningProvider& DUMMY_SIGNING_PROVIDER; @@ -42,6 +43,7 @@ public: bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override; bool GetKey(const CKeyID& keyid, CKey& key) const override; bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override; + bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override; }; struct FlatSigningProvider final : public SigningProvider @@ -50,11 +52,13 @@ struct FlatSigningProvider final : public SigningProvider std::map<CKeyID, CPubKey> pubkeys; std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins; std::map<CKeyID, CKey> keys; + std::map<XOnlyPubKey, TaprootSpendData> tr_spenddata; /** Map from output key to spend data. */ bool GetCScript(const CScriptID& scriptid, CScript& script) const override; bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override; bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override; bool GetKey(const CKeyID& keyid, CKey& key) const override; + bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override; }; FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b); diff --git a/src/script/standard.cpp b/src/script/standard.cpp index a4b11cc0a9..748f00dda5 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -377,6 +377,16 @@ bool IsValidDestination(const CTxDestination& dest) { /*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b) { NodeInfo ret; + /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */ + for (auto& leaf : a.leaves) { + leaf.merkle_branch.push_back(b.hash); + ret.leaves.emplace_back(std::move(leaf)); + } + /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */ + for (auto& leaf : b.leaves) { + leaf.merkle_branch.push_back(a.hash); + ret.leaves.emplace_back(std::move(leaf)); + } /* Lexicographically sort a and b's hash, and compute parent hash. */ if (a.hash < b.hash) { ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256(); @@ -386,6 +396,21 @@ bool IsValidDestination(const CTxDestination& dest) { return ret; } +void TaprootSpendData::Merge(TaprootSpendData other) +{ + // TODO: figure out how to better deal with conflicting information + // being merged. + if (internal_key.IsNull() && !other.internal_key.IsNull()) { + internal_key = other.internal_key; + } + if (merkle_root.IsNull() && !other.merkle_root.IsNull()) { + merkle_root = other.merkle_root; + } + for (auto& [key, control_blocks] : other.scripts) { + scripts[key].merge(std::move(control_blocks)); + } +} + void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth) { assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT); @@ -435,13 +460,14 @@ void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth) return branch.size() == 0 || (branch.size() == 1 && branch[0]); } -TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version) +TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track) { assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0); if (!IsValid()) return *this; - /* Construct NodeInfo object with leaf hash. */ + /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */ NodeInfo node; node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256(); + if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}}); /* Insert into the branch. */ Insert(std::move(node), depth); return *this; @@ -464,8 +490,33 @@ TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key) m_internal_key = internal_key; auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash); assert(ret.has_value()); - std::tie(m_output_key, std::ignore) = *ret; + std::tie(m_output_key, m_parity) = *ret; return *this; } WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; } + +TaprootSpendData TaprootBuilder::GetSpendData() const +{ + TaprootSpendData spd; + spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash; + spd.internal_key = m_internal_key; + if (m_branch.size()) { + // If any script paths exist, they have been combined into the root m_branch[0] + // by now. Compute the control block for each of its tracked leaves, and put them in + // spd.scripts. + for (const auto& leaf : m_branch[0]->leaves) { + std::vector<unsigned char> control_block; + control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size()); + control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0); + std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1); + if (leaf.merkle_branch.size()) { + std::copy(leaf.merkle_branch[0].begin(), + leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(), + control_block.begin() + TAPROOT_CONTROL_BASE_SIZE); + } + spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block)); + } + } + return spd; +} diff --git a/src/script/standard.h b/src/script/standard.h index d7ea5cef27..285dd4c116 100644 --- a/src/script/standard.h +++ b/src/script/standard.h @@ -11,6 +11,7 @@ #include <uint256.h> #include <util/hash_type.h> +#include <map> #include <string> #include <variant> @@ -209,15 +210,50 @@ CScript GetScriptForRawPubKey(const CPubKey& pubkey); /** Generate a multisig script. */ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys); +struct ShortestVectorFirstComparator +{ + bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const + { + if (a.size() < b.size()) return true; + if (a.size() > b.size()) return false; + return a < b; + } +}; + +struct TaprootSpendData +{ + /** The BIP341 internal key. */ + XOnlyPubKey internal_key; + /** The Merkle root of the script tree (0 if no scripts). */ + uint256 merkle_root; + /** Map from (script, leaf_version) to (sets of) control blocks. + * The control blocks are sorted by size, so that the signing logic can + * easily prefer the cheapest one. */ + std::map<std::pair<CScript, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts; + /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */ + void Merge(TaprootSpendData other); +}; + /** Utility class to construct Taproot outputs from internal key and script tree. */ class TaprootBuilder { private: + /** Information about a tracked leaf in the Merkle tree. */ + struct LeafInfo + { + CScript script; //!< The script. + int leaf_version; //!< The leaf version for that script. + std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf. + }; + /** Information associated with a node in the Merkle tree. */ struct NodeInfo { /** Merkle hash of this node. */ uint256 hash; + /** Tracked leaves underneath this node (either from the node itself, or its children). + * The merkle_branch field for each is the partners to get to *this* node. */ + std::vector<LeafInfo> leaves; }; /** Whether the builder is in a valid state so far. */ bool m_valid = true; @@ -260,7 +296,8 @@ private: std::vector<std::optional<NodeInfo>> m_branch; XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing. - XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. */ + XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. + bool m_parity; //!< The tweak parity, computed when finalizing. /** Combine information about a parent Merkle tree node from its child nodes. */ static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b); @@ -269,8 +306,9 @@ private: public: /** Add a new script at a certain depth in the tree. Add() operations must be called - * in depth-first traversal order of binary tree. */ - TaprootBuilder& Add(int depth, const CScript& script, int leaf_version); + * in depth-first traversal order of binary tree. If track is true, it will be included in + * the GetSpendData() output. */ + TaprootBuilder& Add(int depth, const CScript& script, int leaf_version, bool track = true); /** Like Add(), but for a Merkle node with a given hash to the tree. */ TaprootBuilder& AddOmitted(int depth, const uint256& hash); /** Finalize the construction. Can only be called when IsComplete() is true. @@ -285,6 +323,8 @@ public: WitnessV1Taproot GetOutput(); /** Check if a list of depths is legal (will lead to IsComplete()). */ static bool ValidDepths(const std::vector<int>& depths); + /** Compute spending data (after Finalize()). */ + TaprootSpendData GetSpendData() const; }; #endif // BITCOIN_SCRIPT_STANDARD_H |