Addresses (partially) #16779 - no GUI change in this PR
Adds a LocateError function the bech32 library, which is then called by validateaddress RPC, (and then eventually from a GUI tool too, future work). I think modifying validateaddress is nicer than adding a separate RPC for this.
Includes tests.
Based on https://github.com/sipa/bech32/blob/master/ecc/javascript/bech32_ecc.js Credit to sipa for that code
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
381+ int ind = CheckCharacters(str);
382+ if (ind != -1) {
383+ error = "Invalid character";
384+ return ind;
385+ }
386+ if (str.size() > 90) {
9d91c4a046d990d7f648328dfed982ad38c87ff1
Should be first test?
416+ int length = str.size() - 1;
417+ uint32_t syn = Syndrome(residue);
418+ int s0 = syn & 0x3FF;
419+ int s1 = (syn >> 10) & 0x3FF;
420+ int s2 = syn >> 20;
421+ int l_s0 = GF1024_LOG[s0];
9d91c4a046d990d7f648328dfed982ad38c87ff1
Could add at the top:
0static_assert(sizeof(GF1024_LOG) / sizeof(GF1024_LOG[0]) == 2014, "GF1024_LOG length should be 1024");
Same for GF1024_EXP.
24@@ -25,6 +25,9 @@ std::string Encode(const std::string& hrp, const std::vector<uint8_t>& values);
25 /** Decode a Bech32 string. Returns (hrp, data). Empty hrp means failure. */
26 std::pair<std::string, std::vector<uint8_t>> Decode(const std::string& str);
27
28+/** Return the position of an error in a Bech32 string. If no errors are present, return -1. */
29+int LocateError(const std::string& str, std::string& error);
9d91c4a046d990d7f648328dfed982ad38c87ff1
Could add some tests to src/test/bech32_tests.cpp?
431+ return 0;
432+ }
433+ return str.size() - p1 - (p1 >= values.size() ? 2 : 1);
434+ }
435+ }
436+ for (int p1 = 0; p1 < length; p1++) {
9d91c4a046d990d7f648328dfed982ad38c87ff1
nit, ++p1.
39@@ -39,6 +40,8 @@ static UniValue validateaddress(const JSONRPCRequest& request)
40 " \"iswitness\" : true|false, (boolean) If the address is a witness address\n"
41 " \"witness_version\" : version (numeric, optional) The version number of the witness program\n"
42 " \"witness_program\" : \"hex\" (string, optional) The hex value of the witness program\n"
43+ " \"error\" : \"message\" (string, optional) The error message if the address is an invalid bech32 address\n"
f877a9b4af7da6632430eff898b957107514e6de
Could include only when prefix matches CChainParams::Bech32HRP?
+1 @sipa suggestion, something like
0CTxDestination DecodeDestination(const std::string& str, std::string& error);
1CTxDestination DecodeDestination(const std::string& str)
2{
3 const std::string& error;
4 return DecodeDestination(str, error);
5}
And maybe also embed the error index in the message for now.
Concept ACK. I would prefer to make address_type an optional hint, and instead guess the address type.
Distinguishing between base58 and bech32 could be done by counting how many characters of the address are part of the base58/bech32 character set. You can then use error_index to indicate the position of a character that doesn’t belong in the set.
28@@ -28,6 +29,7 @@ static UniValue validateaddress(const JSONRPCRequest& request)
29 "\nReturn information about the given bitcoin address.\n",
30 {
31 {"address", RPCArg::Type::STR, RPCArg::Optional::NO, "The bitcoin address to validate"},
32+ {"address_type", RPCArg::Type::STR, RPCArg::Optional::OMITTED_NAMED_ARG, "The address type provided, used to detect errors. Options are \"legacy\", \"p2sh-segwit\", and \"bech32\"."},
0@@ -0,0 +1,130 @@
1+#!/usr/bin/env python3
Concept ACK to adding Bech32 error location to validateaddress, but echoing earlier comments:
107+
108+ # Legacy address with one error
109+ address = "muehQnn2P5NhiRCGg9HewAWrXLRy2d7TZE"
110+ res = self.nodes[0].validateaddress(address, "legacy")
111+ assert_equal(res['isvalid'], False)
112+ assert_equal(res['error'], "Invalid checksum for Base58 address")
120+
121+ # Legacy address with incorrect prefix for current network
122+ address = "1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2"
123+ res = self.nodes[0].validateaddress(address, "legacy")
124+ assert_equal(res['isvalid'], False)
125+ assert_equal(res['error'], "Invalid prefix for Base58 address")
From ci:
AssertionError: not(Invalid HRP or Base58 character in address == Invalid address format)
285+ std::vector<unsigned char> data;
286+ if (!DecodeBase58(str, data, 21)) {
287+ return "Invalid HRP or Base58 character in address";
288+ }
289+ if (!DecodeBase58Check(str, data, 21)) {
290+ return "Invalid checksum for Base58 address";
Invalid HRP or Base58 character in address rather than a checksum error. It might be useful to introduce rpc_validate_address.py earlier and add some base58 examples to it.
45@@ -46,6 +46,7 @@ static RPCHelpMan validateaddress()
46 {RPCResult::Type::NUM, "witness_version", /* optional */ true, "The version number of the witness program"},
47 {RPCResult::Type::STR_HEX, "witness_program", /* optional */ true, "The hex value of the witness program"},
48 {RPCResult::Type::STR, "error", /* optional */ true, "Error message, if any"},
49+ {RPCResult::Type::STR, "error_locations", /* optional */ true, "Indices of errors locations in address, if known (e.g. Bech32 errors)"},
std::vector<int>& error_locations) in the next commit.
3bc568d looks mostly good and works.
I don’t fully understand the moon math involved in the error position detection, but it seems to work and it’s run if and only if the regular decoding fails.
14+ # Valid address
15+ address = "bcrt1q049ldschfnwystcqnsvyfpj23mpsg3jcedq9xv"
16+ res = self.nodes[0].validateaddress(address)
17+ assert_equal(res['isvalid'], True)
18+ assert 'error' not in res
19+ assert 'error_locations' not in res
In 3bc568d67537e1725ea0d7472412fe9e4331d01c “Add functional test for validateaddress”
A lot of this test is repetitive, would be nice to add a check function (maybe self.assert_valid and self.assert_invalid) that you can just give it all of the different scenarios rather than copying the same 5 lines.
ACK 1414005c5b24f13bb4da850c62c7c3cdc6436ad1
Reviewed everything except the actual bech32(m) error location code as I currently don’t understand the math there. Also tested manually with a few addresses.
101+ 148, 260, 658, 385, 287, 262, 204, 126, 586, 1004, 236, 165, 854, 411,
102+ 932, 560, 19, 215, 1002, 775, 653, 928, 901, 964, 884, 798, 839, 786,
103+ 433, 610, 116, 855, 180, 479, 910, 1014, 599, 915, 905, 306, 516, 731,
104+ 626, 978, 825, 344, 605, 654, 209
105+};
106+static_assert(sizeof(GF1024_EXP) / sizeof(GF1024_EXP[0]) == 1023, "GF1024_EXP length should be 1023");
std::size(GF1024_EXP) == 1023.
464+ }
465+ values[i - pos - 1] = rev;
466+ }
467+
468+ // Base the polymod value off the witness version
469+ Encoding encoding = values[0] > 0 ? Encoding::BECH32M : Encoding::BECH32;
What if there is a typo in the witness version character?
BIP350 actually spells out a strategy for locating errors in this case: https://github.com/bitcoin/bips/blob/master/bip-0350.mediawiki#addresses-for-segregated-witness-outputs
50@@ -51,6 +51,10 @@ static RPCHelpMan validateaddress()
51 {RPCResult::Type::NUM, "witness_version", /* optional */ true, "The version number of the witness program"},
52 {RPCResult::Type::STR_HEX, "witness_program", /* optional */ true, "The hex value of the witness program"},
53 {RPCResult::Type::STR, "error", /* optional */ true, "Error message, if any"},
54+ {RPCResult::Type::ARR, "error_locations", "Indices of error locations in address, if known (e.g. Bech32 errors)",
317+ for (int i = from; i < to; i++) {
318+ vec.push_back(i);
319+ }
320+}
321+
322+/** Return index of first invalid character in a Bech32 string. */
In commit “Add Bech32 error location function” (b62b67e06cc406fdad68da4c091168fb5f11c1d4)
Comment is out of date
461+ if (rev == -1) {
462+ error_locations.push_back(i);
463+ return "Invalid Base 32 character";
464+ }
465+ values[i - pos - 1] = rev;
466+ }
In commit “Add Bech32 error location function” (b62b67e06cc406fdad68da4c091168fb5f11c1d4)
These lines could be moved into a function and deduplicated with lines 415-424 above.
Maybe not worth it because a PR that affects address decoding is more dangerous than a PR that just changes error detection.
34+// The defining polynomial of the extension is x^2 + 9x + 23
35+// Let (e) be a primitive element of GF(1024), that is, a generator of the field.
36+// Every non-zero element of the field can then be represented as (e)^k for some power k.
37+// The array GF1024_EXP contains all these powers of (e) - GF1024_EXP[k] = (e)^k in GF(1024).
38+// Conversely, GF1024_LOG contains the discrete logarithms of these powers, so
39+// GF1024_LOG[GF1024_EXP[k]] == k
In commit “Add lots of comments to Bech32” (5599813b80e53a1539c66625b4320ab1b4fb4848)
Could write a unit test or constexpr compile time test to check this
constexpr algorithm…
101@@ -98,15 +102,27 @@ CTxDestination DecodeDestination(const std::string& str, const CChainParams& par
102 return ScriptHash(hash);
103 }
104
105- // Set potential error message.
106- // This message may be changed if the address can also be interpreted as a Bech32 address.
107- error_str = "Invalid prefix for Base58-encoded address";
108+ if (!std::equal(script_prefix.begin(), script_prefix.end(), data.begin()) &&
In commit “More detailed error checking for base58 addresses” (0b06e720c0182dee8b560d2e8d3891b036f63ea7)
Is there something which guarantees data size is greater or equal to script_prefix and pubkey_prefix sizes? If not then, it seems like this can read uninitialized memory.
Would suggest either adding assert’s to make it clear these cases won’t happen, or else adding size checks to the if statement to handle these cases.
Error: attempt to subscript a past-the-end iterator 1 step from its current position, which falls outside its dereferenceable range.
113+ }
114+ return CNoDestination();
115+ } else if (!is_bech32) {
116+ // Try Base58 decoding without the checksum, using a much larger max length
117+ if (!DecodeBase58(str, data, 100)) {
118+ error_str = "Invalid HRP or Base58 character in address";
In commit “More detailed error checking for base58 addresses” (0b06e720c0182dee8b560d2e8d3891b036f63ea7)
IMO previous error message “Invalid address format” seems more understandable if you aren’t an address format guru than “Invalid HRP or Base58 character in address”. Maybe consider keeping the existing message or switching to something in between like “Not a valid BECH32 or Base58 encoding”
473+ if (residue != 0) {
474+ uint32_t syn = Syndrome(residue);
475+ int s0 = syn & 0x3FF;
476+ int s1 = (syn >> 10) & 0x3FF;
477+ int s2 = syn >> 20;
478+ int l_s0 = GF1024_LOG[s0];
In commit “Add Bech32 error location function” (b62b67e06cc406fdad68da4c091168fb5f11c1d4)
This code doesn’t seem particularly performance critical. Maybe it would be safer to use bounds checked array lookups instead of direct pointer accesses.
re: #16807 (review)
@ryanofsky Alternatively, would it help if there was an (additional)
& 0x3FFinside the[]?
I think most ideal thing would be for it to use something like std::array::at and throw an exception in case of a bug. Alternative of adding & 0x3FF to lookups could help avoid undefined behavior, but also clutter the code and mask potential bugs. What’s best just depends on what your priorities are. No strong opinions from me!
67@@ -68,10 +68,36 @@ BOOST_AUTO_TEST_CASE(bech32_testvectors_invalid)
68 "1qzzfhee",
69 "a12UEL5L",
70 "A12uEL5L",
71+ "abcdef1qpzrz9x8gf2tvdw0s3jn54khce6mua7lmqqqxw",
72 };
73+ static const std::pair<std::string, int> ERRORS[] = {
In commit “Add boost tests for bech32 error detection” (c4979f77c1264f0099d1dfa278b1d9c18340b5f9)
Could be good to static_assert that ERRORS and CASES arrays are the same size.
94 BOOST_CHECK(dec.encoding == bech32::Encoding::INVALID);
95+ std::vector<int> error_locations;
96+ std::string error = bech32::LocateErrors(str, error_locations);
97+ BOOST_CHECK_EQUAL(err.first, error);
98+ if (err.second == -1) BOOST_CHECK(error_locations.empty());
99+ else BOOST_CHECK_EQUAL(err.second, error_locations[0]);
In commit “Add boost tests for bech32 error detection” (c4979f77c1264f0099d1dfa278b1d9c18340b5f9)
Could be good to BOOST_CHECK_EQUAL(error_locations.size(), 1)).
Could also be good to add cases with size > 1 here, but less important since python tests cover some of these.
Same suggestions could apply to bech32m test below
570+ // Compute the error position p1 as l_s1 - l_s0 = p1 (mod 1023)
571+ size_t p1 = (l_s1 - l_s0 + 1023) % 1023; // the +1023 ensures it is positive
572+ // Now because s0 = e1*(e)^(997*p1), we get e1 = s0/((e)^(997*p1)). Remember that (e)^1023 = 1,
573+ // so 1/((e)^997) = (e)^(1023-997).
574 int l_e1 = l_s0 + (1023 - 997) * p1;
575+ // Finally, some sanity checks on the result:
In commit “Add lots of comments to Bech32” (5599813b80e53a1539c66625b4320ab1b4fb4848)
If check below is supposed to be a sanity check, shouldn’t there be an assert, or a log, or a push_back(-1), or some other indication if it fails?
Same comment applies to other sanity checks and continue statements below. The descriptions here seem like they could be clearer about which of these conditions are possible to hit and which should be impossible.
525+
526+ if (error_locations.empty() || (!possible_errors.empty() && possible_errors.size() < error_locations.size())) {
527+ error_locations = std::move(possible_errors);
528+ }
529+ }
530+ return "Invalid checksum";
In commit “Add Bech32 error location function” (b62b67e06cc406fdad68da4c091168fb5f11c1d4)
Might be nice if this mentioned the encoding that was detected. I.e. add an optional<Encoding> error_encoding variable, and set:
0error_locations = std::move(possible_errors);
1error_encoding = encoding;
and return:
0return error_encoding == BECH32M ? "Invalid bech32m checksum" : error_encoding == BECH32 ? "Invalid bech32 checksum" : "Invalid checksum"
0@@ -0,0 +1,6 @@
1+Updated RPCs
2+------------
3+
4+- The `validateaddress` RPC now optionally returns an `error_locations` array, with the indices of
In commit “Add release notes for validateaddress Bech32 error detection” (2eb5792ec7bbeaf7138420b6c85c5cd0a0404946)
Maybe mention that validateaddress returns new more specific error strings if an address can’t be decoded.
Also “optionally returns” here seems a little misleading since this isn’t an option the caller can control. Would maybe just say it returns error locations whenever it’s possible to determine them.
Code review ACK 88cc4810926e4f5af6757ee1b0eed61abda3d746 with caveat that I only checked the new LocateErrors code to try to verify it didn’t have unsafe or unexpected operations or loop forever or crash. Did not try to verify behavior corresponds to the spec. In the worst case bugs here should just affect error messages not actual decoding of addresses so this seemed ok.
I left various review suggestions, but feel to ignore them or just use ones that seem useful.
I do think it should be possible to add more test coverage. I think it would be nice to have a fuzz test that would encode a random address, decode it and verify the address was the same, introduce random errors, and verify the errors were detected at the right locations. Also maybe there could be unit tests or constexpr checks that verify the contents of the new GF1024_EXP / GF1024_LOG arrays.
22@@ -23,7 +23,7 @@ std::string EncodeExtPubKey(const CExtPubKey& extpubkey);
23
24 std::string EncodeDestination(const CTxDestination& dest);
25 CTxDestination DecodeDestination(const std::string& str);
26-CTxDestination DecodeDestination(const std::string& str, std::string& error_msg);
27+CTxDestination DecodeDestination(const std::string& str, std::string& error_msg, std::vector<int>* error_locations = nullptr);
DecodeDestination overload to avoid pointer to vector: https://github.com/promag/bitcoin/commit/94ca6b403e221f12830ea50158547f1142c67230
310 inline unsigned char LowerCase(unsigned char c)
311 {
312 return (c >= 'A' && c <= 'Z') ? (c - 'A') + 'a' : c;
313 }
314
315+void push_range(int from, int to, std::vector<int>& vec)
Instead of this function, it may be worth just using std::iota.
The function is equivalent to:
0void push_range(int from, int to, std::vector<int>& vec)
1{
2 vec.resize(to - from);
3 std::iota(vec.begin(), vec.end(), from);
4}
But I suggest just doing that directly in the call sites.
464+ }
465+ values[i - pos - 1] = rev;
466+ }
467+
468+ // We attempt error detection with both bech32 and bech32m, and choose the one with the fewest errors
469+ // We can't simply use the segwit version, because that may be one of the errors
tACK 88cc481
The command below returns the “error_locations” field on the PR branch.
0./src/bitcoin-cli validateaddress bc1qctxsy54qjhk0dl5ea0pd2xtth2qq9n78wlk39m
Master branch:
0{
1 "isvalid": false,
2 "error": "Invalid address format"
3}
PR Branch:
0{
1 "isvalid": false,
2 "error_locations": [
3 29
4 ],
5 "error": "Invalid checksum"
6}