test/functional/test_framework/segwit_addr.py

   1 #!/usr/bin/env python3
   2 # Copyright (c) 2017 Pieter Wuille
   3 # Distributed under the MIT software license, see the accompanying
   4 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5 """Reference implementation for Bech32 and segwit addresses."""
   6
   7
   8 CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
   9
  10
  11 def bech32_polymod(values):
  12     """Internal function that computes the Bech32 checksum."""
  13     generator = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3]
  14     chk = 1
  15     for value in values:
  16         top = chk >> 25
  17         chk = (chk & 0x1ffffff) << 5 ^ value
  18         for i in range(5):
  19             chk ^= generator[i] if ((top >> i) & 1) else 0
  20     return chk
  21
  22
  23 def bech32_hrp_expand(hrp):
  24     """Expand the HRP into values for checksum computation."""
  25     return [ord(x) >> 5 for x in hrp] + [0] + [ord(x) & 31 for x in hrp]
  26
  27
  28 def bech32_verify_checksum(hrp, data):
  29     """Verify a checksum given HRP and converted data characters."""
  30     return bech32_polymod(bech32_hrp_expand(hrp) + data) == 1
  31
  32
  33 def bech32_create_checksum(hrp, data):
  34     """Compute the checksum values given HRP and data."""
  35     values = bech32_hrp_expand(hrp) + data
  36     polymod = bech32_polymod(values + [0, 0, 0, 0, 0, 0]) ^ 1
  37     return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)]
  38
  39
  40 def bech32_encode(hrp, data):
  41     """Compute a Bech32 string given HRP and data values."""
  42     combined = data + bech32_create_checksum(hrp, data)
  43     return hrp + '1' + ''.join([CHARSET[d] for d in combined])
  44
  45
  46 def bech32_decode(bech):
  47     """Validate a Bech32 string, and determine HRP and data."""
  48     if ((any(ord(x) < 33 or ord(x) > 126 for x in bech)) or
  49             (bech.lower() != bech and bech.upper() != bech)):
  50         return (None, None)
  51     bech = bech.lower()
  52     pos = bech.rfind('1')
  53     if pos < 1 or pos + 7 > len(bech) or len(bech) > 90:
  54         return (None, None)
  55     if not all(x in CHARSET for x in bech[pos+1:]):
  56         return (None, None)
  57     hrp = bech[:pos]
  58     data = [CHARSET.find(x) for x in bech[pos+1:]]
  59     if not bech32_verify_checksum(hrp, data):
  60         return (None, None)
  61     return (hrp, data[:-6])
  62
  63
  64 def convertbits(data, frombits, tobits, pad=True):
  65     """General power-of-2 base conversion."""
  66     acc = 0
  67     bits = 0
  68     ret = []
  69     maxv = (1 << tobits) - 1
  70     max_acc = (1 << (frombits + tobits - 1)) - 1
  71     for value in data:
  72         if value < 0 or (value >> frombits):
  73             return None
  74         acc = ((acc << frombits) | value) & max_acc
  75         bits += frombits
  76         while bits >= tobits:
  77             bits -= tobits
  78             ret.append((acc >> bits) & maxv)
  79     if pad:
  80         if bits:
  81             ret.append((acc << (tobits - bits)) & maxv)
  82     elif bits >= frombits or ((acc << (tobits - bits)) & maxv):
  83         return None
  84     return ret
  85
  86
  87 def decode(hrp, addr):
  88     """Decode a segwit address."""
  89     hrpgot, data = bech32_decode(addr)
  90     if hrpgot != hrp:
  91         return (None, None)
  92     decoded = convertbits(data[1:], 5, 8, False)
  93     if decoded is None or len(decoded) < 2 or len(decoded) > 40:
  94         return (None, None)
  95     if data[0] > 16:
  96         return (None, None)
  97     if data[0] == 0 and len(decoded) != 20 and len(decoded) != 32:
  98         return (None, None)
  99     return (data[0], decoded)
 100
 101
 102 def encode(hrp, witver, witprog):
 103     """Encode a segwit address."""
 104     ret = bech32_encode(hrp, [witver] + convertbits(witprog, 8, 5))
 105     if decode(hrp, ret) == (None, None):
 106         return None
 107     return ret