main.py (14910B)
1 #!/usr/bin/python 2 from .py2specials import * 3 from .py3specials import * 4 import binascii 5 import hashlib 6 import re 7 import sys 8 import os 9 import base64 10 import time 11 import random 12 import hmac 13 14 is_python2 = sys.version_info.major == 2 15 16 # Elliptic curve parameters (secp256k1) 17 18 P = 2**256 - 2**32 - 977 19 N = 115792089237316195423570985008687907852837564279074904382605163141518161494337 20 A = 0 21 B = 7 22 Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 23 Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 24 G = (Gx, Gy) 25 26 # Extended Euclidean Algorithm 27 def inv(a, n): 28 lm, hm = 1, 0 29 low, high = a % n, n 30 while low > 1: 31 r = high // low 32 nm, new = hm - lm * r, high - low * r 33 lm, low, hm, high = nm, new, lm, low 34 return lm % n 35 36 # Elliptic curve Jordan form functions 37 # P = (m, n, p, q) where m/n = x, p/q = y 38 39 def isinf(p): 40 return p[0] == 0 and p[1] == 0 41 42 43 def jordan_isinf(p): 44 return p[0][0] == 0 and p[1][0] == 0 45 46 47 def mulcoords(c1, c2): 48 return (c1[0] * c2[0] % P, c1[1] * c2[1] % P) 49 50 51 def mul_by_const(c, v): 52 return (c[0] * v % P, c[1]) 53 54 55 def addcoords(c1, c2): 56 return ((c1[0] * c2[1] + c2[0] * c1[1]) % P, c1[1] * c2[1] % P) 57 58 59 def subcoords(c1, c2): 60 return ((c1[0] * c2[1] - c2[0] * c1[1]) % P, c1[1] * c2[1] % P) 61 62 63 def invcoords(c): 64 return (c[1], c[0]) 65 66 67 def jordan_add(a, b): 68 if jordan_isinf(a): 69 return b 70 if jordan_isinf(b): 71 return a 72 73 if (a[0][0] * b[0][1] - b[0][0] * a[0][1]) % P == 0: 74 if (a[1][0] * b[1][1] - b[1][0] * a[1][1]) % P == 0: 75 return jordan_double(a) 76 else: 77 return ((0, 1), (0, 1)) 78 xdiff = subcoords(b[0], a[0]) 79 ydiff = subcoords(b[1], a[1]) 80 m = mulcoords(ydiff, invcoords(xdiff)) 81 x = subcoords(subcoords(mulcoords(m, m), a[0]), b[0]) 82 y = subcoords(mulcoords(m, subcoords(a[0], x)), a[1]) 83 return (x, y) 84 85 86 def jordan_double(a): 87 if jordan_isinf(a): 88 return ((0, 1), (0, 1)) 89 num = addcoords(mul_by_const(mulcoords(a[0], a[0]), 3), (A, 1)) 90 den = mul_by_const(a[1], 2) 91 m = mulcoords(num, invcoords(den)) 92 x = subcoords(mulcoords(m, m), mul_by_const(a[0], 2)) 93 y = subcoords(mulcoords(m, subcoords(a[0], x)), a[1]) 94 return (x, y) 95 96 97 def jordan_multiply(a, n): 98 if jordan_isinf(a) or n == 0: 99 return ((0, 0), (0, 0)) 100 if n == 1: 101 return a 102 if n < 0 or n >= N: 103 return jordan_multiply(a, n % N) 104 if (n % 2) == 0: 105 return jordan_double(jordan_multiply(a, n // 2)) 106 if (n % 2) == 1: 107 return jordan_add(jordan_double(jordan_multiply(a, n // 2)), a) 108 109 110 def to_jordan(p): 111 return ((p[0], 1), (p[1], 1)) 112 113 114 def from_jordan(p): 115 return (p[0][0] * inv(p[0][1], P) % P, p[1][0] * inv(p[1][1], P) % P) 116 117 def fast_multiply(a, n): 118 return from_jordan(jordan_multiply(to_jordan(a), n)) 119 120 121 def fast_add(a, b): 122 return from_jordan(jordan_add(to_jordan(a), to_jordan(b))) 123 124 # Functions for handling pubkey and privkey formats 125 126 127 def get_pubkey_format(pub): 128 if is_python2: 129 two = '\x02' 130 three = '\x03' 131 four = '\x04' 132 else: 133 two = 2 134 three = 3 135 four = 4 136 137 if isinstance(pub, (tuple, list)): return 'decimal' 138 elif len(pub) == 65 and pub[0] == four: return 'bin' 139 elif len(pub) == 130 and pub[0:2] == '04': return 'hex' 140 elif len(pub) == 33 and pub[0] in [two, three]: return 'bin_compressed' 141 elif len(pub) == 66 and pub[0:2] in ['02', '03']: return 'hex_compressed' 142 elif len(pub) == 64: return 'bin_electrum' 143 elif len(pub) == 128: return 'hex_electrum' 144 else: raise Exception("Pubkey not in recognized format") 145 146 147 def encode_pubkey(pub, formt): 148 if not isinstance(pub, (tuple, list)): 149 pub = decode_pubkey(pub) 150 if formt == 'decimal': return pub 151 elif formt == 'bin': 152 return b'\x04' + encode(pub[0], 256, 32) + encode(pub[1], 256, 32) 153 elif formt == 'bin_compressed': 154 return from_int_to_byte(2 + (pub[1] % 2)) + encode(pub[0], 256, 32) 155 elif formt == 'hex': 156 return '04' + encode(pub[0], 16, 64) + encode(pub[1], 16, 64) 157 elif formt == 'hex_compressed': 158 return '0' + str(2 + (pub[1] % 2)) + encode(pub[0], 16, 64) 159 elif formt == 'bin_electrum': 160 return encode(pub[0], 256, 32) + encode(pub[1], 256, 32) 161 elif formt == 'hex_electrum': 162 return encode(pub[0], 16, 64) + encode(pub[1], 16, 64) 163 else: 164 raise Exception("Invalid format!") 165 166 167 def decode_pubkey(pub, formt=None): 168 if not formt: formt = get_pubkey_format(pub) 169 if formt == 'decimal': return pub 170 elif formt == 'bin': 171 return (decode(pub[1:33], 256), decode(pub[33:65], 256)) 172 elif formt == 'bin_compressed': 173 x = decode(pub[1:33], 256) 174 beta = pow(int(x * x * x + A * x + B), int((P + 1) // 4), int(P)) 175 y = (P - beta) if ((beta + from_byte_to_int(pub[0])) % 2) else beta 176 return (x, y) 177 elif formt == 'hex': 178 return (decode(pub[2:66], 16), decode(pub[66:130], 16)) 179 elif formt == 'hex_compressed': 180 return decode_pubkey(safe_from_hex(pub), 'bin_compressed') 181 elif formt == 'bin_electrum': 182 return (decode(pub[:32], 256), decode(pub[32:64], 256)) 183 elif formt == 'hex_electrum': 184 return (decode(pub[:64], 16), decode(pub[64:128], 16)) 185 else: 186 raise Exception("Invalid format!") 187 188 189 def get_privkey_format(priv): 190 if isinstance(priv, int_types): return 'decimal' 191 elif len(priv) == 32: return 'bin' 192 elif len(priv) == 33: return 'bin_compressed' 193 elif len(priv) == 64: return 'hex' 194 elif len(priv) == 66: return 'hex_compressed' 195 else: 196 bin_p = b58check_to_bin(priv) 197 if len(bin_p) == 32: return 'wif' 198 elif len(bin_p) == 33: return 'wif_compressed' 199 else: raise Exception("WIF does not represent privkey") 200 201 202 def encode_privkey(priv, formt, vbyte=0): 203 if not isinstance(priv, int_types): 204 return encode_privkey(decode_privkey(priv), formt, vbyte) 205 if formt == 'decimal': return priv 206 elif formt == 'bin': return encode(priv, 256, 32) 207 elif formt == 'bin_compressed': return encode(priv, 256, 32) + b'\x01' 208 elif formt == 'hex': return encode(priv, 16, 64) 209 elif formt == 'hex_compressed': return encode(priv, 16, 64) + '01' 210 elif formt == 'wif': 211 return bin_to_b58check(encode(priv, 256, 32), 128 + int(vbyte)) 212 elif formt == 'wif_compressed': 213 return bin_to_b58check( 214 encode(priv, 256, 32) + b'\x01', 128 + int(vbyte)) 215 else: 216 raise Exception("Invalid format!") 217 218 219 def decode_privkey(priv, formt=None): 220 if not formt: formt = get_privkey_format(priv) 221 if formt == 'decimal': return priv 222 elif formt == 'bin': return decode(priv, 256) 223 elif formt == 'bin_compressed': return decode(priv[:32], 256) 224 elif formt == 'hex': return decode(priv, 16) 225 elif formt == 'hex_compressed': return decode(priv[:64], 16) 226 elif formt == 'wif': return decode(b58check_to_bin(priv), 256) 227 elif formt == 'wif_compressed': 228 return decode(b58check_to_bin(priv)[:32], 256) 229 else: 230 raise Exception("WIF does not represent privkey") 231 232 233 def add_pubkeys(p1, p2): 234 f1, f2 = get_pubkey_format(p1), get_pubkey_format(p2) 235 return encode_pubkey( 236 fast_add( 237 decode_pubkey(p1, f1), decode_pubkey(p2, f2)), f1) 238 239 240 def add_privkeys(p1, p2): 241 f1, f2 = get_privkey_format(p1), get_privkey_format(p2) 242 return encode_privkey( 243 (decode_privkey(p1, f1) + decode_privkey(p2, f2)) % N, f1) 244 245 246 def multiply(pubkey, privkey): 247 f1, f2 = get_pubkey_format(pubkey), get_privkey_format(privkey) 248 pubkey, privkey = decode_pubkey(pubkey, f1), decode_privkey(privkey, f2) 249 # http://safecurves.cr.yp.to/twist.html 250 if not isinf(pubkey) and ( 251 pubkey[0]**3 + B - pubkey[1] * pubkey[1]) % P != 0: 252 raise Exception("Point not on curve") 253 return encode_pubkey(fast_multiply(pubkey, privkey), f1) 254 255 256 def divide(pubkey, privkey): 257 factor = inv(decode_privkey(privkey), N) 258 return multiply(pubkey, factor) 259 260 261 def compress(pubkey): 262 f = get_pubkey_format(pubkey) 263 if 'compressed' in f: return pubkey 264 elif f == 'bin': 265 return encode_pubkey(decode_pubkey(pubkey, f), 'bin_compressed') 266 elif f == 'hex' or f == 'decimal': 267 return encode_pubkey(decode_pubkey(pubkey, f), 'hex_compressed') 268 269 270 def decompress(pubkey): 271 f = get_pubkey_format(pubkey) 272 if 'compressed' not in f: return pubkey 273 elif f == 'bin_compressed': 274 return encode_pubkey(decode_pubkey(pubkey, f), 'bin') 275 elif f == 'hex_compressed' or f == 'decimal': 276 return encode_pubkey(decode_pubkey(pubkey, f), 'hex') 277 278 279 def privkey_to_pubkey(privkey): 280 f = get_privkey_format(privkey) 281 privkey = decode_privkey(privkey, f) 282 if privkey >= N: 283 raise Exception("Invalid privkey") 284 if f in ['bin', 'bin_compressed', 'hex', 'hex_compressed', 'decimal']: 285 return encode_pubkey(fast_multiply(G, privkey), f) 286 else: 287 return encode_pubkey(fast_multiply(G, privkey), f.replace('wif', 'hex')) 288 289 290 privtopub = privkey_to_pubkey 291 292 293 def privkey_to_address(priv, magicbyte=0): 294 return pubkey_to_address(privkey_to_pubkey(priv), magicbyte) 295 296 297 privtoaddr = privkey_to_address 298 299 300 def neg_pubkey(pubkey): 301 f = get_pubkey_format(pubkey) 302 pubkey = decode_pubkey(pubkey, f) 303 return encode_pubkey((pubkey[0], (P - pubkey[1]) % P), f) 304 305 306 def neg_privkey(privkey): 307 f = get_privkey_format(privkey) 308 privkey = decode_privkey(privkey, f) 309 return encode_privkey((N - privkey) % N, f) 310 311 312 def subtract_pubkeys(p1, p2): 313 f1, f2 = get_pubkey_format(p1), get_pubkey_format(p2) 314 k2 = decode_pubkey(p2, f2) 315 return encode_pubkey( 316 fast_add( 317 decode_pubkey(p1, f1), (k2[0], (P - k2[1]) % P)), f1) 318 319 320 def subtract_privkeys(p1, p2): 321 f1, f2 = get_privkey_format(p1), get_privkey_format(p2) 322 k2 = decode_privkey(p2, f2) 323 return encode_privkey((decode_privkey(p1, f1) - k2) % N, f1) 324 325 # Hashes 326 327 328 def bin_hash160(string): 329 intermed = hashlib.sha256(string).digest() 330 digest = '' 331 digest = hashlib.new('ripemd160', intermed).digest() 332 return digest 333 334 335 def hash160(string): 336 return safe_hexlify(bin_hash160(string)) 337 338 339 def bin_sha256(string): 340 binary_data = string if isinstance(string, bytes) else bytes(string, 341 'utf-8') 342 return hashlib.sha256(binary_data).digest() 343 344 345 def sha256(string): 346 return bytes_to_hex_string(bin_sha256(string)) 347 348 349 def bin_ripemd160(string): 350 digest = hashlib.new('ripemd160', string).digest() 351 return digest 352 353 354 def ripemd160(string): 355 return safe_hexlify(bin_ripemd160(string)) 356 357 358 def bin_dbl_sha256(s): 359 bytes_to_hash = from_string_to_bytes(s) 360 return hashlib.sha256(hashlib.sha256(bytes_to_hash).digest()).digest() 361 362 363 def dbl_sha256(string): 364 return safe_hexlify(bin_dbl_sha256(string)) 365 366 367 def bin_slowsha(string): 368 string = from_string_to_bytes(string) 369 orig_input = string 370 for i in range(100000): 371 string = hashlib.sha256(string + orig_input).digest() 372 return string 373 374 375 def slowsha(string): 376 return safe_hexlify(bin_slowsha(string)) 377 378 379 def hash_to_int(x): 380 if len(x) in [40, 64]: 381 return decode(x, 16) 382 return decode(x, 256) 383 384 385 def num_to_var_int(x): 386 x = int(x) 387 if x < 253: return from_int_to_byte(x) 388 elif x < 65536: return from_int_to_byte(253) + encode(x, 256, 2)[::-1] 389 elif x < 4294967296: return from_int_to_byte(254) + encode(x, 256, 4)[::-1] 390 else: return from_int_to_byte(255) + encode(x, 256, 8)[::-1] 391 392 393 # WTF, Electrum? 394 def electrum_sig_hash(message): 395 padded = b"\x18Bitcoin Signed Message:\n" + num_to_var_int(len( 396 message)) + from_string_to_bytes(message) 397 return bin_dbl_sha256(padded) 398 399 # Encodings 400 401 def b58check_to_bin(inp): 402 leadingzbytes = len(re.match('^1*', inp).group(0)) 403 data = b'\x00' * leadingzbytes + changebase(inp, 58, 256) 404 assert bin_dbl_sha256(data[:-4])[:4] == data[-4:] 405 return data[1:-4] 406 407 408 def get_version_byte(inp): 409 leadingzbytes = len(re.match('^1*', inp).group(0)) 410 data = b'\x00' * leadingzbytes + changebase(inp, 58, 256) 411 assert bin_dbl_sha256(data[:-4])[:4] == data[-4:] 412 return ord(data[0]) 413 414 415 def hex_to_b58check(inp, magicbyte=0): 416 return bin_to_b58check(binascii.unhexlify(inp), magicbyte) 417 418 419 def b58check_to_hex(inp): 420 return safe_hexlify(b58check_to_bin(inp)) 421 422 423 def pubkey_to_address(pubkey, magicbyte=0): 424 if isinstance(pubkey, (list, tuple)): 425 pubkey = encode_pubkey(pubkey, 'bin') 426 if len(pubkey) in [66, 130]: 427 return bin_to_b58check( 428 bin_hash160(binascii.unhexlify(pubkey)), magicbyte) 429 return bin_to_b58check(bin_hash160(pubkey), magicbyte) 430 431 432 pubtoaddr = pubkey_to_address 433 434 # EDCSA 435 436 437 def encode_sig(v, r, s): 438 vb, rb, sb = from_int_to_byte(v), encode(r, 256), encode(s, 256) 439 440 result = base64.b64encode(vb + b'\x00' * (32 - len(rb)) + rb + b'\x00' * ( 441 32 - len(sb)) + sb) 442 return result if is_python2 else str(result, 'utf-8') 443 444 445 def decode_sig(sig): 446 bytez = base64.b64decode(sig) 447 return from_byte_to_int(bytez[0]), decode(bytez[1:33], 256), decode( 448 bytez[33:], 256) 449 450 # https://tools.ietf.org/html/rfc6979#section-3.2 451 452 453 def deterministic_generate_k(msghash, priv): 454 v = b'\x01' * 32 455 k = b'\x00' * 32 456 priv = encode_privkey(priv, 'bin') 457 msghash = encode(hash_to_int(msghash), 256, 32) 458 k = hmac.new(k, v + b'\x00' + priv + msghash, hashlib.sha256).digest() 459 v = hmac.new(k, v, hashlib.sha256).digest() 460 k = hmac.new(k, v + b'\x01' + priv + msghash, hashlib.sha256).digest() 461 v = hmac.new(k, v, hashlib.sha256).digest() 462 return decode(hmac.new(k, v, hashlib.sha256).digest(), 256) 463 464 465 def ecdsa_raw_sign(msghash, priv): 466 467 z = hash_to_int(msghash) 468 k = deterministic_generate_k(msghash, priv) 469 470 r, y = fast_multiply(G, k) 471 s = inv(k, N) * (z + r * decode_privkey(priv)) % N 472 473 return 27 + (y % 2), r, s 474 475 476 def ecdsa_sign(msg, priv): 477 return encode_sig(*ecdsa_raw_sign(electrum_sig_hash(msg), priv)) 478 479 def ecdsa_raw_verify(msghash, vrs, pub): 480 v, r, s = vrs 481 482 w = inv(s, N) 483 z = hash_to_int(msghash) 484 485 u1, u2 = z * w % N, r * w % N 486 x, y = fast_add(fast_multiply(G, u1), fast_multiply(decode_pubkey(pub), u2)) 487 488 return r == x 489 490 def ecdsa_verify(msg, sig, pub): 491 return ecdsa_raw_verify(electrum_sig_hash(msg), decode_sig(sig), pub) 492 493 def estimate_tx_size(ins, outs, txtype='p2pkh'): 494 '''Estimate transaction size. 495 Assuming p2pkh: 496 out: 8+1+3+2+20=34, in: 1+32+4+1+1+~73+1+1+33=147, 497 ver:4,seq:4, +2 (len in,out) 498 total ~= 34*len_out + 147*len_in + 10 (sig sizes vary slightly) 499 ''' 500 if txtype=='p2pkh': 501 return 10 + ins*147 +34*outs 502 else: 503 raise NotImplementedError("Non p2pkh transaction size estimation not"+ 504 "yet implemented")