lib/bitcoin.py

   1 # -*- coding: utf-8 -*-
   2 #!/usr/bin/env python
   3 #
   4 # Electrum - lightweight Bitcoin client
   5 # Copyright (C) 2011 thomasv@gitorious
   6 #
   7 # This program is free software: you can redistribute it and/or modify
   8 # it under the terms of the GNU General Public License as published by
   9 # the Free Software Foundation, either version 3 of the License, or
  10 # (at your option) any later version.
  11 #
  12 # This program is distributed in the hope that it will be useful,
  13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15 # GNU General Public License for more details.
  16 #
  17 # You should have received a copy of the GNU General Public License
  18 # along with this program. If not, see <http://www.gnu.org/licenses/>.
  19
  20 import hashlib
  21 import base64
  22 import re
  23 import sys
  24 import hmac
  25
  26 from util import print_error
  27 from version import SEED_PREFIX
  28
  29 try:
  30     import ecdsa
  31 except ImportError:
  32     sys.exit("Error: python-ecdsa does not seem to be installed. Try 'sudo pip install ecdsa'")
  33
  34 try:
  35     import aes
  36 except ImportError:
  37     sys.exit("Error: AES does not seem to be installed. Try 'sudo pip install slowaes'")
  38
  39 ################################## transactions
  40
  41 MIN_RELAY_TX_FEE = 1000
  42
  43
  44 # AES encryption
  45 EncodeAES = lambda secret, s: base64.b64encode(aes.encryptData(secret,s))
  46 DecodeAES = lambda secret, e: aes.decryptData(secret, base64.b64decode(e))
  47
  48
  49 def pw_encode(s, password):
  50     if password:
  51         secret = Hash(password)
  52         return EncodeAES(secret, s.encode("utf8"))
  53     else:
  54         return s
  55
  56
  57 def pw_decode(s, password):
  58     if password is not None:
  59         secret = Hash(password)
  60         try:
  61             d = DecodeAES(secret, s).decode("utf8")
  62         except Exception:
  63             raise Exception('Invalid password')
  64         return d
  65     else:
  66         return s
  67
  68
  69 def rev_hex(s):
  70     return s.decode('hex')[::-1].encode('hex')
  71
  72
  73 def int_to_hex(i, length=1):
  74     s = hex(i)[2:].rstrip('L')
  75     s = "0"*(2*length - len(s)) + s
  76     return rev_hex(s)
  77
  78
  79 def var_int(i):
  80     # https://en.bitcoin.it/wiki/Protocol_specification#Variable_length_integer
  81     if i<0xfd:
  82         return int_to_hex(i)
  83     elif i<=0xffff:
  84         return "fd"+int_to_hex(i,2)
  85     elif i<=0xffffffff:
  86         return "fe"+int_to_hex(i,4)
  87     else:
  88         return "ff"+int_to_hex(i,8)
  89
  90
  91 def op_push(i):
  92     if i<0x4c:
  93         return int_to_hex(i)
  94     elif i<0xff:
  95         return '4c' + int_to_hex(i)
  96     elif i<0xffff:
  97         return '4d' + int_to_hex(i,2)
  98     else:
  99         return '4e' + int_to_hex(i,4)
 100
 101
 102 def sha256(x):
 103     return hashlib.sha256(x).digest()
 104
 105
 106 def Hash(x):
 107     if type(x) is unicode: x=x.encode('utf-8')
 108     return sha256(sha256(x))
 109
 110
 111 hash_encode = lambda x: x[::-1].encode('hex')
 112 hash_decode = lambda x: x.decode('hex')[::-1]
 113 hmac_sha_512 = lambda x,y: hmac.new(x, y, hashlib.sha512).digest()
 114
 115
 116 def mnemonic_to_seed(mnemonic, passphrase):
 117     from pbkdf2 import PBKDF2
 118     import hmac
 119     PBKDF2_ROUNDS = 2048
 120     return PBKDF2(mnemonic, 'mnemonic' + passphrase, iterations = PBKDF2_ROUNDS, macmodule = hmac, digestmodule = hashlib.sha512).read(64)
 121
 122
 123 is_new_seed = lambda x: hmac_sha_512("Seed version", x.encode('utf8')).encode('hex')[0:2].startswith(SEED_PREFIX)
 124
 125 def is_old_seed(seed):
 126     import mnemonic
 127     words = seed.strip().split()
 128     try:
 129         mnemonic.mn_decode(words)
 130         uses_electrum_words = True
 131     except Exception:
 132         uses_electrum_words = False
 133
 134     try:
 135         seed.decode('hex')
 136         is_hex = (len(seed) == 32)
 137     except Exception:
 138         is_hex = False
 139
 140     return is_hex or (uses_electrum_words and len(words) == 12)
 141
 142
 143 # pywallet openssl private key implementation
 144
 145 def i2d_ECPrivateKey(pkey, compressed=False):
 146     if compressed:
 147         key = '3081d30201010420' + \
 148               '%064x' % pkey.secret + \
 149               'a081a53081a2020101302c06072a8648ce3d0101022100' + \
 150               '%064x' % _p + \
 151               '3006040100040107042102' + \
 152               '%064x' % _Gx + \
 153               '022100' + \
 154               '%064x' % _r + \
 155               '020101a124032200'
 156     else:
 157         key = '308201130201010420' + \
 158               '%064x' % pkey.secret + \
 159               'a081a53081a2020101302c06072a8648ce3d0101022100' + \
 160               '%064x' % _p + \
 161               '3006040100040107044104' + \
 162               '%064x' % _Gx + \
 163               '%064x' % _Gy + \
 164               '022100' + \
 165               '%064x' % _r + \
 166               '020101a144034200'
 167
 168     return key.decode('hex') + i2o_ECPublicKey(pkey.pubkey, compressed)
 169
 170 def i2o_ECPublicKey(pubkey, compressed=False):
 171     # public keys are 65 bytes long (520 bits)
 172     # 0x04 + 32-byte X-coordinate + 32-byte Y-coordinate
 173     # 0x00 = point at infinity, 0x02 and 0x03 = compressed, 0x04 = uncompressed
 174     # compressed keys: <sign> <x> where <sign> is 0x02 if y is even and 0x03 if y is odd
 175     if compressed:
 176         if pubkey.point.y() & 1:
 177             key = '03' + '%064x' % pubkey.point.x()
 178         else:
 179             key = '02' + '%064x' % pubkey.point.x()
 180     else:
 181         key = '04' + \
 182               '%064x' % pubkey.point.x() + \
 183               '%064x' % pubkey.point.y()
 184
 185     return key.decode('hex')
 186
 187 # end pywallet openssl private key implementation
 188
 189
 190
 191 ############ functions from pywallet #####################
 192
 193 def hash_160(public_key):
 194     try:
 195         md = hashlib.new('ripemd160')
 196         md.update(sha256(public_key))
 197         return md.digest()
 198     except Exception:
 199         import ripemd
 200         md = ripemd.new(sha256(public_key))
 201         return md.digest()
 202
 203
 204 def public_key_to_bc_address(public_key):
 205     h160 = hash_160(public_key)
 206     return hash_160_to_bc_address(h160)
 207
 208 def hash_160_to_bc_address(h160, addrtype = 0):
 209     vh160 = chr(addrtype) + h160
 210     h = Hash(vh160)
 211     addr = vh160 + h[0:4]
 212     return b58encode(addr)
 213
 214 def bc_address_to_hash_160(addr):
 215     bytes = b58decode(addr, 25)
 216     return ord(bytes[0]), bytes[1:21]
 217
 218
 219 __b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
 220 __b58base = len(__b58chars)
 221
 222
 223 def b58encode(v):
 224     """ encode v, which is a string of bytes, to base58."""
 225
 226     long_value = 0L
 227     for (i, c) in enumerate(v[::-1]):
 228         long_value += (256**i) * ord(c)
 229
 230     result = ''
 231     while long_value >= __b58base:
 232         div, mod = divmod(long_value, __b58base)
 233         result = __b58chars[mod] + result
 234         long_value = div
 235     result = __b58chars[long_value] + result
 236
 237     # Bitcoin does a little leading-zero-compression:
 238     # leading 0-bytes in the input become leading-1s
 239     nPad = 0
 240     for c in v:
 241         if c == '\0': nPad += 1
 242         else: break
 243
 244     return (__b58chars[0]*nPad) + result
 245
 246
 247 def b58decode(v, length):
 248     """ decode v into a string of len bytes."""
 249     long_value = 0L
 250     for (i, c) in enumerate(v[::-1]):
 251         long_value += __b58chars.find(c) * (__b58base**i)
 252
 253     result = ''
 254     while long_value >= 256:
 255         div, mod = divmod(long_value, 256)
 256         result = chr(mod) + result
 257         long_value = div
 258     result = chr(long_value) + result
 259
 260     nPad = 0
 261     for c in v:
 262         if c == __b58chars[0]: nPad += 1
 263         else: break
 264
 265     result = chr(0)*nPad + result
 266     if length is not None and len(result) != length:
 267         return None
 268
 269     return result
 270
 271
 272 def EncodeBase58Check(vchIn):
 273     hash = Hash(vchIn)
 274     return b58encode(vchIn + hash[0:4])
 275
 276
 277 def DecodeBase58Check(psz):
 278     vchRet = b58decode(psz, None)
 279     key = vchRet[0:-4]
 280     csum = vchRet[-4:]
 281     hash = Hash(key)
 282     cs32 = hash[0:4]
 283     if cs32 != csum:
 284         return None
 285     else:
 286         return key
 287
 288
 289 def PrivKeyToSecret(privkey):
 290     return privkey[9:9+32]
 291
 292
 293 def SecretToASecret(secret, compressed=False, addrtype=0):
 294     vchIn = chr((addrtype+128)&255) + secret
 295     if compressed: vchIn += '\01'
 296     return EncodeBase58Check(vchIn)
 297
 298 def ASecretToSecret(key, addrtype=0):
 299     vch = DecodeBase58Check(key)
 300     if vch and vch[0] == chr((addrtype+128)&255):
 301         return vch[1:]
 302     else:
 303         return False
 304
 305 def regenerate_key(sec):
 306     b = ASecretToSecret(sec)
 307     if not b:
 308         return False
 309     b = b[0:32]
 310     return EC_KEY(b)
 311
 312
 313 def GetPubKey(pubkey, compressed=False):
 314     return i2o_ECPublicKey(pubkey, compressed)
 315
 316
 317 def GetPrivKey(pkey, compressed=False):
 318     return i2d_ECPrivateKey(pkey, compressed)
 319
 320
 321 def GetSecret(pkey):
 322     return ('%064x' % pkey.secret).decode('hex')
 323
 324
 325 def is_compressed(sec):
 326     b = ASecretToSecret(sec)
 327     return len(b) == 33
 328
 329
 330 def public_key_from_private_key(sec):
 331     # rebuild public key from private key, compressed or uncompressed
 332     pkey = regenerate_key(sec)
 333     assert pkey
 334     compressed = is_compressed(sec)
 335     public_key = GetPubKey(pkey.pubkey, compressed)
 336     return public_key.encode('hex')
 337
 338
 339 def address_from_private_key(sec):
 340     public_key = public_key_from_private_key(sec)
 341     address = public_key_to_bc_address(public_key.decode('hex'))
 342     return address
 343
 344
 345 def is_valid(addr):
 346     return is_address(addr)
 347
 348
 349 def is_address(addr):
 350     ADDRESS_RE = re.compile('[1-9A-HJ-NP-Za-km-z]{26,}\\Z')
 351     if not ADDRESS_RE.match(addr): return False
 352     try:
 353         addrtype, h = bc_address_to_hash_160(addr)
 354     except Exception:
 355         return False
 356     return addr == hash_160_to_bc_address(h, addrtype)
 357
 358
 359 def is_private_key(key):
 360     try:
 361         k = ASecretToSecret(key)
 362         return k is not False
 363     except:
 364         return False
 365
 366
 367 ########### end pywallet functions #######################
 368
 369 try:
 370     from ecdsa.ecdsa import curve_secp256k1, generator_secp256k1
 371 except Exception:
 372     print "cannot import ecdsa.curve_secp256k1. You probably need to upgrade ecdsa.\nTry: sudo pip install --upgrade ecdsa"
 373     exit()
 374
 375 from ecdsa.curves import SECP256k1
 376 from ecdsa.ellipticcurve import Point
 377 from ecdsa.util import string_to_number, number_to_string
 378
 379 def msg_magic(message):
 380     varint = var_int(len(message))
 381     encoded_varint = "".join([chr(int(varint[i:i+2], 16)) for i in xrange(0, len(varint), 2)])
 382     return "\x18Bitcoin Signed Message:\n" + encoded_varint + message
 383
 384
 385 def verify_message(address, signature, message):
 386     try:
 387         EC_KEY.verify_message(address, signature, message)
 388         return True
 389     except Exception as e:
 390         print_error("Verification error: {0}".format(e))
 391         return False
 392
 393
 394 def encrypt_message(message, pubkey):
 395     return EC_KEY.encrypt_message(message, pubkey.decode('hex'))
 396
 397
 398 def chunks(l, n):
 399     return [l[i:i+n] for i in xrange(0, len(l), n)]
 400
 401
 402 def ECC_YfromX(x,curved=curve_secp256k1, odd=True):
 403     _p = curved.p()
 404     _a = curved.a()
 405     _b = curved.b()
 406     for offset in range(128):
 407         Mx = x + offset
 408         My2 = pow(Mx, 3, _p) + _a * pow(Mx, 2, _p) + _b % _p
 409         My = pow(My2, (_p+1)/4, _p )
 410
 411         if curved.contains_point(Mx,My):
 412             if odd == bool(My&1):
 413                 return [My,offset]
 414             return [_p-My,offset]
 415     raise Exception('ECC_YfromX: No Y found')
 416
 417
 418 def negative_point(P):
 419     return Point( P.curve(), P.x(), -P.y(), P.order() )
 420
 421
 422 def point_to_ser(P, comp=True ):
 423     if comp:
 424         return ( ('%02x'%(2+(P.y()&1)))+('%064x'%P.x()) ).decode('hex')
 425     return ( '04'+('%064x'%P.x())+('%064x'%P.y()) ).decode('hex')
 426
 427
 428 def ser_to_point(Aser):
 429     curve = curve_secp256k1
 430     generator = generator_secp256k1
 431     _r  = generator.order()
 432     assert Aser[0] in ['\x02','\x03','\x04']
 433     if Aser[0] == '\x04':
 434         return Point( curve, string_to_number(Aser[1:33]), string_to_number(Aser[33:]), _r )
 435     Mx = string_to_number(Aser[1:])
 436     return Point( curve, Mx, ECC_YfromX(Mx, curve, Aser[0]=='\x03')[0], _r )
 437
 438
 439
 440 class MyVerifyingKey(ecdsa.VerifyingKey):
 441     @classmethod
 442     def from_signature(klass, sig, recid, h, curve):
 443         """ See http://www.secg.org/download/aid-780/sec1-v2.pdf, chapter 4.1.6 """
 444         from ecdsa import util, numbertheory
 445         import msqr
 446         curveFp = curve.curve
 447         G = curve.generator
 448         order = G.order()
 449         # extract r,s from signature
 450         r, s = util.sigdecode_string(sig, order)
 451         # 1.1
 452         x = r + (recid/2) * order
 453         # 1.3
 454         alpha = ( x * x * x  + curveFp.a() * x + curveFp.b() ) % curveFp.p()
 455         beta = msqr.modular_sqrt(alpha, curveFp.p())
 456         y = beta if (beta - recid) % 2 == 0 else curveFp.p() - beta
 457         # 1.4 the constructor checks that nR is at infinity
 458         R = Point(curveFp, x, y, order)
 459         # 1.5 compute e from message:
 460         e = string_to_number(h)
 461         minus_e = -e % order
 462         # 1.6 compute Q = r^-1 (sR - eG)
 463         inv_r = numbertheory.inverse_mod(r,order)
 464         Q = inv_r * ( s * R + minus_e * G )
 465         return klass.from_public_point( Q, curve )
 466
 467
 468 class EC_KEY(object):
 469     def __init__( self, k ):
 470         secret = string_to_number(k)
 471         self.pubkey = ecdsa.ecdsa.Public_key( generator_secp256k1, generator_secp256k1 * secret )
 472         self.privkey = ecdsa.ecdsa.Private_key( self.pubkey, secret )
 473         self.secret = secret
 474
 475     def get_public_key(self, compressed=True):
 476         return point_to_ser(self.pubkey.point, compressed).encode('hex')
 477
 478     def sign_message(self, message, compressed, address):
 479         private_key = ecdsa.SigningKey.from_secret_exponent( self.secret, curve = SECP256k1 )
 480         public_key = private_key.get_verifying_key()
 481         signature = private_key.sign_digest_deterministic( Hash( msg_magic(message) ), hashfunc=hashlib.sha256, sigencode = ecdsa.util.sigencode_string )
 482         assert public_key.verify_digest( signature, Hash( msg_magic(message) ), sigdecode = ecdsa.util.sigdecode_string)
 483         for i in range(4):
 484             sig = base64.b64encode( chr(27 + i + (4 if compressed else 0)) + signature )
 485             try:
 486                 self.verify_message( address, sig, message)
 487                 return sig
 488             except Exception:
 489                 continue
 490         else:
 491             raise Exception("error: cannot sign message")
 492
 493
 494     @classmethod
 495     def verify_message(self, address, signature, message):
 496         sig = base64.b64decode(signature)
 497         if len(sig) != 65: raise Exception("Wrong encoding")
 498
 499         nV = ord(sig[0])
 500         if nV < 27 or nV >= 35:
 501             raise Exception("Bad encoding")
 502         if nV >= 31:
 503             compressed = True
 504             nV -= 4
 505         else:
 506             compressed = False
 507
 508         recid = nV - 27
 509         h = Hash( msg_magic(message) )
 510         public_key = MyVerifyingKey.from_signature( sig[1:], recid, h, curve = SECP256k1 )
 511
 512         # check public key
 513         public_key.verify_digest( sig[1:], h, sigdecode = ecdsa.util.sigdecode_string)
 514
 515         # check that we get the original signing address
 516         addr = public_key_to_bc_address( point_to_ser(public_key.pubkey.point, compressed) )
 517         if address != addr:
 518             raise Exception("Bad signature")
 519
 520
 521     # ecies encryption/decryption methods; aes-256-cbc is used as the cipher; hmac-sha256 is used as the mac
 522
 523     @classmethod
 524     def encrypt_message(self, message, pubkey):
 525
 526         pk = ser_to_point(pubkey)
 527         if not ecdsa.ecdsa.point_is_valid(generator_secp256k1, pk.x(), pk.y()):
 528             raise Exception('invalid pubkey')
 529
 530         ephemeral_exponent = number_to_string(ecdsa.util.randrange(pow(2,256)), generator_secp256k1.order())
 531         ephemeral = EC_KEY(ephemeral_exponent)
 532
 533         ecdh_key = (pk * ephemeral.privkey.secret_multiplier).x()
 534         ecdh_key = ('%064x' % ecdh_key).decode('hex')
 535         key = hashlib.sha512(ecdh_key).digest()
 536         key_e, key_m = key[:32], key[32:]
 537
 538         iv_ciphertext = aes.encryptData(key_e, message)
 539
 540         ephemeral_pubkey = ephemeral.get_public_key(compressed=True).decode('hex')
 541         encrypted = 'BIE1' + ephemeral_pubkey + iv_ciphertext
 542         mac = hmac.new(key_m, encrypted, hashlib.sha256).digest()
 543
 544         return base64.b64encode(encrypted + mac)
 545
 546
 547     def decrypt_message(self, encrypted):
 548
 549         encrypted = base64.b64decode(encrypted)
 550
 551         if len(encrypted) < 85:
 552             raise Exception('invalid ciphertext: length')
 553
 554         magic = encrypted[:4]
 555         ephemeral_pubkey = encrypted[4:37]
 556         iv_ciphertext = encrypted[37:-32]
 557         mac = encrypted[-32:]
 558
 559         if magic != 'BIE1':
 560             raise Exception('invalid ciphertext: invalid magic bytes')
 561
 562         try:
 563             ephemeral_pubkey = ser_to_point(ephemeral_pubkey)
 564         except AssertionError, e:
 565             raise Exception('invalid ciphertext: invalid ephemeral pubkey')
 566
 567         if not ecdsa.ecdsa.point_is_valid(generator_secp256k1, ephemeral_pubkey.x(), ephemeral_pubkey.y()):
 568             raise Exception('invalid ciphertext: invalid ephemeral pubkey')
 569
 570         ecdh_key = (ephemeral_pubkey * self.privkey.secret_multiplier).x()
 571         ecdh_key = ('%064x' % ecdh_key).decode('hex')
 572         key = hashlib.sha512(ecdh_key).digest()
 573         key_e, key_m = key[:32], key[32:]
 574         if mac != hmac.new(key_m, encrypted[:-32], hashlib.sha256).digest():
 575             raise Exception('invalid ciphertext: invalid mac')
 576
 577         return aes.decryptData(key_e, iv_ciphertext)
 578
 579
 580 ###################################### BIP32 ##############################
 581
 582 random_seed = lambda n: "%032x"%ecdsa.util.randrange( pow(2,n) )
 583 BIP32_PRIME = 0x80000000
 584
 585
 586 def get_pubkeys_from_secret(secret):
 587     # public key
 588     private_key = ecdsa.SigningKey.from_string( secret, curve = SECP256k1 )
 589     public_key = private_key.get_verifying_key()
 590     K = public_key.to_string()
 591     K_compressed = GetPubKey(public_key.pubkey,True)
 592     return K, K_compressed
 593
 594
 595 # Child private key derivation function (from master private key)
 596 # k = master private key (32 bytes)
 597 # c = master chain code (extra entropy for key derivation) (32 bytes)
 598 # n = the index of the key we want to derive. (only 32 bits will be used)
 599 # If n is negative (i.e. the 32nd bit is set), the resulting private key's
 600 #  corresponding public key can NOT be determined without the master private key.
 601 # However, if n is positive, the resulting private key's corresponding
 602 #  public key can be determined without the master private key.
 603 def CKD_priv(k, c, n):
 604     is_prime = n & BIP32_PRIME
 605     return _CKD_priv(k, c, rev_hex(int_to_hex(n,4)).decode('hex'), is_prime)
 606
 607 def _CKD_priv(k, c, s, is_prime):
 608     import hmac
 609     from ecdsa.util import string_to_number, number_to_string
 610     order = generator_secp256k1.order()
 611     keypair = EC_KEY(k)
 612     cK = GetPubKey(keypair.pubkey,True)
 613     data = chr(0) + k + s if is_prime else cK + s
 614     I = hmac.new(c, data, hashlib.sha512).digest()
 615     k_n = number_to_string( (string_to_number(I[0:32]) + string_to_number(k)) % order , order )
 616     c_n = I[32:]
 617     return k_n, c_n
 618
 619 # Child public key derivation function (from public key only)
 620 # K = master public key
 621 # c = master chain code
 622 # n = index of key we want to derive
 623 # This function allows us to find the nth public key, as long as n is
 624 #  non-negative. If n is negative, we need the master private key to find it.
 625 def CKD_pub(cK, c, n):
 626     if n & BIP32_PRIME: raise
 627     return _CKD_pub(cK, c, rev_hex(int_to_hex(n,4)).decode('hex'))
 628
 629 # helper function, callable with arbitrary string
 630 def _CKD_pub(cK, c, s):
 631     import hmac
 632     from ecdsa.util import string_to_number, number_to_string
 633     order = generator_secp256k1.order()
 634     I = hmac.new(c, cK + s, hashlib.sha512).digest()
 635     curve = SECP256k1
 636     pubkey_point = string_to_number(I[0:32])*curve.generator + ser_to_point(cK)
 637     public_key = ecdsa.VerifyingKey.from_public_point( pubkey_point, curve = SECP256k1 )
 638     c_n = I[32:]
 639     cK_n = GetPubKey(public_key.pubkey,True)
 640     return cK_n, c_n
 641
 642
 643 BITCOIN_HEADERS = ["0488ade4", "0488b21e"]
 644 TESTNET_HEADERS = ["043587cf", "04358394"]
 645
 646 BITCOIN_HEAD = "0488ade4"
 647 TESTNET_HEAD = "04358394"
 648
 649 BITCOIN_HEADER_PRIV = "0488ADE4"
 650 BITCOIN_HEADER_PUB = "0488B21E"
 651
 652 TESTNET_HEADER_PRIV = "04358394"
 653 TESTNET_HEADER_PUB = "043587CF"
 654
 655
 656 def _get_headers(testnet):
 657     """Returns the correct headers for either testnet or bitcoin, in the form
 658     of a 2-tuple, like (public, private)."""
 659     if testnet:
 660         return (TESTNET_HEADER_PUB, TESTNET_HEADER_PRIV)
 661     else:
 662         return (BITCOIN_HEADER_PUB, BITCOIN_HEADER_PRIV)
 663
 664
 665 def deserialize_xkey(xkey):
 666
 667     xkey = DecodeBase58Check(xkey)
 668     assert len(xkey) == 78
 669
 670     xkey_header = xkey[0:4].encode('hex')
 671     # Determine if the key is a bitcoin key or a testnet key.
 672     if xkey_header in TESTNET_HEADERS:
 673         head = TESTNET_HEAD
 674     elif xkey_header in BITCOIN_HEADERS:
 675         head = BITCOIN_HEAD
 676     else:
 677         raise Exception("Unknown xkey header: '%s'" % xkey_header)
 678
 679     depth = ord(xkey[4])
 680     fingerprint = xkey[5:9]
 681     child_number = xkey[9:13]
 682     c = xkey[13:13+32]
 683     if xkey[0:4].encode('hex') == head:
 684         K_or_k = xkey[13+33:]
 685     else:
 686         K_or_k = xkey[13+32:]
 687     return depth, fingerprint, child_number, c, K_or_k
 688
 689
 690 def get_xkey_name(xkey, testnet=False):
 691     depth, fingerprint, child_number, c, K = deserialize_xkey(xkey)
 692     n = int(child_number.encode('hex'), 16)
 693     if n & BIP32_PRIME:
 694         child_id = "%d'"%(n - BIP32_PRIME)
 695     else:
 696         child_id = "%d"%n
 697     if depth == 0:
 698         return ''
 699     elif depth == 1:
 700         return child_id
 701     else:
 702         raise BaseException("xpub depth error")
 703
 704
 705 def xpub_from_xprv(xprv, testnet=False):
 706     depth, fingerprint, child_number, c, k = deserialize_xkey(xprv)
 707     K, cK = get_pubkeys_from_secret(k)
 708     header_pub, _  = _get_headers(testnet)
 709     xpub = header_pub.decode('hex') + chr(depth) + fingerprint + child_number + c + cK
 710     return EncodeBase58Check(xpub)
 711
 712
 713 def bip32_root(seed, testnet=False):
 714     import hmac
 715     header_pub, header_priv = _get_headers(testnet)
 716     seed = seed.decode('hex')
 717     I = hmac.new("Bitcoin seed", seed, hashlib.sha512).digest()
 718     master_k = I[0:32]
 719     master_c = I[32:]
 720     K, cK = get_pubkeys_from_secret(master_k)
 721     xprv = (header_priv + "00" + "00000000" + "00000000").decode("hex") + master_c + chr(0) + master_k
 722     xpub = (header_pub + "00" + "00000000" + "00000000").decode("hex") + master_c + cK
 723     return EncodeBase58Check(xprv), EncodeBase58Check(xpub)
 724
 725
 726 def bip32_private_derivation(xprv, branch, sequence, testnet=False):
 727     header_pub, header_priv = _get_headers(testnet)
 728     depth, fingerprint, child_number, c, k = deserialize_xkey(xprv)
 729     assert sequence.startswith(branch)
 730     sequence = sequence[len(branch):]
 731     for n in sequence.split('/'):
 732         if n == '': continue
 733         i = int(n[:-1]) + BIP32_PRIME if n[-1] == "'" else int(n)
 734         parent_k = k
 735         k, c = CKD_priv(k, c, i)
 736         depth += 1
 737
 738     _, parent_cK = get_pubkeys_from_secret(parent_k)
 739     fingerprint = hash_160(parent_cK)[0:4]
 740     child_number = ("%08X"%i).decode('hex')
 741     K, cK = get_pubkeys_from_secret(k)
 742     xprv = header_priv.decode('hex') + chr(depth) + fingerprint + child_number + c + chr(0) + k
 743     xpub = header_pub.decode('hex') + chr(depth) + fingerprint + child_number + c + cK
 744     return EncodeBase58Check(xprv), EncodeBase58Check(xpub)
 745
 746
 747 def bip32_public_derivation(xpub, branch, sequence, testnet=False):
 748     header_pub, _ = _get_headers(testnet)
 749     depth, fingerprint, child_number, c, cK = deserialize_xkey(xpub)
 750     assert sequence.startswith(branch)
 751     sequence = sequence[len(branch):]
 752     for n in sequence.split('/'):
 753         if n == '': continue
 754         i = int(n)
 755         parent_cK = cK
 756         cK, c = CKD_pub(cK, c, i)
 757         depth += 1
 758
 759     fingerprint = hash_160(parent_cK)[0:4]
 760     child_number = ("%08X"%i).decode('hex')
 761     xpub = header_pub.decode('hex') + chr(depth) + fingerprint + child_number + c + cK
 762     return EncodeBase58Check(xpub)
 763
 764
 765 def bip32_private_key(sequence, k, chain):
 766     for i in sequence:
 767         k, chain = CKD_priv(k, chain, i)
 768     return SecretToASecret(k, True)