diff options
Diffstat (limited to 'src/script/descriptor.cpp')
-rw-r--r-- | src/script/descriptor.cpp | 173 |
1 files changed, 156 insertions, 17 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index a702be5b78..43448d7222 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -10,6 +10,7 @@ #include <script/standard.h> #include <span.h> +#include <util/bip32.h> #include <util/system.h> #include <util/strencodings.h> @@ -20,21 +21,130 @@ namespace { //////////////////////////////////////////////////////////////////////////// -// Internal representation // +// Checksum // //////////////////////////////////////////////////////////////////////////// -typedef std::vector<uint32_t> KeyPath; +// This section implements a checksum algorithm for descriptors with the +// following properties: +// * Mistakes in a descriptor string are measured in "symbol errors". The higher +// the number of symbol errors, the harder it is to detect: +// * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{} for +// another in that set always counts as 1 symbol error. +// * Note that hex encoded keys are covered by these characters. Xprvs and +// xpubs use other characters too, but already have their own checksum +// mechanism. +// * Function names like "multi()" use other characters, but mistakes in +// these would generally result in an unparseable descriptor. +// * A case error always counts as 1 symbol error. +// * Any other 1 character substitution error counts as 1 or 2 symbol errors. +// * Any 1 symbol error is always detected. +// * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always detected. +// * Any 4 symbol error in a descriptor of up to 507 characters is always detected. +// * Any 5 symbol error in a descriptor of up to 77 characters is always detected. +// * Is optimized to minimize the chance a 5 symbol error in a descriptor up to 387 characters is undetected +// * Random errors have a chance of 1 in 2**40 of being undetected. +// +// These properties are achieved by expanding every group of 3 (non checksum) characters into +// 4 GF(32) symbols, over which a cyclic code is defined. + +/* + * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8 polynomial over GF(32), + * multiplies that polynomial by x, computes its remainder modulo a generator, and adds the constant term val. + * + * 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}. + * It is chosen to define an cyclic error detecting code which is selected by: + * - Starting from all BCH codes over GF(32) of degree 8 and below, which by construction guarantee detecting + * 3 errors in windows up to 19000 symbols. + * - Taking all those generators, and for degree 7 ones, extend them to degree 8 by adding all degree-1 factors. + * - Selecting just the set of generators that guarantee detecting 4 errors in a window of length 512. + * - Selecting one of those with best worst-case behavior for 5 errors in windows of length up to 512. + * + * The generator and the constants to implement it can be verified using this Sage code: + * B = GF(2) # Binary field + * BP.<b> = B[] # Polynomials over the binary field + * F_mod = b**5 + b**3 + 1 + * F.<f> = GF(32, modulus=F_mod, repr='int') # GF(32) definition + * FP.<x> = F[] # Polynomials over GF(32) + * E_mod = x**3 + x + F.fetch_int(8) + * E.<e> = F.extension(E_mod) # Extension field definition + * alpha = e**2743 # Choice of an element in extension field + * for p in divisors(E.order() - 1): # Verify alpha has order 32767. + * assert((alpha**p == 1) == (p % 32767 == 0)) + * G = lcm([(alpha**i).minpoly() for i in [1056,1057,1058]] + [x + 1]) + * print(G) # Print out the generator + * for i in [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers. + * v = 0 + * for coef in reversed((F.fetch_int(i)*(G % x**8)).coefficients(sparse=True)): + * v = v*32 + coef.integer_representation() + * print("0x%x" % v) + */ +uint64_t PolyMod(uint64_t c, int val) +{ + uint8_t c0 = c >> 35; + c = ((c & 0x7ffffffff) << 5) ^ val; + if (c0 & 1) c ^= 0xf5dee51989; + if (c0 & 2) c ^= 0xa9fdca3312; + if (c0 & 4) c ^= 0x1bab10e32d; + if (c0 & 8) c ^= 0x3706b1677a; + if (c0 & 16) c ^= 0x644d626ffd; + return c; +} -std::string FormatKeyPath(const KeyPath& path) +std::string DescriptorChecksum(const Span<const char>& span) { - std::string ret; - for (auto i : path) { - ret += strprintf("/%i", (i << 1) >> 1); - if (i >> 31) ret += '\''; + /** A character set designed such that: + * - The most common 'unprotected' descriptor characters (hex, keypaths) are in the first group of 32. + * - Case errors cause an offset that's a multiple of 32. + * - As many alphabetic characters are in the same group (while following the above restrictions). + * + * If p(x) gives the position of a character c in this character set, every group of 3 characters + * (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). + * This means that changes that only affect the lower 5 bits of the position, or only the higher 2 bits, will just + * affect a single symbol. + * + * As a result, within-group-of-32 errors count as 1 symbol, as do cross-group errors that don't affect + * the position within the groups. + */ + static std::string INPUT_CHARSET = + "0123456789()[],'/*abcdefgh@:$%{}" + "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~" + "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ "; + + /** The character set for the checksum itself (same as bech32). */ + static std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"; + + uint64_t c = 1; + int cls = 0; + int clscount = 0; + for (auto ch : span) { + auto pos = INPUT_CHARSET.find(ch); + if (pos == std::string::npos) return ""; + c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character. + cls = cls * 3 + (pos >> 5); // Accumulate the group numbers + if (++clscount == 3) { + // Emit an extra symbol representing the group numbers, for every 3 characters. + c = PolyMod(c, cls); + cls = 0; + clscount = 0; + } } + if (clscount > 0) c = PolyMod(c, cls); + for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum. + c ^= 1; // Prevent appending zeroes from not affecting the checksum. + + std::string ret(8, ' '); + for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31]; return ret; } +std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(MakeSpan(str)); } + +//////////////////////////////////////////////////////////////////////////// +// Internal representation // +//////////////////////////////////////////////////////////////////////////// + +typedef std::vector<uint32_t> KeyPath; + /** Interface for public key objects in descriptors. */ struct PubkeyProvider { @@ -63,7 +173,7 @@ class OriginPubkeyProvider final : public PubkeyProvider std::string OriginString() const { - return HexStr(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint)) + FormatKeyPath(m_origin.path); + return HexStr(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint)) + FormatHDKeypath(m_origin.path); } public: @@ -184,7 +294,7 @@ public: } std::string ToString() const override { - std::string ret = EncodeExtPubKey(m_extkey) + FormatKeyPath(m_path); + std::string ret = EncodeExtPubKey(m_extkey) + FormatHDKeypath(m_path); if (IsRange()) { ret += "/*"; if (m_derive == DeriveType::HARDENED) ret += '\''; @@ -195,7 +305,7 @@ public: { CExtKey key; if (!GetExtKey(arg, key)) return false; - out = EncodeExtKey(key) + FormatKeyPath(m_path); + out = EncodeExtKey(key) + FormatHDKeypath(m_path); if (IsRange()) { out += "/*"; if (m_derive == DeriveType::HARDENED) out += '\''; @@ -226,7 +336,7 @@ protected: * @param pubkeys The evaluations of the m_pubkey_args field. * @param script The evaluation of m_script_arg (or nullptr when m_script_arg is nullptr). * @param out A FlatSigningProvider to put scripts or public keys in that are necessary to the solver. - * The script and pubkeys argument to this function are automatically added. + * The script arguments to this function are automatically added, as is the origin info of the provided pubkeys. * @return A vector with scriptPubKeys for this descriptor. */ virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, const CScript* script, FlatSigningProvider& out) const = 0; @@ -282,10 +392,15 @@ public: { std::string ret; ToStringHelper(nullptr, ret, false); - return ret; + return AddChecksum(ret); } - bool ToPrivateString(const SigningProvider& arg, std::string& out) const override final { return ToStringHelper(&arg, out, true); } + bool ToPrivateString(const SigningProvider& arg, std::string& out) const override final + { + bool ret = ToStringHelper(&arg, out, true); + out = AddChecksum(out); + return ret; + } bool ExpandHelper(int pos, const SigningProvider& arg, Span<const unsigned char>* cache_read, std::vector<CScript>& output_scripts, FlatSigningProvider& out, std::vector<unsigned char>* cache_write) const { @@ -322,7 +437,6 @@ public: for (auto& entry : entries) { pubkeys.push_back(entry.first); out.origins.emplace(entry.first.GetID(), std::move(entry.second)); - out.pubkeys.emplace(entry.first.GetID(), entry.first); } if (m_script_arg) { for (const auto& subscript : subscripts) { @@ -396,7 +510,12 @@ public: class PKHDescriptor final : public DescriptorImpl { protected: - std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider&) const override { return Singleton(GetScriptForDestination(keys[0].GetID())); } + std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override + { + CKeyID id = keys[0].GetID(); + out.pubkeys.emplace(id, keys[0]); + return Singleton(GetScriptForDestination(id)); + } public: PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Singleton(std::move(prov)), {}, "pkh") {} }; @@ -405,7 +524,12 @@ public: class WPKHDescriptor final : public DescriptorImpl { protected: - std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider&) const override { return Singleton(GetScriptForDestination(WitnessV0KeyHash(keys[0].GetID()))); } + std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override + { + CKeyID id = keys[0].GetID(); + out.pubkeys.emplace(id, keys[0]); + return Singleton(GetScriptForDestination(WitnessV0KeyHash(id))); + } public: WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Singleton(std::move(prov)), {}, "wpkh") {} }; @@ -418,6 +542,7 @@ protected: { std::vector<CScript> ret; CKeyID id = keys[0].GetID(); + out.pubkeys.emplace(id, keys[0]); ret.emplace_back(GetScriptForRawPubKey(keys[0])); // P2PK ret.emplace_back(GetScriptForDestination(id)); // P2PKH if (keys[0].IsCompressed()) { @@ -750,11 +875,25 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo return MakeUnique<RawDescriptor>(script); } + } // namespace -std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out) +std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, bool require_checksum) { Span<const char> sp(descriptor.data(), descriptor.size()); + + // Checksum checks + auto check_split = Split(sp, '#'); + if (check_split.size() > 2) return nullptr; // Multiple '#' symbols + if (check_split.size() == 1 && require_checksum) return nullptr; // Missing checksum + if (check_split.size() == 2) { + if (check_split[1].size() != 8) return nullptr; // Unexpected length for checksum + auto checksum = DescriptorChecksum(check_split[0]); + if (checksum.empty()) return nullptr; // Invalid characters in payload + if (!std::equal(checksum.begin(), checksum.end(), check_split[1].begin())) return nullptr; // Checksum mismatch + } + sp = check_split[0]; + auto ret = ParseScript(sp, ParseScriptContext::TOP, out); if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret)); return nullptr; |