segwit_addr.py (4616B)
1 2 # Copyright (c) 2017 Pieter Wuille 3 # 4 # Permission is hereby granted, free of charge, to any person obtaining a copy 5 # of this software and associated documentation files (the "Software"), to deal 6 # in the Software without restriction, including without limitation the rights 7 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 # copies of the Software, and to permit persons to whom the Software is 9 # furnished to do so, subject to the following conditions: 10 # 11 # The above copyright notice and this permission notice shall be included in 12 # all copies or substantial portions of the Software. 13 # 14 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 # THE SOFTWARE. 21 22 """Reference implementation for Bech32 and segwit addresses.""" 23 24 25 CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l" 26 _CHARSET_INVERSE = {x: CHARSET.find(x) for x in CHARSET} 27 28 29 def bech32_polymod(values): 30 """Internal function that computes the Bech32 checksum.""" 31 generator = [0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3] 32 chk = 1 33 for value in values: 34 top = chk >> 25 35 chk = (chk & 0x1ffffff) << 5 ^ value 36 for i in range(5): 37 chk ^= generator[i] if ((top >> i) & 1) else 0 38 return chk 39 40 41 def bech32_hrp_expand(hrp): 42 """Expand the HRP into values for checksum computation.""" 43 return [ord(x) >> 5 for x in hrp] + [0] + [ord(x) & 31 for x in hrp] 44 45 46 def bech32_verify_checksum(hrp, data): 47 """Verify a checksum given HRP and converted data characters.""" 48 return bech32_polymod(bech32_hrp_expand(hrp) + data) == 1 49 50 51 def bech32_create_checksum(hrp, data): 52 """Compute the checksum values given HRP and data.""" 53 values = bech32_hrp_expand(hrp) + data 54 polymod = bech32_polymod(values + [0, 0, 0, 0, 0, 0]) ^ 1 55 return [(polymod >> 5 * (5 - i)) & 31 for i in range(6)] 56 57 58 def bech32_encode(hrp, data): 59 """Compute a Bech32 string given HRP and data values.""" 60 combined = data + bech32_create_checksum(hrp, data) 61 return hrp + '1' + ''.join([CHARSET[d] for d in combined]) 62 63 64 def bech32_decode(bech: str, ignore_long_length=False): 65 """Validate a Bech32 string, and determine HRP and data.""" 66 bech_lower = bech.lower() 67 if bech_lower != bech and bech.upper() != bech: 68 return (None, None) 69 pos = bech.rfind('1') 70 if pos < 1 or pos + 7 > len(bech) or (not ignore_long_length and len(bech) > 90): 71 return (None, None) 72 # check that HRP only consists of sane ASCII chars 73 if any(ord(x) < 33 or ord(x) > 126 for x in bech[:pos+1]): 74 return (None, None) 75 bech = bech_lower 76 hrp = bech[:pos] 77 try: 78 data = [_CHARSET_INVERSE[x] for x in bech[pos+1:]] 79 except KeyError: 80 return (None, None) 81 if not bech32_verify_checksum(hrp, data): 82 return (None, None) 83 return (hrp, data[:-6]) 84 85 86 def convertbits(data, frombits, tobits, pad=True): 87 """General power-of-2 base conversion.""" 88 acc = 0 89 bits = 0 90 ret = [] 91 maxv = (1 << tobits) - 1 92 max_acc = (1 << (frombits + tobits - 1)) - 1 93 for value in data: 94 if value < 0 or (value >> frombits): 95 return None 96 acc = ((acc << frombits) | value) & max_acc 97 bits += frombits 98 while bits >= tobits: 99 bits -= tobits 100 ret.append((acc >> bits) & maxv) 101 if pad: 102 if bits: 103 ret.append((acc << (tobits - bits)) & maxv) 104 elif bits >= frombits or ((acc << (tobits - bits)) & maxv): 105 return None 106 return ret 107 108 109 def decode(hrp, addr): 110 """Decode a segwit address.""" 111 if addr is None: 112 return (None, None) 113 hrpgot, data = bech32_decode(addr) 114 if hrpgot != hrp: 115 return (None, None) 116 decoded = convertbits(data[1:], 5, 8, False) 117 if decoded is None or len(decoded) < 2 or len(decoded) > 40: 118 return (None, None) 119 if data[0] > 16: 120 return (None, None) 121 if data[0] == 0 and len(decoded) != 20 and len(decoded) != 32: 122 return (None, None) 123 return (data[0], decoded) 124 125 126 def encode(hrp, witver, witprog): 127 """Encode a segwit address.""" 128 ret = bech32_encode(hrp, [witver] + convertbits(witprog, 8, 5)) 129 assert decode(hrp, ret) != (None, None) 130 return ret