restore old accounts from seed
[electrum-nvc.git] / lib / wallet.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 import sys
20 import base64
21 import os
22 import re
23 import hashlib
24 import copy
25 import operator
26 import ast
27 import threading
28 import random
29 import aes
30 import Queue
31 import time
32
33 from util import print_msg, print_error, user_dir, format_satoshis
34 from bitcoin import *
35 from account import *
36
37 # AES encryption
38 EncodeAES = lambda secret, s: base64.b64encode(aes.encryptData(secret,s))
39 DecodeAES = lambda secret, e: aes.decryptData(secret, base64.b64decode(e))
40
41 def pw_encode(s, password):
42     if password:
43         secret = Hash(password)
44         return EncodeAES(secret, s)
45     else:
46         return s
47
48 def pw_decode(s, password):
49     if password is not None:
50         secret = Hash(password)
51         try:
52             d = DecodeAES(secret, s)
53         except:
54             raise BaseException('Invalid password')
55         return d
56     else:
57         return s
58
59
60
61
62
63 from version import ELECTRUM_VERSION, SEED_VERSION
64
65
66 class Wallet:
67     def __init__(self, config={}):
68
69         self.config = config
70         self.electrum_version = ELECTRUM_VERSION
71         self.gap_limit_for_change = 3 # constant
72
73         # saved fields
74         self.seed_version          = config.get('seed_version', SEED_VERSION)
75
76         self.gap_limit             = config.get('gap_limit', 5)
77         self.use_change            = config.get('use_change',True)
78         self.fee                   = int(config.get('fee_per_kb',20000))
79         self.num_zeros             = int(config.get('num_zeros',0))
80         self.use_encryption        = config.get('use_encryption', False)
81         self.seed                  = config.get('seed', '')               # encrypted
82         self.labels                = config.get('labels', {})
83         self.frozen_addresses      = config.get('frozen_addresses',[])
84         self.prioritized_addresses = config.get('prioritized_addresses',[])
85         self.addressbook           = config.get('contacts', [])
86
87         self.imported_keys         = config.get('imported_keys',{})
88         self.history               = config.get('addr_history',{})        # address -> list(txid, height)
89
90
91         self.master_public_keys = config.get('master_public_keys',{})
92         self.master_private_keys = config.get('master_private_keys', {})
93
94         self.first_addresses = config.get('first_addresses',{})
95
96         #if self.seed_version != SEED_VERSION:
97         #    raise ValueError("This wallet seed is deprecated. Please restore from seed.")
98
99         self.load_accounts(config)
100
101         self.transactions = {}
102         tx = config.get('transactions',{})
103         try:
104             for k,v in tx.items(): self.transactions[k] = Transaction(v)
105         except:
106             print_msg("Warning: Cannot deserialize transactions. skipping")
107         
108         # not saved
109         self.prevout_values = {}     # my own transaction outputs
110         self.spent_outputs = []
111
112         # spv
113         self.verifier = None
114
115         # there is a difference between wallet.up_to_date and interface.is_up_to_date()
116         # interface.is_up_to_date() returns true when all requests have been answered and processed
117         # wallet.up_to_date is true when the wallet is synchronized (stronger requirement)
118         
119         self.up_to_date = False
120         self.lock = threading.Lock()
121         self.transaction_lock = threading.Lock()
122         self.tx_event = threading.Event()
123
124         for tx_hash, tx in self.transactions.items():
125             if self.check_new_tx(tx_hash, tx):
126                 self.update_tx_outputs(tx_hash)
127             else:
128                 print_error("unreferenced tx", tx_hash)
129                 self.transactions.pop(tx_hash)
130
131
132     def set_up_to_date(self,b):
133         with self.lock: self.up_to_date = b
134
135     def is_up_to_date(self):
136         with self.lock: return self.up_to_date
137
138     def update(self):
139         self.up_to_date = False
140         self.interface.poke('synchronizer')
141         while not self.is_up_to_date(): time.sleep(0.1)
142
143     def import_key(self, sec, password):
144         # check password
145         seed = self.decode_seed(password)
146         try:
147             address = address_from_private_key(sec)
148         except:
149             raise BaseException('Invalid private key')
150
151         if self.is_mine(address):
152             raise BaseException('Address already in wallet')
153         
154         # store the originally requested keypair into the imported keys table
155         self.imported_keys[address] = pw_encode(sec, password )
156         self.config.set_key('imported_keys', self.imported_keys, True)
157         return address
158         
159     def delete_imported_key(self, addr):
160         if addr in self.imported_keys:
161             self.imported_keys.pop(addr)
162             self.config.set_key('imported_keys', self.imported_keys, True)
163
164
165     def init_seed(self, seed):
166         if self.seed: raise BaseException("a seed exists")
167         if not seed: 
168             seed = random_seed(128)
169         self.seed = seed
170
171
172     def save_seed(self):
173         self.config.set_key('seed', self.seed, True)
174         self.config.set_key('seed_version', self.seed_version, True)
175
176         master_k, master_c, master_K, master_cK = bip32_init(self.seed)
177         
178         # normal accounts
179         k0, c0, K0, cK0 = bip32_private_derivation(master_k, master_c, "m/", "m/0'/")
180         # p2sh 2of2
181         k1, c1, K1, cK1 = bip32_private_derivation(master_k, master_c, "m/", "m/1'/")
182         k2, c2, K2, cK2 = bip32_private_derivation(master_k, master_c, "m/", "m/2'/")
183         # p2sh 2of3
184         k3, c3, K3, cK3 = bip32_private_derivation(master_k, master_c, "m/", "m/3'/")
185         k4, c4, K4, cK4 = bip32_private_derivation(master_k, master_c, "m/", "m/4'/")
186         k5, c5, K5, cK5 = bip32_private_derivation(master_k, master_c, "m/", "m/5'/")
187
188         self.master_public_keys = {
189             "m/0'/": (c0, K0, cK0),
190             "m/1'/": (c1, K1, cK1),
191             "m/2'/": (c2, K2, cK2),
192             "m/3'/": (c3, K3, cK3),
193             "m/4'/": (c4, K4, cK4),
194             "m/5'/": (c5, K5, cK5)
195             }
196         
197         self.master_private_keys = {
198             "m/0'/": k0,
199             "m/1'/": k1,
200             "m/2'/": k2,
201             "m/3'/": k3,
202             "m/4'/": k4,
203             "m/5'/": k5
204             }
205         
206         self.config.set_key('master_public_keys', self.master_public_keys, True)
207         self.config.set_key('master_private_keys', self.master_private_keys, True)
208
209         # create default account
210         self.create_account('1','Main account')
211
212
213     def find_root_by_master_key(self, c, K):
214         for key, v in self.master_public_keys.items():
215             if key == "m/":continue
216             cc, KK, _ = v
217             if (c == cc) and (K == KK):
218                 return key
219
220     def deseed_root(self, seed, password):
221         # for safety, we ask the user to enter their seed
222         assert seed == self.decode_seed(password)
223         self.seed = ''
224         self.config.set_key('seed', '', True)
225
226
227     def deseed_branch(self, k):
228         # check that parent has no seed
229         assert self.seed == ''
230         self.master_private_keys.pop(k)
231         self.config.set_key('master_private_keys', self.master_private_keys, True)
232
233
234     def account_id(self, account_type, i):
235         if account_type == '1':
236             return "m/0'/%d"%i
237         elif account_type == '2of2':
238             return "m/1'/%d & m/2'/%d"%(i,i)
239         elif account_type == '2of3':
240             return "m/3'/%d & m/4'/%d & m/5'/%d"%(i,i,i)
241         else:
242             raise BaseException('unknown account type')
243
244
245     def num_accounts(self, account_type):
246         keys = self.accounts.keys()
247         i = 0
248         while True:
249             account_id = self.account_id(account_type, i)
250             if account_id not in keys: break
251             i += 1
252         return i
253
254
255     def new_account_address(self, account_type = '1'):
256         i = self.num_accounts(account_type)
257         k = self.account_id(account_type,i)
258
259         addr = self.first_addresses.get(k)
260         if not addr: 
261             account_id, account = self.next_account(account_type)
262             addr = account.first_address()
263             self.first_addresses[k] = addr
264             self.config.set_key('first_addresses',self.first_addresses)
265
266         return addr
267
268
269     def next_account(self, account_type = '1'):
270
271         i = self.num_accounts(account_type)
272         account_id = self.account_id(account_type,i)
273
274         if account_type is '1':
275             master_c0, master_K0, _ = self.master_public_keys["m/0'/"]
276             c0, K0, cK0 = bip32_public_derivation(master_c0.decode('hex'), master_K0.decode('hex'), "m/0'/", "m/0'/%d"%i)
277             account = BIP32_Account({ 'c':c0, 'K':K0, 'cK':cK0 })
278
279         elif account_type == '2of2':
280             master_c1, master_K1, _ = self.master_public_keys["m/1'/"]
281             c1, K1, cK1 = bip32_public_derivation(master_c1.decode('hex'), master_K1.decode('hex'), "m/1'/", "m/1'/%d"%i)
282             master_c2, master_K2, _ = self.master_public_keys["m/2'/"]
283             c2, K2, cK2 = bip32_public_derivation(master_c2.decode('hex'), master_K2.decode('hex'), "m/2'/", "m/2'/%d"%i)
284             account = BIP32_Account_2of2({ 'c':c1, 'K':K1, 'cK':cK1, 'c2':c2, 'K2':K2, 'cK2':cK2 })
285
286         elif account_type == '2of3':
287             master_c3, master_K3, _ = self.master_public_keys["m/3'/"]
288             c3, K3, cK3 = bip32_public_derivation(master_c3.decode('hex'), master_K3.decode('hex'), "m/3'/", "m/3'/%d"%i)
289             master_c4, master_K4, _ = self.master_public_keys["m/4'/"]
290             c4, K4, cK4 = bip32_public_derivation(master_c4.decode('hex'), master_K4.decode('hex'), "m/4'/", "m/4'/%d"%i)
291             master_c5, master_K5, _ = self.master_public_keys["m/5'/"]
292             c5, K5, cK5 = bip32_public_derivation(master_c5.decode('hex'), master_K5.decode('hex'), "m/5'/", "m/5'/%d"%i)
293             account = BIP32_Account_2of3({ 'c':c3, 'K':K3, 'cK':cK3, 'c2':c4, 'K2':K4, 'cK2':cK4, 'c3':c5, 'K3':K5, 'cK3':cK5 })
294
295         return account_id, account
296
297
298     def create_account(self, account_type = '1', name = None):
299         account_id, account = self.next_account(account_type)
300         self.accounts[account_id] = account
301         self.save_accounts()
302         if name: 
303             self.labels[account_id] = name
304         self.config.set_key('labels', self.labels, True)
305
306
307     def create_old_account(self):
308         print self.seed
309         mpk = OldAccount.mpk_from_seed(self.seed)
310         self.config.set_key('master_public_key', mpk, True)
311         self.accounts[0] = OldAccount({'mpk':mpk, 0:[], 1:[]})
312         self.save_accounts()
313
314
315     def save_accounts(self):
316         d = {}
317         for k, v in self.accounts.items():
318             d[k] = v.dump()
319         self.config.set_key('accounts', d, True)
320
321     
322
323     def load_accounts(self, config):
324         d = config.get('accounts', {})
325         self.accounts = {}
326         for k, v in d.items():
327             if k == 0:
328                 v['mpk'] = config.get('master_public_key')
329                 self.accounts[k] = OldAccount(v)
330             elif '&' in k:
331                 self.accounts[k] = BIP32_Account_2of2(v)
332             else:
333                 self.accounts[k] = BIP32_Account(v)
334
335
336     def addresses(self, include_change = True):
337         o = self.get_account_addresses(-1, include_change)
338         for a in self.accounts.keys():
339             o += self.get_account_addresses(a, include_change)
340         o += self.first_addresses.values()
341         return o
342
343
344     def is_mine(self, address):
345         return address in self.addresses(True)
346
347
348     def is_change(self, address):
349         if not self.is_mine(address): return False
350         if address in self.imported_keys.keys(): return False
351         acct, s = self.get_address_index(address)
352         return s[0] == 1
353
354     def get_master_public_key(self):
355         raise
356         return self.config.get("master_public_key")
357
358     def get_master_private_key(self, account, password):
359         master_k = pw_decode( self.master_private_keys[account], password)
360         master_c, master_K, master_Kc = self.master_public_keys[account]
361         try:
362             K, Kc = get_pubkeys_from_secret(master_k.decode('hex'))
363             assert K.encode('hex') == master_K
364         except:
365             raise BaseException("Invalid password")
366         return master_k
367
368
369     def get_address_index(self, address):
370         if address in self.imported_keys.keys():
371             return -1, None
372
373         for account in self.accounts.keys():
374             for for_change in [0,1]:
375                 addresses = self.accounts[account].get_addresses(for_change)
376                 for addr in addresses:
377                     if address == addr:
378                         return account, (for_change, addresses.index(addr))
379
380         raise BaseException("not found")
381
382
383     def rebase_sequence(self, account, sequence):
384         c, i = sequence
385         dd = []
386         for a in account.split('&'):
387             s = a.strip()
388             m = re.match("(m/\d+'/)(\d+)", s)
389             root = m.group(1)
390             num = int(m.group(2))
391             dd.append( (root, [num,c,i] ) )
392         return dd
393         
394
395     def get_keyID(self, account, sequence):
396         rs = self.rebase_sequence(account, sequence)
397         dd = []
398         for root, public_sequence in rs:
399             c, K, _ = self.master_public_keys[root]
400             s = '/' + '/'.join( map(lambda x:str(x), public_sequence) )
401             dd.append( 'bip32(%s,%s,%s)'%(c,K, s) )
402         return '&'.join(dd)
403
404
405     def get_public_key(self, address):
406         account, sequence = self.get_address_index(address)
407         return self.accounts[account].get_pubkey( *sequence )
408
409
410     def decode_seed(self, password):
411         seed = pw_decode(self.seed, password)
412         #todo:  #self.sequences[0].check_seed(seed)
413         return seed
414         
415
416     def get_private_key(self, address, password):
417         out = []
418         if address in self.imported_keys.keys():
419             out.append( pw_decode( self.imported_keys[address], password ) )
420         else:
421             account, sequence = self.get_address_index(address)
422             # assert address == self.accounts[account].get_address(*sequence)
423             rs = self.rebase_sequence( account, sequence)
424             for root, public_sequence in rs:
425
426                 if root not in self.master_private_keys.keys(): continue
427                 master_k = self.get_master_private_key(root, password)
428                 master_c, _, _ = self.master_public_keys[root]
429                 pk = bip32_private_key( public_sequence, master_k.decode('hex'), master_c.decode('hex'))
430                 out.append(pk)
431                     
432         return out
433
434
435
436
437     def signrawtransaction(self, tx, input_info, private_keys, password):
438         import deserialize
439         unspent_coins = self.get_unspent_coins()
440         seed = self.decode_seed(password)
441
442         # build a list of public/private keys
443         keypairs = {}
444         for sec in private_keys:
445             pubkey = public_key_from_private_key(sec)
446             keypairs[ pubkey ] = sec
447
448
449         for txin in tx.inputs:
450             # convert to own format
451             txin['tx_hash'] = txin['prevout_hash']
452             txin['index'] = txin['prevout_n']
453
454             for item in input_info:
455                 if item.get('txid') == txin['tx_hash'] and item.get('vout') == txin['index']:
456                     txin['raw_output_script'] = item['scriptPubKey']
457                     txin['redeemScript'] = item.get('redeemScript')
458                     txin['KeyID'] = item.get('KeyID')
459                     break
460             else:
461                 for item in unspent_coins:
462                     if txin['tx_hash'] == item['tx_hash'] and txin['index'] == item['index']:
463                         print_error( "tx input is in unspent coins" )
464                         txin['raw_output_script'] = item['raw_output_script']
465                         account, sequence = self.get_address_index(item['address'])
466                         if account != -1:
467                             txin['redeemScript'] = self.accounts[account].redeem_script(sequence)
468                         break
469                 else:
470                     raise BaseException("Unknown transaction input. Please provide the 'input_info' parameter, or synchronize this wallet")
471
472             # if available, derive private_keys from KeyID
473             keyid = txin.get('KeyID')
474             if keyid:
475                 roots = []
476                 for s in keyid.split('&'):
477                     m = re.match("bip32\(([0-9a-f]+),([0-9a-f]+),(/\d+/\d+/\d+)", s)
478                     if not m: continue
479                     c = m.group(1)
480                     K = m.group(2)
481                     sequence = m.group(3)
482                     root = self.find_root_by_master_key(c,K)
483                     if not root: continue
484                     sequence = map(lambda x:int(x), sequence.strip('/').split('/'))
485                     root = root + '%d'%sequence[0]
486                     sequence = sequence[1:]
487                     roots.append((root,sequence)) 
488
489                 account_id = " & ".join( map(lambda x:x[0], roots) )
490                 account = self.accounts.get(account_id)
491                 if not account: continue
492                 addr = account.get_address(*sequence)
493                 txin['address'] = addr
494                 pk = self.get_private_key(addr, password)
495                 for sec in pk:
496                     pubkey = public_key_from_private_key(sec)
497                     keypairs[pubkey] = sec
498
499             redeem_script = txin.get("redeemScript")
500             print_error( "p2sh:", "yes" if redeem_script else "no")
501             if redeem_script:
502                 addr = hash_160_to_bc_address(hash_160(redeem_script.decode('hex')), 5)
503             else:
504                 addr = deserialize.get_address_from_output_script(txin["raw_output_script"].decode('hex'))
505             txin['address'] = addr
506
507             # add private keys that are in the wallet
508             pk = self.get_private_key(addr, password)
509             for sec in pk:
510                 pubkey = public_key_from_private_key(sec)
511                 keypairs[pubkey] = sec
512                 if not redeem_script:
513                     txin['redeemPubkey'] = pubkey
514
515             print txin
516
517         tx.sign( keypairs )
518
519     def sign_message(self, address, message, password):
520         sec = self.get_private_key(address, password)
521         key = regenerate_key(sec)
522         compressed = is_compressed(sec)
523         return key.sign_message(message, compressed, address)
524
525     def verify_message(self, address, signature, message):
526         try:
527             EC_KEY.verify_message(address, signature, message)
528             return True
529         except BaseException as e:
530             print_error("Verification error: {0}".format(e))
531             return False
532
533
534     def change_gap_limit(self, value):
535         if value >= self.gap_limit:
536             self.gap_limit = value
537             self.config.set_key('gap_limit', self.gap_limit, True)
538             self.interface.poke('synchronizer')
539             return True
540
541         elif value >= self.min_acceptable_gap():
542             for key, account in self.accounts.items():
543                 addresses = account[0]
544                 k = self.num_unused_trailing_addresses(addresses)
545                 n = len(addresses) - k + value
546                 addresses = addresses[0:n]
547                 self.accounts[key][0] = addresses
548
549             self.gap_limit = value
550             self.config.set_key('gap_limit', self.gap_limit, True)
551             self.save_accounts()
552             return True
553         else:
554             return False
555
556     def num_unused_trailing_addresses(self, addresses):
557         k = 0
558         for a in addresses[::-1]:
559             if self.history.get(a):break
560             k = k + 1
561         return k
562
563     def min_acceptable_gap(self):
564         # fixme: this assumes wallet is synchronized
565         n = 0
566         nmax = 0
567
568         for account in self.accounts.values():
569             addresses = account.get_addresses(0)
570             k = self.num_unused_trailing_addresses(addresses)
571             for a in addresses[0:-k]:
572                 if self.history.get(a):
573                     n = 0
574                 else:
575                     n += 1
576                     if n > nmax: nmax = n
577         return nmax + 1
578
579
580     def address_is_old(self, address):
581         age = -1
582         h = self.history.get(address, [])
583         if h == ['*']:
584             return True
585         for tx_hash, tx_height in h:
586             if tx_height == 0:
587                 tx_age = 0
588             else: 
589                 tx_age = self.verifier.height - tx_height + 1
590             if tx_age > age:
591                 age = tx_age
592         return age > 2
593
594
595     def synchronize_sequence(self, account, for_change):
596         limit = self.gap_limit_for_change if for_change else self.gap_limit
597         new_addresses = []
598         while True:
599             addresses = account.get_addresses(for_change)
600             if len(addresses) < limit:
601                 address = account.create_new_address(for_change)
602                 self.history[address] = []
603                 new_addresses.append( address )
604                 continue
605
606             if map( lambda a: self.address_is_old(a), addresses[-limit:] ) == limit*[False]:
607                 break
608             else:
609                 address = account.create_new_address(for_change)
610                 self.history[address] = []
611                 new_addresses.append( address )
612
613         return new_addresses
614         
615
616
617     def create_pending_accounts(self):
618         for account_type in ['1','2of2','2of3']:
619             a = self.new_account_address(account_type)
620             if self.address_is_old(a):
621                 print "creating account", a
622                 self.create_account(account_type)
623
624
625     def synchronize_account(self, account):
626         new = []
627         new += self.synchronize_sequence(account, 0)
628         new += self.synchronize_sequence(account, 1)
629         return new
630
631
632     def synchronize(self):
633         if self.master_public_keys:
634             self.create_pending_accounts()
635         new = []
636         for account in self.accounts.values():
637             new += self.synchronize_account(account)
638         if new:
639             self.save_accounts()
640             self.config.set_key('addr_history', self.history, True)
641         return new
642
643
644     def is_found(self):
645         return self.history.values() != [[]] * len(self.history) 
646
647
648     def add_contact(self, address, label=None):
649         self.addressbook.append(address)
650         self.config.set_key('contacts', self.addressbook, True)
651         if label:  
652             self.labels[address] = label
653             self.config.set_key('labels', self.labels, True)
654
655     def delete_contact(self, addr):
656         if addr in self.addressbook:
657             self.addressbook.remove(addr)
658             self.config.set_key('addressbook', self.addressbook, True)
659
660
661     def fill_addressbook(self):
662         for tx_hash, tx in self.transactions.items():
663             is_relevant, is_send, _, _ = self.get_tx_value(tx)
664             if is_send:
665                 for addr, v in tx.outputs:
666                     if not self.is_mine(addr) and addr not in self.addressbook:
667                         self.addressbook.append(addr)
668         # redo labels
669         # self.update_tx_labels()
670
671     def get_num_tx(self, address):
672         n = 0 
673         for tx in self.transactions.values():
674             if address in map(lambda x:x[0], tx.outputs): n += 1
675         return n
676
677
678     def get_address_flags(self, addr):
679         flags = "C" if self.is_change(addr) else "I" if addr in self.imported_keys.keys() else "-" 
680         flags += "F" if addr in self.frozen_addresses else "P" if addr in self.prioritized_addresses else "-"
681         return flags
682         
683
684     def get_tx_value(self, tx, account=None):
685         domain = self.get_account_addresses(account)
686         return tx.get_value(domain, self.prevout_values)
687
688     
689     def update_tx_outputs(self, tx_hash):
690         tx = self.transactions.get(tx_hash)
691
692         for i, (addr, value) in enumerate(tx.outputs):
693             key = tx_hash+ ':%d'%i
694             self.prevout_values[key] = value
695
696         for item in tx.inputs:
697             if self.is_mine(item.get('address')):
698                 key = item['prevout_hash'] + ':%d'%item['prevout_n']
699                 self.spent_outputs.append(key)
700
701
702     def get_addr_balance(self, address):
703         assert self.is_mine(address)
704         h = self.history.get(address,[])
705         if h == ['*']: return 0,0
706         c = u = 0
707         received_coins = []   # list of coins received at address
708
709         for tx_hash, tx_height in h:
710             tx = self.transactions.get(tx_hash)
711             if not tx: continue
712
713             for i, (addr, value) in enumerate(tx.outputs):
714                 if addr == address:
715                     key = tx_hash + ':%d'%i
716                     received_coins.append(key)
717
718         for tx_hash, tx_height in h:
719             tx = self.transactions.get(tx_hash)
720             if not tx: continue
721             v = 0
722
723             for item in tx.inputs:
724                 addr = item.get('address')
725                 if addr == address:
726                     key = item['prevout_hash']  + ':%d'%item['prevout_n']
727                     value = self.prevout_values.get( key )
728                     if key in received_coins: 
729                         v -= value
730
731             for i, (addr, value) in enumerate(tx.outputs):
732                 key = tx_hash + ':%d'%i
733                 if addr == address:
734                     v += value
735
736             if tx_height:
737                 c += v
738             else:
739                 u += v
740         return c, u
741
742
743     def get_accounts(self):
744         accounts = {}
745         for k, account in self.accounts.items():
746             accounts[k] = self.labels.get(k, 'unnamed')
747         if self.imported_keys:
748             accounts[-1] = 'Imported keys'
749         return accounts
750
751     def get_account_addresses(self, a, include_change=True):
752         if a is None:
753             o = self.addresses(True)
754         elif a == -1:
755             o = self.imported_keys.keys()
756         else:
757             ac = self.accounts[a]
758             o = ac.get_addresses(0)
759             if include_change: o += ac.get_addresses(1)
760         return o
761
762     def get_imported_balance(self):
763         cc = uu = 0
764         for addr in self.imported_keys.keys():
765             c, u = self.get_addr_balance(addr)
766             cc += c
767             uu += u
768         return cc, uu
769
770     def get_account_balance(self, account):
771         if account is None:
772             return self.get_balance()
773         elif account == -1:
774             return self.get_imported_balance()
775         
776         conf = unconf = 0
777         for addr in self.get_account_addresses(account): 
778             c, u = self.get_addr_balance(addr)
779             conf += c
780             unconf += u
781         return conf, unconf
782
783     def get_frozen_balance(self):
784         conf = unconf = 0
785         for addr in self.frozen_addresses:
786             c, u = self.get_addr_balance(addr)
787             conf += c
788             unconf += u
789         return conf, unconf
790
791         
792     def get_balance(self):
793         cc = uu = 0
794         for a in self.accounts.keys():
795             c, u = self.get_account_balance(a)
796             cc += c
797             uu += u
798         c, u = self.get_imported_balance()
799         cc += c
800         uu += u
801         return cc, uu
802
803
804     def get_unspent_coins(self, domain=None):
805         coins = []
806         if domain is None: domain = self.addresses(True)
807         for addr in domain:
808             h = self.history.get(addr, [])
809             if h == ['*']: continue
810             for tx_hash, tx_height in h:
811                 tx = self.transactions.get(tx_hash)
812                 if tx is None: raise BaseException("Wallet not synchronized")
813                 for output in tx.d.get('outputs'):
814                     if output.get('address') != addr: continue
815                     key = tx_hash + ":%d" % output.get('index')
816                     if key in self.spent_outputs: continue
817                     output['tx_hash'] = tx_hash
818                     coins.append(output)
819         return coins
820
821
822
823     def choose_tx_inputs( self, amount, fixed_fee, account = None ):
824         """ todo: minimize tx size """
825         total = 0
826         fee = self.fee if fixed_fee is None else fixed_fee
827         domain = self.get_account_addresses(account)
828         coins = []
829         prioritized_coins = []
830         for i in self.frozen_addresses:
831             if i in domain: domain.remove(i)
832
833         for i in self.prioritized_addresses:
834             if i in domain: domain.remove(i)
835
836         coins = self.get_unspent_coins(domain)
837         prioritized_coins = self.get_unspent_coins(self.prioritized_addresses)
838
839         inputs = []
840         coins = prioritized_coins + coins
841
842         for item in coins: 
843             addr = item.get('address')
844             v = item.get('value')
845             total += v
846             inputs.append( item )
847             fee = self.estimated_fee(inputs) if fixed_fee is None else fixed_fee
848             if total >= amount + fee: break
849         else:
850             inputs = []
851
852         return inputs, total, fee
853
854
855     def estimated_fee(self, inputs):
856         estimated_size =  len(inputs) * 180 + 80     # this assumes non-compressed keys
857         fee = self.fee * int(round(estimated_size/1024.))
858         if fee == 0: fee = self.fee
859         return fee
860
861
862     def add_tx_change( self, inputs, outputs, amount, fee, total, change_addr=None, account=0 ):
863         "add change to a transaction"
864         change_amount = total - ( amount + fee )
865         if change_amount != 0:
866             if not change_addr:
867                 if account is None: 
868                     # send change to one of the accounts involved in the tx
869                     address = inputs[0].get('address')
870                     account, _ = self.get_address_index(address)
871
872                 if not self.use_change or account == -1:
873                     change_addr = inputs[-1]['address']
874                 else:
875                     change_addr = self.accounts[account].get_addresses(1)[-self.gap_limit_for_change]
876
877             # Insert the change output at a random position in the outputs
878             posn = random.randint(0, len(outputs))
879             outputs[posn:posn] = [( change_addr,  change_amount)]
880         return outputs
881
882
883     def get_history(self, address):
884         with self.lock:
885             return self.history.get(address)
886
887
888     def get_status(self, h):
889         if not h: return None
890         if h == ['*']: return '*'
891         status = ''
892         for tx_hash, height in h:
893             status += tx_hash + ':%d:' % height
894         return hashlib.sha256( status ).digest().encode('hex')
895
896
897     def receive_tx_callback(self, tx_hash, tx, tx_height):
898         if not self.check_new_tx(tx_hash, tx):
899             # may happen due to pruning
900             print_error("received transaction that is no longer referenced in history", tx_hash)
901             return
902
903         with self.transaction_lock:
904             self.transactions[tx_hash] = tx
905
906             self.interface.pending_transactions_for_notifications.append(tx)
907
908             self.save_transactions()
909             if self.verifier and tx_height>0: 
910                 self.verifier.add(tx_hash, tx_height)
911             self.update_tx_outputs(tx_hash)
912
913
914     def save_transactions(self):
915         tx = {}
916         for k,v in self.transactions.items():
917             tx[k] = str(v)
918         self.config.set_key('transactions', tx, True)
919
920     def receive_history_callback(self, addr, hist):
921
922         if not self.check_new_history(addr, hist):
923             raise BaseException("error: received history for %s is not consistent with known transactions"%addr)
924             
925         with self.lock:
926             self.history[addr] = hist
927             self.config.set_key('addr_history', self.history, True)
928
929         if hist != ['*']:
930             for tx_hash, tx_height in hist:
931                 if tx_height>0:
932                     # add it in case it was previously unconfirmed
933                     if self.verifier: self.verifier.add(tx_hash, tx_height)
934
935
936     def get_tx_history(self, account=None):
937         with self.transaction_lock:
938             history = self.transactions.items()
939             history.sort(key = lambda x: self.verifier.get_txpos(x[0]))
940             result = []
941     
942             balance = 0
943             for tx_hash, tx in history:
944                 is_relevant, is_mine, v, fee = self.get_tx_value(tx, account)
945                 if v is not None: balance += v
946
947             c, u = self.get_account_balance(account)
948
949             if balance != c+u:
950                 result.append( ('', 1000, 0, c+u-balance, None, c+u-balance, None ) )
951
952             balance = c + u - balance
953             for tx_hash, tx in history:
954                 is_relevant, is_mine, value, fee = self.get_tx_value(tx, account)
955                 if not is_relevant:
956                     continue
957                 if value is not None:
958                     balance += value
959
960                 conf, timestamp = self.verifier.get_confirmations(tx_hash) if self.verifier else (None, None)
961                 result.append( (tx_hash, conf, is_mine, value, fee, balance, timestamp) )
962
963         return result
964
965
966     def get_label(self, tx_hash):
967         label = self.labels.get(tx_hash)
968         is_default = (label == '') or (label is None)
969         if is_default: label = self.get_default_label(tx_hash)
970         return label, is_default
971
972
973     def get_default_label(self, tx_hash):
974         tx = self.transactions.get(tx_hash)
975         default_label = ''
976         if tx:
977             is_relevant, is_mine, _, _ = self.get_tx_value(tx)
978             if is_mine:
979                 for o in tx.outputs:
980                     o_addr, _ = o
981                     if not self.is_mine(o_addr):
982                         try:
983                             default_label = self.labels[o_addr]
984                         except KeyError:
985                             default_label = o_addr
986                         break
987                 else:
988                     default_label = '(internal)'
989             else:
990                 for o in tx.outputs:
991                     o_addr, _ = o
992                     if self.is_mine(o_addr) and not self.is_change(o_addr):
993                         break
994                 else:
995                     for o in tx.outputs:
996                         o_addr, _ = o
997                         if self.is_mine(o_addr):
998                             break
999                     else:
1000                         o_addr = None
1001
1002                 if o_addr:
1003                     dest_label = self.labels.get(o_addr)
1004                     try:
1005                         default_label = self.labels[o_addr]
1006                     except KeyError:
1007                         default_label = o_addr
1008
1009         return default_label
1010
1011
1012     def mktx(self, outputs, password, fee=None, change_addr=None, account=None ):
1013         
1014         for address, x in outputs:
1015             assert is_valid(address)
1016
1017         amount = sum( map(lambda x:x[1], outputs) )
1018
1019         inputs, total, fee = self.choose_tx_inputs( amount, fee, account )
1020         if not inputs:
1021             raise ValueError("Not enough funds")
1022
1023         outputs = self.add_tx_change(inputs, outputs, amount, fee, total, change_addr, account)
1024         tx = Transaction.from_io(inputs, outputs)
1025
1026         keypairs = {}
1027         for i, txin in enumerate(tx.inputs):
1028             address = txin['address']
1029
1030             account, sequence = self.get_address_index(address)
1031             txin['KeyID'] = self.get_keyID(account, sequence)
1032
1033             redeemScript = self.accounts[account].redeem_script(sequence)
1034             if redeemScript: 
1035                 txin['redeemScript'] = redeemScript
1036             else:
1037                 txin['redeemPubkey'] = self.accounts[account].get_pubkey(*sequence)
1038
1039             private_keys = self.get_private_key(address, password)
1040
1041             for sec in private_keys:
1042                 pubkey = public_key_from_private_key(sec)
1043                 keypairs[ pubkey ] = sec
1044
1045         tx.sign(keypairs)
1046         for address, x in outputs:
1047             if address not in self.addressbook and not self.is_mine(address):
1048                 self.addressbook.append(address)
1049
1050         return tx
1051
1052
1053
1054     def sendtx(self, tx):
1055         # synchronous
1056         h = self.send_tx(tx)
1057         self.tx_event.wait()
1058         return self.receive_tx(h)
1059
1060     def send_tx(self, tx):
1061         # asynchronous
1062         self.tx_event.clear()
1063         self.interface.send([('blockchain.transaction.broadcast', [str(tx)])], 'synchronizer')
1064         return tx.hash()
1065
1066     def receive_tx(self,tx_hash):
1067         out = self.tx_result 
1068         if out != tx_hash:
1069             return False, "error: " + out
1070         return True, out
1071
1072
1073
1074     def update_password(self, seed, old_password, new_password):
1075         if new_password == '': new_password = None
1076         # this will throw an exception if unicode cannot be converted
1077         self.seed = pw_encode( seed, new_password)
1078         self.config.set_key('seed', self.seed, True)
1079         self.use_encryption = (new_password != None)
1080         self.config.set_key('use_encryption', self.use_encryption,True)
1081         for k in self.imported_keys.keys():
1082             a = self.imported_keys[k]
1083             b = pw_decode(a, old_password)
1084             c = pw_encode(b, new_password)
1085             self.imported_keys[k] = c
1086         self.config.set_key('imported_keys', self.imported_keys, True)
1087
1088         for k, v in self.master_private_keys.items():
1089             b = pw_decode(v, old_password)
1090             c = pw_encode(b, new_password)
1091             self.master_private_keys[k] = c
1092         self.config.set_key('master_private_keys', self.master_private_keys, True)
1093
1094
1095     def freeze(self,addr):
1096         if self.is_mine(addr) and addr not in self.frozen_addresses:
1097             self.unprioritize(addr)
1098             self.frozen_addresses.append(addr)
1099             self.config.set_key('frozen_addresses', self.frozen_addresses, True)
1100             return True
1101         else:
1102             return False
1103
1104     def unfreeze(self,addr):
1105         if self.is_mine(addr) and addr in self.frozen_addresses:
1106             self.frozen_addresses.remove(addr)
1107             self.config.set_key('frozen_addresses', self.frozen_addresses, True)
1108             return True
1109         else:
1110             return False
1111
1112     def prioritize(self,addr):
1113         if self.is_mine(addr) and addr not in self.prioritized_addresses:
1114             self.unfreeze(addr)
1115             self.prioritized_addresses.append(addr)
1116             self.config.set_key('prioritized_addresses', self.prioritized_addresses, True)
1117             return True
1118         else:
1119             return False
1120
1121     def unprioritize(self,addr):
1122         if self.is_mine(addr) and addr in self.prioritized_addresses:
1123             self.prioritized_addresses.remove(addr)
1124             self.config.set_key('prioritized_addresses', self.prioritized_addresses, True)
1125             return True
1126         else:
1127             return False
1128
1129     def set_fee(self, fee):
1130         if self.fee != fee:
1131             self.fee = fee
1132             self.config.set_key('fee_per_kb', self.fee, True)
1133         
1134
1135     def save(self):
1136         print_error("Warning: wallet.save() is deprecated")
1137         tx = {}
1138         for k,v in self.transactions.items():
1139             tx[k] = str(v)
1140             
1141         s = {
1142             'use_change': self.use_change,
1143             'fee_per_kb': self.fee,
1144             'addr_history': self.history, 
1145             'labels': self.labels,
1146             'contacts': self.addressbook,
1147             'num_zeros': self.num_zeros,
1148             'frozen_addresses': self.frozen_addresses,
1149             'prioritized_addresses': self.prioritized_addresses,
1150             'gap_limit': self.gap_limit,
1151             'transactions': tx,
1152         }
1153         for k, v in s.items():
1154             self.config.set_key(k,v)
1155         self.config.save()
1156
1157     def set_verifier(self, verifier):
1158         self.verifier = verifier
1159
1160         # review transactions that are in the history
1161         for addr, hist in self.history.items():
1162             if hist == ['*']: continue
1163             for tx_hash, tx_height in hist:
1164                 if tx_height>0:
1165                     # add it in case it was previously unconfirmed
1166                     self.verifier.add(tx_hash, tx_height)
1167
1168
1169         # if we are on a pruning server, remove unverified transactions
1170         vr = self.verifier.transactions.keys() + self.verifier.verified_tx.keys()
1171         for tx_hash in self.transactions.keys():
1172             if tx_hash not in vr:
1173                 self.transactions.pop(tx_hash)
1174
1175
1176
1177     def check_new_history(self, addr, hist):
1178         
1179         # check that all tx in hist are relevant
1180         if hist != ['*']:
1181             for tx_hash, height in hist:
1182                 tx = self.transactions.get(tx_hash)
1183                 if not tx: continue
1184                 if not tx.has_address(addr):
1185                     return False
1186
1187         # check that we are not "orphaning" a transaction
1188         old_hist = self.history.get(addr,[])
1189         if old_hist == ['*']: return True
1190
1191         for tx_hash, height in old_hist:
1192             if tx_hash in map(lambda x:x[0], hist): continue
1193             found = False
1194             for _addr, _hist in self.history.items():
1195                 if _addr == addr: continue
1196                 if _hist == ['*']: continue
1197                 _tx_hist = map(lambda x:x[0], _hist)
1198                 if tx_hash in _tx_hist:
1199                     found = True
1200                     break
1201
1202             if not found:
1203                 tx = self.transactions.get(tx_hash)
1204                 # tx might not be there
1205                 if not tx: continue
1206                 
1207                 # already verified?
1208                 if self.verifier.get_height(tx_hash):
1209                     continue
1210                 # unconfirmed tx
1211                 print_error("new history is orphaning transaction:", tx_hash)
1212                 # check that all outputs are not mine, request histories
1213                 ext_requests = []
1214                 for _addr, _v in tx.outputs:
1215                     # assert not self.is_mine(_addr)
1216                     ext_requests.append( ('blockchain.address.get_history', [_addr]) )
1217
1218                 ext_h = self.interface.synchronous_get(ext_requests)
1219                 print_error("sync:", ext_requests, ext_h)
1220                 height = None
1221                 for h in ext_h:
1222                     if h == ['*']: continue
1223                     for item in h:
1224                         if item.get('tx_hash') == tx_hash:
1225                             height = item.get('height')
1226                 if height:
1227                     print_error("found height for", tx_hash, height)
1228                     self.verifier.add(tx_hash, height)
1229                 else:
1230                     print_error("removing orphaned tx from history", tx_hash)
1231                     self.transactions.pop(tx_hash)
1232
1233         return True
1234
1235
1236
1237     def check_new_tx(self, tx_hash, tx):
1238         # 1 check that tx is referenced in addr_history. 
1239         addresses = []
1240         for addr, hist in self.history.items():
1241             if hist == ['*']:continue
1242             for txh, height in hist:
1243                 if txh == tx_hash: 
1244                     addresses.append(addr)
1245
1246         if not addresses:
1247             return False
1248
1249         # 2 check that referencing addresses are in the tx
1250         for addr in addresses:
1251             if not tx.has_address(addr):
1252                 return False
1253
1254         return True
1255
1256
1257
1258
1259 class WalletSynchronizer(threading.Thread):
1260
1261
1262     def __init__(self, wallet, config):
1263         threading.Thread.__init__(self)
1264         self.daemon = True
1265         self.wallet = wallet
1266         wallet.synchronizer = self
1267         self.interface = self.wallet.interface
1268         self.interface.register_channel('synchronizer')
1269         self.wallet.interface.register_callback('connected', lambda: self.wallet.set_up_to_date(False))
1270         self.was_updated = True
1271         self.running = False
1272         self.lock = threading.Lock()
1273
1274     def stop(self):
1275         with self.lock: self.running = False
1276         self.interface.poke('synchronizer')
1277
1278     def is_running(self):
1279         with self.lock: return self.running
1280
1281     
1282     def subscribe_to_addresses(self, addresses):
1283         messages = []
1284         for addr in addresses:
1285             messages.append(('blockchain.address.subscribe', [addr]))
1286         self.interface.send( messages, 'synchronizer')
1287
1288
1289     def run(self):
1290         with self.lock: self.running = True
1291
1292         requested_tx = []
1293         missing_tx = []
1294         requested_histories = {}
1295
1296         # request any missing transactions
1297         for history in self.wallet.history.values():
1298             if history == ['*']: continue
1299             for tx_hash, tx_height in history:
1300                 if self.wallet.transactions.get(tx_hash) is None and (tx_hash, tx_height) not in missing_tx:
1301                     missing_tx.append( (tx_hash, tx_height) )
1302         print_error("missing tx", missing_tx)
1303
1304         # wait until we are connected, in case the user is not connected
1305         while not self.interface.is_connected:
1306             time.sleep(1)
1307         
1308         # subscriptions
1309         self.subscribe_to_addresses(self.wallet.addresses(True))
1310
1311         while self.is_running():
1312             # 1. create new addresses
1313             new_addresses = self.wallet.synchronize()
1314
1315             # request missing addresses
1316             if new_addresses:
1317                 self.subscribe_to_addresses(new_addresses)
1318
1319             # request missing transactions
1320             for tx_hash, tx_height in missing_tx:
1321                 if (tx_hash, tx_height) not in requested_tx:
1322                     self.interface.send([ ('blockchain.transaction.get',[tx_hash, tx_height]) ], 'synchronizer')
1323                     requested_tx.append( (tx_hash, tx_height) )
1324             missing_tx = []
1325
1326             # detect if situation has changed
1327             if not self.interface.is_up_to_date('synchronizer'):
1328                 if self.wallet.is_up_to_date():
1329                     self.wallet.set_up_to_date(False)
1330                     self.was_updated = True
1331             else:
1332                 if not self.wallet.is_up_to_date():
1333                     self.wallet.set_up_to_date(True)
1334                     self.was_updated = True
1335
1336             if self.was_updated:
1337                 self.interface.trigger_callback('updated')
1338                 self.was_updated = False
1339
1340             # 2. get a response
1341             r = self.interface.get_response('synchronizer')
1342
1343             # poke sends None. (needed during stop)
1344             if not r: continue
1345
1346             # 3. handle response
1347             method = r['method']
1348             params = r['params']
1349             result = r.get('result')
1350             error = r.get('error')
1351             if error:
1352                 print "error", r
1353                 continue
1354
1355             if method == 'blockchain.address.subscribe':
1356                 addr = params[0]
1357                 if self.wallet.get_status(self.wallet.get_history(addr)) != result:
1358                     if requested_histories.get(addr) is None:
1359                         self.interface.send([('blockchain.address.get_history', [addr])], 'synchronizer')
1360                         requested_histories[addr] = result
1361
1362             elif method == 'blockchain.address.get_history':
1363                 addr = params[0]
1364                 print_error("receiving history", addr, result)
1365                 if result == ['*']:
1366                     assert requested_histories.pop(addr) == '*'
1367                     self.wallet.receive_history_callback(addr, result)
1368                 else:
1369                     hist = []
1370                     # check that txids are unique
1371                     txids = []
1372                     for item in result:
1373                         tx_hash = item['tx_hash']
1374                         if tx_hash not in txids:
1375                             txids.append(tx_hash)
1376                             hist.append( (tx_hash, item['height']) )
1377
1378                     if len(hist) != len(result):
1379                         raise BaseException("error: server sent history with non-unique txid", result)
1380
1381                     # check that the status corresponds to what was announced
1382                     rs = requested_histories.pop(addr)
1383                     if self.wallet.get_status(hist) != rs:
1384                         raise BaseException("error: status mismatch: %s"%addr)
1385                 
1386                     # store received history
1387                     self.wallet.receive_history_callback(addr, hist)
1388
1389                     # request transactions that we don't have 
1390                     for tx_hash, tx_height in hist:
1391                         if self.wallet.transactions.get(tx_hash) is None:
1392                             if (tx_hash, tx_height) not in requested_tx and (tx_hash, tx_height) not in missing_tx:
1393                                 missing_tx.append( (tx_hash, tx_height) )
1394
1395             elif method == 'blockchain.transaction.get':
1396                 tx_hash = params[0]
1397                 tx_height = params[1]
1398                 assert tx_hash == hash_encode(Hash(result.decode('hex')))
1399                 tx = Transaction(result)
1400                 self.wallet.receive_tx_callback(tx_hash, tx, tx_height)
1401                 self.was_updated = True
1402                 requested_tx.remove( (tx_hash, tx_height) )
1403                 print_error("received tx:", tx_hash, len(tx.raw))
1404
1405             elif method == 'blockchain.transaction.broadcast':
1406                 self.wallet.tx_result = result
1407                 self.wallet.tx_event.set()
1408
1409             else:
1410                 print_error("Error: Unknown message:" + method + ", " + repr(params) + ", " + repr(result) )
1411
1412             if self.was_updated and not requested_tx:
1413                 self.interface.trigger_callback('updated')
1414                 self.interface.trigger_callback("new_transaction") # Updated gets called too many times from other places as well; if we use that signal we get the notification three times
1415                 
1416
1417                 self.was_updated = False