From 3b40bff9880e9ae2817136b7d14989afccfc1937 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Wed, 6 Feb 2019 18:08:21 -0800 Subject: Descriptor checksum --- src/script/descriptor.cpp | 144 +++++++++++++++++++++++++- src/script/descriptor.h | 11 +- src/test/descriptor_tests.cpp | 34 ++++-- test/functional/rpc_scantxoutset.py | 6 +- test/functional/test_framework/descriptors.py | 55 ++++++++++ test/functional/wallet_address_types.py | 21 ++-- 6 files changed, 251 insertions(+), 20 deletions(-) create mode 100644 test/functional/test_framework/descriptors.py diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index 532a8028a2..43448d7222 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -20,6 +20,125 @@ namespace { +//////////////////////////////////////////////////////////////////////////// +// Checksum // +//////////////////////////////////////////////////////////////////////////// + +// 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[] # Polynomials over the binary field + * F_mod = b**5 + b**3 + 1 + * F. = GF(32, modulus=F_mod, repr='int') # GF(32) definition + * FP. = F[] # Polynomials over GF(32) + * E_mod = x**3 + x + F.fetch_int(8) + * 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 DescriptorChecksum(const Span& span) +{ + /** 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 // //////////////////////////////////////////////////////////////////////////// @@ -273,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* cache_read, std::vector& output_scripts, FlatSigningProvider& out, std::vector* cache_write) const { @@ -751,11 +875,25 @@ std::unique_ptr InferScript(const CScript& script, ParseScriptCo return MakeUnique(script); } + } // namespace -std::unique_ptr Parse(const std::string& descriptor, FlatSigningProvider& out) +std::unique_ptr Parse(const std::string& descriptor, FlatSigningProvider& out, bool require_checksum) { Span 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(std::move(ret)); return nullptr; diff --git a/src/script/descriptor.h b/src/script/descriptor.h index 44f0efca03..907a102284 100644 --- a/src/script/descriptor.h +++ b/src/script/descriptor.h @@ -62,8 +62,15 @@ struct Descriptor { virtual bool ExpandFromCache(int pos, const std::vector& cache, std::vector& output_scripts, FlatSigningProvider& out) const = 0; }; -/** Parse a descriptor string. Included private keys are put in out. Returns nullptr if parsing fails. */ -std::unique_ptr Parse(const std::string& descriptor, FlatSigningProvider& out); +/** Parse a descriptor string. Included private keys are put in out. + * + * If the descriptor has a checksum, it must be valid. If require_checksum + * is set, the checksum is mandatory - otherwise it is optional. + * + * If a parse error occurs, or the checksum is missing/invalid, or anything + * else is wrong, nullptr is returned. + */ +std::unique_ptr Parse(const std::string& descriptor, FlatSigningProvider& out, bool require_checksum = false); /** Find a descriptor for the specified script, using information from provider where possible. * diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp index 8da8cfc00c..ff2b8d4fc9 100644 --- a/src/test/descriptor_tests.cpp +++ b/src/test/descriptor_tests.cpp @@ -18,8 +18,8 @@ void CheckUnparsable(const std::string& prv, const std::string& pub) FlatSigningProvider keys_priv, keys_pub; auto parse_priv = Parse(prv, keys_priv); auto parse_pub = Parse(pub, keys_pub); - BOOST_CHECK(!parse_priv); - BOOST_CHECK(!parse_pub); + BOOST_CHECK_MESSAGE(!parse_priv, prv); + BOOST_CHECK_MESSAGE(!parse_pub, pub); } constexpr int DEFAULT = 0; @@ -28,6 +28,18 @@ constexpr int HARDENED = 2; // Derivation needs access to private keys constexpr int UNSOLVABLE = 4; // This descriptor is not expected to be solvable constexpr int SIGNABLE = 8; // We can sign with this descriptor (this is not true when actual BIP32 derivation is used, as that's not integrated in our signing code) +/** Compare two descriptors. If only one of them has a checksum, the checksum is ignored. */ +bool EqualDescriptor(std::string a, std::string b) +{ + bool a_check = (a.size() > 9 && a[a.size() - 9] == '#'); + bool b_check = (b.size() > 9 && b[b.size() - 9] == '#'); + if (a_check != b_check) { + if (a_check) a = a.substr(0, a.size() - 9); + if (b_check) b = b.substr(0, b.size() - 9); + } + return a == b; +} + std::string MaybeUseHInsteadOfApostrophy(std::string ret) { if (InsecureRandBool()) { @@ -35,6 +47,7 @@ std::string MaybeUseHInsteadOfApostrophy(std::string ret) auto it = ret.find("'"); if (it != std::string::npos) { ret[it] = 'h'; + if (ret.size() > 9 && ret[ret.size() - 9] == '#') ret = ret.substr(0, ret.size() - 9); // Changing apostrophe to h breaks the checksum } else { break; } @@ -63,16 +76,16 @@ void Check(const std::string& prv, const std::string& pub, int flags, const std: // Check that both versions serialize back to the public version. std::string pub1 = parse_priv->ToString(); std::string pub2 = parse_pub->ToString(); - BOOST_CHECK_EQUAL(pub, pub1); - BOOST_CHECK_EQUAL(pub, pub2); + BOOST_CHECK(EqualDescriptor(pub, pub1)); + BOOST_CHECK(EqualDescriptor(pub, pub2)); // Check that both can be serialized with private key back to the private version, but not without private key. std::string prv1; BOOST_CHECK(parse_priv->ToPrivateString(keys_priv, prv1)); - BOOST_CHECK_EQUAL(prv, prv1); + BOOST_CHECK(EqualDescriptor(prv, prv1)); BOOST_CHECK(!parse_priv->ToPrivateString(keys_pub, prv1)); BOOST_CHECK(parse_pub->ToPrivateString(keys_priv, prv1)); - BOOST_CHECK_EQUAL(prv, prv1); + BOOST_CHECK(EqualDescriptor(prv, prv1)); BOOST_CHECK(!parse_pub->ToPrivateString(keys_pub, prv1)); // Check whether IsRange on both returns the expected result @@ -210,6 +223,15 @@ BOOST_AUTO_TEST_CASE(descriptor_test) CheckUnparsable("wsh(sh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)))", "wsh(sh(pk(03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)))"); // Cannot embed P2SH inside P2WSH CheckUnparsable("sh(sh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)))", "sh(sh(pk(03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)))"); // Cannot embed P2SH inside P2SH CheckUnparsable("wsh(wsh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)))", "wsh(wsh(pk(03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)))"); // Cannot embed P2WSH inside P2WSH + + // Checksums + Check("sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfy", "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5t", DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}}, {{0x8000006FUL,222},{0}}); + Check("sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))", "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))", DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}}, {{0x8000006FUL,222},{0}}); + CheckUnparsable("sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#", "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#"); // Empty checksum + CheckUnparsable("sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfyq", "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5tq"); // Too long checksum + CheckUnparsable("sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxf", "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5"); // Too short checksum + CheckUnparsable("sh(multi(3,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfy", "sh(multi(3,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5t"); // Error in payload + CheckUnparsable("sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggssrxfy", "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjq09x4t"); // Error in checksum } BOOST_AUTO_TEST_SUITE_END() diff --git a/test/functional/rpc_scantxoutset.py b/test/functional/rpc_scantxoutset.py index 11b4db6ec5..29074c6af3 100755 --- a/test/functional/rpc_scantxoutset.py +++ b/test/functional/rpc_scantxoutset.py @@ -97,9 +97,9 @@ class ScantxoutsetTest(BitcoinTestFramework): assert_equal(self.nodes[0].scantxoutset("start", [ {"desc": "combo(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/*)", "range": 1500}])['total_amount'], Decimal("28.672")) # Test the reported descriptors for a few matches - assert_equal(descriptors(self.nodes[0].scantxoutset("start", [ {"desc": "combo(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/0h/0'/*)", "range": 1499}])), ["pkh([0c5f9a1e/0'/0'/0]026dbd8b2315f296d36e6b6920b1579ca75569464875c7ebe869b536a7d9503c8c)", "pkh([0c5f9a1e/0'/0'/1]033e6f25d76c00bedb3a8993c7d5739ee806397f0529b1b31dda31ef890f19a60c)"]) - assert_equal(descriptors(self.nodes[0].scantxoutset("start", [ "combo(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/1/1/0)"])), ["pkh([0c5f9a1e/1/1/0]03e1c5b6e650966971d7e71ef2674f80222752740fc1dfd63bbbd220d2da9bd0fb)"]) - assert_equal(descriptors(self.nodes[0].scantxoutset("start", [ {"desc": "combo(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/*)", "range": 1500}])), ['pkh([0c5f9a1e/1/1/0]03e1c5b6e650966971d7e71ef2674f80222752740fc1dfd63bbbd220d2da9bd0fb)', 'pkh([0c5f9a1e/1/1/1500]03832901c250025da2aebae2bfb38d5c703a57ab66ad477f9c578bfbcd78abca6f)', 'pkh([0c5f9a1e/1/1/1]030d820fc9e8211c4169be8530efbc632775d8286167afd178caaf1089b77daba7)']) + assert_equal(descriptors(self.nodes[0].scantxoutset("start", [ {"desc": "combo(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/0h/0'/*)", "range": 1499}])), ["pkh([0c5f9a1e/0'/0'/0]026dbd8b2315f296d36e6b6920b1579ca75569464875c7ebe869b536a7d9503c8c)#dzxw429x", "pkh([0c5f9a1e/0'/0'/1]033e6f25d76c00bedb3a8993c7d5739ee806397f0529b1b31dda31ef890f19a60c)#43rvceed"]) + assert_equal(descriptors(self.nodes[0].scantxoutset("start", [ "combo(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/1/1/0)"])), ["pkh([0c5f9a1e/1/1/0]03e1c5b6e650966971d7e71ef2674f80222752740fc1dfd63bbbd220d2da9bd0fb)#cxmct4w8"]) + assert_equal(descriptors(self.nodes[0].scantxoutset("start", [ {"desc": "combo(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/*)", "range": 1500}])), ['pkh([0c5f9a1e/1/1/0]03e1c5b6e650966971d7e71ef2674f80222752740fc1dfd63bbbd220d2da9bd0fb)#cxmct4w8', 'pkh([0c5f9a1e/1/1/1500]03832901c250025da2aebae2bfb38d5c703a57ab66ad477f9c578bfbcd78abca6f)#vchwd07g', 'pkh([0c5f9a1e/1/1/1]030d820fc9e8211c4169be8530efbc632775d8286167afd178caaf1089b77daba7)#z2t3ypsa']) if __name__ == '__main__': ScantxoutsetTest().main() diff --git a/test/functional/test_framework/descriptors.py b/test/functional/test_framework/descriptors.py new file mode 100644 index 0000000000..29482ce01e --- /dev/null +++ b/test/functional/test_framework/descriptors.py @@ -0,0 +1,55 @@ +#!/usr/bin/env python3 +# Copyright (c) 2019 Pieter Wuille +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. +"""Utility functions related to output descriptors""" + +INPUT_CHARSET = "0123456789()[],'/*abcdefgh@:$%{}IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~ijklmnopqrstuvwxyzABCDEFGH`#\"\\ " +CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l" +GENERATOR = [0xf5dee51989, 0xa9fdca3312, 0x1bab10e32d, 0x3706b1677a, 0x644d626ffd] + +def descsum_polymod(symbols): + """Internal function that computes the descriptor checksum.""" + chk = 1 + for value in symbols: + top = chk >> 35 + chk = (chk & 0x7ffffffff) << 5 ^ value + for i in range(5): + chk ^= GENERATOR[i] if ((top >> i) & 1) else 0 + return chk + +def descsum_expand(s): + """Internal function that does the character to symbol expansion""" + groups = [] + symbols = [] + for c in s: + if not c in INPUT_CHARSET: + return None + v = INPUT_CHARSET.find(c) + symbols.append(v & 31) + groups.append(v >> 5) + if len(groups) == 3: + symbols.append(groups[0] * 9 + groups[1] * 3 + groups[2]) + groups = [] + if len(groups) == 1: + symbols.append(groups[0]) + elif len(groups) == 2: + symbols.append(groups[0] * 3 + groups[1]) + return symbols + +def descsum_create(s): + """Add a checksum to a descriptor without""" + symbols = descsum_expand(s) + [0, 0, 0, 0, 0, 0, 0, 0] + checksum = descsum_polymod(symbols) ^ 1 + return s + '#' + ''.join(CHECKSUM_CHARSET[(checksum >> (5 * (7 - i))) & 31] for i in range(8)) + +def descsum_check(s, require=True): + """Verify that the checksum is correct in a descriptor""" + if not '#' in s: + return not require + if s[-9] != '#': + return False + if not all(x in CHECKSUM_CHARSET for x in s[-8:]): + return False + symbols = descsum_expand(s[:-9]) + [CHECKSUM_CHARSET.find(x) for x in s[-8:]] + return descsum_polymod(symbols) == 1 diff --git a/test/functional/wallet_address_types.py b/test/functional/wallet_address_types.py index bafa556aad..027229111e 100755 --- a/test/functional/wallet_address_types.py +++ b/test/functional/wallet_address_types.py @@ -54,6 +54,10 @@ from decimal import Decimal import itertools from test_framework.test_framework import BitcoinTestFramework +from test_framework.descriptors import ( + descsum_create, + descsum_check, +) from test_framework.util import ( assert_equal, assert_greater_than, @@ -167,24 +171,29 @@ class AddressTypeTest(BitcoinTestFramework): assert_equal(deriv['path'][0], 'm') key_descs[deriv['pubkey']] = '[' + deriv['master_fingerprint'] + deriv['path'][1:] + ']' + deriv['pubkey'] + # Verify the descriptor checksum against the Python implementation + assert(descsum_check(info['desc'])) + # Verify that stripping the checksum and recreating it using Python roundtrips + assert(info['desc'] == descsum_create(info['desc'][:-9])) + if not multisig and typ == 'legacy': # P2PKH - assert_equal(info['desc'], "pkh(%s)" % key_descs[info['pubkey']]) + assert_equal(info['desc'], descsum_create("pkh(%s)" % key_descs[info['pubkey']])) elif not multisig and typ == 'p2sh-segwit': # P2SH-P2WPKH - assert_equal(info['desc'], "sh(wpkh(%s))" % key_descs[info['pubkey']]) + assert_equal(info['desc'], descsum_create("sh(wpkh(%s))" % key_descs[info['pubkey']])) elif not multisig and typ == 'bech32': # P2WPKH - assert_equal(info['desc'], "wpkh(%s)" % key_descs[info['pubkey']]) + assert_equal(info['desc'], descsum_create("wpkh(%s)" % key_descs[info['pubkey']])) elif typ == 'legacy': # P2SH-multisig - assert_equal(info['desc'], "sh(multi(2,%s,%s))" % (key_descs[info['pubkeys'][0]], key_descs[info['pubkeys'][1]])) + assert_equal(info['desc'], descsum_create("sh(multi(2,%s,%s))" % (key_descs[info['pubkeys'][0]], key_descs[info['pubkeys'][1]]))) elif typ == 'p2sh-segwit': # P2SH-P2WSH-multisig - assert_equal(info['desc'], "sh(wsh(multi(2,%s,%s)))" % (key_descs[info['embedded']['pubkeys'][0]], key_descs[info['embedded']['pubkeys'][1]])) + assert_equal(info['desc'], descsum_create("sh(wsh(multi(2,%s,%s)))" % (key_descs[info['embedded']['pubkeys'][0]], key_descs[info['embedded']['pubkeys'][1]]))) elif typ == 'bech32': # P2WSH-multisig - assert_equal(info['desc'], "wsh(multi(2,%s,%s))" % (key_descs[info['pubkeys'][0]], key_descs[info['pubkeys'][1]])) + assert_equal(info['desc'], descsum_create("wsh(multi(2,%s,%s))" % (key_descs[info['pubkeys'][0]], key_descs[info['pubkeys'][1]]))) else: # Unknown type assert(False) -- cgit v1.2.3 From b52cb6368869c9f6dd2cd8f309b3000de514d439 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 7 Feb 2019 15:09:08 -0800 Subject: Add getdescriptorinfo to compute checksum --- src/rpc/misc.cpp | 41 +++++++++++++++++++++++++++++++++ test/functional/wallet_address_types.py | 2 ++ 2 files changed, 43 insertions(+) diff --git a/src/rpc/misc.cpp b/src/rpc/misc.cpp index 784adfa969..bfb86aa12b 100644 --- a/src/rpc/misc.cpp +++ b/src/rpc/misc.cpp @@ -143,6 +143,46 @@ static UniValue createmultisig(const JSONRPCRequest& request) return result; } +UniValue getdescriptorinfo(const JSONRPCRequest& request) +{ + if (request.fHelp || request.params.size() != 1) { + throw std::runtime_error( + RPCHelpMan{"getdescriptorinfo", + {"\nAnalyses a descriptor.\n"}, + { + {"descriptor", RPCArg::Type::STR, RPCArg::Optional::NO, "The descriptor."}, + }, + RPCResult{ + "{\n" + " \"descriptor\" : \"desc\", (string) The descriptor in canonical form, without private keys\n" + " \"isrange\" : true|false, (boolean) Whether the descriptor is ranged\n" + " \"issolvable\" : true|false, (boolean) Whether the descriptor is solvable\n" + " \"hasprivatekeys\" : true|false, (boolean) Whether the input descriptor contained at least one private key\n" + "}\n" + }, + RPCExamples{ + "Analyse a descriptor\n" + + HelpExampleCli("getdescriptorinfo", "\"wpkh([d34db33f/84h/0h/0h]0279be667ef9dcbbac55a06295Ce870b07029Bfcdb2dce28d959f2815b16f81798)\"") + }}.ToString() + ); + } + + RPCTypeCheck(request.params, {UniValue::VSTR}); + + FlatSigningProvider provider; + auto desc = Parse(request.params[0].get_str(), provider); + if (!desc) { + throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, strprintf("Invalid descriptor")); + } + + UniValue result(UniValue::VOBJ); + result.pushKV("descriptor", desc->ToString()); + result.pushKV("isrange", desc->IsRange()); + result.pushKV("issolvable", desc->IsSolvable()); + result.pushKV("hasprivatekeys", provider.keys.size() > 0); + return result; +} + UniValue deriveaddresses(const JSONRPCRequest& request) { if (request.fHelp || request.params.empty() || request.params.size() > 3) { @@ -564,6 +604,7 @@ static const CRPCCommand commands[] = { "util", "validateaddress", &validateaddress, {"address"} }, { "util", "createmultisig", &createmultisig, {"nrequired","keys","address_type"} }, { "util", "deriveaddresses", &deriveaddresses, {"descriptor", "begin", "end"} }, + { "util", "getdescriptorinfo", &getdescriptorinfo, {"descriptor"} }, { "util", "verifymessage", &verifymessage, {"address","signature","message"} }, { "util", "signmessagewithprivkey", &signmessagewithprivkey, {"privkey","message"} }, diff --git a/test/functional/wallet_address_types.py b/test/functional/wallet_address_types.py index 027229111e..380dd9c0ad 100755 --- a/test/functional/wallet_address_types.py +++ b/test/functional/wallet_address_types.py @@ -175,6 +175,8 @@ class AddressTypeTest(BitcoinTestFramework): assert(descsum_check(info['desc'])) # Verify that stripping the checksum and recreating it using Python roundtrips assert(info['desc'] == descsum_create(info['desc'][:-9])) + # Verify that stripping the checksum and feeding it to getdescriptorinfo roundtrips + assert(info['desc'] == self.nodes[0].getdescriptorinfo(info['desc'][:-9])['descriptor']) if not multisig and typ == 'legacy': # P2PKH -- cgit v1.2.3 From be62903c417293f6217e124669e62fd2172a18f1 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 12 Feb 2019 18:56:53 -0800 Subject: Make descriptor checksums mandatory in deriveaddresses and importmulti --- src/rpc/misc.cpp | 4 ++-- src/wallet/rpcdump.cpp | 2 +- test/functional/rpc_deriveaddresses.py | 28 ++++++++++++----------- test/functional/wallet_importmulti.py | 42 ++++++++++++++++++++++------------ 4 files changed, 45 insertions(+), 31 deletions(-) diff --git a/src/rpc/misc.cpp b/src/rpc/misc.cpp index bfb86aa12b..999a307e2b 100644 --- a/src/rpc/misc.cpp +++ b/src/rpc/misc.cpp @@ -207,7 +207,7 @@ UniValue deriveaddresses(const JSONRPCRequest& request) }, RPCExamples{ "First three native segwit receive addresses\n" + - HelpExampleCli("deriveaddresses", "\"wpkh([d34db33f/84h/0h/0h]xpub6DJ2dNUysrn5Vt36jH2KLBT2i1auw1tTSSomg8PhqNiUtx8QX2SvC9nrHu81fT41fvDUnhMjEzQgXnQjKEu3oaqMSzhSrHMxyyoEAmUHQbY/0/*)\" 0 2") + HelpExampleCli("deriveaddresses", "\"wpkh([d34db33f/84h/0h/0h]xpub6DJ2dNUysrn5Vt36jH2KLBT2i1auw1tTSSomg8PhqNiUtx8QX2SvC9nrHu81fT41fvDUnhMjEzQgXnQjKEu3oaqMSzhSrHMxyyoEAmUHQbY/0/*)#trd0mf0l\" 0 2") }}.ToString() ); } @@ -233,7 +233,7 @@ UniValue deriveaddresses(const JSONRPCRequest& request) } FlatSigningProvider provider; - auto desc = Parse(desc_str, provider); + auto desc = Parse(desc_str, provider, /* require_checksum = */ true); if (!desc) { throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, strprintf("Invalid descriptor")); } diff --git a/src/wallet/rpcdump.cpp b/src/wallet/rpcdump.cpp index 930274f8a1..66a52c1270 100644 --- a/src/wallet/rpcdump.cpp +++ b/src/wallet/rpcdump.cpp @@ -1117,7 +1117,7 @@ static UniValue ProcessImportDescriptor(ImportData& import_data, std::map Date: Fri, 8 Feb 2019 12:03:32 -0800 Subject: Add checksums to descriptors.md --- doc/descriptors.md | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-) diff --git a/doc/descriptors.md b/doc/descriptors.md index de4d4e574f..5dbcd95e1d 100644 --- a/doc/descriptors.md +++ b/doc/descriptors.md @@ -39,7 +39,7 @@ Output descriptors currently support: ## Reference -Descriptors consist of several types of expressions. The top level expression is always a `SCRIPT`. +Descriptors consist of several types of expressions. The top level expression is either a `SCRIPT`, or `SCRIPT#CHECKSUM` where `CHECKSUM` is an 8-character alphanumeric descriptor checksum. `SCRIPT` expressions: - `sh(SCRIPT)` (top level only): P2SH embed the argument. @@ -169,3 +169,20 @@ existing Bitcoin Core wallets, a convenience function `combo` is provided, which takes as input a public key, and describes a set of P2PK, P2PKH, P2WPKH, and P2SH-P2WPH scripts for that key. In case the key is uncompressed, the set only includes P2PK and P2PKH scripts. + +### Checksums + +Descriptors can optionally be suffixed with a checksum to protect against +typos or copy-paste errors. + +These checksums consist of 8 alphanumeric characters. As long as errors are +restricted to substituting characters in `0123456789()[],'/*abcdefgh@:$%{}` +for others in that set and changes in letter case, up to 4 errors will always +be detected in descriptors up to 501 characters, and up to 3 errors in longer +ones. For larger numbers of errors, or other types of errors, there is a +roughly 1 in a trillion chance of not detecting the errors. + +All RPCs in Bitcoin Core will include the checksum in their output. Only +certain RPCs require checksums on input, including `deriveaddress` and +`importmulti`. The checksum for a descriptor without one can be computed +using the `getdescriptorinfo` RPC. -- cgit v1.2.3