diff --git a/src/script/descriptor.h b/src/script/descriptor.h --- a/src/script/descriptor.h +++ b/src/script/descriptor.h @@ -82,12 +82,17 @@ FlatSigningProvider &out) const = 0; }; -/** - * Parse a descriptor string. Included private keys are put in out. - * Returns nullptr if parsing fails. +/** 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); + FlatSigningProvider &out, + bool require_checksum = false); /** * Find a descriptor for the specified script, using information from provider diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -21,6 +21,156 @@ 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 ""; + } + // Emit a symbol for the position inside the group, for every character. + c = PolyMod(c, pos & 31); + // Accumulate the group numbers + cls = cls * 3 + (pos >> 5); + 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) { + // Shift further to determine the checksum. + c = PolyMod(c, 0); + } + // Prevent appending zeroes from not affecting the checksum. + c ^= 1; + + 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 // //////////////////////////////////////////////////////////////////////////// @@ -341,12 +491,14 @@ std::string ToString() const final { 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 ret = ToStringHelper(&arg, out, true); + out = AddChecksum(out); + return ret; } bool ExpandHelper(int pos, const SigningProvider &arg, @@ -915,8 +1067,38 @@ } // namespace std::unique_ptr Parse(const std::string &descriptor, - FlatSigningProvider &out) { + FlatSigningProvider &out, + bool require_checksum) { Span sp(descriptor.data(), descriptor.size()); + + // Checksum checks + auto check_split = Split(sp, '#'); + if (check_split.size() > 2) { + // Multiple '#' symbols + return nullptr; + } + if (check_split.size() == 1 && require_checksum) { + // Missing checksum + return nullptr; + } + if (check_split.size() == 2) { + if (check_split[1].size() != 8) { + // Unexpected length for checksum + return nullptr; + } + auto checksum = DescriptorChecksum(check_split[0]); + if (checksum.empty()) { + // Invalid characters in payload + return nullptr; + } + if (!std::equal(checksum.begin(), checksum.end(), + check_split[1].begin())) { + // Checksum mismatch + return nullptr; + } + } + sp = check_split[0]; + auto ret = ParseScript(sp, ParseScriptContext::TOP, out); if (sp.size() == 0 && ret) { return std::unique_ptr(std::move(ret)); diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp --- a/src/test/descriptor_tests.cpp +++ b/src/test/descriptor_tests.cpp @@ -20,8 +20,8 @@ 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; @@ -35,12 +35,34 @@ // derivation is used, as that's not integrated in our signing code) constexpr int SIGNABLE = 8; +/** + * 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()) { while (true) { auto it = ret.find("'"); if (it != std::string::npos) { ret[it] = 'h'; + if (ret.size() > 9 && ret[ret.size() - 9] == '#') { + // Changing apostrophe to h breaks the checksum + ret = ret.substr(0, ret.size() - 9); + } } else { break; } @@ -71,17 +93,17 @@ // 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, prv2; 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 @@ -385,6 +407,106 @@ "sh(sh(pk(" "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd))" ")"); + + // Checksums + Check("sh(multi(2,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39" + "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7" + "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfy", + "sh(multi(2,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4" + "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB" + "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5t", + DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}}, + {{0x8000006FUL, 222}, {0}}); + Check("sh(multi(2,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39" + "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7" + "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))", + "sh(multi(2,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4" + "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB" + "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))", + DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}}, + {{0x8000006FUL, 222}, {0}}); + // Empty checksum + CheckUnparsable( + "sh(multi(2,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj" + "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA" + "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#", + "sh(multi(2,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko" + "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao" + "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#"); + // Too long checksum + CheckUnparsable( + "sh(multi(2,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj" + "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA" + "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfyq", + "sh(multi(2,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko" + "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao" + "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5tq"); + // Too short checksum + CheckUnparsable( + "sh(multi(2,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj" + "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA" + "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxf", + "sh(multi(2,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko" + "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao" + "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5"); + // Error in payload + CheckUnparsable( + "sh(multi(3,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj" + "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA" + "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfy", + "sh(multi(3,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko" + "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao" + "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5t"); + // Error in checksum + CheckUnparsable( + "sh(multi(2,[00000000/111'/" + "222]" + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj" + "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA" + "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggssrxfy", + "sh(multi(2,[00000000/111'/" + "222]" + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko" + "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao" + "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjq09x4t"); } BOOST_AUTO_TEST_SUITE_END() diff --git a/test/functional/rpc_scantxoutset.py b/test/functional/rpc_scantxoutset.py --- a/test/functional/rpc_scantxoutset.py +++ b/test/functional/rpc_scantxoutset.py @@ -148,20 +148,20 @@ 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)"]) + ["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)"]) + ["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)', - 'pkh([0c5f9a1e/1/1/1500]03832901c250025da2aebae2bfb38d5c703a57ab66ad477f9c578bfbcd78abca6f)', - 'pkh([0c5f9a1e/1/1/1]030d820fc9e8211c4169be8530efbc632775d8286167afd178caaf1089b77daba7)']) + ['pkh([0c5f9a1e/1/1/0]03e1c5b6e650966971d7e71ef2674f80222752740fc1dfd63bbbd220d2da9bd0fb)#cxmct4w8', + 'pkh([0c5f9a1e/1/1/1500]03832901c250025da2aebae2bfb38d5c703a57ab66ad477f9c578bfbcd78abca6f)#vchwd07g', + 'pkh([0c5f9a1e/1/1/1]030d820fc9e8211c4169be8530efbc632775d8286167afd178caaf1089b77daba7)#z2t3ypsa']) if __name__ == '__main__': diff --git a/test/functional/test_framework/descriptors.py b/test/functional/test_framework/descriptors.py new file mode 100644 --- /dev/null +++ b/test/functional/test_framework/descriptors.py @@ -0,0 +1,67 @@ +#!/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 c not 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 --- a/test/functional/wallet_address_types.py +++ b/test/functional/wallet_address_types.py @@ -36,6 +36,10 @@ 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, @@ -111,14 +115,20 @@ 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({})".format(key_descs[info['pubkey']])) + descsum_create("pkh({})".format(key_descs[info['pubkey']]))) elif typ == 'legacy': # P2SH-multisig - assert_equal(info['desc'], "sh(multi(2,{},{}))".format( - key_descs[info['pubkeys'][0]], key_descs[info['pubkeys'][1]])) + assert_equal(info['desc'], descsum_create("sh(multi(2,{},{}))".format( + key_descs[info['pubkeys'][0]], key_descs[info['pubkeys'][1]]))) else: # Unknown type assert(False)