Merge pull request #736 from chrisglass/more-tests-2
[electrum-nvc.git] / lib / transaction.py
1 #!/usr/bin/env python
2 #
3 # Electrum - lightweight Bitcoin client
4 # Copyright (C) 2011 thomasv@gitorious
5 #
6 # This program is free software: you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation, either version 3 of the License, or
9 # (at your option) any later version.
10 #
11 # This program is distributed in the hope that it will be useful,
12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 # GNU General Public License for more details.
15 #
16 # You should have received a copy of the GNU General Public License
17 # along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19
20 # Note: The deserialization code originally comes from ABE.
21
22
23 import bitcoin
24 from bitcoin import *
25 from util import print_error
26 import time
27 import struct
28
29 #
30 # Workalike python implementation of Bitcoin's CDataStream class.
31 #
32 import struct
33 import StringIO
34 import mmap
35
36 NO_SIGNATURE = 'ff'
37
38 class SerializationError(Exception):
39     """ Thrown when there's a problem deserializing or serializing """
40
41 class BCDataStream(object):
42     def __init__(self):
43         self.input = None
44         self.read_cursor = 0
45
46     def clear(self):
47         self.input = None
48         self.read_cursor = 0
49
50     def write(self, bytes):  # Initialize with string of bytes
51         if self.input is None:
52             self.input = bytes
53         else:
54             self.input += bytes
55
56     def map_file(self, file, start):  # Initialize with bytes from file
57         self.input = mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_READ)
58         self.read_cursor = start
59
60     def seek_file(self, position):
61         self.read_cursor = position
62         
63     def close_file(self):
64         self.input.close()
65
66     def read_string(self):
67         # Strings are encoded depending on length:
68         # 0 to 252 :  1-byte-length followed by bytes (if any)
69         # 253 to 65,535 : byte'253' 2-byte-length followed by bytes
70         # 65,536 to 4,294,967,295 : byte '254' 4-byte-length followed by bytes
71         # ... and the Bitcoin client is coded to understand:
72         # greater than 4,294,967,295 : byte '255' 8-byte-length followed by bytes of string
73         # ... but I don't think it actually handles any strings that big.
74         if self.input is None:
75             raise SerializationError("call write(bytes) before trying to deserialize")
76
77         try:
78             length = self.read_compact_size()
79         except IndexError:
80             raise SerializationError("attempt to read past end of buffer")
81
82         return self.read_bytes(length)
83
84     def write_string(self, string):
85         # Length-encoded as with read-string
86         self.write_compact_size(len(string))
87         self.write(string)
88
89     def read_bytes(self, length):
90         try:
91             result = self.input[self.read_cursor:self.read_cursor+length]
92             self.read_cursor += length
93             return result
94         except IndexError:
95             raise SerializationError("attempt to read past end of buffer")
96
97         return ''
98
99     def read_boolean(self): return self.read_bytes(1)[0] != chr(0)
100     def read_int16(self): return self._read_num('<h')
101     def read_uint16(self): return self._read_num('<H')
102     def read_int32(self): return self._read_num('<i')
103     def read_uint32(self): return self._read_num('<I')
104     def read_int64(self): return self._read_num('<q')
105     def read_uint64(self): return self._read_num('<Q')
106
107     def write_boolean(self, val): return self.write(chr(1) if val else chr(0))
108     def write_int16(self, val): return self._write_num('<h', val)
109     def write_uint16(self, val): return self._write_num('<H', val)
110     def write_int32(self, val): return self._write_num('<i', val)
111     def write_uint32(self, val): return self._write_num('<I', val)
112     def write_int64(self, val): return self._write_num('<q', val)
113     def write_uint64(self, val): return self._write_num('<Q', val)
114
115     def read_compact_size(self):
116         size = ord(self.input[self.read_cursor])
117         self.read_cursor += 1
118         if size == 253:
119             size = self._read_num('<H')
120         elif size == 254:
121             size = self._read_num('<I')
122         elif size == 255:
123             size = self._read_num('<Q')
124         return size
125
126     def write_compact_size(self, size):
127         if size < 0:
128             raise SerializationError("attempt to write size < 0")
129         elif size < 253:
130             self.write(chr(size))
131         elif size < 2**16:
132             self.write('\xfd')
133             self._write_num('<H', size)
134         elif size < 2**32:
135             self.write('\xfe')
136             self._write_num('<I', size)
137         elif size < 2**64:
138             self.write('\xff')
139             self._write_num('<Q', size)
140
141     def _read_num(self, format):
142         (i,) = struct.unpack_from(format, self.input, self.read_cursor)
143         self.read_cursor += struct.calcsize(format)
144         return i
145
146     def _write_num(self, format, num):
147         s = struct.pack(format, num)
148         self.write(s)
149
150 #
151 # enum-like type
152 # From the Python Cookbook, downloaded from http://code.activestate.com/recipes/67107/
153 #
154 import types, string, exceptions
155
156 class EnumException(exceptions.Exception):
157     pass
158
159 class Enumeration:
160     def __init__(self, name, enumList):
161         self.__doc__ = name
162         lookup = { }
163         reverseLookup = { }
164         i = 0
165         uniqueNames = [ ]
166         uniqueValues = [ ]
167         for x in enumList:
168             if type(x) == types.TupleType:
169                 x, i = x
170             if type(x) != types.StringType:
171                 raise EnumException, "enum name is not a string: " + x
172             if type(i) != types.IntType:
173                 raise EnumException, "enum value is not an integer: " + i
174             if x in uniqueNames:
175                 raise EnumException, "enum name is not unique: " + x
176             if i in uniqueValues:
177                 raise EnumException, "enum value is not unique for " + x
178             uniqueNames.append(x)
179             uniqueValues.append(i)
180             lookup[x] = i
181             reverseLookup[i] = x
182             i = i + 1
183         self.lookup = lookup
184         self.reverseLookup = reverseLookup
185     def __getattr__(self, attr):
186         if not self.lookup.has_key(attr):
187             raise AttributeError
188         return self.lookup[attr]
189     def whatis(self, value):
190         return self.reverseLookup[value]
191
192
193 # This function comes from bitcointools, bct-LICENSE.txt.
194 def long_hex(bytes):
195     return bytes.encode('hex_codec')
196
197 # This function comes from bitcointools, bct-LICENSE.txt.
198 def short_hex(bytes):
199     t = bytes.encode('hex_codec')
200     if len(t) < 11:
201         return t
202     return t[0:4]+"..."+t[-4:]
203
204
205
206
207 def parse_redeemScript(bytes):
208     dec = [ x for x in script_GetOp(bytes.decode('hex')) ]
209
210     # 2 of 2
211     match = [ opcodes.OP_2, opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4, opcodes.OP_2, opcodes.OP_CHECKMULTISIG ]
212     if match_decoded(dec, match):
213         pubkeys = [ dec[1][1].encode('hex'), dec[2][1].encode('hex') ]
214         return 2, pubkeys
215
216     # 2 of 3
217     match = [ opcodes.OP_2, opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4, opcodes.OP_3, opcodes.OP_CHECKMULTISIG ]
218     if match_decoded(dec, match):
219         pubkeys = [ dec[1][1].encode('hex'), dec[2][1].encode('hex'), dec[3][1].encode('hex') ]
220         return 2, pubkeys
221
222
223
224 opcodes = Enumeration("Opcodes", [
225     ("OP_0", 0), ("OP_PUSHDATA1",76), "OP_PUSHDATA2", "OP_PUSHDATA4", "OP_1NEGATE", "OP_RESERVED",
226     "OP_1", "OP_2", "OP_3", "OP_4", "OP_5", "OP_6", "OP_7",
227     "OP_8", "OP_9", "OP_10", "OP_11", "OP_12", "OP_13", "OP_14", "OP_15", "OP_16",
228     "OP_NOP", "OP_VER", "OP_IF", "OP_NOTIF", "OP_VERIF", "OP_VERNOTIF", "OP_ELSE", "OP_ENDIF", "OP_VERIFY",
229     "OP_RETURN", "OP_TOALTSTACK", "OP_FROMALTSTACK", "OP_2DROP", "OP_2DUP", "OP_3DUP", "OP_2OVER", "OP_2ROT", "OP_2SWAP",
230     "OP_IFDUP", "OP_DEPTH", "OP_DROP", "OP_DUP", "OP_NIP", "OP_OVER", "OP_PICK", "OP_ROLL", "OP_ROT",
231     "OP_SWAP", "OP_TUCK", "OP_CAT", "OP_SUBSTR", "OP_LEFT", "OP_RIGHT", "OP_SIZE", "OP_INVERT", "OP_AND",
232     "OP_OR", "OP_XOR", "OP_EQUAL", "OP_EQUALVERIFY", "OP_RESERVED1", "OP_RESERVED2", "OP_1ADD", "OP_1SUB", "OP_2MUL",
233     "OP_2DIV", "OP_NEGATE", "OP_ABS", "OP_NOT", "OP_0NOTEQUAL", "OP_ADD", "OP_SUB", "OP_MUL", "OP_DIV",
234     "OP_MOD", "OP_LSHIFT", "OP_RSHIFT", "OP_BOOLAND", "OP_BOOLOR",
235     "OP_NUMEQUAL", "OP_NUMEQUALVERIFY", "OP_NUMNOTEQUAL", "OP_LESSTHAN",
236     "OP_GREATERTHAN", "OP_LESSTHANOREQUAL", "OP_GREATERTHANOREQUAL", "OP_MIN", "OP_MAX",
237     "OP_WITHIN", "OP_RIPEMD160", "OP_SHA1", "OP_SHA256", "OP_HASH160",
238     "OP_HASH256", "OP_CODESEPARATOR", "OP_CHECKSIG", "OP_CHECKSIGVERIFY", "OP_CHECKMULTISIG",
239     "OP_CHECKMULTISIGVERIFY",
240     ("OP_SINGLEBYTE_END", 0xF0),
241     ("OP_DOUBLEBYTE_BEGIN", 0xF000),
242     "OP_PUBKEY", "OP_PUBKEYHASH",
243     ("OP_INVALIDOPCODE", 0xFFFF),
244 ])
245
246
247 def script_GetOp(bytes):
248     i = 0
249     while i < len(bytes):
250         vch = None
251         opcode = ord(bytes[i])
252         i += 1
253         if opcode >= opcodes.OP_SINGLEBYTE_END:
254             opcode <<= 8
255             opcode |= ord(bytes[i])
256             i += 1
257
258         if opcode <= opcodes.OP_PUSHDATA4:
259             nSize = opcode
260             if opcode == opcodes.OP_PUSHDATA1:
261                 nSize = ord(bytes[i])
262                 i += 1
263             elif opcode == opcodes.OP_PUSHDATA2:
264                 (nSize,) = struct.unpack_from('<H', bytes, i)
265                 i += 2
266             elif opcode == opcodes.OP_PUSHDATA4:
267                 (nSize,) = struct.unpack_from('<I', bytes, i)
268                 i += 4
269             vch = bytes[i:i+nSize]
270             i += nSize
271
272         yield (opcode, vch, i)
273
274
275 def script_GetOpName(opcode):
276     return (opcodes.whatis(opcode)).replace("OP_", "")
277
278
279 def decode_script(bytes):
280     result = ''
281     for (opcode, vch, i) in script_GetOp(bytes):
282         if len(result) > 0: result += " "
283         if opcode <= opcodes.OP_PUSHDATA4:
284             result += "%d:"%(opcode,)
285             result += short_hex(vch)
286         else:
287             result += script_GetOpName(opcode)
288     return result
289
290
291 def match_decoded(decoded, to_match):
292     if len(decoded) != len(to_match):
293         return False;
294     for i in range(len(decoded)):
295         if to_match[i] == opcodes.OP_PUSHDATA4 and decoded[i][0] <= opcodes.OP_PUSHDATA4 and decoded[i][0]>0:
296             continue  # Opcodes below OP_PUSHDATA4 all just push data onto stack, and are equivalent.
297         if to_match[i] != decoded[i][0]:
298             return False
299     return True
300
301
302 def parse_sig(x_sig):
303     s = []
304     for sig in x_sig:
305         if sig[-2:] == '01':
306             s.append(sig[:-2])
307         else:
308             assert sig == NO_SIGNATURE
309             s.append(None)
310     return s
311
312 def is_extended_pubkey(x_pubkey):
313     return x_pubkey[0:2] in ['fe', 'ff']
314
315 def x_to_xpub(x_pubkey):
316     if x_pubkey[0:2] == 'ff':
317         from account import BIP32_Account
318         xpub, s = BIP32_Account.parse_xpubkey(x_pubkey)
319         return xpub
320
321         
322
323 def parse_xpub(x_pubkey):
324     if x_pubkey[0:2] == 'ff':
325         from account import BIP32_Account
326         xpub, s = BIP32_Account.parse_xpubkey(x_pubkey)
327         pubkey = BIP32_Account.get_pubkey_from_x(xpub, s[0], s[1])
328     elif x_pubkey[0:2] == 'fe':
329         from account import OldAccount
330         mpk, s = OldAccount.parse_xpubkey(x_pubkey)
331         pubkey = OldAccount.get_pubkey_from_mpk(mpk.decode('hex'), s[0], s[1])
332     else:
333         pubkey = x_pubkey
334     return pubkey
335
336
337 def parse_scriptSig(d, bytes):
338     try:
339         decoded = [ x for x in script_GetOp(bytes) ]
340     except Exception:
341         # coinbase transactions raise an exception
342         print_error("cannot find address in input script", bytes.encode('hex'))
343         return
344
345     # payto_pubkey
346     match = [ opcodes.OP_PUSHDATA4 ]
347     if match_decoded(decoded, match):
348         return
349
350     # non-generated TxIn transactions push a signature
351     # (seventy-something bytes) and then their public key
352     # (65 bytes) onto the stack:
353     match = [ opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4 ]
354     if match_decoded(decoded, match):
355         sig = decoded[0][1].encode('hex')
356         x_pubkey = decoded[1][1].encode('hex')
357         try:
358             signatures = parse_sig([sig])
359             pubkey = parse_xpub(x_pubkey)
360         except:
361             import traceback
362             traceback.print_exc(file=sys.stdout)
363             print_error("cannot find address in input script", bytes.encode('hex'))
364             return
365         d['signatures'] = signatures
366         d['x_pubkeys'] = [x_pubkey]
367         d['num_sig'] = 1
368         d['pubkeys'] = [pubkey]
369         d['address'] = public_key_to_bc_address(pubkey.decode('hex'))
370         return
371
372     # p2sh transaction, 2 of n
373     match = [ opcodes.OP_0 ]
374     while len(match) < len(decoded):
375         match.append(opcodes.OP_PUSHDATA4)
376
377     if not match_decoded(decoded, match):
378         print_error("cannot find address in input script", bytes.encode('hex'))
379         return
380
381     x_sig = map(lambda x:x[1].encode('hex'), decoded[1:-1])
382     d['signatures'] = parse_sig(x_sig)
383     d['num_sig'] = 2
384
385     dec2 = [ x for x in script_GetOp(decoded[-1][1]) ]
386     match_2of2 = [ opcodes.OP_2, opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4, opcodes.OP_2, opcodes.OP_CHECKMULTISIG ]
387     match_2of3 = [ opcodes.OP_2, opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4, opcodes.OP_PUSHDATA4, opcodes.OP_3, opcodes.OP_CHECKMULTISIG ]
388     if match_decoded(dec2, match_2of2):
389         x_pubkeys = [ dec2[1][1].encode('hex'), dec2[2][1].encode('hex') ]
390     elif match_decoded(dec2, match_2of3):
391         x_pubkeys = [ dec2[1][1].encode('hex'), dec2[2][1].encode('hex'), dec2[3][1].encode('hex') ]
392     else:
393         print_error("cannot find address in input script", bytes.encode('hex'))
394         return
395
396     d['x_pubkeys'] = x_pubkeys
397     pubkeys = map(parse_xpub, x_pubkeys)
398     d['pubkeys'] = pubkeys
399
400     redeemScript = Transaction.multisig_script(pubkeys,2)
401     d['redeemScript'] = redeemScript
402     d['address'] = hash_160_to_bc_address(hash_160(redeemScript.decode('hex')), 5)
403
404
405
406
407 def get_address_from_output_script(bytes):
408     decoded = [ x for x in script_GetOp(bytes) ]
409
410     # The Genesis Block, self-payments, and pay-by-IP-address payments look like:
411     # 65 BYTES:... CHECKSIG
412     match = [ opcodes.OP_PUSHDATA4, opcodes.OP_CHECKSIG ]
413     if match_decoded(decoded, match):
414         return True, public_key_to_bc_address(decoded[0][1])
415
416     # Pay-by-Bitcoin-address TxOuts look like:
417     # DUP HASH160 20 BYTES:... EQUALVERIFY CHECKSIG
418     match = [ opcodes.OP_DUP, opcodes.OP_HASH160, opcodes.OP_PUSHDATA4, opcodes.OP_EQUALVERIFY, opcodes.OP_CHECKSIG ]
419     if match_decoded(decoded, match):
420         return False, hash_160_to_bc_address(decoded[2][1])
421
422     # p2sh
423     match = [ opcodes.OP_HASH160, opcodes.OP_PUSHDATA4, opcodes.OP_EQUAL ]
424     if match_decoded(decoded, match):
425         return False, hash_160_to_bc_address(decoded[1][1],5)
426
427     return False, "(None)"
428
429
430
431
432 class Transaction:
433     
434     def __init__(self, raw):
435         self.raw = raw
436         self.deserialize()
437         self.inputs = self.d['inputs']
438         self.outputs = self.d['outputs']
439         self.outputs = map(lambda x: (x['address'],x['value']), self.outputs)
440         self.locktime = self.d['lockTime']
441
442     def __str__(self):
443         return self.raw
444
445     @classmethod
446     def from_io(klass, inputs, outputs):
447         raw = klass.serialize(inputs, outputs, for_sig = None) # for_sig=-1 means do not sign
448         self = klass(raw)
449         self.inputs = inputs
450         self.outputs = outputs
451         return self
452
453     @classmethod 
454     def sweep(klass, privkeys, network, to_address, fee):
455         inputs = []
456         for privkey in privkeys:
457             pubkey = public_key_from_private_key(privkey)
458             address = address_from_private_key(privkey)
459             u = network.synchronous_get([ ('blockchain.address.listunspent',[address])])[0]
460             pay_script = klass.pay_script(address)
461             for item in u:
462                 item['scriptPubKey'] = pay_script
463                 item['redeemPubkey'] = pubkey
464                 item['address'] = address
465                 item['prevout_hash'] = item['tx_hash']
466                 item['prevout_n'] = item['tx_pos']
467             inputs += u
468
469         if not inputs:
470             return
471
472         total = sum( map(lambda x:int(x.get('value')), inputs) ) - fee
473         outputs = [(to_address, total)]
474         self = klass.from_io(inputs, outputs)
475         self.sign({ pubkey:privkey })
476         return self
477
478     @classmethod
479     def multisig_script(klass, public_keys, num=None):
480         n = len(public_keys)
481         if num is None: num = n
482         # supports only "2 of 2", and "2 of 3" transactions
483         assert num <= n and n in [2,3]
484     
485         if num==2:
486             s = '52'
487         elif num == 3:
488             s = '53'
489         else:
490             raise
491     
492         for k in public_keys:
493             s += op_push(len(k)/2)
494             s += k
495         if n==2:
496             s += '52'
497         elif n==3:
498             s += '53'
499         else:
500             raise
501         s += 'ae'
502
503         return s
504
505
506     @classmethod
507     def pay_script(self, addr):
508         addrtype, hash_160 = bc_address_to_hash_160(addr)
509         if addrtype == 0:
510             script = '76a9'                                      # op_dup, op_hash_160
511             script += '14'                                       # push 0x14 bytes
512             script += hash_160.encode('hex')
513             script += '88ac'                                     # op_equalverify, op_checksig
514         elif addrtype == 5:
515             script = 'a9'                                        # op_hash_160
516             script += '14'                                       # push 0x14 bytes
517             script += hash_160.encode('hex')
518             script += '87'                                       # op_equal
519         else:
520             raise
521         return script
522
523
524     @classmethod
525     def serialize( klass, inputs, outputs, for_sig = None ):
526
527         push_script = lambda x: op_push(len(x)/2) + x
528         s  = int_to_hex(1,4)                                         # version
529         s += var_int( len(inputs) )                                  # number of inputs
530         for i in range(len(inputs)):
531             txin = inputs[i]
532
533             s += txin['prevout_hash'].decode('hex')[::-1].encode('hex')   # prev hash
534             s += int_to_hex(txin['prevout_n'],4)                          # prev index
535
536             p2sh = txin.get('redeemScript') is not None
537             num_sig = txin['num_sig']
538             address = txin['address']
539
540             x_signatures = txin['signatures']
541             signatures = filter(lambda x: x is not None, x_signatures)
542             is_complete = len(signatures) == num_sig
543
544             if for_sig is None:
545                 # if we have enough signatures, we use the actual pubkeys
546                 # use extended pubkeys (with bip32 derivation)
547                 sig_list = []
548                 if is_complete:
549                     pubkeys = txin['pubkeys']
550                     for signature in signatures:
551                         sig_list.append(signature + '01')
552                 else:
553                     pubkeys = txin['x_pubkeys']
554                     for signature in x_signatures:
555                         sig_list.append((signature + '01') if signature is not None else NO_SIGNATURE)
556
557                 sig_list = ''.join( map( lambda x: push_script(x), sig_list))
558                 if not p2sh:
559                     script = sig_list
560                     script += push_script(pubkeys[0])
561                 else:
562                     script = '00'                                    # op_0
563                     script += sig_list
564                     redeem_script = klass.multisig_script(pubkeys,2)
565                     script += push_script(redeem_script)
566
567             elif for_sig==i:
568                 script = txin['redeemScript'] if p2sh else klass.pay_script(address)
569             else:
570                 script = ''
571             s += var_int( len(script)/2 )                            # script length
572             s += script
573             s += "ffffffff"                                          # sequence
574
575         s += var_int( len(outputs) )                                 # number of outputs
576         for output in outputs:
577             addr, amount = output
578             s += int_to_hex( amount, 8)                              # amount
579             script = klass.pay_script(addr)
580             s += var_int( len(script)/2 )                           #  script length
581             s += script                                             #  script
582         s += int_to_hex(0,4)                                        #  lock time
583         if for_sig is not None and for_sig != -1:
584             s += int_to_hex(1, 4)                                   #  hash type
585         return s
586
587
588     def tx_for_sig(self,i):
589         return self.serialize(self.inputs, self.outputs, for_sig = i)
590
591
592     def hash(self):
593         return Hash(self.raw.decode('hex') )[::-1].encode('hex')
594
595     def add_signature(self, i, pubkey, sig):
596         print_error("adding signature for", pubkey)
597         txin = self.inputs[i]
598         pubkeys = txin['pubkeys']
599         ii = pubkeys.index(pubkey)
600         txin['signatures'][ii] = sig
601         txin['x_pubkeys'][ii] = pubkey
602         self.inputs[i] = txin
603         self.raw = self.serialize(self.inputs, self.outputs)
604
605
606     def signature_count(self):
607         r = 0
608         s = 0
609         for txin in self.inputs:
610             signatures = filter(lambda x: x is not None, txin['signatures'])
611             s += len(signatures)
612             r += txin['num_sig']
613         return s, r
614
615
616     def is_complete(self):
617         s, r = self.signature_count()
618         return r == s
619
620
621     def inputs_to_sign(self):
622         from account import BIP32_Account, OldAccount
623         xpub_list = []
624         addr_list = set()
625         for txin in self.inputs:
626             x_signatures = txin['signatures']
627             signatures = filter(lambda x: x is not None, x_signatures)
628
629             if len(signatures) == txin['num_sig']:
630                 # input is complete
631                 continue
632
633             for k, x_pubkey in enumerate(txin['x_pubkeys']):
634
635                 if x_signatures[k] is not None:
636                     # this pubkey already signed
637                     continue
638
639                 if x_pubkey[0:2] == 'ff':
640                     xpub, sequence = BIP32_Account.parse_xpubkey(x_pubkey)
641                     xpub_list.append((xpub,sequence))
642                 elif x_pubkey[0:2] == 'fe':
643                     xpub, sequence = OldAccount.parse_xpubkey(x_pubkey)
644                     xpub_list.append((xpub,sequence))
645                 else:
646                     addr_list.add(txin['address'])
647
648         return addr_list, xpub_list
649
650
651     def sign(self, keypairs):
652         print_error("tx.sign(), keypairs:", keypairs)
653
654         for i, txin in enumerate(self.inputs):
655
656             # continue if this txin is complete
657             signatures = filter(lambda x: x is not None, txin['signatures'])
658             num = txin['num_sig']
659             if len(signatures) == num:
660                 continue
661
662             redeem_pubkeys = txin['pubkeys']
663             for_sig = Hash(self.tx_for_sig(i).decode('hex'))
664             for pubkey in redeem_pubkeys:
665                 if pubkey in keypairs.keys():
666                     # add signature
667                     sec = keypairs[pubkey]
668                     pkey = regenerate_key(sec)
669                     secexp = pkey.secret
670                     private_key = ecdsa.SigningKey.from_secret_exponent( secexp, curve = SECP256k1 )
671                     public_key = private_key.get_verifying_key()
672                     sig = private_key.sign_digest_deterministic( for_sig, hashfunc=hashlib.sha256, sigencode = ecdsa.util.sigencode_der )
673                     assert public_key.verify_digest( sig, for_sig, sigdecode = ecdsa.util.sigdecode_der)
674                     self.add_signature(i, pubkey, sig.encode('hex'))
675
676
677         print_error("is_complete", self.is_complete())
678         self.raw = self.serialize( self.inputs, self.outputs )
679
680
681
682     def deserialize(self):
683         vds = BCDataStream()
684         vds.write(self.raw.decode('hex'))
685         d = {}
686         start = vds.read_cursor
687         d['version'] = vds.read_int32()
688         n_vin = vds.read_compact_size()
689         d['inputs'] = []
690         for i in xrange(n_vin):
691             d['inputs'].append(self.parse_input(vds))
692         n_vout = vds.read_compact_size()
693         d['outputs'] = []
694         for i in xrange(n_vout):
695             d['outputs'].append(self.parse_output(vds, i))
696         d['lockTime'] = vds.read_uint32()
697         self.d = d
698         return self.d
699     
700
701     def parse_input(self, vds):
702         d = {}
703         prevout_hash = hash_encode(vds.read_bytes(32))
704         prevout_n = vds.read_uint32()
705         scriptSig = vds.read_bytes(vds.read_compact_size())
706         sequence = vds.read_uint32()
707
708         if prevout_hash == '00'*32:
709             d['is_coinbase'] = True
710         else:
711             d['is_coinbase'] = False
712             d['prevout_hash'] = prevout_hash
713             d['prevout_n'] = prevout_n
714             d['sequence'] = sequence
715
716             d['pubkeys'] = []
717             d['signatures'] = {}
718             d['address'] = None
719             if scriptSig:
720                 parse_scriptSig(d, scriptSig)
721         return d
722
723
724     def parse_output(self, vds, i):
725         d = {}
726         d['value'] = vds.read_int64()
727         scriptPubKey = vds.read_bytes(vds.read_compact_size())
728         is_pubkey, address = get_address_from_output_script(scriptPubKey)
729         d['is_pubkey'] = is_pubkey
730         d['address'] = address
731         d['scriptPubKey'] = scriptPubKey.encode('hex')
732         d['prevout_n'] = i
733         return d
734
735
736     def add_extra_addresses(self, txlist):
737         for i in self.inputs:
738             if i.get("address") == "(pubkey)":
739                 prev_tx = txlist.get(i.get('prevout_hash'))
740                 if prev_tx:
741                     address, value = prev_tx.outputs[i.get('prevout_n')]
742                     print_error("found pay-to-pubkey address:", address)
743                     i["address"] = address
744
745
746     def has_address(self, addr):
747         found = False
748         for txin in self.inputs:
749             if addr == txin.get('address'): 
750                 found = True
751                 break
752         for txout in self.outputs:
753             if addr == txout[0]:
754                 found = True
755                 break
756         return found
757
758
759     def get_value(self, addresses, prevout_values):
760         # return the balance for that tx
761         is_relevant = False
762         is_send = False
763         is_pruned = False
764         is_partial = False
765         v_in = v_out = v_out_mine = 0
766
767         for item in self.inputs:
768             addr = item.get('address')
769             if addr in addresses:
770                 is_send = True
771                 is_relevant = True
772                 key = item['prevout_hash']  + ':%d'%item['prevout_n']
773                 value = prevout_values.get( key )
774                 if value is None:
775                     is_pruned = True
776                 else:
777                     v_in += value
778             else:
779                 is_partial = True
780
781         if not is_send: is_partial = False
782                     
783         for item in self.outputs:
784             addr, value = item
785             v_out += value
786             if addr in addresses:
787                 v_out_mine += value
788                 is_relevant = True
789
790         if is_pruned:
791             # some inputs are mine:
792             fee = None
793             if is_send:
794                 v = v_out_mine - v_out
795             else:
796                 # no input is mine
797                 v = v_out_mine
798
799         else:
800             v = v_out_mine - v_in
801
802             if is_partial:
803                 # some inputs are mine, but not all
804                 fee = None
805                 is_send = v < 0
806             else:
807                 # all inputs are mine
808                 fee = v_out - v_in
809
810         return is_relevant, is_send, v, fee
811
812
813     def as_dict(self):
814         import json
815         out = {
816             "hex":self.raw,
817             "complete":self.is_complete()
818             }
819         return out
820
821
822     def requires_fee(self, verifier):
823         # see https://en.bitcoin.it/wiki/Transaction_fees
824         threshold = 57600000
825         size = len(self.raw)/2
826         if size >= 10000: 
827             return True
828
829         for o in self.outputs:
830             value = o[1]
831             if value < 1000000:
832                 return True
833         sum = 0
834         for i in self.inputs:
835             age = verifier.get_confirmations(i["prevout_hash"])[0]
836             sum += i["value"] * age
837         priority = sum / size
838         print_error(priority, threshold)
839         return priority < threshold 
840
841
842