data-driven base58 CBitcoinAddress/CBitcoinSecret tests

Arbitrary numbers of test vectors can be generated using the script
`gen_base58_test_vectors.py`.

3 files changed, 231 insertions, 0 deletions

diff --git a/contrib/testgen/README b/contrib/testgen/README
new file mode 100644
index 0000000000..02d6c4cdc2
--- /dev/null
+++ b/contrib/testgen/README
@@ -0,0 +1 @@
+Utilities to generate test vectors for the data-driven Bitcoin tests
diff --git a/contrib/testgen/base58.py b/contrib/testgen/base58.py
new file mode 100644
index 0000000000..b716495145
--- /dev/null
+++ b/contrib/testgen/base58.py
@@ -0,0 +1,104 @@
+'''
+Bitcoin base58 encoding and decoding.
+
+Based on https://bitcointalk.org/index.php?topic=1026.0 (public domain)
+'''
+import hashlib
+
+# for compatibility with following code...
+class SHA256:
+    new = hashlib.sha256
+
+if str != bytes:
+    # Python 3.x
+    def ord(c):
+        return c
+    def chr(n):
+        return bytes( (n,) )
+
+__b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
+__b58base = len(__b58chars)
+b58chars = __b58chars
+
+def b58encode(v):
+    """ encode v, which is a string of bytes, to base58.
+    """
+    long_value = 0
+    for (i, c) in enumerate(v[::-1]):
+        long_value += (256**i) * ord(c)
+
+    result = ''
+    while long_value >= __b58base:
+        div, mod = divmod(long_value, __b58base)
+        result = __b58chars[mod] + result
+        long_value = div
+    result = __b58chars[long_value] + result
+
+    # Bitcoin does a little leading-zero-compression:
+    # leading 0-bytes in the input become leading-1s
+    nPad = 0
+    for c in v:
+        if c == '\0': nPad += 1
+        else: break
+
+    return (__b58chars[0]*nPad) + result
+
+def b58decode(v, length = None):
+    """ decode v into a string of len bytes
+    """
+    long_value = 0
+    for (i, c) in enumerate(v[::-1]):
+        long_value += __b58chars.find(c) * (__b58base**i)
+
+    result = bytes()
+    while long_value >= 256:
+        div, mod = divmod(long_value, 256)
+        result = chr(mod) + result
+        long_value = div
+    result = chr(long_value) + result
+
+    nPad = 0
+    for c in v:
+        if c == __b58chars[0]: nPad += 1
+        else: break
+
+    result = chr(0)*nPad + result
+    if length is not None and len(result) != length:
+        return None
+
+    return result
+
+def checksum(v):
+    """Return 32-bit checksum based on SHA256"""
+    return SHA256.new(SHA256.new(v).digest()).digest()[0:4]
+
+def b58encode_chk(v):
+    """b58encode a string, with 32-bit checksum"""
+    return b58encode(v + checksum(v))
+
+def b58decode_chk(v):
+    """decode a base58 string, check and remove checksum"""
+    result = b58decode(v)
+    if result is None:
+        return None
+    h3 = checksum(result[:-4])
+    if result[-4:] == checksum(result[:-4]):
+        return result[:-4]
+    else:
+        return None
+
+def get_bcaddress_version(strAddress):
+    """ Returns None if strAddress is invalid.  Otherwise returns integer version of address. """
+    addr = b58decode_chk(strAddress)
+    if addr is None or len(addr)!=21: return None
+    version = addr[0]
+    return ord(version)
+
+if __name__ == '__main__':
+    # Test case (from http://gitorious.org/bitcoin/python-base58.git)
+    assert get_bcaddress_version('15VjRaDX9zpbA8LVnbrCAFzrVzN7ixHNsC') is 0
+    _ohai = 'o hai'.encode('ascii')
+    _tmp = b58encode(_ohai)
+    assert _tmp == 'DYB3oMS'
+    assert b58decode(_tmp, 5) == _ohai
+    print("Tests passed")
diff --git a/contrib/testgen/gen_base58_test_vectors.py b/contrib/testgen/gen_base58_test_vectors.py
new file mode 100755
index 0000000000..1813436953
--- /dev/null
+++ b/contrib/testgen/gen_base58_test_vectors.py
@@ -0,0 +1,126 @@
+#!/usr/bin/env python
+'''
+Generate valid and invalid base58 address and private key test vectors.
+
+Usage: 
+    gen_base58_test_vectors.py valid 50 > ../../src/test/data/base58_keys_valid.json
+    gen_base58_test_vectors.py invalid 50 > ../../src/test/data/base58_keys_invalid.json
+'''
+# 2012 Wladimir J. van der Laan
+# Released under MIT License
+import os
+from itertools import islice
+from base58 import b58encode, b58decode, b58encode_chk, b58decode_chk, b58chars
+import random
+from binascii import b2a_hex
+
+# key types
+PUBKEY_ADDRESS = 0
+SCRIPT_ADDRESS = 5
+PUBKEY_ADDRESS_TEST = 111
+SCRIPT_ADDRESS_TEST = 196
+PRIVKEY = 128
+PRIVKEY_TEST = 239
+
+metadata_keys = ['isPrivkey', 'isTestnet', 'addrType', 'isCompressed']
+# templates for valid sequences
+templates = [
+  # prefix, payload_size, suffix, metadata
+  #                                  None = N/A
+  ((PUBKEY_ADDRESS,),      20, (),   (False, False, 'pubkey', None)),
+  ((SCRIPT_ADDRESS,),      20, (),   (False, False, 'script',  None)),
+  ((PUBKEY_ADDRESS_TEST,), 20, (),   (False, True,  'pubkey', None)),
+  ((SCRIPT_ADDRESS_TEST,), 20, (),   (False, True,  'script',  None)),
+  ((PRIVKEY,),             32, (),   (True,  False, None,  False)),
+  ((PRIVKEY,),             32, (1,), (True,  False, None,  True)),
+  ((PRIVKEY_TEST,),        32, (),   (True,  True,  None,  False)),
+  ((PRIVKEY_TEST,),        32, (1,), (True,  True,  None,  True))
+]
+
+def is_valid(v):
+    '''Check vector v for validity'''
+    result = b58decode_chk(v)
+    if result is None:
+        return False
+    valid = False
+    for template in templates:
+        prefix = str(bytearray(template[0]))
+        suffix = str(bytearray(template[2]))
+        if result.startswith(prefix) and result.endswith(suffix):
+            if (len(result) - len(prefix) - len(suffix)) == template[1]:
+                return True
+    return False
+
+def gen_valid_vectors():
+    '''Generate valid test vectors'''
+    while True:
+        for template in templates:
+            prefix = str(bytearray(template[0]))
+            payload = os.urandom(template[1]) 
+            suffix = str(bytearray(template[2]))
+            rv = b58encode_chk(prefix + payload + suffix)
+            assert is_valid(rv)
+            metadata = dict([(x,y) for (x,y) in zip(metadata_keys,template[3]) if y is not None])
+            yield (rv, b2a_hex(payload), metadata)
+
+def gen_invalid_vector(template, corrupt_prefix, randomize_payload_size, corrupt_suffix):
+    '''Generate possibly invalid vector'''
+    if corrupt_prefix:
+        prefix = os.urandom(1)
+    else:
+        prefix = str(bytearray(template[0]))
+    
+    if randomize_payload_size:
+        payload = os.urandom(max(int(random.expovariate(0.5)), 50))
+    else:
+        payload = os.urandom(template[1])
+    
+    if corrupt_suffix:
+        suffix = os.urandom(len(template[2]))
+    else:
+        suffix = str(bytearray(template[2]))
+
+    return b58encode_chk(prefix + payload + suffix)
+
+def randbool(p = 0.5):
+    '''Return True with P(p)'''
+    return random.random() < p
+
+def gen_invalid_vectors():
+    '''Generate invalid test vectors'''
+    # start with some manual edge-cases
+    yield "",
+    yield "x",
+    while True:
+        # kinds of invalid vectors:
+        #   invalid prefix
+        #   invalid payload length
+        #   invalid (randomized) suffix (add random data)
+        #   corrupt checksum
+        for template in templates:
+            val = gen_invalid_vector(template, randbool(0.2), randbool(0.2), randbool(0.2))
+            if random.randint(0,10)<1: # line corruption
+                if randbool(): # add random character to end
+                    val += random.choice(b58chars)
+                else: # replace random character in the middle
+                    n = random.randint(0, len(val))
+                    val = val[0:n] + random.choice(b58chars) + val[n+1:]
+            if not is_valid(val):
+                yield val,
+
+if __name__ == '__main__':
+    import sys, json
+    iters = {'valid':gen_valid_vectors, 'invalid':gen_invalid_vectors}
+    try:
+        uiter = iters[sys.argv[1]]
+    except IndexError:
+        uiter = gen_valid_vectors
+    try:
+        count = int(sys.argv[2])
+    except IndexError:
+        count = 0
+   
+    data = list(islice(uiter(), count))
+    json.dump(data, sys.stdout, sort_keys=True, indent=4)
+    sys.stdout.write('\n')
+