Merge #20861: BIP 350: Implement Bech32m and use it for v1+ segwit addresses

03346022d611871f2cc185440b19d928b9264d9d naming nits (Fabian Jahr)
2e7c80fb5be82ad4a3f737cab65b31f70a772a23 Add signet support to gen_key_io_test_vectors.py (Pieter Wuille)
fe5e495c31de47b0ec732b943db11fe345d874af Use Bech32m encoding for v1+ segwit addresses (Pieter Wuille)
25b1c6e13ddf1626210d5e3d37298d1f3a78a94f Add Bech32m test vectors (Pieter Wuille)
da2bb6976dadeec682d163c258c9afecc87d6428 Implement Bech32m encoding/decoding (Pieter Wuille)

Pull request description:

  This implements [BIP 350](https://github.com/bitcoin/bips/blob/master/bip-0350.mediawiki):
  * For segwit v1+ addresses, a new checksum algorithm called Bech32m is used.
  * Segwit v0 address keep using Bech32 as specified in [BIP 173](https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki).

ACKs for top commit:
  Sjors:
    utACK 0334602
  jnewbery:
    utACK 03346022d6
  achow101:
    ACK 0334602
  fjahr:
    re-ACK 0334602
  benthecarman:
    ACK 03346022d611871f2cc185440b19d928b9264d9d

Tree-SHA512: 4424cfd44869d813d6152fb3ed867b204036736bc2344a039b93700b6f36a43e9110478f138eb81c97c77ab27ecb776dada5ba632cb5a3a9d244924d2540a557

2 files changed, 55 insertions, 33 deletions

diff --git a/contrib/testgen/README.md b/contrib/testgen/README.md
index eaca473b40..fcc5a378e2 100644
--- a/contrib/testgen/README.md
+++ b/contrib/testgen/README.md
@@ -4,5 +4,5 @@ Utilities to generate test vectors for the data-driven Bitcoin tests.
 
 Usage:
 
-    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py valid 50 > ../../src/test/data/key_io_valid.json
-    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py invalid 50 > ../../src/test/data/key_io_invalid.json
+    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py valid 70 > ../../src/test/data/key_io_valid.json
+    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py invalid 70 > ../../src/test/data/key_io_invalid.json
diff --git a/contrib/testgen/gen_key_io_test_vectors.py b/contrib/testgen/gen_key_io_test_vectors.py
index 8a3918da6b..2f3189eca9 100755
--- a/contrib/testgen/gen_key_io_test_vectors.py
+++ b/contrib/testgen/gen_key_io_test_vectors.py
@@ -3,11 +3,11 @@
 # Distributed under the MIT software license, see the accompanying
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 '''
-Generate valid and invalid base58 address and private key test vectors.
+Generate valid and invalid base58/bech32(m) address and private key test vectors.
 
 Usage:
-    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py valid 50 > ../../src/test/data/key_io_valid.json
-    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py invalid 50 > ../../src/test/data/key_io_invalid.json
+    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py valid 70 > ../../src/test/data/key_io_valid.json
+    PYTHONPATH=../../test/functional/test_framework ./gen_key_io_test_vectors.py invalid 70 > ../../src/test/data/key_io_invalid.json
 '''
 # 2012 Wladimir J. van der Laan
 # Released under MIT License
@@ -15,7 +15,7 @@ import os
 from itertools import islice
 from base58 import b58encode_chk, b58decode_chk, b58chars
 import random
-from segwit_addr import bech32_encode, decode_segwit_address, convertbits, CHARSET
+from segwit_addr import bech32_encode, decode_segwit_address, convertbits, CHARSET, Encoding
 
 # key types
 PUBKEY_ADDRESS = 0
@@ -32,6 +32,7 @@ PRIVKEY_REGTEST = 239
 OP_0 = 0x00
 OP_1 = 0x51
 OP_2 = 0x52
+OP_3 = 0x53
 OP_16 = 0x60
 OP_DUP = 0x76
 OP_EQUAL = 0x87
@@ -44,6 +45,7 @@ script_prefix = (OP_HASH160, 20)
 script_suffix = (OP_EQUAL,)
 p2wpkh_prefix = (OP_0, 20)
 p2wsh_prefix = (OP_0, 32)
+p2tr_prefix = (OP_1, 32)
 
 metadata_keys = ['isPrivkey', 'chain', 'isCompressed', 'tryCaseFlip']
 # templates for valid sequences
@@ -54,40 +56,58 @@ templates = [
   ((SCRIPT_ADDRESS,),         20, (),   (False, 'main',    None,  None), script_prefix, script_suffix),
   ((PUBKEY_ADDRESS_TEST,),    20, (),   (False, 'test',    None,  None), pubkey_prefix, pubkey_suffix),
   ((SCRIPT_ADDRESS_TEST,),    20, (),   (False, 'test',    None,  None), script_prefix, script_suffix),
+  ((PUBKEY_ADDRESS_TEST,),    20, (),   (False, 'signet',  None,  None), pubkey_prefix, pubkey_suffix),
+  ((SCRIPT_ADDRESS_TEST,),    20, (),   (False, 'signet',  None,  None), script_prefix, script_suffix),
   ((PUBKEY_ADDRESS_REGTEST,), 20, (),   (False, 'regtest', None,  None), pubkey_prefix, pubkey_suffix),
   ((SCRIPT_ADDRESS_REGTEST,), 20, (),   (False, 'regtest', None,  None), script_prefix, script_suffix),
   ((PRIVKEY,),                32, (),   (True,  'main',    False, None), (),            ()),
   ((PRIVKEY,),                32, (1,), (True,  'main',    True,  None), (),            ()),
   ((PRIVKEY_TEST,),           32, (),   (True,  'test',    False, None), (),            ()),
   ((PRIVKEY_TEST,),           32, (1,), (True,  'test',    True,  None), (),            ()),
+  ((PRIVKEY_TEST,),           32, (),   (True,  'signet',  False, None), (),            ()),
+  ((PRIVKEY_TEST,),           32, (1,), (True,  'signet',  True,  None), (),            ()),
   ((PRIVKEY_REGTEST,),        32, (),   (True,  'regtest', False, None), (),            ()),
   ((PRIVKEY_REGTEST,),        32, (1,), (True,  'regtest', True,  None), (),            ())
 ]
 # templates for valid bech32 sequences
 bech32_templates = [
-  # hrp, version, witprog_size, metadata, output_prefix
-  ('bc',    0, 20, (False, 'main',    None, True), p2wpkh_prefix),
-  ('bc',    0, 32, (False, 'main',    None, True), p2wsh_prefix),
-  ('bc',    1,  2, (False, 'main',    None, True), (OP_1, 2)),
-  ('tb',    0, 20, (False, 'test',    None, True), p2wpkh_prefix),
-  ('tb',    0, 32, (False, 'test',    None, True), p2wsh_prefix),
-  ('tb',    2, 16, (False, 'test',    None, True), (OP_2, 16)),
-  ('bcrt',  0, 20, (False, 'regtest', None, True), p2wpkh_prefix),
-  ('bcrt',  0, 32, (False, 'regtest', None, True), p2wsh_prefix),
-  ('bcrt', 16, 40, (False, 'regtest', None, True), (OP_16, 40))
+  # hrp, version, witprog_size, metadata, encoding, output_prefix
+  ('bc',    0, 20, (False, 'main',    None, True), Encoding.BECH32,  p2wpkh_prefix),
+  ('bc',    0, 32, (False, 'main',    None, True), Encoding.BECH32,  p2wsh_prefix),
+  ('bc',    1, 32, (False, 'main',    None, True), Encoding.BECH32M, p2tr_prefix),
+  ('bc',    2,  2, (False, 'main',    None, True), Encoding.BECH32M, (OP_2, 2)),
+  ('tb',    0, 20, (False, 'test',    None, True), Encoding.BECH32,  p2wpkh_prefix),
+  ('tb',    0, 32, (False, 'test',    None, True), Encoding.BECH32,  p2wsh_prefix),
+  ('tb',    1, 32, (False, 'test',    None, True), Encoding.BECH32M, p2tr_prefix),
+  ('tb',    3, 16, (False, 'test',    None, True), Encoding.BECH32M, (OP_3, 16)),
+  ('tb',    0, 20, (False, 'signet',  None, True), Encoding.BECH32,  p2wpkh_prefix),
+  ('tb',    0, 32, (False, 'signet',  None, True), Encoding.BECH32,  p2wsh_prefix),
+  ('tb',    1, 32, (False, 'signet',  None, True), Encoding.BECH32M, p2tr_prefix),
+  ('tb',    3, 32, (False, 'signet',  None, True), Encoding.BECH32M, (OP_3, 32)),
+  ('bcrt',  0, 20, (False, 'regtest', None, True), Encoding.BECH32,  p2wpkh_prefix),
+  ('bcrt',  0, 32, (False, 'regtest', None, True), Encoding.BECH32,  p2wsh_prefix),
+  ('bcrt',  1, 32, (False, 'regtest', None, True), Encoding.BECH32M, p2tr_prefix),
+  ('bcrt', 16, 40, (False, 'regtest', None, True), Encoding.BECH32M, (OP_16, 40))
 ]
 # templates for invalid bech32 sequences
 bech32_ng_templates = [
-  # hrp, version, witprog_size, invalid_bech32, invalid_checksum, invalid_char
-  ('tc',    0, 20, False, False, False),
-  ('tb',   17, 32, False, False, False),
-  ('bcrt',  3,  1, False, False, False),
-  ('bc',   15, 41, False, False, False),
-  ('tb',    0, 16, False, False, False),
-  ('bcrt',  0, 32, True,  False, False),
-  ('bc',    0, 16, True,  False, False),
-  ('tb',    0, 32, False, True,  False),
-  ('bcrt',  0, 20, False, False, True)
+  # hrp, version, witprog_size, encoding, invalid_bech32, invalid_checksum, invalid_char
+  ('tc',    0, 20, Encoding.BECH32,  False, False, False),
+  ('bt',    1, 32, Encoding.BECH32M, False, False, False),
+  ('tb',   17, 32, Encoding.BECH32M, False, False, False),
+  ('bcrt',  3,  1, Encoding.BECH32M, False, False, False),
+  ('bc',   15, 41, Encoding.BECH32M, False, False, False),
+  ('tb',    0, 16, Encoding.BECH32,  False, False, False),
+  ('bcrt',  0, 32, Encoding.BECH32,  True,  False, False),
+  ('bc',    0, 16, Encoding.BECH32,  True,  False, False),
+  ('tb',    0, 32, Encoding.BECH32,  False, True,  False),
+  ('bcrt',  0, 20, Encoding.BECH32,  False, False, True),
+  ('bc',    0, 20, Encoding.BECH32M, False, False, False),
+  ('tb',    0, 32, Encoding.BECH32M, False, False, False),
+  ('bcrt',  0, 20, Encoding.BECH32M, False, False, False),
+  ('bc',    1, 32, Encoding.BECH32,  False, False, False),
+  ('tb',    2, 16, Encoding.BECH32,  False, False, False),
+  ('bcrt', 16, 20, Encoding.BECH32,  False, False, False),
 ]
 
 def is_valid(v):
@@ -127,8 +147,9 @@ def gen_valid_bech32_vector(template):
     hrp = template[0]
     witver = template[1]
     witprog = bytearray(os.urandom(template[2]))
-    dst_prefix = bytearray(template[4])
-    rv = bech32_encode(hrp, [witver] + convertbits(witprog, 8, 5))
+    encoding = template[4]
+    dst_prefix = bytearray(template[5])
+    rv = bech32_encode(hrp, [witver] + convertbits(witprog, 8, 5), encoding)
     return rv, dst_prefix + witprog
 
 def gen_valid_vectors():
@@ -186,22 +207,23 @@ def gen_invalid_bech32_vector(template):
     hrp = template[0]
     witver = template[1]
     witprog = bytearray(os.urandom(template[2]))
+    encoding = template[3]
 
     if no_data:
-        rv = bech32_encode(hrp, [])
+        rv = bech32_encode(hrp, [], encoding)
     else:
         data = [witver] + convertbits(witprog, 8, 5)
-        if template[3] and not no_data:
+        if template[4] and not no_data:
             if template[2] % 5 in {2, 4}:
                 data[-1] |= 1
             else:
                 data.append(0)
-        rv = bech32_encode(hrp, data)
+        rv = bech32_encode(hrp, data, encoding)
 
-    if template[4]:
+    if template[5]:
         i = len(rv) - random.randrange(1, 7)
         rv = rv[:i] + random.choice(CHARSET.replace(rv[i], '')) + rv[i + 1:]
-    if template[5]:
+    if template[6]:
         i = len(hrp) + 1 + random.randrange(0, len(rv) - len(hrp) - 4)
         rv = rv[:i] + rv[i:i + 4].upper() + rv[i + 4:]