Merge #11167: Full BIP173 (Bech32) support

8213838 [Qt] tolerate BIP173/bech32 addresses during input validation (Jonas Schnelli)
06eaca6 [RPC] Wallet: test importing of native witness scripts (NicolasDorier)
fd0041a Use BIP173 addresses in segwit.py test (Pieter Wuille)
e278f12 Support BIP173 in addwitnessaddress (Pieter Wuille)
c091b99 Implement BIP173 addresses and tests (Pieter Wuille)
bd355b8 Add regtest testing to base58_tests (Pieter Wuille)
6565c55 Convert base58_tests from type/payload to scriptPubKey comparison (Pieter Wuille)
8fd2267 Import Bech32 C++ reference code & tests (Pieter Wuille)
1e46ebd Implement {Encode,Decode}Destination without CBitcoinAddress (Pieter Wuille)

Pull request description:

  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](https://github.com/sipa/bech32/tree/master/ref/c%2B%2B) 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.

Tree-SHA512: 238031185fd07f3ac873c586043970cc2db91bf7735c3c168cb33a3db39a7bda81d4891b649685bb17ef90dc63af0328e7705d8cd3e8dafd6c4d3c08fb230341

6 files changed, 200 insertions, 16 deletions

diff --git a/test/functional/segwit.py b/test/functional/segwit.py
index f465c1683b..de5c8c6c87 100755
--- a/test/functional/segwit.py
+++ b/test/functional/segwit.py
@@ -7,7 +7,7 @@
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import *
 from test_framework.mininode import sha256, CTransaction, CTxIn, COutPoint, CTxOut, COIN, ToHex, FromHex
-from test_framework.address import script_to_p2sh, key_to_p2pkh
+from test_framework.address import script_to_p2sh, key_to_p2pkh, key_to_p2sh_p2wpkh, key_to_p2wpkh, script_to_p2sh_p2wsh, script_to_p2wsh, program_to_witness
 from test_framework.script import CScript, OP_HASH160, OP_CHECKSIG, OP_0, hash160, OP_EQUAL, OP_DUP, OP_EQUALVERIFY, OP_1, OP_2, OP_CHECKMULTISIG, OP_TRUE
 from io import BytesIO
 
@@ -33,15 +33,15 @@ def witness_script(use_p2wsh, pubkey):
 
 # Return a transaction (in hex) that spends the given utxo to a segwit output,
 # optionally wrapping the segwit output using P2SH.
-def create_witnessprogram(use_p2wsh, utxo, pubkey, encode_p2sh, amount):
-    pkscript = hex_str_to_bytes(witness_script(use_p2wsh, pubkey))
-    if (encode_p2sh):
-        p2sh_hash = hash160(pkscript)
-        pkscript = CScript([OP_HASH160, p2sh_hash, OP_EQUAL])
-    tx = CTransaction()
-    tx.vin.append(CTxIn(COutPoint(int(utxo["txid"], 16), utxo["vout"]), b""))
-    tx.vout.append(CTxOut(int(amount*COIN), pkscript))
-    return ToHex(tx)
+def create_witness_tx(node, use_p2wsh, utxo, pubkey, encode_p2sh, amount):
+    if use_p2wsh:
+        program = CScript([OP_1, hex_str_to_bytes(pubkey), OP_1, OP_CHECKMULTISIG])
+        addr = script_to_p2sh_p2wsh(program) if encode_p2sh else script_to_p2wsh(program)
+    else:
+        addr = key_to_p2sh_p2wpkh(pubkey) if encode_p2sh else key_to_p2wpkh(pubkey)
+    if not encode_p2sh:
+        assert_equal(node.validateaddress(addr)['scriptPubKey'], witness_script(use_p2wsh, pubkey))
+    return node.createrawtransaction([utxo], {addr: amount})
 
 # Create a transaction spending a given utxo to a segwit output corresponding
 # to the given pubkey: use_p2wsh determines whether to use P2WPKH or P2WSH;
@@ -49,7 +49,7 @@ def create_witnessprogram(use_p2wsh, utxo, pubkey, encode_p2sh, amount):
 # sign=True will have the given node sign the transaction.
 # insert_redeem_script will be added to the scriptSig, if given.
 def send_to_witness(use_p2wsh, node, utxo, pubkey, encode_p2sh, amount, sign=True, insert_redeem_script=""):
-    tx_to_witness = create_witnessprogram(use_p2wsh, utxo, pubkey, encode_p2sh, amount)
+    tx_to_witness = create_witness_tx(node, use_p2wsh, utxo, pubkey, encode_p2sh, amount)
     if (sign):
         signed = node.signrawtransaction(tx_to_witness)
         assert("errors" not in signed or len(["errors"]) == 0)
@@ -133,8 +133,15 @@ class SegWitTest(BitcoinTestFramework):
             newaddress = self.nodes[i].getnewaddress()
             self.pubkey.append(self.nodes[i].validateaddress(newaddress)["pubkey"])
             multiaddress = self.nodes[i].addmultisigaddress(1, [self.pubkey[-1]])
-            self.nodes[i].addwitnessaddress(newaddress)
-            self.nodes[i].addwitnessaddress(multiaddress)
+            multiscript = CScript([OP_1, hex_str_to_bytes(self.pubkey[-1]), OP_1, OP_CHECKMULTISIG])
+            p2sh_addr = self.nodes[i].addwitnessaddress(newaddress, True)
+            bip173_addr = self.nodes[i].addwitnessaddress(newaddress, False)
+            p2sh_ms_addr = self.nodes[i].addwitnessaddress(multiaddress, True)
+            bip173_ms_addr = self.nodes[i].addwitnessaddress(multiaddress, False)
+            assert_equal(p2sh_addr, key_to_p2sh_p2wpkh(self.pubkey[-1]))
+            assert_equal(bip173_addr, key_to_p2wpkh(self.pubkey[-1]))
+            assert_equal(p2sh_ms_addr, script_to_p2sh_p2wsh(multiscript))
+            assert_equal(bip173_ms_addr, script_to_p2wsh(multiscript))
             p2sh_ids.append([])
             wit_ids.append([])
             for v in range(2):
@@ -558,6 +565,13 @@ class SegWitTest(BitcoinTestFramework):
         solvable_txid.append(self.mine_and_test_listunspent(solvable_after_addwitnessaddress, 1))
         self.mine_and_test_listunspent(unseen_anytime, 0)
 
+        # Check that createrawtransaction/decoderawtransaction with non-v0 Bech32 works
+        v1_addr = program_to_witness(1, [3,5])
+        v1_tx = self.nodes[0].createrawtransaction([getutxo(spendable_txid[0])],{v1_addr: 1})
+        v1_decoded = self.nodes[1].decoderawtransaction(v1_tx)
+        assert_equal(v1_decoded['vout'][0]['scriptPubKey']['addresses'][0], v1_addr)
+        assert_equal(v1_decoded['vout'][0]['scriptPubKey']['hex'], "51020305")
+
         # Check that spendable outputs are really spendable
         self.create_and_mine_tx_from_txids(spendable_txid)
 
@@ -570,6 +584,29 @@ class SegWitTest(BitcoinTestFramework):
         self.nodes[0].importprivkey("cTW5mR5M45vHxXkeChZdtSPozrFwFgmEvTNnanCW6wrqwaCZ1X7K")
         self.create_and_mine_tx_from_txids(solvable_txid)
 
+        # Test that importing native P2WPKH/P2WSH scripts works
+        for use_p2wsh in [False, True]:
+            if use_p2wsh:
+                scriptPubKey = "00203a59f3f56b713fdcf5d1a57357f02c44342cbf306ffe0c4741046837bf90561a"
+                transaction = "01000000000100e1f505000000002200203a59f3f56b713fdcf5d1a57357f02c44342cbf306ffe0c4741046837bf90561a00000000"
+            else:
+                scriptPubKey = "a9142f8c469c2f0084c48e11f998ffbe7efa7549f26d87"
+                transaction = "01000000000100e1f5050000000017a9142f8c469c2f0084c48e11f998ffbe7efa7549f26d8700000000"
+
+            self.nodes[1].importaddress(scriptPubKey, "", False)
+            rawtxfund = self.nodes[1].fundrawtransaction(transaction)['hex']
+            rawtxfund = self.nodes[1].signrawtransaction(rawtxfund)["hex"]
+            txid = self.nodes[1].sendrawtransaction(rawtxfund)
+
+            assert_equal(self.nodes[1].gettransaction(txid, True)["txid"], txid)
+            assert_equal(self.nodes[1].listtransactions("*", 1, 0, True)[0]["txid"], txid)
+
+            # Assert it is properly saved
+            self.stop_node(1)
+            self.start_node(1)
+            assert_equal(self.nodes[1].gettransaction(txid, True)["txid"], txid)
+            assert_equal(self.nodes[1].listtransactions("*", 1, 0, True)[0]["txid"], txid)
+
     def mine_and_test_listunspent(self, script_list, ismine):
         utxo = find_unspent(self.nodes[0], 50)
         tx = CTransaction()
diff --git a/test/functional/test_framework/address.py b/test/functional/test_framework/address.py
index 180dac197e..2e2db5ffb2 100644
--- a/test/functional/test_framework/address.py
+++ b/test/functional/test_framework/address.py
@@ -7,6 +7,8 @@
 from .script import hash256, hash160, sha256, CScript, OP_0
 from .util import bytes_to_hex_str, hex_str_to_bytes
 
+from . import segwit_addr
+
 chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
 
 def byte_to_base58(b, version):
@@ -44,6 +46,32 @@ def script_to_p2sh(script, main = False):
     script = check_script(script)
     return scripthash_to_p2sh(hash160(script), main)
 
+def key_to_p2sh_p2wpkh(key, main = False):
+    key = check_key(key)
+    p2shscript = CScript([OP_0, hash160(key)])
+    return script_to_p2sh(p2shscript, main)
+
+def program_to_witness(version, program, main = False):
+    if (type(program) is str):
+        program = hex_str_to_bytes(program)
+    assert 0 <= version <= 16
+    assert 2 <= len(program) <= 40
+    assert version > 0 or len(program) in [20, 32]
+    return segwit_addr.encode("bc" if main else "bcrt", version, program)
+
+def script_to_p2wsh(script, main = False):
+    script = check_script(script)
+    return program_to_witness(0, sha256(script), main)
+
+def key_to_p2wpkh(key, main = False):
+    key = check_key(key)
+    return program_to_witness(0, hash160(key), main)
+
+def script_to_p2sh_p2wsh(script, main = False):
+    script = check_script(script)
+    p2shscript = CScript([OP_0, sha256(script)])
+    return script_to_p2sh(p2shscript, main)
+
 def check_key(key):
     if (type(key) is str):
         key = hex_str_to_bytes(key) # Assuming this is hex string
diff --git a/test/functional/test_framework/segwit_addr.py b/test/functional/test_framework/segwit_addr.py
new file mode 100644
index 0000000000..02368e938f
--- /dev/null
+++ b/test/functional/test_framework/segwit_addr.py
@@ -0,0 +1,107 @@
+#!/usr/bin/env python3
+# Copyright (c) 2017 Pieter Wuille
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""Reference implementation for Bech32 and segwit addresses."""
+
+
+CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
+
+
+def bech32_polymod(values):
+    """Internal function that computes the Bech32 checksum."""
+    generator = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
+    chk = 1
+    for value in values:
+        top = chk >> 25
+        chk = (chk & 0x1ffffff) << 5 ^ value
+        for i in range(5):
+            chk ^= generator[i] if ((top >> i) & 1) else 0
+    return chk
+
+
+def bech32_hrp_expand(hrp):
+    """Expand the HRP into values for checksum computation."""
+    return [ord(x) >> 5 for x in hrp] + [0] + [ord(x) & 31 for x in hrp]
+
+
+def bech32_verify_checksum(hrp, data):
+    """Verify a checksum given HRP and converted data characters."""
+    return bech32_polymod(bech32_hrp_expand(hrp) + data) == 1
+
+
+def bech32_create_checksum(hrp, data):
+    """Compute the checksum values given HRP and data."""
+    values = bech32_hrp_expand(hrp) + data
+    polymod = bech32_polymod(values + [0, 0, 0, 0, 0, 0]) ^ 1
+    return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]
+
+
+def bech32_encode(hrp, data):
+    """Compute a Bech32 string given HRP and data values."""
+    combined = data + bech32_create_checksum(hrp, data)
+    return hrp + '1' + ''.join([CHARSET[d] for d in combined])
+
+
+def bech32_decode(bech):
+    """Validate a Bech32 string, and determine HRP and data."""
+    if ((any(ord(x) < 33 or ord(x) > 126 for x in bech)) or
+            (bech.lower() != bech and bech.upper() != bech)):
+        return (None, None)
+    bech = bech.lower()
+    pos = bech.rfind('1')
+    if pos < 1 or pos + 7 > len(bech) or len(bech) > 90:
+        return (None, None)
+    if not all(x in CHARSET for x in bech[pos+1:]):
+        return (None, None)
+    hrp = bech[:pos]
+    data = [CHARSET.find(x) for x in bech[pos+1:]]
+    if not bech32_verify_checksum(hrp, data):
+        return (None, None)
+    return (hrp, data[:-6])
+
+
+def convertbits(data, frombits, tobits, pad=True):
+    """General power-of-2 base conversion."""
+    acc = 0
+    bits = 0
+    ret = []
+    maxv = (1 << tobits) - 1
+    max_acc = (1 << (frombits + tobits - 1)) - 1
+    for value in data:
+        if value < 0 or (value >> frombits):
+            return None
+        acc = ((acc << frombits) | value) & max_acc
+        bits += frombits
+        while bits >= tobits:
+            bits -= tobits
+            ret.append((acc >> bits) & maxv)
+    if pad:
+        if bits:
+            ret.append((acc << (tobits - bits)) & maxv)
+    elif bits >= frombits or ((acc << (tobits - bits)) & maxv):
+        return None
+    return ret
+
+
+def decode(hrp, addr):
+    """Decode a segwit address."""
+    hrpgot, data = bech32_decode(addr)
+    if hrpgot != hrp:
+        return (None, None)
+    decoded = convertbits(data[1:], 5, 8, False)
+    if decoded is None or len(decoded) < 2 or len(decoded) > 40:
+        return (None, None)
+    if data[0] > 16:
+        return (None, None)
+    if data[0] == 0 and len(decoded) != 20 and len(decoded) != 32:
+        return (None, None)
+    return (data[0], decoded)
+
+
+def encode(hrp, witver, witprog):
+    """Encode a segwit address."""
+    ret = bech32_encode(hrp, [witver] + convertbits(witprog, 8, 5))
+    if decode(hrp, ret) == (None, None):
+        return None
+    return ret
diff --git a/test/util/data/txcreatemultisig3.json b/test/util/data/txcreatemultisig3.json
index 06e093e224..6c5b49d876 100644
--- a/test/util/data/txcreatemultisig3.json
+++ b/test/util/data/txcreatemultisig3.json
@@ -14,7 +14,11 @@
             "scriptPubKey": {
                 "asm": "0 e15a86a23178f433d514dbbce042e87d72662b8b5edcacfd2e37ab7a2d135f05",
                 "hex": "0020e15a86a23178f433d514dbbce042e87d72662b8b5edcacfd2e37ab7a2d135f05",
-                "type": "witness_v0_scripthash"
+                "reqSigs": 1,
+                "type": "witness_v0_scripthash",
+                "addresses": [
+                    "bc1qu9dgdg330r6r84g5mw7wqshg04exv2uttmw2elfwx74h5tgntuzs44gyfg"
+                ]
             }
         }
     ],
diff --git a/test/util/data/txcreateoutpubkey2.json b/test/util/data/txcreateoutpubkey2.json
index 5144722230..4ba5dcb282 100644
--- a/test/util/data/txcreateoutpubkey2.json
+++ b/test/util/data/txcreateoutpubkey2.json
@@ -14,7 +14,11 @@
             "scriptPubKey": {
                 "asm": "0 a2516e770582864a6a56ed21a102044e388c62e3",
                 "hex": "0014a2516e770582864a6a56ed21a102044e388c62e3",
-                "type": "witness_v0_keyhash"
+                "reqSigs": 1,
+                "type": "witness_v0_keyhash",
+                "addresses": [
+                    "bc1q5fgkuac9s2ry56jka5s6zqsyfcugcchry5cwu0"
+                ]
             }
         }
     ],
diff --git a/test/util/data/txcreatescript3.json b/test/util/data/txcreatescript3.json
index 980da2fb31..31b6459214 100644
--- a/test/util/data/txcreatescript3.json
+++ b/test/util/data/txcreatescript3.json
@@ -14,7 +14,11 @@
             "scriptPubKey": {
                 "asm": "0 0bfe935e70c321c7ca3afc75ce0d0ca2f98b5422e008bb31c00c6d7f1f1c0ad6",
                 "hex": "00200bfe935e70c321c7ca3afc75ce0d0ca2f98b5422e008bb31c00c6d7f1f1c0ad6",
-                "type": "witness_v0_scripthash"
+                "reqSigs": 1,
+                "type": "witness_v0_scripthash",
+                "addresses": [
+                    "bc1qp0lfxhnscvsu0j36l36uurgv5tuck4pzuqytkvwqp3kh78cupttqyf705v"
+                ]
             }
         }
     ],