1#!/usr/bin/env python3
2# Copyright (c) 2015-2020 The Bitcoin Core developers
3# Distributed under the MIT software license, see the accompanying
4# file COPYING or http://www.opensource.org/licenses/mit-license.php.
5"""Functionality to build scripts, as well as signature hash functions.
6
7This file is modified from python-bitcoinlib.
8"""
9
10from collections import namedtuple
11import hashlib
12import struct
13import unittest
14from typing import List, Dict
15
16from .key import TaggedHash, tweak_add_pubkey
17
18from .messages import (
19    CTransaction,
20    CTxOut,
21    hash256,
22    ser_string,
23    ser_uint256,
24    sha256,
25    uint256_from_str,
26)
27
28MAX_SCRIPT_ELEMENT_SIZE = 520
29LOCKTIME_THRESHOLD = 500000000
30ANNEX_TAG = 0x50
31
32LEAF_VERSION_TAPSCRIPT = 0xc0
33
34def hash160(s):
35    return hashlib.new('ripemd160', sha256(s)).digest()
36
37def bn2vch(v):
38    """Convert number to bitcoin-specific little endian format."""
39    # We need v.bit_length() bits, plus a sign bit for every nonzero number.
40    n_bits = v.bit_length() + (v != 0)
41    # The number of bytes for that is:
42    n_bytes = (n_bits + 7) // 8
43    # Convert number to absolute value + sign in top bit.
44    encoded_v = 0 if v == 0 else abs(v) | ((v < 0) << (n_bytes * 8 - 1))
45    # Serialize to bytes
46    return encoded_v.to_bytes(n_bytes, 'little')
47
48class CScriptOp(int):
49    """A single script opcode"""
50    __slots__ = ()
51
52    @staticmethod
53    def encode_op_pushdata(d):
54        """Encode a PUSHDATA op, returning bytes"""
55        if len(d) < 0x4c:
56            return b'' + bytes([len(d)]) + d  # OP_PUSHDATA
57        elif len(d) <= 0xff:
58            return b'\x4c' + bytes([len(d)]) + d  # OP_PUSHDATA1
59        elif len(d) <= 0xffff:
60            return b'\x4d' + struct.pack(b'<H', len(d)) + d  # OP_PUSHDATA2
61        elif len(d) <= 0xffffffff:
62            return b'\x4e' + struct.pack(b'<I', len(d)) + d  # OP_PUSHDATA4
63        else:
64            raise ValueError("Data too long to encode in a PUSHDATA op")
65
66    @staticmethod
67    def encode_op_n(n):
68        """Encode a small integer op, returning an opcode"""
69        if not (0 <= n <= 16):
70            raise ValueError('Integer must be in range 0 <= n <= 16, got %d' % n)
71
72        if n == 0:
73            return OP_0
74        else:
75            return CScriptOp(OP_1 + n - 1)
76
77    def decode_op_n(self):
78        """Decode a small integer opcode, returning an integer"""
79        if self == OP_0:
80            return 0
81
82        if not (self == OP_0 or OP_1 <= self <= OP_16):
83            raise ValueError('op %r is not an OP_N' % self)
84
85        return int(self - OP_1 + 1)
86
87    def is_small_int(self):
88        """Return true if the op pushes a small integer to the stack"""
89        if 0x51 <= self <= 0x60 or self == 0:
90            return True
91        else:
92            return False
93
94    def __str__(self):
95        return repr(self)
96
97    def __repr__(self):
98        if self in OPCODE_NAMES:
99            return OPCODE_NAMES[self]
100        else:
101            return 'CScriptOp(0x%x)' % self
102
103    def __new__(cls, n):
104        try:
105            return _opcode_instances[n]
106        except IndexError:
107            assert len(_opcode_instances) == n
108            _opcode_instances.append(super().__new__(cls, n))
109            return _opcode_instances[n]
110
111OPCODE_NAMES: Dict[CScriptOp, str] = {}
112_opcode_instances: List[CScriptOp] = []
113
114# Populate opcode instance table
115for n in range(0xff + 1):
116    CScriptOp(n)
117
118
119# push value
120OP_0 = CScriptOp(0x00)
121OP_FALSE = OP_0
122OP_PUSHDATA1 = CScriptOp(0x4c)
123OP_PUSHDATA2 = CScriptOp(0x4d)
124OP_PUSHDATA4 = CScriptOp(0x4e)
125OP_1NEGATE = CScriptOp(0x4f)
126OP_RESERVED = CScriptOp(0x50)
127OP_1 = CScriptOp(0x51)
128OP_TRUE = OP_1
129OP_2 = CScriptOp(0x52)
130OP_3 = CScriptOp(0x53)
131OP_4 = CScriptOp(0x54)
132OP_5 = CScriptOp(0x55)
133OP_6 = CScriptOp(0x56)
134OP_7 = CScriptOp(0x57)
135OP_8 = CScriptOp(0x58)
136OP_9 = CScriptOp(0x59)
137OP_10 = CScriptOp(0x5a)
138OP_11 = CScriptOp(0x5b)
139OP_12 = CScriptOp(0x5c)
140OP_13 = CScriptOp(0x5d)
141OP_14 = CScriptOp(0x5e)
142OP_15 = CScriptOp(0x5f)
143OP_16 = CScriptOp(0x60)
144
145# control
146OP_NOP = CScriptOp(0x61)
147OP_VER = CScriptOp(0x62)
148OP_IF = CScriptOp(0x63)
149OP_NOTIF = CScriptOp(0x64)
150OP_VERIF = CScriptOp(0x65)
151OP_VERNOTIF = CScriptOp(0x66)
152OP_ELSE = CScriptOp(0x67)
153OP_ENDIF = CScriptOp(0x68)
154OP_VERIFY = CScriptOp(0x69)
155OP_RETURN = CScriptOp(0x6a)
156
157# stack ops
158OP_TOALTSTACK = CScriptOp(0x6b)
159OP_FROMALTSTACK = CScriptOp(0x6c)
160OP_2DROP = CScriptOp(0x6d)
161OP_2DUP = CScriptOp(0x6e)
162OP_3DUP = CScriptOp(0x6f)
163OP_2OVER = CScriptOp(0x70)
164OP_2ROT = CScriptOp(0x71)
165OP_2SWAP = CScriptOp(0x72)
166OP_IFDUP = CScriptOp(0x73)
167OP_DEPTH = CScriptOp(0x74)
168OP_DROP = CScriptOp(0x75)
169OP_DUP = CScriptOp(0x76)
170OP_NIP = CScriptOp(0x77)
171OP_OVER = CScriptOp(0x78)
172OP_PICK = CScriptOp(0x79)
173OP_ROLL = CScriptOp(0x7a)
174OP_ROT = CScriptOp(0x7b)
175OP_SWAP = CScriptOp(0x7c)
176OP_TUCK = CScriptOp(0x7d)
177
178# splice ops
179OP_CAT = CScriptOp(0x7e)
180OP_SUBSTR = CScriptOp(0x7f)
181OP_LEFT = CScriptOp(0x80)
182OP_RIGHT = CScriptOp(0x81)
183OP_SIZE = CScriptOp(0x82)
184
185# bit logic
186OP_INVERT = CScriptOp(0x83)
187OP_AND = CScriptOp(0x84)
188OP_OR = CScriptOp(0x85)
189OP_XOR = CScriptOp(0x86)
190OP_EQUAL = CScriptOp(0x87)
191OP_EQUALVERIFY = CScriptOp(0x88)
192OP_RESERVED1 = CScriptOp(0x89)
193OP_RESERVED2 = CScriptOp(0x8a)
194
195# numeric
196OP_1ADD = CScriptOp(0x8b)
197OP_1SUB = CScriptOp(0x8c)
198OP_2MUL = CScriptOp(0x8d)
199OP_2DIV = CScriptOp(0x8e)
200OP_NEGATE = CScriptOp(0x8f)
201OP_ABS = CScriptOp(0x90)
202OP_NOT = CScriptOp(0x91)
203OP_0NOTEQUAL = CScriptOp(0x92)
204
205OP_ADD = CScriptOp(0x93)
206OP_SUB = CScriptOp(0x94)
207OP_MUL = CScriptOp(0x95)
208OP_DIV = CScriptOp(0x96)
209OP_MOD = CScriptOp(0x97)
210OP_LSHIFT = CScriptOp(0x98)
211OP_RSHIFT = CScriptOp(0x99)
212
213OP_BOOLAND = CScriptOp(0x9a)
214OP_BOOLOR = CScriptOp(0x9b)
215OP_NUMEQUAL = CScriptOp(0x9c)
216OP_NUMEQUALVERIFY = CScriptOp(0x9d)
217OP_NUMNOTEQUAL = CScriptOp(0x9e)
218OP_LESSTHAN = CScriptOp(0x9f)
219OP_GREATERTHAN = CScriptOp(0xa0)
220OP_LESSTHANOREQUAL = CScriptOp(0xa1)
221OP_GREATERTHANOREQUAL = CScriptOp(0xa2)
222OP_MIN = CScriptOp(0xa3)
223OP_MAX = CScriptOp(0xa4)
224
225OP_WITHIN = CScriptOp(0xa5)
226
227# crypto
228OP_RIPEMD160 = CScriptOp(0xa6)
229OP_SHA1 = CScriptOp(0xa7)
230OP_SHA256 = CScriptOp(0xa8)
231OP_HASH160 = CScriptOp(0xa9)
232OP_HASH256 = CScriptOp(0xaa)
233OP_CODESEPARATOR = CScriptOp(0xab)
234OP_CHECKSIG = CScriptOp(0xac)
235OP_CHECKSIGVERIFY = CScriptOp(0xad)
236OP_CHECKMULTISIG = CScriptOp(0xae)
237OP_CHECKMULTISIGVERIFY = CScriptOp(0xaf)
238
239# expansion
240OP_NOP1 = CScriptOp(0xb0)
241OP_CHECKLOCKTIMEVERIFY = CScriptOp(0xb1)
242OP_CHECKSEQUENCEVERIFY = CScriptOp(0xb2)
243OP_NOP4 = CScriptOp(0xb3)
244OP_NOP5 = CScriptOp(0xb4)
245OP_NOP6 = CScriptOp(0xb5)
246OP_NOP7 = CScriptOp(0xb6)
247OP_NOP8 = CScriptOp(0xb7)
248OP_NOP9 = CScriptOp(0xb8)
249OP_NOP10 = CScriptOp(0xb9)
250
251# BIP 342 opcodes (Tapscript)
252OP_CHECKSIGADD = CScriptOp(0xba)
253
254OP_INVALIDOPCODE = CScriptOp(0xff)
255
256OPCODE_NAMES.update({
257    OP_0: 'OP_0',
258    OP_PUSHDATA1: 'OP_PUSHDATA1',
259    OP_PUSHDATA2: 'OP_PUSHDATA2',
260    OP_PUSHDATA4: 'OP_PUSHDATA4',
261    OP_1NEGATE: 'OP_1NEGATE',
262    OP_RESERVED: 'OP_RESERVED',
263    OP_1: 'OP_1',
264    OP_2: 'OP_2',
265    OP_3: 'OP_3',
266    OP_4: 'OP_4',
267    OP_5: 'OP_5',
268    OP_6: 'OP_6',
269    OP_7: 'OP_7',
270    OP_8: 'OP_8',
271    OP_9: 'OP_9',
272    OP_10: 'OP_10',
273    OP_11: 'OP_11',
274    OP_12: 'OP_12',
275    OP_13: 'OP_13',
276    OP_14: 'OP_14',
277    OP_15: 'OP_15',
278    OP_16: 'OP_16',
279    OP_NOP: 'OP_NOP',
280    OP_VER: 'OP_VER',
281    OP_IF: 'OP_IF',
282    OP_NOTIF: 'OP_NOTIF',
283    OP_VERIF: 'OP_VERIF',
284    OP_VERNOTIF: 'OP_VERNOTIF',
285    OP_ELSE: 'OP_ELSE',
286    OP_ENDIF: 'OP_ENDIF',
287    OP_VERIFY: 'OP_VERIFY',
288    OP_RETURN: 'OP_RETURN',
289    OP_TOALTSTACK: 'OP_TOALTSTACK',
290    OP_FROMALTSTACK: 'OP_FROMALTSTACK',
291    OP_2DROP: 'OP_2DROP',
292    OP_2DUP: 'OP_2DUP',
293    OP_3DUP: 'OP_3DUP',
294    OP_2OVER: 'OP_2OVER',
295    OP_2ROT: 'OP_2ROT',
296    OP_2SWAP: 'OP_2SWAP',
297    OP_IFDUP: 'OP_IFDUP',
298    OP_DEPTH: 'OP_DEPTH',
299    OP_DROP: 'OP_DROP',
300    OP_DUP: 'OP_DUP',
301    OP_NIP: 'OP_NIP',
302    OP_OVER: 'OP_OVER',
303    OP_PICK: 'OP_PICK',
304    OP_ROLL: 'OP_ROLL',
305    OP_ROT: 'OP_ROT',
306    OP_SWAP: 'OP_SWAP',
307    OP_TUCK: 'OP_TUCK',
308    OP_CAT: 'OP_CAT',
309    OP_SUBSTR: 'OP_SUBSTR',
310    OP_LEFT: 'OP_LEFT',
311    OP_RIGHT: 'OP_RIGHT',
312    OP_SIZE: 'OP_SIZE',
313    OP_INVERT: 'OP_INVERT',
314    OP_AND: 'OP_AND',
315    OP_OR: 'OP_OR',
316    OP_XOR: 'OP_XOR',
317    OP_EQUAL: 'OP_EQUAL',
318    OP_EQUALVERIFY: 'OP_EQUALVERIFY',
319    OP_RESERVED1: 'OP_RESERVED1',
320    OP_RESERVED2: 'OP_RESERVED2',
321    OP_1ADD: 'OP_1ADD',
322    OP_1SUB: 'OP_1SUB',
323    OP_2MUL: 'OP_2MUL',
324    OP_2DIV: 'OP_2DIV',
325    OP_NEGATE: 'OP_NEGATE',
326    OP_ABS: 'OP_ABS',
327    OP_NOT: 'OP_NOT',
328    OP_0NOTEQUAL: 'OP_0NOTEQUAL',
329    OP_ADD: 'OP_ADD',
330    OP_SUB: 'OP_SUB',
331    OP_MUL: 'OP_MUL',
332    OP_DIV: 'OP_DIV',
333    OP_MOD: 'OP_MOD',
334    OP_LSHIFT: 'OP_LSHIFT',
335    OP_RSHIFT: 'OP_RSHIFT',
336    OP_BOOLAND: 'OP_BOOLAND',
337    OP_BOOLOR: 'OP_BOOLOR',
338    OP_NUMEQUAL: 'OP_NUMEQUAL',
339    OP_NUMEQUALVERIFY: 'OP_NUMEQUALVERIFY',
340    OP_NUMNOTEQUAL: 'OP_NUMNOTEQUAL',
341    OP_LESSTHAN: 'OP_LESSTHAN',
342    OP_GREATERTHAN: 'OP_GREATERTHAN',
343    OP_LESSTHANOREQUAL: 'OP_LESSTHANOREQUAL',
344    OP_GREATERTHANOREQUAL: 'OP_GREATERTHANOREQUAL',
345    OP_MIN: 'OP_MIN',
346    OP_MAX: 'OP_MAX',
347    OP_WITHIN: 'OP_WITHIN',
348    OP_RIPEMD160: 'OP_RIPEMD160',
349    OP_SHA1: 'OP_SHA1',
350    OP_SHA256: 'OP_SHA256',
351    OP_HASH160: 'OP_HASH160',
352    OP_HASH256: 'OP_HASH256',
353    OP_CODESEPARATOR: 'OP_CODESEPARATOR',
354    OP_CHECKSIG: 'OP_CHECKSIG',
355    OP_CHECKSIGVERIFY: 'OP_CHECKSIGVERIFY',
356    OP_CHECKMULTISIG: 'OP_CHECKMULTISIG',
357    OP_CHECKMULTISIGVERIFY: 'OP_CHECKMULTISIGVERIFY',
358    OP_NOP1: 'OP_NOP1',
359    OP_CHECKLOCKTIMEVERIFY: 'OP_CHECKLOCKTIMEVERIFY',
360    OP_CHECKSEQUENCEVERIFY: 'OP_CHECKSEQUENCEVERIFY',
361    OP_NOP4: 'OP_NOP4',
362    OP_NOP5: 'OP_NOP5',
363    OP_NOP6: 'OP_NOP6',
364    OP_NOP7: 'OP_NOP7',
365    OP_NOP8: 'OP_NOP8',
366    OP_NOP9: 'OP_NOP9',
367    OP_NOP10: 'OP_NOP10',
368    OP_CHECKSIGADD: 'OP_CHECKSIGADD',
369    OP_INVALIDOPCODE: 'OP_INVALIDOPCODE',
370})
371
372class CScriptInvalidError(Exception):
373    """Base class for CScript exceptions"""
374    pass
375
376class CScriptTruncatedPushDataError(CScriptInvalidError):
377    """Invalid pushdata due to truncation"""
378    def __init__(self, msg, data):
379        self.data = data
380        super().__init__(msg)
381
382
383# This is used, eg, for blockchain heights in coinbase scripts (bip34)
384class CScriptNum:
385    __slots__ = ("value",)
386
387    def __init__(self, d=0):
388        self.value = d
389
390    @staticmethod
391    def encode(obj):
392        r = bytearray(0)
393        if obj.value == 0:
394            return bytes(r)
395        neg = obj.value < 0
396        absvalue = -obj.value if neg else obj.value
397        while (absvalue):
398            r.append(absvalue & 0xff)
399            absvalue >>= 8
400        if r[-1] & 0x80:
401            r.append(0x80 if neg else 0)
402        elif neg:
403            r[-1] |= 0x80
404        return bytes([len(r)]) + r
405
406    @staticmethod
407    def decode(vch):
408        result = 0
409        # We assume valid push_size and minimal encoding
410        value = vch[1:]
411        if len(value) == 0:
412            return result
413        for i, byte in enumerate(value):
414            result |= int(byte) << 8 * i
415        if value[-1] >= 0x80:
416            # Mask for all but the highest result bit
417            num_mask = (2**(len(value) * 8) - 1) >> 1
418            result &= num_mask
419            result *= -1
420        return result
421
422
423class CScript(bytes):
424    """Serialized script
425
426    A bytes subclass, so you can use this directly whenever bytes are accepted.
427    Note that this means that indexing does *not* work - you'll get an index by
428    byte rather than opcode. This format was chosen for efficiency so that the
429    general case would not require creating a lot of little CScriptOP objects.
430
431    iter(script) however does iterate by opcode.
432    """
433    __slots__ = ()
434
435    @classmethod
436    def __coerce_instance(cls, other):
437        # Coerce other into bytes
438        if isinstance(other, CScriptOp):
439            other = bytes([other])
440        elif isinstance(other, CScriptNum):
441            if (other.value == 0):
442                other = bytes([CScriptOp(OP_0)])
443            else:
444                other = CScriptNum.encode(other)
445        elif isinstance(other, int):
446            if 0 <= other <= 16:
447                other = bytes([CScriptOp.encode_op_n(other)])
448            elif other == -1:
449                other = bytes([OP_1NEGATE])
450            else:
451                other = CScriptOp.encode_op_pushdata(bn2vch(other))
452        elif isinstance(other, (bytes, bytearray)):
453            other = CScriptOp.encode_op_pushdata(other)
454        return other
455
456    def __add__(self, other):
457        # add makes no sense for a CScript()
458        raise NotImplementedError
459
460    def join(self, iterable):
461        # join makes no sense for a CScript()
462        raise NotImplementedError
463
464    def __new__(cls, value=b''):
465        if isinstance(value, bytes) or isinstance(value, bytearray):
466            return super().__new__(cls, value)
467        else:
468            def coerce_iterable(iterable):
469                for instance in iterable:
470                    yield cls.__coerce_instance(instance)
471            # Annoyingly on both python2 and python3 bytes.join() always
472            # returns a bytes instance even when subclassed.
473            return super().__new__(cls, b''.join(coerce_iterable(value)))
474
475    def raw_iter(self):
476        """Raw iteration
477
478        Yields tuples of (opcode, data, sop_idx) so that the different possible
479        PUSHDATA encodings can be accurately distinguished, as well as
480        determining the exact opcode byte indexes. (sop_idx)
481        """
482        i = 0
483        while i < len(self):
484            sop_idx = i
485            opcode = self[i]
486            i += 1
487
488            if opcode > OP_PUSHDATA4:
489                yield (opcode, None, sop_idx)
490            else:
491                datasize = None
492                pushdata_type = None
493                if opcode < OP_PUSHDATA1:
494                    pushdata_type = 'PUSHDATA(%d)' % opcode
495                    datasize = opcode
496
497                elif opcode == OP_PUSHDATA1:
498                    pushdata_type = 'PUSHDATA1'
499                    if i >= len(self):
500                        raise CScriptInvalidError('PUSHDATA1: missing data length')
501                    datasize = self[i]
502                    i += 1
503
504                elif opcode == OP_PUSHDATA2:
505                    pushdata_type = 'PUSHDATA2'
506                    if i + 1 >= len(self):
507                        raise CScriptInvalidError('PUSHDATA2: missing data length')
508                    datasize = self[i] + (self[i + 1] << 8)
509                    i += 2
510
511                elif opcode == OP_PUSHDATA4:
512                    pushdata_type = 'PUSHDATA4'
513                    if i + 3 >= len(self):
514                        raise CScriptInvalidError('PUSHDATA4: missing data length')
515                    datasize = self[i] + (self[i + 1] << 8) + (self[i + 2] << 16) + (self[i + 3] << 24)
516                    i += 4
517
518                else:
519                    assert False  # shouldn't happen
520
521                data = bytes(self[i:i + datasize])
522
523                # Check for truncation
524                if len(data) < datasize:
525                    raise CScriptTruncatedPushDataError('%s: truncated data' % pushdata_type, data)
526
527                i += datasize
528
529                yield (opcode, data, sop_idx)
530
531    def __iter__(self):
532        """'Cooked' iteration
533
534        Returns either a CScriptOP instance, an integer, or bytes, as
535        appropriate.
536
537        See raw_iter() if you need to distinguish the different possible
538        PUSHDATA encodings.
539        """
540        for (opcode, data, sop_idx) in self.raw_iter():
541            if data is not None:
542                yield data
543            else:
544                opcode = CScriptOp(opcode)
545
546                if opcode.is_small_int():
547                    yield opcode.decode_op_n()
548                else:
549                    yield CScriptOp(opcode)
550
551    def __repr__(self):
552        def _repr(o):
553            if isinstance(o, bytes):
554                return "x('%s')" % o.hex()
555            else:
556                return repr(o)
557
558        ops = []
559        i = iter(self)
560        while True:
561            op = None
562            try:
563                op = _repr(next(i))
564            except CScriptTruncatedPushDataError as err:
565                op = '%s...<ERROR: %s>' % (_repr(err.data), err)
566                break
567            except CScriptInvalidError as err:
568                op = '<ERROR: %s>' % err
569                break
570            except StopIteration:
571                break
572            finally:
573                if op is not None:
574                    ops.append(op)
575
576        return "CScript([%s])" % ', '.join(ops)
577
578    def GetSigOpCount(self, fAccurate):
579        """Get the SigOp count.
580
581        fAccurate - Accurately count CHECKMULTISIG, see BIP16 for details.
582
583        Note that this is consensus-critical.
584        """
585        n = 0
586        lastOpcode = OP_INVALIDOPCODE
587        for (opcode, data, sop_idx) in self.raw_iter():
588            if opcode in (OP_CHECKSIG, OP_CHECKSIGVERIFY):
589                n += 1
590            elif opcode in (OP_CHECKMULTISIG, OP_CHECKMULTISIGVERIFY):
591                if fAccurate and (OP_1 <= lastOpcode <= OP_16):
592                    n += opcode.decode_op_n()
593                else:
594                    n += 20
595            lastOpcode = opcode
596        return n
597
598
599SIGHASH_DEFAULT = 0 # Taproot-only default, semantics same as SIGHASH_ALL
600SIGHASH_ALL = 1
601SIGHASH_NONE = 2
602SIGHASH_SINGLE = 3
603SIGHASH_ANYONECANPAY = 0x80
604
605def FindAndDelete(script, sig):
606    """Consensus critical, see FindAndDelete() in Satoshi codebase"""
607    r = b''
608    last_sop_idx = sop_idx = 0
609    skip = True
610    for (opcode, data, sop_idx) in script.raw_iter():
611        if not skip:
612            r += script[last_sop_idx:sop_idx]
613        last_sop_idx = sop_idx
614        if script[sop_idx:sop_idx + len(sig)] == sig:
615            skip = True
616        else:
617            skip = False
618    if not skip:
619        r += script[last_sop_idx:]
620    return CScript(r)
621
622def LegacySignatureHash(script, txTo, inIdx, hashtype):
623    """Consensus-correct SignatureHash
624
625    Returns (hash, err) to precisely match the consensus-critical behavior of
626    the SIGHASH_SINGLE bug. (inIdx is *not* checked for validity)
627    """
628    HASH_ONE = b'\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
629
630    if inIdx >= len(txTo.vin):
631        return (HASH_ONE, "inIdx %d out of range (%d)" % (inIdx, len(txTo.vin)))
632    txtmp = CTransaction(txTo)
633
634    for txin in txtmp.vin:
635        txin.scriptSig = b''
636    txtmp.vin[inIdx].scriptSig = FindAndDelete(script, CScript([OP_CODESEPARATOR]))
637
638    if (hashtype & 0x1f) == SIGHASH_NONE:
639        txtmp.vout = []
640
641        for i in range(len(txtmp.vin)):
642            if i != inIdx:
643                txtmp.vin[i].nSequence = 0
644
645    elif (hashtype & 0x1f) == SIGHASH_SINGLE:
646        outIdx = inIdx
647        if outIdx >= len(txtmp.vout):
648            return (HASH_ONE, "outIdx %d out of range (%d)" % (outIdx, len(txtmp.vout)))
649
650        tmp = txtmp.vout[outIdx]
651        txtmp.vout = []
652        for _ in range(outIdx):
653            txtmp.vout.append(CTxOut(-1))
654        txtmp.vout.append(tmp)
655
656        for i in range(len(txtmp.vin)):
657            if i != inIdx:
658                txtmp.vin[i].nSequence = 0
659
660    if hashtype & SIGHASH_ANYONECANPAY:
661        tmp = txtmp.vin[inIdx]
662        txtmp.vin = []
663        txtmp.vin.append(tmp)
664
665    s = txtmp.serialize_without_witness()
666    s += struct.pack(b"<I", hashtype)
667
668    hash = hash256(s)
669
670    return (hash, None)
671
672# TODO: Allow cached hashPrevouts/hashSequence/hashOutputs to be provided.
673# Performance optimization probably not necessary for python tests, however.
674# Note that this corresponds to sigversion == 1 in EvalScript, which is used
675# for version 0 witnesses.
676def SegwitV0SignatureHash(script, txTo, inIdx, hashtype, amount):
677
678    hashPrevouts = 0
679    hashSequence = 0
680    hashOutputs = 0
681
682    if not (hashtype & SIGHASH_ANYONECANPAY):
683        serialize_prevouts = bytes()
684        for i in txTo.vin:
685            serialize_prevouts += i.prevout.serialize()
686        hashPrevouts = uint256_from_str(hash256(serialize_prevouts))
687
688    if (not (hashtype & SIGHASH_ANYONECANPAY) and (hashtype & 0x1f) != SIGHASH_SINGLE and (hashtype & 0x1f) != SIGHASH_NONE):
689        serialize_sequence = bytes()
690        for i in txTo.vin:
691            serialize_sequence += struct.pack("<I", i.nSequence)
692        hashSequence = uint256_from_str(hash256(serialize_sequence))
693
694    if ((hashtype & 0x1f) != SIGHASH_SINGLE and (hashtype & 0x1f) != SIGHASH_NONE):
695        serialize_outputs = bytes()
696        for o in txTo.vout:
697            serialize_outputs += o.serialize()
698        hashOutputs = uint256_from_str(hash256(serialize_outputs))
699    elif ((hashtype & 0x1f) == SIGHASH_SINGLE and inIdx < len(txTo.vout)):
700        serialize_outputs = txTo.vout[inIdx].serialize()
701        hashOutputs = uint256_from_str(hash256(serialize_outputs))
702
703    ss = bytes()
704    ss += struct.pack("<i", txTo.nVersion)
705    ss += ser_uint256(hashPrevouts)
706    ss += ser_uint256(hashSequence)
707    ss += txTo.vin[inIdx].prevout.serialize()
708    ss += ser_string(script)
709    ss += struct.pack("<q", amount)
710    ss += struct.pack("<I", txTo.vin[inIdx].nSequence)
711    ss += ser_uint256(hashOutputs)
712    ss += struct.pack("<i", txTo.nLockTime)
713    ss += struct.pack("<I", hashtype)
714
715    return hash256(ss)
716
717class TestFrameworkScript(unittest.TestCase):
718    def test_bn2vch(self):
719        self.assertEqual(bn2vch(0), bytes([]))
720        self.assertEqual(bn2vch(1), bytes([0x01]))
721        self.assertEqual(bn2vch(-1), bytes([0x81]))
722        self.assertEqual(bn2vch(0x7F), bytes([0x7F]))
723        self.assertEqual(bn2vch(-0x7F), bytes([0xFF]))
724        self.assertEqual(bn2vch(0x80), bytes([0x80, 0x00]))
725        self.assertEqual(bn2vch(-0x80), bytes([0x80, 0x80]))
726        self.assertEqual(bn2vch(0xFF), bytes([0xFF, 0x00]))
727        self.assertEqual(bn2vch(-0xFF), bytes([0xFF, 0x80]))
728        self.assertEqual(bn2vch(0x100), bytes([0x00, 0x01]))
729        self.assertEqual(bn2vch(-0x100), bytes([0x00, 0x81]))
730        self.assertEqual(bn2vch(0x7FFF), bytes([0xFF, 0x7F]))
731        self.assertEqual(bn2vch(-0x8000), bytes([0x00, 0x80, 0x80]))
732        self.assertEqual(bn2vch(-0x7FFFFF), bytes([0xFF, 0xFF, 0xFF]))
733        self.assertEqual(bn2vch(0x80000000), bytes([0x00, 0x00, 0x00, 0x80, 0x00]))
734        self.assertEqual(bn2vch(-0x80000000), bytes([0x00, 0x00, 0x00, 0x80, 0x80]))
735        self.assertEqual(bn2vch(0xFFFFFFFF), bytes([0xFF, 0xFF, 0xFF, 0xFF, 0x00]))
736        self.assertEqual(bn2vch(123456789), bytes([0x15, 0xCD, 0x5B, 0x07]))
737        self.assertEqual(bn2vch(-54321), bytes([0x31, 0xD4, 0x80]))
738
739    def test_cscriptnum_encoding(self):
740        # round-trip negative and multi-byte CScriptNums
741        values = [0, 1, -1, -2, 127, 128, -255, 256, (1 << 15) - 1, -(1 << 16), (1 << 24) - 1, (1 << 31), 1 - (1 << 32), 1 << 40, 1500, -1500]
742        for value in values:
743            self.assertEqual(CScriptNum.decode(CScriptNum.encode(CScriptNum(value))), value)
744
745def TaprootSignatureHash(txTo, spent_utxos, hash_type, input_index = 0, scriptpath = False, script = CScript(), codeseparator_pos = -1, annex = None, leaf_ver = LEAF_VERSION_TAPSCRIPT):
746    assert (len(txTo.vin) == len(spent_utxos))
747    assert (input_index < len(txTo.vin))
748    out_type = SIGHASH_ALL if hash_type == 0 else hash_type & 3
749    in_type = hash_type & SIGHASH_ANYONECANPAY
750    spk = spent_utxos[input_index].scriptPubKey
751    ss = bytes([0, hash_type]) # epoch, hash_type
752    ss += struct.pack("<i", txTo.nVersion)
753    ss += struct.pack("<I", txTo.nLockTime)
754    if in_type != SIGHASH_ANYONECANPAY:
755        ss += sha256(b"".join(i.prevout.serialize() for i in txTo.vin))
756        ss += sha256(b"".join(struct.pack("<q", u.nValue) for u in spent_utxos))
757        ss += sha256(b"".join(ser_string(u.scriptPubKey) for u in spent_utxos))
758        ss += sha256(b"".join(struct.pack("<I", i.nSequence) for i in txTo.vin))
759    if out_type == SIGHASH_ALL:
760        ss += sha256(b"".join(o.serialize() for o in txTo.vout))
761    spend_type = 0
762    if annex is not None:
763        spend_type |= 1
764    if (scriptpath):
765        spend_type |= 2
766    ss += bytes([spend_type])
767    if in_type == SIGHASH_ANYONECANPAY:
768        ss += txTo.vin[input_index].prevout.serialize()
769        ss += struct.pack("<q", spent_utxos[input_index].nValue)
770        ss += ser_string(spk)
771        ss += struct.pack("<I", txTo.vin[input_index].nSequence)
772    else:
773        ss += struct.pack("<I", input_index)
774    if (spend_type & 1):
775        ss += sha256(ser_string(annex))
776    if out_type == SIGHASH_SINGLE:
777        if input_index < len(txTo.vout):
778            ss += sha256(txTo.vout[input_index].serialize())
779        else:
780            ss += bytes(0 for _ in range(32))
781    if (scriptpath):
782        ss += TaggedHash("TapLeaf", bytes([leaf_ver]) + ser_string(script))
783        ss += bytes([0])
784        ss += struct.pack("<i", codeseparator_pos)
785    assert len(ss) ==  175 - (in_type == SIGHASH_ANYONECANPAY) * 49 - (out_type != SIGHASH_ALL and out_type != SIGHASH_SINGLE) * 32 + (annex is not None) * 32 + scriptpath * 37
786    return TaggedHash("TapSighash", ss)
787
788def taproot_tree_helper(scripts):
789    if len(scripts) == 0:
790        return ([], bytes())
791    if len(scripts) == 1:
792        # One entry: treat as a leaf
793        script = scripts[0]
794        assert(not callable(script))
795        if isinstance(script, list):
796            return taproot_tree_helper(script)
797        assert(isinstance(script, tuple))
798        version = LEAF_VERSION_TAPSCRIPT
799        name = script[0]
800        code = script[1]
801        if len(script) == 3:
802            version = script[2]
803        assert version & 1 == 0
804        assert isinstance(code, bytes)
805        h = TaggedHash("TapLeaf", bytes([version]) + ser_string(code))
806        if name is None:
807            return ([], h)
808        return ([(name, version, code, bytes())], h)
809    elif len(scripts) == 2 and callable(scripts[1]):
810        # Two entries, and the right one is a function
811        left, left_h = taproot_tree_helper(scripts[0:1])
812        right_h = scripts[1](left_h)
813        left = [(name, version, script, control + right_h) for name, version, script, control in left]
814        right = []
815    else:
816        # Two or more entries: descend into each side
817        split_pos = len(scripts) // 2
818        left, left_h = taproot_tree_helper(scripts[0:split_pos])
819        right, right_h = taproot_tree_helper(scripts[split_pos:])
820        left = [(name, version, script, control + right_h) for name, version, script, control in left]
821        right = [(name, version, script, control + left_h) for name, version, script, control in right]
822    if right_h < left_h:
823        right_h, left_h = left_h, right_h
824    h = TaggedHash("TapBranch", left_h + right_h)
825    return (left + right, h)
826
827# A TaprootInfo object has the following fields:
828# - scriptPubKey: the scriptPubKey (witness v1 CScript)
829# - internal_pubkey: the internal pubkey (32 bytes)
830# - negflag: whether the pubkey in the scriptPubKey was negated from internal_pubkey+tweak*G (bool).
831# - tweak: the tweak (32 bytes)
832# - leaves: a dict of name -> TaprootLeafInfo objects for all known leaves
833TaprootInfo = namedtuple("TaprootInfo", "scriptPubKey,internal_pubkey,negflag,tweak,leaves")
834
835# A TaprootLeafInfo object has the following fields:
836# - script: the leaf script (CScript or bytes)
837# - version: the leaf version (0xc0 for BIP342 tapscript)
838# - merklebranch: the merkle branch to use for this leaf (32*N bytes)
839TaprootLeafInfo = namedtuple("TaprootLeafInfo", "script,version,merklebranch")
840
841def taproot_construct(pubkey, scripts=None):
842    """Construct a tree of Taproot spending conditions
843
844    pubkey: a 32-byte xonly pubkey for the internal pubkey (bytes)
845    scripts: a list of items; each item is either:
846             - a (name, CScript or bytes, leaf version) tuple
847             - a (name, CScript or bytes) tuple (defaulting to leaf version 0xc0)
848             - another list of items (with the same structure)
849             - a list of two items; the first of which is an item itself, and the
850               second is a function. The function takes as input the Merkle root of the
851               first item, and produces a (fictitious) partner to hash with.
852
853    Returns: a TaprootInfo object
854    """
855    if scripts is None:
856        scripts = []
857
858    ret, h = taproot_tree_helper(scripts)
859    tweak = TaggedHash("TapTweak", pubkey + h)
860    tweaked, negated = tweak_add_pubkey(pubkey, tweak)
861    leaves = dict((name, TaprootLeafInfo(script, version, merklebranch)) for name, version, script, merklebranch in ret)
862    return TaprootInfo(CScript([OP_1, tweaked]), pubkey, negated + 0, tweak, leaves)
863
864def is_op_success(o):
865    return o == 0x50 or o == 0x62 or o == 0x89 or o == 0x8a or o == 0x8d or o == 0x8e or (o >= 0x7e and o <= 0x81) or (o >= 0x83 and o <= 0x86) or (o >= 0x95 and o <= 0x99) or (o >= 0xbb and o <= 0xfe)
866