1// Copyright (c) 2018-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <script/descriptor.h>
6
7#include <addresstype.h>
8#include <attributes.h>
9#include <consensus/consensus.h>
10#include <crypto/hex_base.h>
11#include <crypto/sha256.h>
12#include <hash.h>
13#include <key.h>
14#include <key_io.h>
15#include <musig.h>
16#include <primitives/transaction.h>
17#include <pubkey.h>
18#include <script/interpreter.h>
19#include <script/keyorigin.h>
20#include <script/miniscript.h>
21#include <script/parsing.h>
22#include <script/script.h>
23#include <script/signingprovider.h>
24#include <script/solver.h>
25#include <serialize.h>
26#include <tinyformat.h>
27#include <uint256.h>
28#include <util/bip32.h>
29#include <util/check.h>
30#include <util/expected.h>
31#include <util/strencodings.h>
32#include <util/string.h>
33#include <util/vector.h>
34
35#include <algorithm>
36#include <compare>
37#include <iterator>
38#include <map>
39#include <memory>
40#include <numeric>
41#include <optional>
42#include <span>
43#include <stdexcept>
44#include <string>
45#include <tuple>
46#include <unordered_set>
47#include <utility>
48#include <vector>
49
50using util::Split;
51
52namespace {
53
54////////////////////////////////////////////////////////////////////////////
55// Checksum                                                               //
56////////////////////////////////////////////////////////////////////////////
57
58// This section implements a checksum algorithm for descriptors with the
59// following properties:
60// * Mistakes in a descriptor string are measured in "symbol errors". The higher
61//   the number of symbol errors, the harder it is to detect:
62//   * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{} for
63//     another in that set always counts as 1 symbol error.
64//     * Note that hex encoded keys are covered by these characters. Xprvs and
65//       xpubs use other characters too, but already have their own checksum
66//       mechanism.
67//     * Function names like "multi()" use other characters, but mistakes in
68//       these would generally result in an unparsable descriptor.
69//   * A case error always counts as 1 symbol error.
70//   * Any other 1 character substitution error counts as 1 or 2 symbol errors.
71// * Any 1 symbol error is always detected.
72// * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always detected.
73// * Any 4 symbol error in a descriptor of up to 507 characters is always detected.
74// * Any 5 symbol error in a descriptor of up to 77 characters is always detected.
75// * Is optimized to minimize the chance a 5 symbol error in a descriptor up to 387 characters is undetected
76// * Random errors have a chance of 1 in 2**40 of being undetected.
77//
78// These properties are achieved by expanding every group of 3 (non checksum) characters into
79// 4 GF(32) symbols, over which a cyclic code is defined.
80
81/*
82 * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8 polynomial over GF(32),
83 * multiplies that polynomial by x, computes its remainder modulo a generator, and adds the constant term val.
84 *
85 * This generator is G(x) = x^8 + {30}x^7 + {23}x^6 + {15}x^5 + {14}x^4 + {10}x^3 + {6}x^2 + {12}x + {9}.
86 * It is chosen to define an cyclic error detecting code which is selected by:
87 * - Starting from all BCH codes over GF(32) of degree 8 and below, which by construction guarantee detecting
88 *   3 errors in windows up to 19000 symbols.
89 * - Taking all those generators, and for degree 7 ones, extend them to degree 8 by adding all degree-1 factors.
90 * - Selecting just the set of generators that guarantee detecting 4 errors in a window of length 512.
91 * - Selecting one of those with best worst-case behavior for 5 errors in windows of length up to 512.
92 *
93 * The generator and the constants to implement it can be verified using this Sage code:
94 *   B = GF(2) # Binary field
95 *   BP.<b> = B[] # Polynomials over the binary field
96 *   F_mod = b**5 + b**3 + 1
97 *   F.<f> = GF(32, modulus=F_mod, repr='int') # GF(32) definition
98 *   FP.<x> = F[] # Polynomials over GF(32)
99 *   E_mod = x**3 + x + F.fetch_int(8)
100 *   E.<e> = F.extension(E_mod) # Extension field definition
101 *   alpha = e**2743 # Choice of an element in extension field
102 *   for p in divisors(E.order() - 1): # Verify alpha has order 32767.
103 *       assert((alpha**p == 1) == (p % 32767 == 0))
104 *   G = lcm([(alpha**i).minpoly() for i in [1056,1057,1058]] + [x + 1])
105 *   print(G) # Print out the generator
106 *   for i in [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers.
107 *       v = 0
108 *       for coef in reversed((F.fetch_int(i)*(G % x**8)).coefficients(sparse=True)):
109 *           v = v*32 + coef.integer_representation()
110 *       print("0x%x" % v)
111 */
112uint64_t PolyMod(uint64_t c, int val)
113{
114    uint8_t c0 = c >> 35;
115    c = ((c & 0x7ffffffff) << 5) ^ val;
116    if (c0 & 1) c ^= 0xf5dee51989;
117    if (c0 & 2) c ^= 0xa9fdca3312;
118    if (c0 & 4) c ^= 0x1bab10e32d;
119    if (c0 & 8) c ^= 0x3706b1677a;
120    if (c0 & 16) c ^= 0x644d626ffd;
121    return c;
122}
123
124std::string DescriptorChecksum(const std::span<const char>& span)
125{
126    /** A character set designed such that:
127     *  - The most common 'unprotected' descriptor characters (hex, keypaths) are in the first group of 32.
128     *  - Case errors cause an offset that's a multiple of 32.
129     *  - As many alphabetic characters are in the same group (while following the above restrictions).
130     *
131     * If p(x) gives the position of a character c in this character set, every group of 3 characters
132     * (a,b,c) is encoded as the 4 symbols (p(a) & 31, p(b) & 31, p(c) & 31, (p(a) / 32) + 3 * (p(b) / 32) + 9 * (p(c) / 32).
133     * This means that changes that only affect the lower 5 bits of the position, or only the higher 2 bits, will just
134     * affect a single symbol.
135     *
136     * As a result, within-group-of-32 errors count as 1 symbol, as do cross-group errors that don't affect
137     * the position within the groups.
138     */
139    static const std::string INPUT_CHARSET =
140        "0123456789()[],'/*abcdefgh@:$%{}"
141        "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~"
142        "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
143
144    /** The character set for the checksum itself (same as bech32). */
145    static const std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
146
147    uint64_t c = 1;
148    int cls = 0;
149    int clscount = 0;
150    for (auto ch : span) {
151        auto pos = INPUT_CHARSET.find(ch);
152        if (pos == std::string::npos) return "";
153        c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character.
154        cls = cls * 3 + (pos >> 5); // Accumulate the group numbers
155        if (++clscount == 3) {
156            // Emit an extra symbol representing the group numbers, for every 3 characters.
157            c = PolyMod(c, cls);
158            cls = 0;
159            clscount = 0;
160        }
161    }
162    if (clscount > 0) c = PolyMod(c, cls);
163    for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum.
164    c ^= 1; // Prevent appending zeroes from not affecting the checksum.
165
166    std::string ret(8, ' ');
167    for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31];
168    return ret;
169}
170
171std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); }
172
173////////////////////////////////////////////////////////////////////////////
174// Internal representation                                                //
175////////////////////////////////////////////////////////////////////////////
176
177typedef std::vector<uint32_t> KeyPath;
178
179/** Interface for public key objects in descriptors. */
180struct PubkeyProvider
181{
182public:
183    //! Index of this key expression in the descriptor
184    //! E.g. If this PubkeyProvider is key1 in multi(2, key1, key2, key3), then m_expr_index = 0
185    const uint32_t m_expr_index;
186
187    explicit PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {}
188
189    virtual ~PubkeyProvider() = default;
190
191    /** Derive a public key and put it into out.
192     *  read_cache is the cache to read keys from (if not nullptr)
193     *  write_cache is the cache to write keys to (if not nullptr)
194     *  Caches are not exclusive but this is not tested. Currently we use them exclusively
195     */
196    virtual std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const = 0;
197
198    /** Whether this represent multiple public keys at different positions. */
199    virtual bool IsRange() const = 0;
200
201    /** Get the size of the generated public key(s) in bytes (33 or 65). */
202    virtual size_t GetSize() const = 0;
203
204    enum class StringType {
205        PUBLIC,
206        CANONICAL, // string calculation that always use h
207        COMPAT // string calculation that mustn't change over time to stay compatible with previous software versions
208    };
209
210    /** Get the descriptor string form. */
211    virtual std::string ToString(StringType type) const = 0;
212
213    /** Get the descriptor string form including private data (if available in arg).
214     *  If the private data is not available, the output string in the "out" parameter
215     *  will not contain any private key information,
216     *  and this function will return "false".
217     */
218    virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0;
219
220    /** Get the descriptor string form with the xpub at the last hardened derivation,
221     *  and always use h for hardened derivation.
222     */
223    virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache = nullptr) const = 0;
224
225    /** Derive a private key, if private data is available in arg and put it into out. */
226    virtual void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const = 0;
227
228    /** Whether private data for this provider is available in arg. */
229    virtual bool HavePrivateKeys(const SigningProvider& arg) const
230    {
231        FlatSigningProvider tmp_provider;
232        GetPrivKey(/*pos=*/0, arg, tmp_provider);
233        return !tmp_provider.keys.empty();
234    }
235
236    /** Return the non-extended public key for this PubkeyProvider, if it has one. */
237    virtual std::optional<CPubKey> GetRootPubKey() const = 0;
238    /** Return the extended public key for this PubkeyProvider, if it has one. */
239    virtual std::optional<CExtPubKey> GetRootExtPubKey() const = 0;
240
241    /** Make a deep copy of this PubkeyProvider */
242    virtual std::unique_ptr<PubkeyProvider> Clone() const = 0;
243
244    /** Whether this PubkeyProvider is a BIP 32 extended key that can be derived from */
245    virtual bool IsBIP32() const = 0;
246
247    /** Get the count of keys known by this PubkeyProvider. Usually one, but may be more for key aggregation schemes */
248    virtual size_t GetKeyCount() const { return 1; }
249
250    /** Whether this PubkeyProvider can always provide a public key without cache or private key arguments */