LCOV - code coverage report
Current view: top level - src/script - signingprovider.h (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 23 38 60.5 %
Date: 2023-10-05 15:40:34 Functions: 35 55 63.6 %
Branches: 19 49 38.8 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2                 :            : // Copyright (c) 2009-2022 The Bitcoin Core developers
       3                 :            : // Distributed under the MIT software license, see the accompanying
       4                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5                 :            : 
       6                 :            : #ifndef BITCOIN_SCRIPT_SIGNINGPROVIDER_H
       7                 :            : #define BITCOIN_SCRIPT_SIGNINGPROVIDER_H
       8                 :            : 
       9                 :            : #include <addresstype.h>
      10                 :            : #include <attributes.h>
      11                 :            : #include <key.h>
      12                 :            : #include <pubkey.h>
      13                 :            : #include <script/keyorigin.h>
      14                 :            : #include <script/script.h>
      15                 :            : #include <sync.h>
      16                 :            : 
      17                 :            : struct ShortestVectorFirstComparator
      18                 :            : {
      19                 :      16739 :     bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const
      20                 :            :     {
      21         [ +  + ]:      16739 :         if (a.size() < b.size()) return true;
      22         [ +  + ]:      14106 :         if (a.size() > b.size()) return false;
      23                 :      12333 :         return a < b;
      24                 :      16739 :     }
      25                 :            : };
      26                 :            : 
      27                 :            : struct TaprootSpendData
      28                 :            : {
      29                 :            :     /** The BIP341 internal key. */
      30                 :            :     XOnlyPubKey internal_key;
      31                 :            :     /** The Merkle root of the script tree (0 if no scripts). */
      32                 :            :     uint256 merkle_root;
      33                 :            :     /** Map from (script, leaf_version) to (sets of) control blocks.
      34                 :            :      *  More than one control block for a given script is only possible if it
      35                 :            :      *  appears in multiple branches of the tree. We keep them all so that
      36                 :            :      *  inference can reconstruct the full tree. Within each set, the control
      37                 :            :      *  blocks are sorted by size, so that the signing logic can easily
      38                 :            :      *  prefer the cheapest one. */
      39                 :            :     std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts;
      40                 :            :     /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */
      41                 :            :     void Merge(TaprootSpendData other);
      42                 :            : };
      43                 :            : 
      44                 :            : /** Utility class to construct Taproot outputs from internal key and script tree. */
      45   [ +  -  +  - ]:       5110 : class TaprootBuilder
      46                 :            : {
      47                 :            : private:
      48                 :            :     /** Information about a tracked leaf in the Merkle tree. */
      49                 :        813 :     struct LeafInfo
      50                 :            :     {
      51                 :            :         std::vector<unsigned char> script;   //!< The script.
      52                 :            :         int leaf_version;                    //!< The leaf version for that script.
      53                 :            :         std::vector<uint256> merkle_branch;  //!< The hashing partners above this leaf.
      54                 :            :     };
      55                 :            : 
      56                 :            :     /** Information associated with a node in the Merkle tree. */
      57                 :            :     struct NodeInfo
      58                 :            :     {
      59                 :            :         /** Merkle hash of this node. */
      60                 :            :         uint256 hash;
      61                 :            :         /** Tracked leaves underneath this node (either from the node itself, or its children).
      62                 :            :          *  The merkle_branch field of each is the partners to get to *this* node. */
      63                 :            :         std::vector<LeafInfo> leaves;
      64                 :            :     };
      65                 :            :     /** Whether the builder is in a valid state so far. */
      66                 :       5110 :     bool m_valid = true;
      67                 :            : 
      68                 :            :     /** The current state of the builder.
      69                 :            :      *
      70                 :            :      * For each level in the tree, one NodeInfo object may be present. m_branch[0]
      71                 :            :      * is information about the root; further values are for deeper subtrees being
      72                 :            :      * explored.
      73                 :            :      *
      74                 :            :      * For every right branch taken to reach the position we're currently
      75                 :            :      * working in, there will be a (non-nullopt) entry in m_branch corresponding
      76                 :            :      * to the left branch at that level.
      77                 :            :      *
      78                 :            :      * For example, imagine this tree:     - N0 -
      79                 :            :      *                                    /      \
      80                 :            :      *                                   N1      N2
      81                 :            :      *                                  /  \    /  \
      82                 :            :      *                                 A    B  C   N3
      83                 :            :      *                                            /  \
      84                 :            :      *                                           D    E
      85                 :            :      *
      86                 :            :      * Initially, m_branch is empty. After processing leaf A, it would become
      87                 :            :      * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already
      88                 :            :      * exists, and it would thus be combined with it to produce a level 1 one,
      89                 :            :      * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C}
      90                 :            :      * and {nullopt, N1, C, D} respectively. When E is processed, it is combined
      91                 :            :      * with D, and then C, and then N1, to produce the root, resulting in {N0}.
      92                 :            :      *
      93                 :            :      * This structure allows processing with just O(log n) overhead if the leaves
      94                 :            :      * are computed on the fly.
      95                 :            :      *
      96                 :            :      * As an invariant, there can never be nullopt entries at the end. There can
      97                 :            :      * also not be more than 128 entries (as that would mean more than 128 levels
      98                 :            :      * in the tree). The depth of newly added entries will always be at least
      99                 :            :      * equal to the current size of m_branch (otherwise it does not correspond
     100                 :            :      * to a depth-first traversal of a tree). m_branch is only empty if no entries
     101                 :            :      * have ever be processed. m_branch having length 1 corresponds to being done.
     102                 :            :      */
     103                 :            :     std::vector<std::optional<NodeInfo>> m_branch;
     104                 :            : 
     105                 :            :     XOnlyPubKey m_internal_key;  //!< The internal key, set when finalizing.
     106                 :            :     XOnlyPubKey m_output_key;    //!< The output key, computed when finalizing.
     107                 :            :     bool m_parity;               //!< The tweak parity, computed when finalizing.
     108                 :            : 
     109                 :            :     /** Combine information about a parent Merkle tree node from its child nodes. */
     110                 :            :     static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b);
     111                 :            :     /** Insert information about a node at a certain depth, and propagate information up. */
     112                 :            :     void Insert(NodeInfo&& node, int depth);
     113                 :            : 
     114                 :            : public:
     115                 :            :     /** Add a new script at a certain depth in the tree. Add() operations must be called
     116                 :            :      *  in depth-first traversal order of binary tree. If track is true, it will be included in
     117                 :            :      *  the GetSpendData() output. */
     118                 :            :     TaprootBuilder& Add(int depth, Span<const unsigned char> script, int leaf_version, bool track = true);
     119                 :            :     /** Like Add(), but for a Merkle node with a given hash to the tree. */
     120                 :            :     TaprootBuilder& AddOmitted(int depth, const uint256& hash);
     121                 :            :     /** Finalize the construction. Can only be called when IsComplete() is true.
     122                 :            :         internal_key.IsFullyValid() must be true. */
     123                 :            :     TaprootBuilder& Finalize(const XOnlyPubKey& internal_key);
     124                 :            : 
     125                 :            :     /** Return true if so far all input was valid. */
     126                 :      78047 :     bool IsValid() const { return m_valid; }
     127                 :            :     /** Return whether there were either no leaves, or the leaves form a Huffman tree. */
     128   [ +  +  +  +  :       4326 :     bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); }
                   +  + ]
     129                 :            :     /** Compute scriptPubKey (after Finalize()). */
     130                 :            :     WitnessV1Taproot GetOutput();
     131                 :            :     /** Check if a list of depths is legal (will lead to IsComplete()). */
     132                 :            :     static bool ValidDepths(const std::vector<int>& depths);
     133                 :            :     /** Compute spending data (after Finalize()). */
     134                 :            :     TaprootSpendData GetSpendData() const;
     135                 :            :     /** Returns a vector of tuples representing the depth, leaf version, and script */
     136                 :            :     std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> GetTreeTuples() const;
     137                 :            :     /** Returns true if there are any tapscripts */
     138                 :          0 :     bool HasScripts() const { return !m_branch.empty(); }
     139                 :            : };
     140                 :            : 
     141                 :            : /** Given a TaprootSpendData and the output key, reconstruct its script tree.
     142                 :            :  *
     143                 :            :  * If the output doesn't match the spenddata, or if the data in spenddata is incomplete,
     144                 :            :  * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is
     145                 :            :  * returned, corresponding to a depth-first traversal of the script tree.
     146                 :            :  */
     147                 :            : std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output);
     148                 :            : 
     149                 :            : /** An interface to be implemented by keystores that support signing. */
     150                 :            : class SigningProvider
     151                 :            : {
     152                 :            : public:
     153                 :      30326 :     virtual ~SigningProvider() {}
     154                 :      76460 :     virtual bool GetCScript(const CScriptID &scriptid, CScript& script) const { return false; }
     155                 :          0 :     virtual bool HaveCScript(const CScriptID &scriptid) const { return false; }
     156                 :      39625 :     virtual bool GetPubKey(const CKeyID &address, CPubKey& pubkey) const { return false; }
     157                 :       3327 :     virtual bool GetKey(const CKeyID &address, CKey& key) const { return false; }
     158                 :          0 :     virtual bool HaveKey(const CKeyID &address) const { return false; }
     159                 :      42344 :     virtual bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const { return false; }
     160                 :       4361 :     virtual bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const { return false; }
     161                 :          0 :     virtual bool GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const { return false; }
     162                 :            : 
     163                 :          0 :     bool GetKeyByXOnly(const XOnlyPubKey& pubkey, CKey& key) const
     164                 :            :     {
     165   [ #  #  #  #  :          0 :         for (const auto& id : pubkey.GetKeyIDs()) {
                      # ]
     166   [ #  #  #  # ]:          0 :             if (GetKey(id, key)) return true;
     167                 :            :         }
     168                 :          0 :         return false;
     169                 :          0 :     }
     170                 :            : 
     171                 :          0 :     bool GetPubKeyByXOnly(const XOnlyPubKey& pubkey, CPubKey& out) const
     172                 :            :     {
     173   [ #  #  #  #  :          0 :         for (const auto& id : pubkey.GetKeyIDs()) {
                      # ]
     174   [ #  #  #  # ]:          0 :             if (GetPubKey(id, out)) return true;
     175                 :            :         }
     176                 :          0 :         return false;
     177                 :          0 :     }
     178                 :            : 
     179                 :       4474 :     bool GetKeyOriginByXOnly(const XOnlyPubKey& pubkey, KeyOriginInfo& info) const
     180                 :            :     {
     181   [ +  +  -  +  :      12511 :         for (const auto& id : pubkey.GetKeyIDs()) {
                      + ]
     182   [ +  -  +  + ]:       8037 :             if (GetKeyOrigin(id, info)) return true;
     183                 :            :         }
     184                 :       3531 :         return false;
     185                 :       4474 :     }
     186                 :            : };
     187                 :            : 
     188                 :            : extern const SigningProvider& DUMMY_SIGNING_PROVIDER;
     189                 :            : 
     190                 :            : class HidingSigningProvider : public SigningProvider
     191                 :            : {
     192                 :            : private:
     193                 :            :     const bool m_hide_secret;
     194                 :            :     const bool m_hide_origin;
     195                 :            :     const SigningProvider* m_provider;
     196                 :            : 
     197                 :            : public:
     198                 :         41 :     HidingSigningProvider(const SigningProvider* provider, bool hide_secret, bool hide_origin) : m_hide_secret(hide_secret), m_hide_origin(hide_origin), m_provider(provider) {}
     199                 :            :     bool GetCScript(const CScriptID& scriptid, CScript& script) const override;
     200                 :            :     bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override;
     201                 :            :     bool GetKey(const CKeyID& keyid, CKey& key) const override;
     202                 :            :     bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override;
     203                 :            :     bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override;
     204                 :            :     bool GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const override;
     205                 :            : };
     206                 :            : 
     207   [ #  #  #  #  :          0 : struct FlatSigningProvider final : public SigningProvider
             #  #  #  # ]
     208                 :            : {
     209                 :            :     std::map<CScriptID, CScript> scripts;
     210                 :            :     std::map<CKeyID, CPubKey> pubkeys;
     211                 :            :     std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins;
     212                 :            :     std::map<CKeyID, CKey> keys;
     213                 :            :     std::map<XOnlyPubKey, TaprootBuilder> tr_trees; /** Map from output key to Taproot tree (which can then make the TaprootSpendData */
     214                 :            : 
     215                 :            :     bool GetCScript(const CScriptID& scriptid, CScript& script) const override;
     216                 :            :     bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override;
     217                 :            :     bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override;
     218                 :            :     bool GetKey(const CKeyID& keyid, CKey& key) const override;
     219                 :            :     bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override;
     220                 :            :     bool GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const override;
     221                 :            : 
     222                 :            :     FlatSigningProvider& Merge(FlatSigningProvider&& b) LIFETIMEBOUND;
     223                 :            : };
     224                 :            : 
     225                 :            : /** Fillable signing provider that keeps keys in an address->secret map */
     226                 :            : class FillableSigningProvider : public SigningProvider
     227                 :            : {
     228                 :            : protected:
     229                 :            :     using KeyMap = std::map<CKeyID, CKey>;
     230                 :            :     using ScriptMap = std::map<CScriptID, CScript>;
     231                 :            : 
     232                 :            :     /**
     233                 :            :      * Map of key id to unencrypted private keys known by the signing provider.
     234                 :            :      * Map may be empty if the provider has another source of keys, like an
     235                 :            :      * encrypted store.
     236                 :            :      */
     237                 :            :     KeyMap mapKeys GUARDED_BY(cs_KeyStore);
     238                 :            : 
     239                 :            :     /**
     240                 :            :      * Map of script id to scripts known by the signing provider.
     241                 :            :      *
     242                 :            :      * This map originally just held P2SH redeemScripts, and was used by wallet
     243                 :            :      * code to look up script ids referenced in "OP_HASH160 <script id>
     244                 :            :      * OP_EQUAL" P2SH outputs. Later in 605e8473a7d it was extended to hold
     245                 :            :      * P2WSH witnessScripts as well, and used to look up nested scripts
     246                 :            :      * referenced in "OP_0 <script hash>" P2WSH outputs. Later in commits
     247                 :            :      * f4691ab3a9d and 248f3a76a82, it was extended once again to hold segwit
     248                 :            :      * "OP_0 <key or script hash>" scriptPubKeys, in order to give the wallet a
     249                 :            :      * way to distinguish between segwit outputs that it generated addresses for
     250                 :            :      * and wanted to receive payments from, and segwit outputs that it never
     251                 :            :      * generated addresses for, but it could spend just because of having keys.
     252                 :            :      * (Before segwit activation it was also important to not treat segwit
     253                 :            :      * outputs to arbitrary wallet keys as payments, because these could be
     254                 :            :      * spent by anyone without even needing to sign with the keys.)
     255                 :            :      *
     256                 :            :      * Some of the scripts stored in mapScripts are memory-only and
     257                 :            :      * intentionally not saved to disk. Specifically, scripts added by
     258                 :            :      * ImplicitlyLearnRelatedKeyScripts(pubkey) calls are not written to disk so
     259                 :            :      * future wallet code can have flexibility to be more selective about what
     260                 :            :      * transaction outputs it recognizes as payments, instead of having to treat
     261                 :            :      * all outputs spending to keys it knows as payments. By contrast,
     262                 :            :      * mapScripts entries added by AddCScript(script),
     263                 :            :      * LearnRelatedScripts(pubkey, type), and LearnAllRelatedScripts(pubkey)
     264                 :            :      * calls are saved because they are all intentionally used to receive
     265                 :            :      * payments.
     266                 :            :      *
     267                 :            :      * The FillableSigningProvider::mapScripts script map should not be confused
     268                 :            :      * with LegacyScriptPubKeyMan::setWatchOnly script set. The two collections
     269                 :            :      * can hold the same scripts, but they serve different purposes. The
     270                 :            :      * setWatchOnly script set is intended to expand the set of outputs the
     271                 :            :      * wallet considers payments. Every output with a script it contains is
     272                 :            :      * considered to belong to the wallet, regardless of whether the script is
     273                 :            :      * solvable or signable. By contrast, the scripts in mapScripts are only
     274                 :            :      * used for solving, and to restrict which outputs are considered payments
     275                 :            :      * by the wallet. An output with a script in mapScripts, unlike
     276                 :            :      * setWatchOnly, is not automatically considered to belong to the wallet if
     277                 :            :      * it can't be solved and signed for.
     278                 :            :      */
     279                 :            :     ScriptMap mapScripts GUARDED_BY(cs_KeyStore);
     280                 :            : 
     281                 :            :     void ImplicitlyLearnRelatedKeyScripts(const CPubKey& pubkey) EXCLUSIVE_LOCKS_REQUIRED(cs_KeyStore);
     282                 :            : 
     283                 :            : public:
     284                 :            :     mutable RecursiveMutex cs_KeyStore;
     285                 :            : 
     286                 :            :     virtual bool AddKeyPubKey(const CKey& key, const CPubKey &pubkey);
     287                 :       4575 :     virtual bool AddKey(const CKey &key) { return AddKeyPubKey(key, key.GetPubKey()); }
     288                 :            :     virtual bool GetPubKey(const CKeyID &address, CPubKey& vchPubKeyOut) const override;
     289                 :            :     virtual bool HaveKey(const CKeyID &address) const override;
     290                 :            :     virtual std::set<CKeyID> GetKeys() const;
     291                 :            :     virtual bool GetKey(const CKeyID &address, CKey &keyOut) const override;
     292                 :            :     virtual bool AddCScript(const CScript& redeemScript);
     293                 :            :     virtual bool HaveCScript(const CScriptID &hash) const override;
     294                 :            :     virtual std::set<CScriptID> GetCScripts() const;
     295                 :            :     virtual bool GetCScript(const CScriptID &hash, CScript& redeemScriptOut) const override;
     296                 :            : };
     297                 :            : 
     298                 :            : /** Return the CKeyID of the key involved in a script (if there is a unique one). */
     299                 :            : CKeyID GetKeyForDestination(const SigningProvider& store, const CTxDestination& dest);
     300                 :            : 
     301                 :            : /** A signing provider to be used to interface with multiple signing providers at once. */
     302                 :            : class MultiSigningProvider: public SigningProvider {
     303                 :            :     std::vector<std::unique_ptr<SigningProvider>> m_providers;
     304                 :            : 
     305                 :            : public:
     306                 :            :     void AddProvider(std::unique_ptr<SigningProvider> provider);
     307                 :            : 
     308                 :            :     bool GetCScript(const CScriptID& scriptid, CScript& script) const override;
     309                 :            :     bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override;
     310                 :            :     bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override;
     311                 :            :     bool GetKey(const CKeyID& keyid, CKey& key) const override;
     312                 :            :     bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override;
     313                 :            :     bool GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const override;
     314                 :            : };
     315                 :            : 
     316                 :            : #endif // BITCOIN_SCRIPT_SIGNINGPROVIDER_H

Generated by: LCOV version 1.14