1# bitcoin.py - functions for handling Bitcoin addresses
2#
3# Copyright (C) 2018 Arthur de Jong
4#
5# This library is free software; you can redistribute it and/or
6# modify it under the terms of the GNU Lesser General Public
7# License as published by the Free Software Foundation; either
8# version 2.1 of the License, or (at your option) any later version.
9#
10# This library is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13# Lesser General Public License for more details.
14#
15# You should have received a copy of the GNU Lesser General Public
16# License along with this library; if not, write to the Free Software
17# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18# 02110-1301 USA
19
20"""Bitcoin address.
21
22A Bitcoin address is an identifier that is used as destination in a Bitcoin
23transaction. It is based on a hash of the public portion of a keypair.
24
25There are currently three address formats in use:
26
27* P2PKH: pay to pubkey hash
28* P2SH: pay to script hash
29* Bech32
30
31More information:
32
33* https://en.bitcoin.it/wiki/Address
34
35>>> validate('1NEDqZPvTWRaoho48qXuLLsrYomMXPABfD')
36'1NEDqZPvTWRaoho48qXuLLsrYomMXPABfD'
37>>> validate('BC1QARDV855YJNGSPVXUTTQ897AQCA3LXJU2Y69JCE')
38'bc1qardv855yjngspvxuttq897aqca3lxju2y69jce'
39>>> validate('1NEDqZPvTWRaoho48qXuLLsrYomMXPABfX')
40Traceback (most recent call last):
41    ...
42InvalidChecksum: ...
43"""
44
45import hashlib
46import struct
47from functools import reduce
48
49from stdnum.exceptions import *
50from stdnum.util import clean
51
52
53def compact(number):
54    """Convert the number to the minimal representation. This strips the
55    number of any valid separators and removes surrounding whitespace."""
56    number = clean(number, ' ').strip()
57    if number[:3].lower() == 'bc1':
58        number = number.lower()
59    return number
60
61
62# Base58 encoding character set as used in Bitcoin addresses
63_base58_alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
64
65
66def b58decode(s):
67    """Decode a Base58 encoded string to a bytestring."""
68    value = reduce(lambda a, c: a * 58 + _base58_alphabet.index(c), s, 0)
69    result = b''
70    while value >= 256:
71        value, mod = divmod(value, 256)
72        result = struct.pack('B', mod) + result
73    result = struct.pack('B', value) + result
74    return struct.pack('B', 0) * (len(s) - len(s.lstrip('1'))) + result
75
76
77# Bech32 character set as used in Bitcoin addresses
78_bech32_alphabet = 'qpzry9x8gf2tvdw0s3jn54khce6mua7l'
79
80
81# The Bech32 generator tests and values for checksum calculation
82_bech32_generator = (
83    (1 << 0, 0x3b6a57b2), (1 << 1, 0x26508e6d), (1 << 2, 0x1ea119fa),
84    (1 << 3, 0x3d4233dd), (1 << 4, 0x2a1462b3))
85
86
87def bech32_checksum(values):
88    """Calculate the Bech32 checksum."""
89    chk = 1
90    for value in values:
91        top = chk >> 25
92        chk = (chk & 0x1ffffff) << 5 | value
93        for t, v in _bech32_generator:
94            chk ^= v if top & t else 0
95    return chk
96
97
98def b32decode(data):
99    """Decode a list of Base32 values to a bytestring."""
100    acc, bits = 0, 0
101    result = b''
102    for value in data:
103        acc = ((acc << 5) | value) & 0xfff
104        bits += 5
105        if bits >= 8:
106            bits -= 8
107            result = result + struct.pack('B', (acc >> bits) & 0xff)
108    if bits >= 5 or acc & ((1 << bits) - 1):
109        raise InvalidComponent()
110    return result
111
112
113def _expand_hrp(hrp):
114    """Convert the human-readable part to format for checksum calculation."""
115    return [ord(c) >> 5 for c in hrp] + [0] + [ord(c) & 31 for c in hrp]
116
117
118def validate(number):
119    """Check if the number provided is valid. This checks the length and
120    check digit."""
121    number = compact(number)
122    if number.startswith('1') or number.startswith('3'):
123        # P2PKH (pay to pubkey hash) or P2SH (pay to script hash) address
124        if not all(x in _base58_alphabet for x in number):
125            raise InvalidFormat()
126        address = b58decode(number)
127        if len(address) != 25:
128            raise InvalidLength()
129        if hashlib.sha256(hashlib.sha256(address[:-4]).digest()).digest()[:4] != address[-4:]:
130            raise InvalidChecksum()
131    elif number.startswith('bc1'):
132        # Bech32 type address
133        if not all(x in _bech32_alphabet for x in number[3:]):
134            raise InvalidFormat()
135        if len(number) < 11 or len(number) > 90:
136            raise InvalidLength()
137        data = [_bech32_alphabet.index(x) for x in number[3:]]
138        if bech32_checksum(_expand_hrp('bc') + data) != 1:
139            raise InvalidChecksum()
140        witness_version = data[0]
141        witness_program = b32decode(data[1:-6])
142        if witness_version > 16:
143            raise InvalidComponent()
144        if len(witness_program) < 2 or len(witness_program) > 40:
145            raise InvalidLength()
146        if witness_version == 0 and len(witness_program) not in (20, 32):
147            raise InvalidLength()
148    else:
149        raise InvalidComponent()
150    return number
151
152
153def is_valid(number):
154    """Check if the number provided is valid. This checks the length and
155    check digit."""
156    try:
157        return bool(validate(number))
158    except ValidationError:
159        return False
160