Workaround for bug in Python's math.log function
[bitcoin:eloipool.git] / merklemaker.py
1 # Eloipool - Python Bitcoin pool server
2 # Copyright (C) 2011-2012  Luke Dashjr <luke-jr+eloipool@utopios.org>
3 #
4 # This program is free software: you can redistribute it and/or modify
5 # it under the terms of the GNU Affero General Public License as
6 # published by the Free Software Foundation, either version 3 of the
7 # License, or (at your option) any later version.
8 #
9 # This program is distributed in the hope that it will be useful,
10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 # GNU Affero General Public License for more details.
13 #
14 # You should have received a copy of the GNU Affero General Public License
15 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
16
17 from binascii import b2a_hex
18 import bitcoin.script
19 from bitcoin.script import countSigOps
20 from bitcoin.txn import Txn
21 from collections import deque
22 from copy import deepcopy
23 from queue import Queue
24 import jsonrpc
25 import logging
26 from math import log
27 from merkletree import MerkleTree
28 from struct import pack
29 import threading
30 from time import sleep, time
31 import traceback
32
33 _makeCoinbase = [0, 0]
34
35 class merkleMaker(threading.Thread):
36         OldGMP = None
37         GBTCaps = [
38                 'coinbasevalue',
39                 'coinbase/append',
40                 'coinbase',
41                 'generation',
42                 'time',
43                 'transactions/remove',
44                 'prevblock',
45         ]
46         GBTReq = {
47                 'capabilities': GBTCaps,
48         }
49         GMPReq = {
50                 'capabilities': GBTCaps,
51                 'tx': 'obj',
52         }
53         
54         def __init__(self, *a, **k):
55                 super().__init__(*a, **k)
56                 self.daemon = True
57                 self.logger = logging.getLogger('merkleMaker')
58                 self.CoinbasePrefix = b''
59                 self.CoinbaseAux = {}
60                 self.isOverflowed = False
61                 self.lastWarning = {}
62                 self.MinimumTxnUpdateWait = 5
63                 self.overflowed = 0
64                 self.DifficultyChangeMod = 2016
65         
66         def _prepare(self):
67                 self.access = jsonrpc.ServiceProxy(self.UpstreamURI)
68                 
69                 self.currentBlock = (None, None, None)
70                 
71                 self.currentMerkleTree = None
72                 self.merkleRoots = deque(maxlen=self.WorkQueueSizeRegular[1])
73                 self.LowestMerkleRoots = self.WorkQueueSizeRegular[1]
74                 
75                 if not hasattr(self, 'WorkQueueSizeClear'):
76                         self.WorkQueueSizeClear = self.WorkQueueSizeLongpoll
77                 self._MaxClearSize = max(self.WorkQueueSizeClear[1], self.WorkQueueSizeLongpoll[1])
78                 self.clearMerkleTree = MerkleTree([self.clearCoinbaseTxn])
79                 self.clearMerkleRoots = Queue(self._MaxClearSize)
80                 self.LowestClearMerkleRoots = self.WorkQueueSizeClear[1]
81                 self.nextMerkleRoots = Queue(self._MaxClearSize)
82                 
83                 if not hasattr(self, 'WarningDelay'):
84                         self.WarningDelay = max(15, self.MinimumTxnUpdateWait * 2)
85                 if not hasattr(self, 'WarningDelayTxnLongpoll'):
86                         self.WarningDelayTxnLongpoll = self.WarningDelay
87                 if not hasattr(self, 'WarningDelayMerkleUpdate'):
88                         self.WarningDelayMerkleUpdate = self.WarningDelay
89                 
90                 self.lastMerkleUpdate = 0
91                 self.nextMerkleUpdate = 0
92                 global now
93                 now = time()
94                 self.updateMerkleTree()
95         
96         def updateBlock(self, newBlock, height = None, bits = None, _HBH = None):
97                 if newBlock == self.currentBlock[0]:
98                         if height in (None, self.currentBlock[1]) and bits in (None, self.currentBlock[2]):
99                                 return
100                         if not self.currentBlock[2] is None:
101                                 self.logger.error('Was working on block with wrong specs: %s (height: %d->%d; bits: %s->%s' % (
102                                         b2a_hex(newBlock[::-1]).decode('utf8'),
103                                         self.currentBlock[1],
104                                         height,
105                                         b2a_hex(self.currentBlock[2][::-1]).decode('utf8'),
106                                         b2a_hex(bits[::-1]).decode('utf8'),
107                                 ))
108                 
109                 # Old block is invalid
110                 self.currentMerkleTree = self.clearMerkleTree
111                 if self.currentBlock[0] != newBlock:
112                         self.lastBlock = self.currentBlock
113                 
114                 if height is None:
115                         height = self.currentBlock[1] + 1
116                 if bits is None:
117                         if height % self.DifficultyChangeMod == 1 or self.currentBlock[2] is None:
118                                 self.logger.warning('New block: %s (height %d; bits: UNKNOWN)' % (b2a_hex(newBlock[::-1]).decode('utf8'), height))
119                                 # Pretend to be 1 lower height, so we possibly retain nextMerkleRoots
120                                 self.currentBlock = (None, height - 1, None)
121                                 self.clearMerkleRoots = Queue(0)
122                                 self.merkleRoots.clear()
123                                 return
124                         else:
125                                 bits = self.currentBlock[2]
126                 
127                 if _HBH is None:
128                         _HBH = (b2a_hex(newBlock[::-1]).decode('utf8'), b2a_hex(bits[::-1]).decode('utf8'))
129                 self.logger.info('New block: %s (height: %d; bits: %s)' % (_HBH[0], height, _HBH[1]))
130                 self.currentBlock = (newBlock, height, bits)
131                 
132                 if self.currentBlock[1] != height:
133                         if self.currentBlock[1] == height - 1:
134                                 self.clearMerkleRoots = self.nextMerkleRoots
135                                 self.logger.debug('Adopting next-height clear merkleroots :)')
136                         else:
137                                 if self.currentBlock[1]:
138                                         self.logger.warning('Change from height %d->%d; no longpoll merkleroots available!' % (self.currentBlock[1], height))
139                                 self.clearMerkleRoots = Queue(self.WorkQueueSizeClear[1])
140                         self.nextMerkleRoots = Queue(self._MaxClearSize)
141                 else:
142                         self.logger.debug('Already using clear merkleroots for this height')
143                 self.merkleRoots.clear()
144                 
145                 self.needMerkle = 2
146                 self.onBlockChange()
147         
148         def _trimBlock(self, MP, txnlist, txninfo, floodn, msgf):
149                 fee = txninfo[-1].get('fee', None)
150                 if fee is None:
151                         raise self._floodCritical(now, floodn, doin=msgf('fees unknown'))
152                 if fee:
153                         # FIXME: coinbasevalue is *not* guaranteed to exist here
154                         MP['coinbasevalue'] -= fee
155                 
156                 txnlist[-1:] = ()
157                 txninfo[-1:] = ()
158                 
159                 return True
160         
161         # Aggressive "Power Of Two": Remove transactions even with fees to reach our goal
162         def _APOT(self, txninfopot, MP, POTInfo):
163                 feeTxnsTrimmed = 0
164                 feesTrimmed = 0
165                 for txn in txninfopot:
166                         if txn.get('fee') is None:
167                                 self._floodWarning(now, 'APOT-No-Fees', doin='Upstream didn\'t provide fee information required for aggressive POT', logf=self.logger.info)
168                                 return
169                         if not txn['fee']:
170                                 continue
171                         feesTrimmed += txn['fee']
172                         feeTxnsTrimmed += 1
173                 MP['coinbasevalue'] -= feesTrimmed
174                 
175                 POTInfo[2] = [feeTxnsTrimmed, feesTrimmed]
176                 self._floodWarning(now, 'POT-Trimming-Fees', doin='Aggressive POT trimming %d transactions with %d.%08d BTC total fees' % (feeTxnsTrimmed, feesTrimmed//100000000, feesTrimmed % 100000000), logf=self.logger.debug)
177                 
178                 return True
179         
180         def _makeBlockSafe(self, MP, txnlist, txninfo):
181                 blocksize = sum(map(len, txnlist)) + 80
182                 while blocksize > 934464:  # 1 "MB" limit - 64 KB breathing room
183                         txnsize = len(txnlist[-1])
184                         self._trimBlock(MP, txnlist, txninfo, 'SizeLimit', lambda x: 'Making blocks over 1 MB size limit (%d bytes; %s)' % (blocksize, x))
185                         blocksize -= txnsize
186                 
187                 # NOTE: This check doesn't work at all without BIP22 transaction obj format
188                 blocksigops = sum(a.get('sigops', 0) for a in txninfo)
189                 while blocksigops > 19488:  # 20k limit - 0x200 breathing room
190                         txnsigops = txninfo[-1]['sigops']
191                         self._trimBlock(MP, txnlist, txninfo, 'SigOpLimit', lambda x: 'Making blocks over 20k SigOp limit (%d; %s)' % (blocksigops, x))
192                         blocksigops -= txnsigops
193                 
194                 # Aim to produce blocks with "Power Of Two" transaction counts
195                 # This helps avoid any chance of someone abusing CVE-2012-2459 with them
196                 POTMode = getattr(self, 'POT', 1)
197                 txncount = len(txnlist) + 1
198                 if POTMode:
199                         feetxncount = txncount
200                         for i in range(txncount - 2, -1, -1):
201                                 if 'fee' not in txninfo[i] or txninfo[i]['fee']:
202                                         break
203                                 feetxncount -= 1
204                         
205                         if getattr(self, 'Greedy', None):
206                                 # Aim to cut off extra zero-fee transactions on the end
207                                 # NOTE: not cutting out ones intermixed, in case of dependencies
208                                 idealtxncount = feetxncount
209                         else:
210                                 idealtxncount = txncount
211                         
212                         pot = 2**int(log(idealtxncount, 2))
213                         POTInfo = MP['POTInfo'] = [[idealtxncount, feetxncount, txncount], [pot, None], None]
214                         if pot < idealtxncount:
215                                 if pot * 2 <= txncount:
216                                         pot *= 2
217                                 elif pot >= feetxncount:
218                                         pass
219                                 elif POTMode > 1 and self._APOT(txninfo[pot-1:], MP, POTInfo):
220                                         # Trimmed even transactions with fees
221                                         pass
222                                 else:
223                                         pot = idealtxncount
224                                         self._floodWarning(now, 'Non-POT', doin='Making merkle tree with %d transactions (ideal: %d; max: %d)' % (pot, idealtxncount, txncount))
225                         POTInfo[1][1] = pot
226                         pot -= 1
227                         txnlist[pot:] = ()
228                         txninfo[pot:] = ()
229         
230         def updateMerkleTree(self):
231                 global now
232                 self.logger.debug('Polling bitcoind for memorypool')
233                 self.nextMerkleUpdate = now + self.TxnUpdateRetryWait
234                 
235                 try:
236                         # First, try BIP 22 standard getblocktemplate :)
237                         MP = self.access.getblocktemplate(self.GBTReq)
238                         self.OldGMP = False
239                 except:
240                         try:
241                                 # Failing that, give BIP 22 draft (2012-02 through 2012-07) getmemorypool a chance
242                                 MP = self.access.getmemorypool(self.GMPReq)
243                         except:
244                                 try:
245                                         # Finally, fall back to bitcoind 0.5/0.6 getmemorypool
246                                         MP = self.access.getmemorypool()
247                                 except:
248                                         MP = False
249                         if MP is False:
250                                 # This way, we get the error from the BIP22 call if the old one fails too
251                                 raise
252                         
253                         # Pre-BIP22 server (bitcoind <0.7 or Eloipool <20120513)
254                         if not self.OldGMP:
255                                 self.OldGMP = True
256                                 self.logger.warning('Upstream server is not BIP 22 compatible')
257                 
258                 oMP = deepcopy(MP)
259                 
260                 prevBlock = bytes.fromhex(MP['previousblockhash'])[::-1]
261                 if 'height' in MP:
262                         height = MP['height']
263                 else:
264                         height = self.access.getinfo()['blocks'] + 1
265                 bits = bytes.fromhex(MP['bits'])[::-1]
266                 if (prevBlock, height, bits) != self.currentBlock:
267                         self.updateBlock(prevBlock, height, bits, _HBH=(MP['previousblockhash'], MP['bits']))
268                 
269                 txnlist = MP['transactions']
270                 if len(txnlist) and isinstance(txnlist[0], dict):
271                         txninfo = txnlist
272                         txnlist = tuple(a['data'] for a in txnlist)
273                         txninfo.insert(0, {
274                         })
275                 elif 'transactionfees' in MP:
276                         # Backward compatibility with pre-BIP22 gmp_fees branch
277                         txninfo = [{'fee':a} for a in MP['transactionfees']]
278                 else:
279                         # Backward compatibility with pre-BIP22 hex-only (bitcoind <0.7, Eloipool <future)
280                         txninfo = [{}] * len(txnlist)
281                 # TODO: cache Txn or at least txid from previous merkle roots?
282                 txnlist = [a for a in map(bytes.fromhex, txnlist)]
283                 
284                 self._makeBlockSafe(MP, txnlist, txninfo)
285                 
286                 cbtxn = self.makeCoinbaseTxn(MP['coinbasevalue'])
287                 cbtxn.setCoinbase(b'\0\0')
288                 cbtxn.assemble()
289                 txnlist.insert(0, cbtxn.data)
290                 
291                 txnlist = [a for a in map(Txn, txnlist[1:])]
292                 txnlist.insert(0, cbtxn)
293                 txnlist = list(txnlist)
294                 newMerkleTree = MerkleTree(txnlist)
295                 if newMerkleTree.merkleRoot() != self.currentMerkleTree.merkleRoot():
296                         newMerkleTree.POTInfo = MP.get('POTInfo')
297                         newMerkleTree.oMP = oMP
298                         self.logger.debug('Updating merkle tree')
299                         self.currentMerkleTree = newMerkleTree
300                 self.lastMerkleUpdate = now
301                 self.nextMerkleUpdate = now + self.MinimumTxnUpdateWait
302                 
303                 if self.needMerkle == 2:
304                         self.needMerkle = 1
305                         self.needMerkleSince = now
306         
307         def makeCoinbase(self, height):
308                 now = int(time())
309                 if now > _makeCoinbase[0]:
310                         _makeCoinbase[0] = now
311                         _makeCoinbase[1] = 0
312                 else:
313                         _makeCoinbase[1] += 1
314                 rv = self.CoinbasePrefix
315                 rv += pack('>L', now) + pack('>Q', _makeCoinbase[1]).lstrip(b'\0')
316                 # NOTE: Not using varlenEncode, since this is always guaranteed to be < 100
317                 rv = bytes( (len(rv),) ) + rv
318                 for v in self.CoinbaseAux.values():
319                         rv += v
320                 if len(rv) > 95:
321                         t = time()
322                         if self.overflowed < t - 300:
323                                 self.logger.warning('Overflowing coinbase data! %d bytes long' % (len(rv),))
324                                 self.overflowed = t
325                                 self.isOverflowed = True
326                         rv = rv[:95]
327                 else:
328                         self.isOverflowed = False
329                 rv = bitcoin.script.encodeUNum(height) + rv
330                 return rv
331         
332         def makeMerkleRoot(self, merkleTree, height):
333                 cbtxn = merkleTree.data[0]
334                 cb = self.makeCoinbase(height=height)
335                 cbtxn.setCoinbase(cb)
336                 cbtxn.assemble()
337                 merkleRoot = merkleTree.merkleRoot()
338                 return (merkleRoot, merkleTree, cb)
339         
340         _doing_last = None
341         def _doing(self, what):
342                 if self._doing_last == what:
343                         self._doing_i += 1
344                         return
345                 global now
346                 if self._doing_last:
347                         self.logger.debug("Switching from (%4dx in %5.3f seconds) %s => %s" % (self._doing_i, now - self._doing_s, self._doing_last, what))
348                 self._doing_last = what
349                 self._doing_i = 1
350                 self._doing_s = now
351         
352         def _floodWarning(self, now, wid, wmsgf = None, doin = True, logf = None):
353                 if doin is True:
354                         doin = self._doing_last
355                         def a(f = wmsgf):
356                                 return lambda: "%s (doing %s)" % (f(), doin)
357                         wmsgf = a()
358                 winfo = self.lastWarning.setdefault(wid, [0, None])
359                 (lastTime, lastDoing) = winfo
360                 if now <= lastTime + max(5, self.MinimumTxnUpdateWait):
361                         return
362                 winfo[0] = now
363                 nowDoing = doin
364                 winfo[1] = nowDoing
365                 if logf is None:
366                         logf = self.logger.warning
367                 logf(wmsgf() if wmsgf else doin)
368         
369         def _makeOne(self, putf, merkleTree, height):
370                 MT = self.currentMerkleTree
371                 height = self.currentBlock[1]
372                 MR = self.makeMerkleRoot(MT, height=height)
373                 # Only add it if the height hasn't changed in the meantime, to avoid a race
374                 if self.currentBlock[1] == height:
375                         putf(MR)
376         
377         def makeClear(self):
378                 self._doing('clear merkle roots')
379                 self._makeOne(self.clearMerkleRoots.put, self.clearMerkleTree, height=self.currentBlock[1])
380         
381         def makeNext(self):
382                 self._doing('longpoll merkle roots')
383                 self._makeOne(self.nextMerkleRoots.put, self.clearMerkleTree, height=self.currentBlock[1] + 1)
384         
385         def makeRegular(self):
386                 self._doing('regular merkle roots')
387                 self._makeOne(self.merkleRoots.append, self.currentMerkleTree, height=self.currentBlock[1])
388         
389         def merkleMaker_II(self):
390                 global now
391                 
392                 # No bits = no mining :(
393                 if self.currentBlock[2] is None:
394                         return self.updateMerkleTree()
395                 
396                 # First, ensure we have the minimum clear, next, and regular (in that order)
397                 if self.clearMerkleRoots.qsize() < self.WorkQueueSizeClear[0]:
398                         return self.makeClear()
399                 if self.nextMerkleRoots.qsize() < self.WorkQueueSizeLongpoll[0]:
400                         return self.makeNext()
401                 if len(self.merkleRoots) < self.WorkQueueSizeRegular[0]:
402                         return self.makeRegular()
403                 
404                 # If we've met the minimum requirements, consider updating the merkle tree
405                 if self.nextMerkleUpdate <= now:
406                         return self.updateMerkleTree()
407                 
408                 # Finally, fill up clear, next, and regular until we've met the maximums
409                 if self.clearMerkleRoots.qsize() < self.WorkQueueSizeClear[1]:
410                         return self.makeClear()
411                 if self.nextMerkleRoots.qsize() < self.WorkQueueSizeLongpoll[1]:
412                         return self.makeNext()
413                 if len(self.merkleRoots) < self.WorkQueueSizeRegular[1] or self.merkleRoots[0][1] != self.currentMerkleTree:
414                         return self.makeRegular()
415                 
416                 # Nothing left to do, fire onBlockUpdate event (if appropriate) and sleep
417                 if self.needMerkle == 1:
418                         self.onBlockUpdate()
419                         self.needMerkle = False
420                 self._doing('idle')
421                 # TODO: rather than sleepspin, block until MinimumTxnUpdateWait expires or threading.Condition(?)
422                 sleep(self.IdleSleepTime)
423         
424         def merkleMaker_I(self):
425                 global now
426                 now = time()
427                 
428                 self.merkleMaker_II()
429                 
430                 if self.needMerkle == 1 and now > self.needMerkleSince + self.WarningDelayTxnLongpoll:
431                         self._floodWarning(now, 'NeedMerkle', lambda: 'Transaction-longpoll requested %d seconds ago, and still not ready. Is your server fast enough to keep up with your configured WorkQueueSizeRegular maximum?' % (now - self.needMerkleSince,))
432                 if now > self.nextMerkleUpdate + self.WarningDelayMerkleUpdate:
433                         self._floodWarning(now, 'MerkleUpdate', lambda: "Haven't updated the merkle tree in at least %d seconds! Is your server fast enough to keep up with your configured work queue minimums?" % (now - self.lastMerkleUpdate,))
434         
435         def run(self):
436                 while True:
437                         try:
438                                 self.merkleMaker_I()
439                         except:
440                                 self.logger.critical(traceback.format_exc())
441         
442         def start(self, *a, **k):
443                 self._prepare()
444                 super().start(*a, **k)
445         
446         def getMRD(self):
447                 try:
448                         MRD = self.merkleRoots.pop()
449                         self.LowestMerkleRoots = min(len(self.merkleRoots), self.LowestMerkleRoots)
450                         rollPrevBlk = False
451                 except IndexError:
452                         qsz = self.clearMerkleRoots.qsize()
453                         if qsz < 0x10:
454                                 self.logger.warning('clearMerkleRoots running out! only %d left' % (qsz,))
455                         MRD = self.clearMerkleRoots.get()
456                         self.LowestClearMerkleRoots = min(self.clearMerkleRoots.qsize(), self.LowestClearMerkleRoots)
457                         rollPrevBlk = True
458                 (merkleRoot, merkleTree, cb) = MRD
459                 (prevBlock, height, bits) = self.currentBlock
460                 return (merkleRoot, merkleTree, cb, prevBlock, bits, rollPrevBlk)
461         
462         def getMC(self):
463                 (prevBlock, height, bits) = self.currentBlock
464                 mt = self.currentMerkleTree
465                 cb = self.makeCoinbase(height=height)
466                 rollPrevBlk = (mt == self.clearMerkleTree)
467                 return (height, mt, cb, prevBlock, bits, rollPrevBlk)
468
469 # merkleMaker tests
470 def _test():
471         global now
472         now = 1337039788
473         MM = merkleMaker()
474         reallogger = MM.logger
475         class fakelogger:
476                 LO = False
477                 def critical(self, *a):
478                         if self.LO > 1: return
479                         reallogger.critical(*a)
480                 def warning(self, *a):
481                         if self.LO: return
482                         reallogger.warning(*a)
483                 def debug(self, *a):
484                         pass
485         MM.logger = fakelogger()
486         class NMTClass:
487                 pass
488         
489         # _makeBlockSafe tests
490         from copy import deepcopy
491         MP = {
492                 'coinbasevalue':50,
493         }
494         txnlist = [b'\0', b'\x01', b'\x02']
495         txninfo = [{'fee':0, 'sigops':1}, {'fee':5, 'sigops':10000}, {'fee':0, 'sigops':10001}]
496         def MBS(LO = 0):
497                 m = deepcopy( (MP, txnlist, txninfo) )
498                 MM.logger.LO = LO
499                 try:
500                         MM._makeBlockSafe(*m)
501                 except:
502                         if LO < 2:
503                                 raise
504                 else:
505                         assert LO < 2  # An expected error wasn't thrown
506                 if 'POTInfo' in m[0]:
507                         del m[0]['POTInfo']
508                 return m
509         MM.POT = 0
510         assert MBS() == (MP, txnlist[:2], txninfo[:2])
511         txninfo[2]['fee'] = 1
512         MPx = deepcopy(MP)
513         MPx['coinbasevalue'] -= 1
514         assert MBS() == (MPx, txnlist[:2], txninfo[:2])
515         txninfo[2]['sigops'] = 1
516         assert MBS(1) == (MP, txnlist, txninfo)
517         # APOT tests
518         MM.POT = 2
519         txnlist.append(b'\x03')
520         txninfo.append({'fee':1, 'sigops':0})
521         MPx = deepcopy(MP)
522         MPx['coinbasevalue'] -= 1
523         assert MBS() == (MPx, txnlist[:3], txninfo[:3])
524
525 _test()