Full BIP173 (Bech32) support

sipa commented at 10:18 pm on August 26, 2017: member

Builds on top of #11117.

This adds support for:

Creating BIP173 addresses for testing (through addwitnessaddress, though by default it still produces P2SH versions)
Sending to BIP173 addresses (including non-v0 ones)
Analysing BIP173 addresses (through validateaddress)

It includes a reformatted version of the C++ Bech32 reference code and an independent implementation of the address encoding/decoding logic (integrated with CTxDestination). All BIP173 test vectors are included.

Not included (and intended for other PRs):

Full wallet support for SegWit (which would include automatically adding witness scripts to the wallet during automatic keypool topup, SegWit change outputs, …) [see #11403]
Splitting base58.cpp and tests/base58_tests.cpp up into base58-specific code, and “address encoding”-code [see #11372]
Error locating in UI for BIP173 addresses.

sipa force-pushed on Aug 26, 2017

luke-jr commented at 10:37 pm on August 26, 2017: member

Would prefer to have simply sending-to (maybe validating/analyzing too?) as a separate PR, before wallet upgrades.

I’m not sure when it would make sense to convert between P2SH and BIP173…

sipa commented at 10:38 pm on August 26, 2017: member

@luke-jr I agree, but I consider addwitnessaddress an RPC to aid with testing, not full support.

I’m not sure when it would make sense to convert between P2SH and BIP173…

I think you’re right. I’ll remove that.

gmaxwell commented at 10:45 pm on August 26, 2017: contributor

addwitnessaddress is very much not actual support, it’s a test shim.

sipa force-pushed on Aug 26, 2017

luke-jr commented at 10:58 pm on August 26, 2017: member

But it modifies the wallet, no? Seems useful to review independently from the rest. Especially since it has the additional considerations of what happens if you try to use it and then downgrade to an older version…

sipa commented at 11:00 pm on August 26, 2017: member

@luke-jr Consider that we’ve since 0.13.1 had support for receiving and spending native witness outputs in the wallet (without that, testing the consensus logic for it would have been much harder), just no way to encode such outputs as strings. So I think the encoding is somewhat orthogonal.

It does modify the wallet, but I’m not sure it’s worth trying to separate the logic. We only have one data type (CTxDestination) to encode things we can receive on or send to. Having the ability to send to something but not being able to encode it ourselves would require separating the two, and I expect would be more work then just implementing it all.

Wallet backward compatibility is only affected when you use an import or addwitnessaddress with p2sh=false (the default is `true).

sipa force-pushed on Aug 27, 2017

sipa commented at 7:49 am on August 27, 2017: member

Added support in Python framework, and some integrated some functional tests into the segwit.py test.

FelixWeis referenced this in commit 65ac986a41 on Aug 27, 2017

in src/bech32.cpp:159 in 6177ca1446 outdated

120+    }
121+    return ret;
122+}
123+
124+/** Decode a Bech32 string. */
125+std::pair<std::string, data> Decode(const std::string& str) {

promag commented at 1:12 pm on August 27, 2017:

IMO bool Decode(const std::string& str, const std::string& hrp, data& d) feels better, and this way below it can early return.

sipa commented at 5:07 pm on August 27, 2017:

It’s not often used in the Bitcoin Core codebase, but using pairs for multiple returned values is very typical in C++ (see the return type of std::map::insert for example). In C++03 it was a bit verbose to use, but with C++11’s auto types and std::tie for assigning to multiple variables, it’s pretty convenient. I’d rather stick with the current approach.

in src/base58.cpp:289 in ee10c3985e outdated

284+                    memcpy(id.begin(), data.data(), 32);
285+                    return id;
286+                }
287+                return CNoDestination();
288+            }
289+            if (version > 16 || data.size() < 2 || data.size() > 40) return CNoDestination();

promag commented at 1:16 pm on August 27, 2017:

Return in new line?

sipa commented at 5:12 pm on August 27, 2017:

done

in src/base58.cpp:16 in ab8d5093fe outdated

12 #include <assert.h>
13 #include <stdint.h>
14 #include <string.h>
15 #include <vector>
16 #include <string>
17+#include <algorithm>

promag commented at 1:17 pm on August 27, 2017:

Sort.

sipa commented at 5:12 pm on August 27, 2017:

Done.

in src/bech32.h:23 in ab8d5093fe outdated

18+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19+ * THE SOFTWARE.
20+ */
21+
22+#include <stdint.h>
23+#include <vector>

promag commented at 1:19 pm on August 27, 2017:

Sort.

sipa commented at 5:13 pm on August 27, 2017:

Done.

in src/base58.cpp:289 in ee10c3985e outdated

266 
267 CTxDestination DecodeDestination(const std::string& str, const CChainParams& params)
268 {
269     std::vector<unsigned char> data;
270     uint160 hash;
271+    auto bech = bech32::Decode(str);

promag commented at 1:22 pm on August 27, 2017:

Must come first? If not which is the cheapest?

sipa commented at 5:12 pm on August 27, 2017:

bech32 is far cheaper (no basis conversion, no SHA256).

in src/base58.cpp:289 in ab8d5093fe outdated

310-    else if (vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS))
311-        return CScriptID(id);
312-    else
313+    std::vector<unsigned char> data;
314+    uint160 hash;
315+    auto bech = bech32::Decode(str);

promag commented at 1:23 pm on August 27, 2017:

Must come first? If not which is the cheapest?

sipa commented at 5:14 pm on August 27, 2017:

I haven’t benchmarked, but Bech32 should be far cheaper (no SHA256, no basis conversion). There should never be overlap between the addresses, so the order shouldn’t matter.

promag commented at 10:29 am on August 28, 2017:

Right, in terms of functionality the order doesn’t matter. But at the moment most addresses (don’t know numbers) are base58 so for now move bech32::Decode() after DecodeBase58Check()?

It would be cool to move this out of base58.cpp, follow up maybe?

sipa commented at 6:03 pm on August 28, 2017:

Right, in terms of functionality the order doesn’t matter. But at the moment most addresses (don’t know numbers) are base58 so for now move bech32::Decode() after DecodeBase58Check()?

I was using a fail-fast approach, making the thing that most quickly fails first. You’re right that as long as there are hardly any bech32 addresses, putting Base58 would be overall faster. But none of this is performance critical anyway…

promag commented at 1:25 pm on August 27, 2017: member

Fast code review. Move 4bc71a6 to #11117??

sipa force-pushed on Aug 27, 2017

in src/chainparams.cpp:338 in 128c217052 outdated

333@@ -330,6 +334,8 @@ class CRegTestParams : public CChainParams {
334         base58Prefixes[SECRET_KEY] =     std::vector<unsigned char>(1,239);
335         base58Prefixes[EXT_PUBLIC_KEY] = {0x04, 0x35, 0x87, 0xCF};
336         base58Prefixes[EXT_SECRET_KEY] = {0x04, 0x35, 0x83, 0x94};
337+
338+        bech32_hrp = "rt";

sipa commented at 8:11 pm on August 27, 2017:

I arbitrarily chose a bech32 prefix for regtest. Feel free to bikeshed (it doesn’t even need to be just 2 characters).

sipa force-pushed on Aug 28, 2017

laanwj added the label Wallet on Aug 28, 2017

in src/bech32.cpp:113 in bfada9e998 outdated

108+std::pair<std::string, data> Decode(const std::string& str) {
109+    bool lower = false, upper = false;
110+    bool ok = true;
111+    for (size_t i = 0; ok && i < str.size(); ++i) {
112+        unsigned char c = str[i];
113+        if (c < 33 || c > 126) ok = false;

promag commented at 10:30 am on August 28, 2017:

Early return?

sipa commented at 0:57 am on August 29, 2017:

Done.

in src/bech32.cpp:117 in bfada9e998 outdated

112+        unsigned char c = str[i];
113+        if (c < 33 || c > 126) ok = false;
114+        if (c >= 'a' && c <= 'z') lower = true;
115+        if (c >= 'A' && c <= 'Z') upper = true;
116+    }
117+    if (lower && upper) ok = false;

promag commented at 10:31 am on August 28, 2017:

Early return?

sipa commented at 0:57 am on August 29, 2017:

Done.

in src/bech32.cpp:124 in bfada9e998 outdated

119+    if (ok && str.size() <= 90 && pos != str.npos && pos >= 1 && pos + 7 <= str.size()) {
120+        data values;
121+        values.resize(str.size() - 1 - pos);
122+        for (size_t i = 0; i < str.size() - 1 - pos; ++i) {
123+            unsigned char c = str[i + pos + 1];
124+            if (CHARSET_REV[c] == -1) ok = false;

promag commented at 10:32 am on August 28, 2017:

Early return?

sipa commented at 0:57 am on August 29, 2017:

Done.

sipa force-pushed on Aug 29, 2017

in src/bech32.h:16 in ab8942c405 outdated

0@@ -0,0 +1,18 @@
1+// Copyright (c) 2017 Pieter Wuille
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 <stdint.h>
6+#include <string>
7+#include <vector>
8+
9+namespace bech32

jimpo commented at 11:28 pm on September 1, 2017:

Could you leave a comment referring the reader to more complete documentation on bech32 (either the BIP or reference repo)? Also would be nice to document somewhere in the codebase what hrp stands for.

I’m thinking something as simple as: “Bech32 is a data encoding used for some newer address formats. Output consists of a human-readable part (HRP) followed by a separator, then the data itself with a checksum. For more details, see documentation of BIP 173.”

sipa commented at 8:09 pm on September 3, 2017:

Done.

sipa commented at 8:42 pm on September 9, 2017:

Done again - I somehow lost this change.

achow101 commented at 3:43 pm on September 15, 2017:

I don’t see the comment… I think you lost it again.

sipa commented at 7:39 pm on September 15, 2017:

It’s there, just a bit higher up in the file.

in src/test/base58_tests.cpp:275 in fe4e51c274 outdated

274+
275+            CTxDestination dest2 = DecodeDestination(address);
276+            BOOST_CHECK_MESSAGE(dest == dest2, strprintf("mismatch in encoding: %s", strTest));
277+
278+            for (char& c : address) {
279+                if (c >= 'a' && c <= 'z') {

jimpo commented at 6:55 pm on September 3, 2017:

nit: Maybe use toupper here to be more descriptive and succinct.

sipa commented at 8:09 pm on September 3, 2017:

Unfortunately, toupper is locale-dependent, so it can’t be used for consistent behaviour.

jimpo commented at 8:25 pm on September 3, 2017:

std::toupper(c, std::locale::classic())?

sipa commented at 8:29 pm on September 3, 2017:

Seems overkill.

sipa force-pushed on Sep 3, 2017

sipa added the label Needs backport on Sep 5, 2017

sipa added the label Needs release notes on Sep 5, 2017

sipa added this to the milestone 0.15.1 on Sep 5, 2017

sipa force-pushed on Sep 5, 2017

instagibbs commented at 11:22 pm on September 5, 2017: member

Include a test with v1+ address?

sipa force-pushed on Sep 6, 2017

sipa commented at 0:36 am on September 6, 2017: member

@instagibbs Done

sipa force-pushed on Sep 6, 2017

instagibbs commented at 9:05 pm on September 6, 2017: member

super surprising to me that regtest has a different human readable part: bcrt1.

Legacy addresses shared prefix between testnet and regtest. Perhaps note this somewhere in the code and/or in this PR description.

laanwj commented at 9:57 pm on September 6, 2017: member

super surprising to me that regtest has a different human readable part: bcrt1.

That was surprising to me too, but I found it a pleasant surprise. It’s not like prefixes are a very rare resource, this decreases ambiguity, and fits in with regtest getting its own RPC port in #10825.

instagibbs commented at 10:06 pm on September 6, 2017: member

Definitely not arguing against it!

On Wed, Sep 6, 2017 at 5:58 PM, Wladimir J. van der Laan < notifications@github.com> wrote:

super surprising to me that regtest has a different human readable part: bcrt1.

That was surprising to me too, but I found it a pleasant surprise. It’s not like prefixes are a very rare resource, this decreases ambiguity, and fits in with regtest getting its own RPC port in #10825 https://github.com/bitcoin/bitcoin/pull/10825.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/11167#issuecomment-327623706, or mute the thread https://github.com/notifications/unsubscribe-auth/AFgC0yE1TXYCzEvLBbEeCPST4eRCXuW4ks5sfxWYgaJpZM4PDot9 .

in src/wallet/rpcwallet.cpp:1269 in ccc6a163b9 outdated

1265         throw JSONRPCError(RPC_WALLET_ERROR, "Public key or redeemscript not known to wallet, or the key is uncompressed");
1266     }
1267 
1268-    pwallet->SetAddressBook(w.result, "", "receive");
1269+    CScript redeemscript = GetScriptForDestination(w.result);
1270+    if (!w.already_witness) pwallet->AddCScript(redeemscript);

instagibbs commented at 11:29 pm on September 6, 2017:

move this inside of the else statement below

sipa commented at 0:43 am on September 7, 2017:

Done.

in src/wallet/rpcwallet.cpp:1268 in ccc6a163b9 outdated

1264     if (!ret) {
1265         throw JSONRPCError(RPC_WALLET_ERROR, "Public key or redeemscript not known to wallet, or the key is uncompressed");
1266     }
1267 
1268-    pwallet->SetAddressBook(w.result, "", "receive");
1269+    CScript redeemscript = GetScriptForDestination(w.result);

instagibbs commented at 11:31 pm on September 6, 2017:

this is more aptly described as a witness program script, since w.result will always be a witness program.

sipa commented at 0:43 am on September 7, 2017:

Fixed.

sipa force-pushed on Sep 6, 2017

sipa force-pushed on Sep 7, 2017

theuni commented at 6:30 pm on September 7, 2017: member

quick nit reminder, TX_WITNESS_UNKNOWN isn’t explicitly handled in CombineSignatures/SignStep

in src/base58.cpp:249 in 2719a42b3b outdated

314+    uint160 hash;
315+    if (DecodeBase58Check(str, data)) {
316+        // Base58 decoding
317+        const std::vector<unsigned char>& pubkey_prefix = params.Base58Prefix(CChainParams::PUBKEY_ADDRESS);
318+        if (data.size() == 20 + pubkey_prefix.size() && std::equal(pubkey_prefix.begin(), pubkey_prefix.end(), data.begin())) {
319+            memcpy(hash.begin(), &data[1], 20);

theuni commented at 1:26 am on September 9, 2017:

Why is this not &data[pubkey_prefix.size()] (or data.data() + pubkey_prefix.size()) ?

sipa commented at 9:10 am on September 9, 2017:

Nice catch, fixed!

theuni commented at 1:42 am on September 9, 2017: member

utACK other than those two nits, and excluding the bech32 implementation itself. It looks sane, but I’d like to audit more thoroughly before ACKing.

sipa force-pushed on Sep 9, 2017

in src/bech32.cpp:134 in 25b31c16ca outdated

129+    }
130+    std::string hrp;
131+    for (size_t i = 0; i < pos; ++i) {
132+        hrp += LowerCase(str[i]);
133+    }
134+    if (!VerifyChecksum(hrp, values)) return std::make_pair(std::string(), data());

meshcollider commented at 10:23 am on September 9, 2017:

{ } just to be consistent with the previous one-line if statements in this function?

sipa commented at 8:43 pm on September 9, 2017:

Fixed.

in src/bech32.cpp:156 in 25b31c16ca outdated

100+    ret.reserve(ret.size() + combined.size());
101+    for (size_t i = 0; i < combined.size(); ++i) {
102+        ret += CHARSET[combined[i]];
103+    }
104+    return ret;
105+}

meshcollider commented at 10:23 am on September 9, 2017:

Tiny nit, end-of-namespace comment? Same for other namespaces in this file and in bech32.h

sipa commented at 8:43 pm on September 9, 2017:

Fixed.

in src/wallet/rpcwallet.cpp:1236 in d46216bc25 outdated

1233             "\nAdd a witness address for a script (with pubkey or redeemscript known).\n"
1234             "It returns the witness script.\n"
1235 
1236             "\nArguments:\n"
1237             "1. \"address\"       (string, required) An address known to the wallet\n"
1238+            "2. p2sh            (bool, optional) Embed inside P2SH (default: true)\n"

meshcollider commented at 10:42 am on September 9, 2017:

Move default=true into the brackets after optional to be consistent with other RPCs

sipa commented at 8:43 pm on September 9, 2017:

Fixed.

in src/wallet/rpcwallet.cpp:1239 in d46216bc25 outdated

1237             "1. \"address\"       (string, required) An address known to the wallet\n"
1238+            "2. p2sh            (bool, optional) Embed inside P2SH (default: true)\n"
1239 
1240             "\nResult:\n"
1241-            "\"witnessaddress\",  (string) The value of the new address (P2SH of witness script).\n"
1242+            "\"witnessaddress\",  (string) The value of the new address (P2SH or BIP173).\n"

meshcollider commented at 10:49 am on September 9, 2017:

Why BIP173 not Bech32?

sipa commented at 8:17 pm on September 9, 2017:

Bech32 is the generic encoding format (and should be contrasted with Base58Check), BIP173 specifies a specific way of encoding SegWit addresses using Bech32 (like P2SH/BIP13 specifies a specific way of encoding BIP16 addresses using Base58Check).

in src/script/standard.cpp:208 in 0e04862cac outdated

202@@ -198,6 +203,23 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
203     {
204         addressRet = CScriptID(uint160(vSolutions[0]));
205         return true;
206+    } else if (whichType == TX_WITNESS_V0_KEYHASH) {
207+        WitnessV0KeyHash hash;
208+        memcpy(hash.begin(), &vSolutions[0][0], 20);

meshcollider commented at 10:56 am on September 9, 2017:

vSolutions[0].data()? Same for TX_WITNESS_V0_SCRIPTHASH case below

sipa commented at 8:43 pm on September 9, 2017:

Fixed.

meshcollider commented at 11:10 am on September 9, 2017: contributor

utACK https://github.com/bitcoin/bitcoin/pull/11167/commits/efceb6ec12321d698203b26be1a4cdeed49514b7 … https://github.com/bitcoin/bitcoin/pull/11167/commits/8a42338bb968c213e3837e5b5c008355ce05cc23

I’m not really familiar with the technicalities of how Bech32 encoding and decoding work, but the code is consistent with what’s in BIP 173. Didn’t review the tests very thoroughly but they look ok

sipa force-pushed on Sep 9, 2017

sipa commented at 8:44 pm on September 9, 2017: member

I think I’ve addressed all comments. I’ve also added a few extra comments in some places.

quick nit reminder, TX_WITNESS_UNKNOWN isn’t explicitly handled in CombineSignatures/SignStep

Fixed.

sipa force-pushed on Sep 10, 2017

sipa commented at 6:50 am on September 10, 2017: member

Rebased on top of #11297 to hopefully address the Travis issue.

NicolasDorier commented at 7:52 am on September 10, 2017: contributor

should fix #10924 I made tests on https://github.com/NicolasDorier/bitcoin/commits/importaddresssegwit can you include them @sipa ? (this one https://github.com/NicolasDorier/bitcoin/commit/a17a74708ddfc8628d5943e0835ff45eb54e06b5)

sipa commented at 7:39 pm on September 10, 2017: member

@NicolasDorier Cherry-picked with some refactoring and merging into segwit.py.

sipa force-pushed on Sep 10, 2017

NicolasDorier commented at 4:10 am on September 11, 2017: contributor

seems good for me.

Will try later this PR against NTumbleBit. I am using P2SH-P2WSH right now because core was not supporting otherwise. I should be able to move to pure P2WSH thanks to this PR.

ecdsa commented at 9:08 am on September 12, 2017: none

FYI, this BIP is now supported in Electrum, and will be part of the next release

in src/base58.cpp:258 in 770d0ff3c5 outdated

302-    return IsValid(Params());
303-}
304+    std::string operator()(const WitnessUnknown& id) const
305+    {
306+        if (id.version < 1 || id.version > 16 || id.length < 2 || id.length > 40) {
307+            return "";

promag commented at 10:41 pm on September 13, 2017:

Here and in other places where an empty string is returned prefer:

0return {};

See https://stackoverflow.com/a/26588207.

sipa commented at 6:36 am on September 14, 2017:

Fixed.

danra commented at 6:28 pm on September 28, 2017:

@sipa The change in operator() for CNoDestination should be rebased onto 1e46ebdf8618e585568ffc1b093c79cc9be07b57

in src/base58.cpp:286 in 770d0ff3c5 outdated

348+            memcpy(hash.begin(), &data[script_prefix.size()], 20);
349+            return CScriptID(hash);
350+        }
351+    }
352+    auto bech = bech32::Decode(str);
353+    if (bech.first == params.Bech32HRP() && bech.second.size() > 0) {

promag commented at 10:54 pm on September 13, 2017:

Swap conditions?

sipa commented at 6:36 am on September 14, 2017:

Done.

in src/bech32.cpp:90 in 770d0ff3c5 outdated

85+        ret[i] = (mod >> (5 * (5 - i))) & 31;
86+    }
87+    return ret;
88+}
89+
90+}

promag commented at 10:57 pm on September 13, 2017:

0} // namespace

meshcollider commented at 4:25 am on September 14, 2017:

Ohh heh I must have misclicked and put my comment on the wrong line, I thought I pointed this one out already but it seems I just commented on the end of a function

sipa commented at 6:36 am on September 14, 2017:

Done.

sipa force-pushed on Sep 14, 2017

in test/functional/segwit.py:601 in 0036987294 outdated

596+            self.nodes[1].importaddress(scriptPubKey, "", False)
597+            rawtxfund = self.nodes[1].fundrawtransaction(transaction)['hex']
598+            rawtxfund = self.nodes[1].signrawtransaction(rawtxfund)["hex"]
599+            txid = self.nodes[1].decoderawtransaction(rawtxfund)["txid"]
600+
601+            self.nodes[1].sendrawtransaction(rawtxfund)

promag commented at 9:35 am on September 14, 2017:

0txid = self.nodes[1].sendrawtransaction(rawtxfund)

And remove above?

sipa force-pushed on Sep 14, 2017

laanwj added this to the "Blockers" column in a project

instagibbs commented at 9:24 pm on September 14, 2017: member

tACK https://github.com/bitcoin/bitcoin/pull/11167/commits/0571b9271b27ce2767e9c7034c23facb495fab65

Did a couple commits on top to get hdkey info returned with native segwit keyhashes. Something like this can be done as a quick followup, perhaps a modified version of #11089: https://github.com/instagibbs/bitcoin/commits/fullseg

in src/bech32.cpp:1 in 0571b9271b outdated

0@@ -0,0 +1,140 @@
1+// Copyright (c) 2017 Pieter Wuille

achow101 commented at 3:43 pm on September 15, 2017:

Is this the right copyright header (here and in bech32.h and elsewhere)?

sipa commented at 7:32 pm on September 15, 2017:

I think so.

achow101 commented at 4:28 pm on September 16, 2017:

Ok, just checking since most files in this repo have Copyright (c) The Bitcoin Core developers

danra commented at 6:38 pm on September 28, 2017:

Perhaps add that copyright as well?

in src/script/ismine.cpp:146 in 0571b9271b outdated

141@@ -142,6 +142,9 @@ isminetype IsMine(const CKeyStore &keystore, const CScript& scriptPubKey, bool&
142             return ISMINE_SPENDABLE;
143         break;
144     }
145+
146+    case TX_WITNESS_UNKNOWN:

achow101 commented at 3:46 pm on September 15, 2017:

I think this should be above with the TX_NULL_DATA and TX_NONSTANDARD cases.

sipa commented at 7:33 pm on September 15, 2017:

Nice catch, done.

achow101 commented at 3:51 pm on September 15, 2017: member

Concept ACK. I just did a brief pass through of things that jumped out to me. Will do more review and testing later.

in src/bech32.cpp:35 in bcd3f74b64 outdated

30+    x.insert(x.end(), y.begin(), y.end());
31+    return x;
32+}
33+
34+/** Find the polynomial with value coefficients mod the generator as 30-bit. */
35+uint32_t PolyMod(const data& values)

sdaftuar commented at 3:58 pm on September 15, 2017:

It took me a while to figure out how this function implements Bech32. Not sure if this is out of scope since you’re bringing this reference implementation in from another repo, and maybe these idioms here are common for math code, but as a newcomer to this I would have found it helpful to explain:

a) initializing chk = 1 is how we implement the prepending of a {1} to the values being encoded (which is done to prevent zero-prefixing a valid string from being valid);

b) chk is a 30-bit integer, and each 5 bits is a coefficient of a degree 5 polynomial over GF(32) (perhaps also give the particular construction of GF(32) used here);

c) the hardcoded values (0x3b6a57b2UL etc) are similar 30-bit integers, each 5 bits of which represents a coefficient of a degree 5 polynomial; the first of which represents the generator function g(x) for the BCH code, and subsequent values represent alpha * g(x), alpha^2 * g(x), etc. (where alpha is in GF(32) and is a generator of the multiplicative group). (It might be helpful to others to explicitly write out these polynomials; I did that myself to verify them.)

d) each step through the loop, we’re multiplying the existing polynomial stored in chk by x (which corresponds to right shift of 5 bits) and adding in the new value as the constant term, and using the generator polynomial (and its multiples) to replace the x^6 term that is removed by adding in polynomials of degree less than 6. (Perhaps this can be phrased better than I just did.)

sipa commented at 7:33 pm on September 15, 2017:

I’ve added a long explanation.

in src/bech32.cpp:45 in bcd3f74b64 outdated

40+        chk = (chk & 0x1ffffff) << 5 ^ values[i] ^
41+            (-((top >> 0) & 1) & 0x3b6a57b2UL) ^
42+            (-((top >> 1) & 1) & 0x26508e6dUL) ^
43+            (-((top >> 2) & 1) & 0x1ea119faUL) ^
44+            (-((top >> 3) & 1) & 0x3d4233ddUL) ^
45+            (-((top >> 4) & 1) & 0x2a1462b3UL);

sdaftuar commented at 3:58 pm on September 15, 2017:

Perhaps document the fancy bit arithmetic and negation being done here to avoid the conditional? I find the type conversions here a bit confusing – we start with a uint8_t and calculate either a 0 or 1. Then we negate it – still as a uint8_t? – and then cast to an unsigned long to do the final bit operation? It’s not clear to me that the negation and then promotion must result in 0xffffffff versus 0xff.

Oh – maybe what’s happening is that the promotion from uint8_t to uint happens with the initial bitshift or the first bitwise and, so the negation is already on a 32-bit type? That would seem more logical I guess…

sipa commented at 7:34 pm on September 15, 2017:

I’ve replaced it with much more readable conditions. I’ve verified that at least GCC 6.3 compiles it to efficient code (without any jumps).

in src/bech32.cpp:40 in bcd3f74b64 outdated

35+uint32_t PolyMod(const data& values)
36+{
37+    uint32_t chk = 1;
38+    for (size_t i = 0; i < values.size(); ++i) {
39+        uint8_t top = chk >> 25;
40+        chk = (chk & 0x1ffffff) << 5 ^ values[i] ^

sdaftuar commented at 4:01 pm on September 15, 2017:

Perhaps parens around the « operator? Order of operations between « and ^ was not obvious to me without looking this up.

sipa commented at 7:33 pm on September 15, 2017:

Done.

in src/bech32.cpp:81 in bcd3f74b64 outdated

76+/** Create a checksum. */
77+data CreateChecksum(const std::string& hrp, const data& values)
78+{
79+    data enc = Cat(ExpandHRP(hrp), values);
80+    enc.resize(enc.size() + 6);
81+    uint32_t mod = PolyMod(enc) ^ 1;

sdaftuar commented at 4:23 pm on September 15, 2017:

Might be helpful to document the ^ 1 here comes from the requirement that the reminder mod g(x) be 1 (rather than 0).

sipa commented at 7:34 pm on September 15, 2017:

Done.

sdaftuar commented at 5:14 pm on September 15, 2017: member

I’ve only code-reviewed the Bech32 implementation (bcd3f74b649da1482c242371ddebeaf78d8b7813 ) so far, which looks good. Left a few comment suggestions that would have been helpful for my review; feel free to take or leave, but I figured I would post them at least to help others who may be reviewing as well.

(Will continue to review the rest of the PR.)

sipa force-pushed on Sep 15, 2017

sipa force-pushed on Sep 16, 2017

in src/test/base58_tests.cpp:262 in d270d5eee5 outdated

260+                dest = id;
261+            } else if (exp_addrType.size() == 5 && exp_addrType.substr(0, 4) == "p2w?") {
262+                WitnessUnknown unk;
263+                memcpy(unk.program, exp_payload.data(), exp_payload.size());
264+                unk.length = exp_payload.size();
265+                unk.version = exp_addrType[4] - 'a';

gmaxwell commented at 10:26 pm on September 18, 2017:

gross. Can these tests be changed to work with whole script pubkeys rather than tweaking the addrType?

sipa commented at 10:51 pm on September 19, 2017:

gross

I agree.

Can these tests be changed to work with whole script pubkeys rather than tweaking the addrType?

Done. I’ve added an extra commit to first refactor the tests into testing scriptPubKeys.

sipa force-pushed on Sep 19, 2017

in src/test/data/base58_keys_valid.json:532 in ed22f8e0f9 outdated

474+        {
475+            "isPrivkey": false,
476+            "isTestnet": true,
477+            "tryCaseFlip": true
478+        }
479     ]

gmaxwell commented at 6:32 am on September 20, 2017:

no bcrt tests?

sipa commented at 7:27 am on September 20, 2017:

Fixed.

gmaxwell approved

gmaxwell commented at 6:38 am on September 20, 2017: contributor

utACK.

sipa force-pushed on Sep 20, 2017

sipa commented at 7:35 pm on September 20, 2017: member

Addressed @gmaxwell’s comment about bcrt tests, by adding an extra commit that introduces regtest examples to base58_tests, and then extending those in the BIP173 tests commit.

mruddy commented at 2:54 pm on September 22, 2017: contributor

Related to these changes: https://github.com/bitcoin/bips/pull/587 I think this is a bug in violation of the BIP, but I’d like feedback on my BIP change proposals, in-case I mis-interpreted something:

0segwit_addr.bech32_encode('A', [])
1'A1g7sgd8'  # violates "The lowercase form is used when determining a character's value for checksum purposes."

in src/test/base58_tests.cpp:199 in 4172ea94d7 outdated

195-        secret.SetString(exp_base58string);
196-        BOOST_CHECK_MESSAGE(!secret.IsValid(), "IsValid privkey:" + strTest);
197+        for (auto chain : { CBaseChainParams::MAIN, CBaseChainParams::TESTNET, CBaseChainParams::REGTEST }) {
198+            SelectParams(chain);
199+            destination = DecodeDestination(exp_base58string);
200+            BOOST_CHECK_MESSAGE(!IsValidDestination(destination), "IsValid pubkey in mainnet:" + strTest);

TheBlueMatt commented at 8:58 pm on September 22, 2017:

nit: it seems you changed the description text to match the old test and then also changed the test out from under it?

jonasschnelli commented at 2:52 am on September 23, 2017: contributor

Maybe cherry-pick https://github.com/jonasschnelli/bitcoin/commit/f86c0585dccd29dca63cef3e6a0d434f49abac49 to enable sending to BIP173 addresses through the GUI

danra commented at 11:20 am on September 23, 2017: contributor

@sipa (More of a BIP 173 question) - what’s the reasoning for xoring 1 to the checksum both when creating and validating it?

More specifically: polymod in bech32_create_checksum() is xored with 1 and bech32_verify_checksum() checks for bench32_polymod(...) == 1. Instead, one could avoid the xor, and check bench32_polymod(...) == 0.

in src/base58.cpp:14 in e7ae19456d outdated

14-#include <vector>
15-#include <string>
16+
17+#include <algorithm>
18 #include <boost/variant/apply_visitor.hpp>
19 #include <boost/variant/static_visitor.hpp>

danra commented at 3:39 pm on September 23, 2017:

IMHO boost headers should come before standard library headers

danra commented at 6:45 pm on September 23, 2017:

The reasoning for this is the same as why user includes should come before system includes - avoid hidden dependencies.

While boost is canonical and well-tested, it’s probably still better practice to have non-standard system headers be included before standard system headers, if only for consistency.

sipa commented at 6:48 pm on September 23, 2017:

Interesting, I hadn’t heard about this reason. I’ll take it into account in the future.

in src/base58.cpp:16 in e7ae19456d outdated

12-#include <stdint.h>
13 #include <string.h>
14-#include <vector>
15-#include <string>
16+
17+#include <algorithm>

danra commented at 3:40 pm on September 23, 2017:

<algorithm> should be in the same group as <assert.h>, <string.h>, all three are standard headers, with the difference being just that the latter two expose functionality into the global namespace.

sipa commented at 6:24 pm on September 23, 2017:

We don’t have strict rules about header include order, and I’m not convinced they would be a good trade-off (more work for reviewers, only marginally more readable code).

danra commented at 6:44 pm on September 23, 2017:

IMHO Having the headers not arranged is just a more overhead to the reader. When it’s a few headers, it’s just a bit of overhead. When it’s plenty, the overhead grows.

In any case, this specific comment is just about grouping standard header together, sorting them alphabetically, a guideline which I got the impression is mostly observed in the code.

sipa commented at 6:47 pm on September 23, 2017:

They’re already sorted alphabetically and grouped together (but with C headers separate for C++ headers), which seems perfectly reasonable to me.

in src/base58.cpp:220 in e7ae19456d outdated

212@@ -212,86 +213,51 @@ int CBase58Data::CompareTo(const CBase58Data& b58) const
213 
214 namespace
215 {
216-/** base58-encoded Bitcoin addresses.
217- * Public-key-hash-addresses have version 0 (or 111 testnet).
218- * The data vector contains RIPEMD160(SHA256(pubkey)), where pubkey is the serialized public key.
219- * Script-hash-addresses have version 5 (or 196 testnet).
220- * The data vector contains RIPEMD160(SHA256(cscript)), where cscript is the serialized redemption script.
221- */

danra commented at 3:43 pm on September 23, 2017:

Isn’t it a shame to completely drop the contents of this comment? Could be nice to have it as-is or split near the Base58 encoding parts.

sipa commented at 6:25 pm on September 23, 2017:

I’ve merged it into the implementation.

danra commented at 6:46 pm on September 23, 2017:

I thought I searched for the contents and didn’t find it, I guess I missed it. Thanks!

sipa commented at 6:49 pm on September 23, 2017:

I only did it after you commented. Thanks for pointing it out.

danra commented at 7:17 pm on September 23, 2017:

Ah, I misunderstood. Thanks!

in src/base58.cpp:377 in e7ae19456d outdated

314 
315 bool IsValidDestinationString(const std::string& str)
316 {
317-    return CBitcoinAddress(str).IsValid();
318+    return IsValidDestination(DecodeDestination(str, Params()));
319 }

danra commented at 3:56 pm on September 23, 2017:

Reuse previous overload of IsValidDestinationString()

sipa commented at 6:27 pm on September 23, 2017:

Done.

in src/base58.cpp:249 in e7ae19456d outdated

314+    uint160 hash;
315+    if (DecodeBase58Check(str, data)) {
316+        // Base58Check decoding
317+        const std::vector<unsigned char>& pubkey_prefix = params.Base58Prefix(CChainParams::PUBKEY_ADDRESS);
318+        if (data.size() == 20 + pubkey_prefix.size() && std::equal(pubkey_prefix.begin(), pubkey_prefix.end(), data.begin())) {
319+            memcpy(hash.begin(), &data[pubkey_prefix.size()], 20);

danra commented at 4:36 pm on September 23, 2017:

Use std::copy[_n] instead of memcpy
Suggest DRYing constant lengths 20, 32. Either defining them here or using existing definition from another header.

sipa commented at 6:25 pm on September 23, 2017:

Both done, in multiple places.

danra changes_requested

sipa force-pushed on Sep 23, 2017

sipa commented at 6:31 pm on September 23, 2017: member

@jonasschnelli Cool, cherry-picked your commit. @danra The xor 1 to verify the checksum is actually explained in this PR:

0    // PolyMod computes what value to xor into the final values to make the checksum 0. However,
1    // if we required that the checksum was 0, it would be the case that appending a 0 to a valid
2    // list of values would result in a new valid list. For that reason, Bech32 requires the
3    // resulting checksum to be 1 instead.

I’ll update the BIP to explain it there as well.

sipa force-pushed on Sep 23, 2017

Implement {Encode,Decode}Destination without CBitcoinAddress 1e46ebdf86

sipa force-pushed on Sep 23, 2017

sipa commented at 10:10 pm on September 23, 2017: member

Rebased on top of #11116, and fixed a bug that it exposed (Solver would treat non-length 20/32 v0 witness outputs as WitnessUnknown rather than failing). Thanks, @jimpo!

gmaxwell approved

gmaxwell commented at 6:14 am on September 26, 2017: contributor

ACK

in src/qt/bitcoinaddressvalidator.cpp:70 in 7e6a930c5d outdated

66@@ -67,7 +67,7 @@ QValidator::State BitcoinAddressEntryValidator::validate(QString &input, int &po
67         if (((ch >= '0' && ch<='9') ||
68             (ch >= 'a' && ch<='z') ||
69             (ch >= 'A' && ch<='Z')) &&
70-            ch != 'l' && ch != 'I' && ch != '0' && ch != 'O')
71+            ch != 'I' && ch != 'O')

instagibbs commented at 2:19 pm on September 26, 2017:

nit: I think this deserves an in-line comment.

sipa commented at 6:00 pm on September 26, 2017:

Fixed.

in src/base58.cpp:294 in 615a972aad outdated

284@@ -259,6 +285,34 @@ CTxDestination DecodeDestination(const std::string& str, const CChainParams& par
285             return CScriptID(hash);
286         }
287     }
288+    auto bech = bech32::Decode(str);
289+    if (bech.second.size() > 0 && bech.first == params.Bech32HRP()) {
290+        // Bech32 decoding
291+        int version = bech.second[0];
292+        if (ConvertBits<5, 8, false>(data, bech.second.begin() + 1, bech.second.end())) {

instagibbs commented at 2:46 pm on September 26, 2017:

Not obvious to me here why it’s bech.second.begin() + 1.

sipa commented at 6:01 pm on September 26, 2017:

Added a comment.

in src/script/standard.cpp:185 in 615a972aad outdated

181@@ -175,6 +182,7 @@ bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, std::vector<std::v
182 
183 bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
184 {
185+    valtype witness_program;

instagibbs commented at 2:54 pm on September 26, 2017:

unused?

sipa commented at 6:01 pm on September 26, 2017:

Removed.

instagibbs commented at 3:04 pm on September 26, 2017: member

re-ACK, with some small nits

sipa force-pushed on Sep 26, 2017

in src/base58.cpp:228 in 86d42998b8 outdated

254-};
255-
256-} // namespace
257+    std::string operator()(const CKeyID& id) const
258+    {
259+        std::vector<unsigned char> data = m_params.Base58Prefix(CChainParams::PUBKEY_ADDRESS);

promag commented at 1:41 pm on September 27, 2017:

Call data.reserve(prefix.size() + id.size()) before filling data to avoid reallocation?

Otherwise use copy constructor? Same below.

sipa commented at 6:26 pm on September 27, 2017:

The copy constructor is used here when initializing the data variable.

in src/bech32.cpp:130 in 86d42998b8 outdated

124+}
125+
126+/** Create a checksum. */
127+data CreateChecksum(const std::string& hrp, const data& values)
128+{
129+    data enc = Cat(ExpandHRP(hrp), values);

promag commented at 2:03 pm on September 27, 2017:

Avoid copy?

sipa commented at 5:46 pm on September 27, 2017:

No copy occurs here.

Note that Cat’s first argument takes a vector by value, not by const reference. This means that the value returned by ExpandHRP (which is a temporary) will use a move constructor to become Cat’s first argument (instead of just passing a reference). However, no copy occurs, and Cat is then free to modify that variable.

Cat then extends that vector, and returns it (probably using copy elision, but even when not, using moving) to the enc variable here.

in src/bech32.cpp:131 in 86d42998b8 outdated

125+
126+/** Create a checksum. */
127+data CreateChecksum(const std::string& hrp, const data& values)
128+{
129+    data enc = Cat(ExpandHRP(hrp), values);
130+    enc.resize(enc.size() + 6); // Append 6 zeroes

promag commented at 2:03 pm on September 27, 2017:

I believe this is the 3rd possible reallocation on the same vector:

1st L106: ret.resize()
2nd L30: x.insert(...)
3rd L130: enc.resize(enc.size() + 6)

Suggestion, add 2nd argument capacity = 0 to ExpandHRP?

sipa commented at 10:27 pm on September 28, 2017:

Fixed. I’ve added a reserve call in ExpandHRP (which reserves 90 + hrp.size(), the maximum valid expanded size the checksum is computed over).

in src/test/base58_tests.cpp:99 in 86d42998b8 outdated

 98-        if (isTestnet)
 99+        bool isTestnet = find_value(metadata, "chain").get_str() == "testnet";
100+        bool regtest = find_value(metadata, "chain").get_str() == "regtest";
101+        bool try_case_flip = find_value(metadata, "tryCaseFlip").isNull() ? false : find_value(metadata, "tryCaseFlip").get_bool();
102+        if (regtest) {
103+            SelectParams(CBaseChainParams::REGTEST);

laanwj commented at 11:05 am on September 28, 2017:

I wonder why we don’t use the SelectParams by string here.

sipa commented at 10:28 pm on September 28, 2017:

Good idea, fixed.

in src/test/base58_tests.cpp:164 in 86d42998b8 outdated

159@@ -188,50 +160,37 @@ BOOST_AUTO_TEST_CASE(base58_keys_valid_gen)
160         std::vector<unsigned char> exp_payload = ParseHex(test[1].get_str());
161         const UniValue &metadata = test[2].get_obj();
162         bool isPrivkey = find_value(metadata, "isPrivkey").get_bool();
163-        bool isTestnet = find_value(metadata, "isTestnet").get_bool();
164-        if (isTestnet)
165+        bool isTestnet = find_value(metadata, "chain").get_str() == "testnet";
166+        bool regtest = find_value(metadata, "chain").get_str() == "regtest";

laanwj commented at 11:06 am on September 28, 2017:

Same here, SelectParams(find_value(metadata, "chain").get_str()) would do?

sipa commented at 10:28 pm on September 28, 2017:

Fixed.

in src/bech32.cpp:16 in 86d42998b8 outdated

11+
12+/** The Bech32 character set for encoding. */
13+const char* CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
14+
15+/** The Bech32 character set for decoding. */
16+const int8_t CHARSET_REV[128] = {

laanwj commented at 11:31 am on September 28, 2017:

As this is indexed using a uint8_t I’d feel slightly more at ease if we extend this array to size 256, or add an explicit check against 128 in the loop where it is referenced. I know the check at the beginning of Decode() makes it impossible to hit this, but it seems something that is easily forgotten with a future code change.

sipa commented at 10:28 pm on September 28, 2017:

Fixed.

laanwj commented at 11:46 am on September 28, 2017: member

utACK +/- nits

in src/base58.cpp:287 in 86d42998b8 outdated

349+        const std::vector<unsigned char>& script_prefix = params.Base58Prefix(CChainParams::SCRIPT_ADDRESS);
350+        if (data.size() == hash.size() + script_prefix.size() && std::equal(script_prefix.begin(), script_prefix.end(), data.begin())) {
351+            std::copy(data.begin() + script_prefix.size(), data.end(), hash.begin());
352+            return CScriptID(hash);
353+        }
354+    }

danra commented at 6:34 pm on September 28, 2017:

Would be nice to extract the common functionality here (validating some prefix+size+extracting hash) into a function

theuni commented at 7:17 pm on September 28, 2017:

data.clear()

sipa commented at 11:34 pm on September 28, 2017:

Fixed.

sipa commented at 11:35 pm on September 28, 2017:

I prefer to do that later.

danra commented at 8:22 am on September 29, 2017:

@theuni Good catch! @sipa Suggest splitting DecodeDestination to two functions, one for decoding Base58 and one for Bech32. This would have trivially eliminated the bug above. Another example of something which would be fixed is hash being used only for Base58 decoding but being visible for the entirety of the Bech32 decoding as well.

theuni commented at 10:52 pm on September 29, 2017:

+1 to this in some future follow-up.

in src/bech32.cpp:13 in 86d42998b8 outdated

 8+{
 9+
10+typedef std::vector<uint8_t> data;
11+
12+/** The Bech32 character set for encoding. */
13+const char* CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";

danra commented at 6:39 pm on September 28, 2017:

Suggest adding a comment here explaining reasoning for the CHARSET (similar to how it’s explained in BIP 173). Also, is there an implementation available showing how the visual similarity was minimized, or was this minimization just done manually? In case of the former, suggest adding a link to that here or in the BIP (or in both)

sipa commented at 10:37 pm on September 28, 2017:

I think the implementation should focus on explaining why it is a correct implementation of the BIP. It doesn’t need to include things the BIP already explains well - that’s just gratuitously splitting the knowledge over multiple places.

Yes, the code for that optimization is in my repository, but it’s very ad-hoc and not really intended for publishing.

danra commented at 10:44 pm on September 28, 2017:

Make sense regarding the information location. Where in your repo can one find the optimization code you used?

sipa commented at 11:35 pm on September 28, 2017:

https://github.com/sipa/ezbase32/blob/master/dist32.cpp

in src/bech32.cpp:25 in 86d42998b8 outdated

20+    15, -1, 10, 17, 21, 20, 26, 30,  7,  5, -1, -1, -1, -1, -1, -1,
21+    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
22+     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1,
23+    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
24+     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1
25+};

danra commented at 6:39 pm on September 28, 2017:

This can probably be directly derived from CHARSET at compilation time using constexpr functions and making CHARSET and this constexpr as well, making it more robust. I can try implementing it, if you agree it’s of interest.

sipa commented at 10:39 pm on September 28, 2017:

Sounds good, but seems out of scope for this PR.

in src/bech32.cpp:55 in 86d42998b8 outdated

50+
51+    // Note that the coefficients are elements of GF(32), here represented as decimal numbers
52+    // between {}. In this finite field, addition is just XOR of the corresponding numbers. For
53+    // example, {27} + {13} = {27 ^ 13} = {22}. Multiplication is more complicated, and requires
54+    // treating the bits of values themselves as coefficients of a polynomial over a smaller field,
55+    // GF(2), and multiplying those polynomials mod a^5 + a^3 + 1. For example, {5} * {26} =

danra commented at 6:50 pm on September 28, 2017:

I suggest rephrasing, IIRC multiplication requires some irreducible polynomial, a^5 + a^3 + 1 is just one possibility which was specifically chosen here. Current phrasing implies multiplication “requires” this specific polynomial.

sipa commented at 10:43 pm on September 28, 2017:

Yes and no.

There is only one field of size 32 up to isomorphism. However, the multiplication of GF(32) elements when represented as bits absolutely depends on the choice of the polynomial - and this is the one used in Bech32. It just so happens that you could do a mapping of the input values to the respective elements in an isomorphic representation (which uses another polynomial), do the multiplication, and map things back.

I think the current explanation is sufficiently accurate.

danra commented at 10:49 pm on September 28, 2017:

However, the multiplication of GF(32) elements when represented as bits absolutely depends on the choice of the polynomial - and this is the one used in Bech32

Yes, that’s what I meant - emphasizing the fact that this polynomial was chosen, not that it is the one required for multiplication. I think this point could be better made. Though, I agree that even without this nit, the documentation is great :)

sipa commented at 11:47 pm on September 28, 2017:

Well I think it is the one required for multiplication.

The specific representation of GF(32) we use, is defined as bits representing polynomials over GF(2) modulo exactly the polynomial a^5 + a^3 + 1 and no other.

Yes, other representations using other polynomials exist, and given that all size 32 fields are isomorphic, it’s guaranteed that a mapping exists between them which is consistent with addition and multiplication. But we’re not using any of those :)

EDIT: Or do you mean that I should point out that Bech32 could have used any of the other irreducible polynomials? That would be correct, but again, that’d be material for the BIP, not here.

danra commented at 8:12 am on September 29, 2017:

Or do you mean that I should point out that Bech32 could have used any of the other irreducible polynomials?

Yes. I just suggest a more precise phrasing. e.g., instead of

Multiplication is more complicated, and requires […] multiplying those polynomials mod a^5 + a^3 + 1

write

Multiplication is more complicated, and requires […] multiplying those polynomials mod an irreducible polynomial, chosen as a^5 + a^3 + 1 in Bech32."

in src/bech32.cpp:65 in 86d42998b8 outdated

60+    // polynomial constructed from just the values of v that were processed so far, mod g(x). In
61+    // the above example, `c` initially corresponds to 1 mod (x), and after processing 2 inputs of
62+    // v, it corresponds to x^2 + v0*x + v1 mod g(x). As 1 mod g(x) = 1, that is the starting value
63+    // for `c`.
64+    uint32_t c = 1;
65+    for (size_t i = 0; i < v.size(); ++i) {

danra commented at 7:09 pm on September 28, 2017:

Use a range-for loop, i isn’t used except for accessing element (and in comments)

sipa commented at 11:36 pm on September 28, 2017:

This wasn’t done originally, as the reference code is C++03, but by now it’s diverged enough that I’ll just bite the bullet and make it C++11 inside Core.

in src/bech32.cpp:99 in 86d42998b8 outdated

94+}
95+
96+/** Convert to lower case. */
97+inline unsigned char LowerCase(unsigned char c)
98+{
99+    return (c >= 'A' && c <= 'Z') ? (c - 'A') + 'a' : c;

danra commented at 7:11 pm on September 28, 2017:

Here and later, 'A' <= c && c <= 'Z' is better style (c is ‘between’ the values. Easier to read, harder to get wrong when used consistently)

sipa commented at 10:52 pm on September 28, 2017:

I prefer variables up front.

in src/bech32.cpp:123 in 86d42998b8 outdated

117+bool VerifyChecksum(const std::string& hrp, const data& values)
118+{
119+    // PolyMod computes what value to xor into the final values to make the checksum 0. However,
120+    // if we required that the checksum was 0, it would be the case that appending a 0 to a valid
121+    // list of values would result in a new valid list. For that reason, Bech32 requires the
122+    // resulting checksum to be 1 instead.

danra commented at 7:21 pm on September 28, 2017:

I might be wrong, but isn’t the problem with prepending a 0, rather than appending one?

sipa commented at 10:56 pm on September 28, 2017:

Thanks for taking the time to think through it, but no, this is about appending.

If the requirement was that the checksum was zero, it would mean that c(x) (the codeword polynomial) mod g(x) = 0, or in other words, c(x) is a multiple of g(x) (the generator). If c(x) is a multiple of g(x), then x*c(x) is a multiple of g(x) as well. The corresponding codeword for c(x)*x is the characters of the original with a 0 appended.

There is also a measure taken to avoid being able to prepend zeroes, namely the fact that for the codeword [a,b,c,d] we use x^4 + a*x^3 + b*x^2 + c*x + d, rather than a*x^3 + b*x^2 + c*x + d (see the comment above, about initializing the c variable to 1).

in src/bech32.cpp:134 in 86d42998b8 outdated

128+{
129+    data enc = Cat(ExpandHRP(hrp), values);
130+    enc.resize(enc.size() + 6); // Append 6 zeroes
131+    uint32_t mod = PolyMod(enc) ^ 1; // Determine what to XOR into those 6 zeroes.
132+    data ret;
133+    ret.resize(6);

danra commented at 7:25 pm on September 28, 2017:

Just data ret(6);

sipa commented at 11:36 pm on September 28, 2017:

Done.

in src/bech32.cpp:153 in 86d42998b8 outdated

147+std::string Encode(const std::string& hrp, const data& values) {
148+    data checksum = CreateChecksum(hrp, values);
149+    data combined = Cat(values, checksum);
150+    std::string ret = hrp + '1';
151+    ret.reserve(ret.size() + combined.size());
152+    for (size_t i = 0; i < combined.size(); ++i) {

danra commented at 7:29 pm on September 28, 2017:

Use range-for loop

sipa commented at 11:36 pm on September 28, 2017:

Done.

in src/bech32.cpp:174 in 86d42998b8 outdated

168+    size_t pos = str.rfind('1');
169+    if (str.size() > 90 || pos == str.npos || pos == 0 || pos + 7 > str.size()) {
170+        return std::make_pair(std::string(), data());
171+    }
172+    data values;
173+    values.resize(str.size() - 1 - pos);

danra commented at 7:43 pm on September 28, 2017:

Just data values(str.size() - 1 - pos);

sipa commented at 11:37 pm on September 28, 2017:

Done.

in src/bech32.cpp:164 in 86d42998b8 outdated

158+/** Decode a Bech32 string. */
159+std::pair<std::string, data> Decode(const std::string& str) {
160+    bool lower = false, upper = false;
161+    for (size_t i = 0; i < str.size(); ++i) {
162+        unsigned char c = str[i];
163+        if (c < 33 || c > 126) return std::make_pair(std::string(), data());

danra commented at 7:45 pm on September 28, 2017:

Here and later, just return {}

sipa commented at 11:37 pm on September 28, 2017:

Done.

in src/bech32.cpp:179 in 86d42998b8 outdated

174+    for (size_t i = 0; i < str.size() - 1 - pos; ++i) {
175+        unsigned char c = str[i + pos + 1];
176+        if (CHARSET_REV[c] == -1) {
177+            return std::make_pair(std::string(), data());
178+        }
179+        values[i] = CHARSET_REV[c];

danra commented at 7:49 pm on September 28, 2017:

Access CHARSET_REV just once, store const int8_t& val = CHARSET_REV[c]

sipa commented at 11:01 pm on September 28, 2017:

Fixed.

in src/bech32.cpp:190 in 86d42998b8 outdated

183+        hrp += LowerCase(str[i]);
184+    }
185+    if (!VerifyChecksum(hrp, values)) {
186+        return std::make_pair(std::string(), data());
187+    }
188+    return std::make_pair(hrp, data(values.begin(), values.end() - 6));

danra commented at 7:56 pm on September 28, 2017:

Here too std::make_pair can be removed in favor of {}

sipa commented at 11:37 pm on September 28, 2017:

Cool, done.

danra changes_requested

in src/test/bech32_tests.cpp:23 in 86d42998b8 outdated

18+        char c2 = s2[i];
19+        if (c2 >= 'A' && c2 <= 'Z') c2 -= ('A' - 'a');
20+        if (c1 != c2) return false;
21+    }
22+    return true;
23+}

danra commented at 8:53 pm on September 28, 2017:

Suggest using std::tolower() and standard algorithms to simplify the implementation

sipa commented at 11:03 pm on September 28, 2017:

Unfortunately, tolower is locale-dependent. I don’t feel that the complexity of avoiding that is worth it for such a trivial algorithm.

sipa commented at 11:38 pm on September 28, 2017:

there’s a version of tolower where you can specify the locale yourself, so there is no concern about the wrong one being set in the system

Locales scare me. As a reviewer, I would be far less confident that such code is correct due to it as opposed to an absolutely trivial algorithm that obvious does what it should.

theuni commented at 11:46 pm on September 28, 2017:

Agree. Seeing “locale” always means a non-trivial amount of googling is in store.

danra commented at 8:04 am on September 29, 2017:

Ok, makes sense. In that case I adding a utility function for ’english’ [is|to][lower|upper], there’s too much repetition of the same (simple) functionality.

laanwj commented at 8:07 am on September 29, 2017:

Yes, that really doesn’t help. Please don’t introduce dependence on locale. We prefer deterministic, well-defined, nation-independent string processing, even if that means writing some extra code at least we know what it’s doing then. Also this is specific to bechs32 (part of the standard) so it’s better to keep it self-contained.

danra commented at 8:16 am on September 29, 2017:

@laanwj Just to repeat an earlier comment, <locale> has overloads of these functions where you can specify the locale, so there are no hidden dependencies on the default system locale. I do agree it might require more googling, and is perhaps a bit less obvious.

in src/test/base58_tests.cpp:96 in 86d42998b8 outdated

 95         const UniValue &metadata = test[2].get_obj();
 96         bool isPrivkey = find_value(metadata, "isPrivkey").get_bool();
 97-        bool isTestnet = find_value(metadata, "isTestnet").get_bool();
 98-        if (isTestnet)
 99+        bool isTestnet = find_value(metadata, "chain").get_str() == "testnet";
100+        bool regtest = find_value(metadata, "chain").get_str() == "regtest";

danra commented at 8:59 pm on September 28, 2017:

isRegtest for consistency

sipa commented at 11:03 pm on September 28, 2017:

Already removed in response to @laanwj’s comment above.

in src/base58.cpp:252 in 86d42998b8 outdated

292+    std::string operator()(const WitnessV0ScriptHash& id) const
293+    {
294+        std::vector<unsigned char> data = {0};
295+        ConvertBits<8, 5, true>(data, id.begin(), id.end());
296+        return bech32::Encode(m_params.Bech32HRP(), data);
297+    }

danra commented at 9:09 pm on September 28, 2017:

WitnessV0KeyHash and WitnessV0ScriptHash overloads have identical implementation, refactor it to a private template (templated on id type) function and call it from these two?

sipa commented at 11:05 pm on September 28, 2017:

I think being explicit here is clearer. I also don’t expect that this correspondence will be maintained in future witness versions.

in src/base58.cpp:309 in 86d42998b8 outdated

366+                }
367+                WitnessV0ScriptHash scriptid;
368+                if (data.size() == scriptid.size()) {
369+                    std::copy(data.begin(), data.end(), scriptid.begin());
370+                    return scriptid;
371+                }

danra commented at 9:13 pm on September 28, 2017:

Braces around each of keyid and scriptid segments would reduce their visibility to just the scope where they’re needed.

sipa commented at 11:38 pm on September 28, 2017:

Done.

in src/base58.cpp:312 in 86d42998b8 outdated

374+            if (version > 16 || data.size() < 2 || data.size() > 40) {
375+                return CNoDestination();
376+            }
377+            WitnessUnknown unk;
378+            unk.version = version;
379+            memcpy(unk.program, data.data(), data.size());

danra commented at 9:14 pm on September 28, 2017:

std::copy

sipa commented at 11:38 pm on September 28, 2017:

Done.

in src/base58.cpp:294 in 86d42998b8 outdated

355+    auto bech = bech32::Decode(str);
356+    if (bech.second.size() > 0 && bech.first == params.Bech32HRP()) {
357+        // Bech32 decoding
358+        int version = bech.second[0]; // The first 5 bit symbol is the witness version (0-16)
359+        // The rest of the symbols are converted witness program bytes.
360+        if (ConvertBits<5, 8, false>(data, bech.second.begin() + 1, bech.second.end())) {

danra commented at 9:16 pm on September 28, 2017:

Early return if the condition fails would reduce indentation

sipa commented at 11:10 pm on September 28, 2017:

It would, but I believe it would reduce readability: there are a number of alternatives being tried, and each has its branch to process it. If it were unindented, it would need to be reindented anyway if more cases were added.

danra commented at 8:00 am on September 29, 2017:

I agree with the principle. But, the only block I suggest dedenting is the one under the condition if (ConvertBits<5, 8, false>(data, bech.second.begin() + 1, bech.second.end())) which is after a case has been decided (Bech32 decoding), and if this condition fails, the decoding fails, so early return makes sense. It’s unlikely any additional cases would be added in case of failure here.

in src/script/standard.cpp:210 in 86d42998b8 outdated

204@@ -198,6 +205,23 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
205     {
206         addressRet = CScriptID(uint160(vSolutions[0]));
207         return true;
208+    } else if (whichType == TX_WITNESS_V0_KEYHASH) {
209+        WitnessV0KeyHash hash;
210+        memcpy(hash.begin(), vSolutions[0].data(), 20);

danra commented at 9:28 pm on September 28, 2017:

std::copy

sipa commented at 11:38 pm on September 28, 2017:

Done.

in src/script/standard.cpp:224 in 86d42998b8 outdated

219+        WitnessUnknown unk;
220+        unk.version = vSolutions[0][0];
221+        memcpy(unk.program, vSolutions[1].data(), vSolutions[1].size());
222+        unk.length = vSolutions[1].size();
223+        addressRet = unk;
224+        return true;

danra commented at 9:33 pm on September 28, 2017:

The header comment for ExtractDestination is out of date now that P2WPKH and P2WSH are supported, it says

Currently only works for P2PK, P2PKH, and P2SH scripts.

sipa commented at 11:38 pm on September 28, 2017:

Fixed.

in src/script/standard.h:89 in 86d42998b8 outdated

84+    unsigned char program[40];
85+
86+    friend bool operator==(const WitnessUnknown& w1, const WitnessUnknown& w2) {
87+        if (w1.version != w2.version) return false;
88+        if (w1.length != w2.length) return false;
89+        if (memcmp(w1.program, w2.program, w1.length)) return false;

danra commented at 9:36 pm on September 28, 2017:

return std::equal(...);

sipa commented at 11:39 pm on September 28, 2017:

Done.

in src/script/standard.h:98 in 86d42998b8 outdated

93+    friend bool operator<(const WitnessUnknown& w1, const WitnessUnknown& w2) {
94+        if (w1.version < w2.version) return true;
95+        if (w1.version > w2.version) return false;
96+        if (w1.length < w2.length) return true;
97+        if (w1.length > w2.length) return false;
98+        if (memcmp(w1.program, w2.program, w1.length) < 0) return true;

danra commented at 9:40 pm on September 28, 2017:

return std::lexicographical_compare(...);

sipa commented at 11:39 pm on September 28, 2017:

Done.

sipa force-pushed on Sep 28, 2017

QingjingJing commented at 10:30 pm on September 28, 2017: none

Resolved?

On Thu, Sep 28, 2017 at 12:07 PM, Wladimir J. van der Laan < notifications@github.com> wrote:

@laanwj commented on this pull request.

In src/test/base58_tests.cpp https://github.com/bitcoin/bitcoin/pull/11167#discussion_r141588515:

@@ -188,50 +160,37 @@ BOOST_AUTO_TEST_CASE(base58_keys_valid_gen) std::vector exp_payload = ParseHex(test[1].get_str()); const UniValue &metadata = test[2].get_obj(); bool isPrivkey = find_value(metadata, “isPrivkey”).get_bool();
   bool isTestnet = find_value(metadata, "isTestnet").get_bool();
   if (isTestnet)
   bool isTestnet = find_value(metadata, "chain").get_str() == "testnet";
   bool regtest = find_value(metadata, "chain").get_str() == "regtest";
Same here, SelectParams(find_value(metadata, “chain”).get_str()) would do?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/11167#pullrequestreview-65823840, or mute the thread https://github.com/notifications/unsubscribe-auth/AdBhRyBBC4C-vDSFk4z6vB1n8MupJTWLks5sm33xgaJpZM4PDot9 .

Import Bech32 C++ reference code & tests

This includes a reformatted version of the Bech32 reference code
(see https://github.com/sipa/bech32/tree/master/ref/c%2B%2B), with
extra documentation.

8fd2267053

Convert base58_tests from type/payload to scriptPubKey comparison 6565c5501c

Add regtest testing to base58_tests bd355b8db9

danra commented at 11:07 pm on September 28, 2017: contributor

there’s a version of tolower where you can specify the locale yourself, so there is no concern about the wrong one being set in the system

On 29 Sep 2017, at 2:04, Pieter Wuille notifications@github.com wrote:

@sipa commented on this pull request.

In src/test/bech32_tests.cpp:

+#include <boost/test/unit_test.hpp>

+BOOST_FIXTURE_TEST_SUITE(bech32_tests, BasicTestingSetup) + +bool CaseInsensitiveEqual(const std::string &s1, const std::string &s2) +{
if (s1.size() != s2.size()) return false;

for (size_t i = 0; i < s1.size(); ++i) {
   char c1 = s1[i];
   if (c1 >= 'A' && c1 <= 'Z') c1 -= ('A' - 'a');
   char c2 = s2[i];
   if (c2 >= 'A' && c2 <= 'Z') c2 -= ('A' - 'a');
   if (c1 != c2) return false;
}

return true; +} Unfortunately, tolower is locale-dependent. I don’t feel that the complexity of avoiding that is worth it for such a trivial algorithm.
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

Implement BIP173 addresses and tests c091b99379

Support BIP173 in addwitnessaddress e278f12ca7

sipa force-pushed on Sep 28, 2017

sipa commented at 11:43 pm on September 28, 2017: member

I believe I’ve addressed or at least responded to all comments by @promag, @laanwj, @theuni, and @danra.

I’ve also updated the Bech32 tests with some new additions to the BIP.

in test/functional/test_framework/address.py:57 in 574688141d outdated

52+    return script_to_p2sh(p2shscript, main)
53+
54+def program_to_witness(version, program, main = False):
55+    if (type(program) is str):
56+        program = hex_str_to_bytes(program)
57+    assert(version >= 0 and version <= 16)

promag commented at 11:44 pm on September 28, 2017:

0assert 0 <= version <= 16

in test/functional/test_framework/address.py:58 in 574688141d outdated

53+
54+def program_to_witness(version, program, main = False):
55+    if (type(program) is str):
56+        program = hex_str_to_bytes(program)
57+    assert(version >= 0 and version <= 16)
58+    assert(len(program) >= 2 and len(program) <= 40)

promag commented at 11:45 pm on September 28, 2017:

0assert 2 <= len(program) <= 40

in test/functional/test_framework/address.py:59 in 574688141d outdated

54+def program_to_witness(version, program, main = False):
55+    if (type(program) is str):
56+        program = hex_str_to_bytes(program)
57+    assert(version >= 0 and version <= 16)
58+    assert(len(program) >= 2 and len(program) <= 40)
59+    assert(version > 0 or len(program) == 20 or len(program) == 32)

promag commented at 11:51 pm on September 28, 2017:

0assert version > 0 or len(program) in [20, 32]

in test/functional/segwit.py:606 in 574688141d outdated

601+            assert_equal(self.nodes[1].gettransaction(txid, True)["txid"], txid)
602+            assert_equal(self.nodes[1].listtransactions("*", 1, 0, True)[0]["txid"], txid)
603+
604+            # Assert it is properly saved
605+            self.stop_node(1)
606+            self.start_node(1)

promag commented at 11:52 pm on September 28, 2017:

0restart_node(1)

sipa commented at 0:30 am on September 29, 2017:

0  File "./segwit.py", line 606, in run_test
1    self.restart_node(1)
2AttributeError: 'SegWitTest' object has no attribute 'restart_node'

Use BIP173 addresses in segwit.py test fd0041aa27

[RPC] Wallet: test importing of native witness scripts

Integration into segwit.py test by Pieter Wuille.

06eaca6313

[Qt] tolerate BIP173/bech32 addresses during input validation

This eases the during-type validation to allow Bech32 chars.
Once the focus has been lost, the address will be properly verified through IsValidDestinationString

8213838db2

sipa force-pushed on Sep 29, 2017

laanwj commented at 8:10 am on September 29, 2017: member

The commentary seems to have reached the level of nano-nits, which is likely an indication this is ready for merge.

laanwj merged this on Sep 29, 2017

laanwj closed this on Sep 29, 2017

laanwj referenced this in commit aa624b61c9 on Sep 29, 2017

laanwj removed this from the "Blockers" column in a project

TheBlueMatt commented at 5:59 pm on September 29, 2017: member

postumous Matt was here and didn’t finish review.

in src/bech32.cpp:109 in 8213838db2

104+{
105+    data ret;
106+    ret.reserve(hrp.size() + 90);
107+    ret.resize(hrp.size() * 2 + 1);
108+    for (size_t i = 0; i < hrp.size(); ++i) {
109+        unsigned char c = hrp[i];

theuni commented at 7:44 pm on November 2, 2017:

Unlikely to matter, but shouldn’t this be LowerCase(hrp[i]) ?

MarcoFalke removed the label Needs backport on Nov 9, 2017

MarcoFalke removed this from the milestone 0.15.2 on Nov 9, 2017

MarcoFalke commented at 7:44 pm on November 9, 2017: member

Removing from backport

laanwj referenced this in commit b225010a80 on Mar 6, 2018

zkbot referenced this in commit 2c1f65d6e2 on Apr 23, 2018

zkbot referenced this in commit 1c2f24793b on Apr 24, 2018

zkbot referenced this in commit d5b558ba5b on Apr 25, 2018

zkbot referenced this in commit 962ba99b36 on Apr 25, 2018

zkbot referenced this in commit 88849fa479 on May 3, 2018

zkbot referenced this in commit d97bfb766b on May 4, 2018

mkjekk referenced this in commit 3d3904f74b on May 4, 2018

zkbot referenced this in commit 19ac942045 on May 7, 2018

zkbot referenced this in commit 42037a9b35 on May 7, 2018

zkbot referenced this in commit c31718fea2 on May 8, 2018

zkbot referenced this in commit 01b1962cb6 on May 8, 2018

zkbot referenced this in commit b1d2a69908 on May 8, 2018

str4d referenced this in commit 6b759fb092 on Jun 7, 2018

zkbot referenced this in commit 771aee5d88 on Jun 11, 2018

zkbot referenced this in commit 2ebde5860e on Jun 19, 2018

underdarkskies referenced this in commit 3e9ace9ce3 on Jul 3, 2018

arcalinea referenced this in commit 10b2ba41d1 on Jul 5, 2018

underdarkskies referenced this in commit 5482874437 on Jul 6, 2018

underdarkskies referenced this in commit b9a428fd7d on Jul 7, 2018

underdarkskies referenced this in commit 7b0d96c308 on Jul 10, 2018

underdarkskies referenced this in commit 4fa1e8060d on Jul 14, 2018

underdarkskies referenced this in commit 487c61c956 on Jul 14, 2018

underdarkskies referenced this in commit 88fbe58ba4 on Jul 14, 2018

underdarkskies referenced this in commit 83bdf74140 on Jul 18, 2018

underdarkskies referenced this in commit 9725a10ab3 on Aug 1, 2018

mkjekk referenced this in commit 78344bb4e1 on Aug 12, 2018

mkjekk referenced this in commit cadb67b07b on Aug 12, 2018

sipa removed the label Needs release notes on Aug 14, 2018

FornaxA referenced this in commit a0dafa6b40 on Dec 3, 2019

FornaxA referenced this in commit f0388b35f0 on Dec 3, 2019

FornaxA referenced this in commit 62d3bd4e17 on Dec 4, 2019

FornaxA referenced this in commit 9fab14f78e on Dec 4, 2019

FornaxA referenced this in commit 8e72bd1944 on Dec 4, 2019

FornaxA referenced this in commit 12ee4bae5e on Dec 4, 2019

furszy referenced this in commit 8588d419b7 on Jun 4, 2020

furszy referenced this in commit 78ad0dfa27 on Jun 10, 2020

furszy referenced this in commit 4efa2b91ba on Jun 15, 2020

furszy referenced this in commit ff037695ed on Jul 9, 2020

furszy referenced this in commit cc82b3727a on Jul 15, 2020

furszy referenced this in commit a7d5e44898 on Aug 3, 2020

random-zebra referenced this in commit fddf765132 on Aug 5, 2020

UdjinM6 referenced this in commit 5e311b6164 on Dec 25, 2020

UdjinM6 referenced this in commit c9936a5115 on Jan 8, 2021

UdjinM6 referenced this in commit 70c82570b2 on Jan 8, 2021

cryptolinux referenced this in commit c53adfadce on Feb 6, 2021

cryptolinux referenced this in commit a45c5d4adc on Feb 6, 2021

ckti referenced this in commit dfdbeba8e8 on Mar 29, 2021

ckti referenced this in commit 7c598f5657 on Mar 29, 2021

MarcoFalke locked this on Sep 8, 2021

Full BIP173 (Bech32) support #11167

@laanwj commented on this pull request.