1 package txscript
2 3 import (
4 "fmt"
5 )
6 7 const (
8 maxInt32 = 1<<31 - 1
9 minInt32 = -1 << 31
10 // defaultScriptNumLen is the default number of bytes data being interpreted as an integer may be.
11 defaultScriptNumLen = 4
12 )
13 14 // scriptNum represents a numeric value used in the scripting engine with special handling to deal with the subtle
15 // semantics required by consensus. All numbers are stored on the data and alternate stacks encoded as little endian
16 // with a sign bit. All numeric opcodes such as OP_ADD, OP_SUB, and OP_MUL, are only allowed to operate on 4-byte
17 // integers in the range [-2^31 + 1, 2^31 - 1], however the results of numeric operations may overflow and remain valid
18 // so long as they are not used as inputs to other numeric operations or otherwise interpreted as an integer. For
19 // example, it is possible for OP_ADD to have 2^31 - 1 for its two operands resulting 2^32 - 2, which overflows, but is
20 // still pushed to the stack as the result of the addition. That value can then be used as input to OP_VERIFY which will
21 // succeed because the data is being interpreted as a boolean. However, if that same value were to be used as input to
22 // another numeric opcode, such as OP_SUB, it must fail. This type handles the aforementioned requirements by storing
23 // all numeric operation results as an int64 to handle overflow and provides the Hash method to get the serialized
24 // representation (including values that overflow). Then, whenever data is interpreted as an integer, it is converted to
25 // this type by using the makeScriptNum function which will return an error if the number is out of range or not
26 // minimally encoded depending on parameters. Since all numeric opcodes involve pulling data from the stack and
27 // interpreting it as an integer, it provides the required behavior.
28 type scriptNum int64
29 30 // checkMinimalDataEncoding returns whether or not the passed byte array adheres to the minimal encoding requirements.
31 func checkMinimalDataEncoding(v []byte) (e error) {
32 if len(v) == 0 {
33 return nil
34 }
35 // Chk that the number is encoded with the minimum possible number of bytes. If the most-significant-byte -
36 // excluding the sign bit - is zero then we're not minimal. Note how this test also rejects the negative-zero
37 // encoding, [0x80].
38 if v[len(v)-1]&0x7f == 0 {
39 // One exception: if there's more than one byte and the most significant bit of the second-most-significant-byte
40 // is set it would conflict with the sign bit. An example of this case is +-255, which encode to 0xff00 and
41 // 0xff80 respectively. (big-endian).
42 if len(v) == 1 || v[len(v)-2]&0x80 == 0 {
43 str := fmt.Sprintf("numeric value encoded as %x is "+
44 "not minimally encoded", v,
45 )
46 return scriptError(ErrMinimalData, str)
47 }
48 }
49 return nil
50 }
51 52 // Bytes returns the number serialized as a little endian with a sign bit.
53 // Example encodings:
54 // 127 -> [0x7f]
55 // -127 -> [0xff]
56 // 128 -> [0x80 0x00]
57 // -128 -> [0x80 0x80]
58 // 129 -> [0x81 0x00]
59 // -129 -> [0x81 0x80]
60 // 256 -> [0x00 0x01]
61 // -256 -> [0x00 0x81]
62 // 32767 -> [0xff 0x7f]
63 // -32767 -> [0xff 0xff]
64 // 32768 -> [0x00 0x80 0x00]
65 // -32768 -> [0x00 0x80 0x80]
66 func (sn scriptNum) Bytes() []byte {
67 n := sn
68 // Zero encodes as an empty byte slice.
69 if n == 0 {
70 return nil
71 }
72 // Take the absolute value and keep track of whether it was originally negative.
73 isNegative := n < 0
74 if isNegative {
75 n = -n
76 }
77 // Encode to little endian. The maximum number of encoded bytes is 9 (8 bytes for max int64 plus a potential byte
78 // for sign extension).
79 result := make([]byte, 0, 9)
80 for n > 0 {
81 result = append(result, byte(n&0xff))
82 n >>= 8
83 }
84 // When the most significant byte already has the high bit set, an additional high byte is required to indicate
85 // whether the number is negative or positive. The additional byte is removed when converting back to an integral
86 // and its high bit is used to denote the sign. Otherwise, when the most significant byte does not already have the
87 // high bit set, use it to indicate the value is negative, if needed.
88 if result[len(result)-1]&0x80 != 0 {
89 extraByte := byte(0x00)
90 if isNegative {
91 extraByte = 0x80
92 }
93 result = append(result, extraByte)
94 } else if isNegative {
95 result[len(result)-1] |= 0x80
96 }
97 return result
98 }
99 100 // Int32 returns the script number clamped to a valid int32. That is to say when the script number is higher than the
101 // max allowed int32, the max int32 value is returned and vice versa for the minimum value. Note that this behavior is
102 // different from a simple int32 cast because that truncates and the consensus rules dictate numbers which are directly
103 // cast to ints provide this behavior. In practice, for most opcodes, the number should never be out of range since it
104 // will have been created with makeScriptNum using the defaultScriptLen value, which rejects them. In case something in
105 // the future ends up calling this function against the result of some arithmetic, which IS allowed to be out of range
106 // before being reinterpreted as an integer, this will provide the correct behavior.
107 func (sn scriptNum) Int32() int32 {
108 if sn > maxInt32 {
109 return maxInt32
110 }
111 if sn < minInt32 {
112 return minInt32
113 }
114 return int32(sn)
115 }
116 117 // makeScriptNum interprets the passed serialized bytes as an encoded integer and returns the result as a script number.
118 // Since the consensus rules dictate that serialized bytes interpreted as ints are only allowed to be in the range
119 // determined by a maximum number of bytes, on a per opcode basis, an error will be returned when the provided bytes
120 // would result in a number outside of that range. In particular, the range for the vast majority of opcodes dealing
121 // with numeric values are limited to 4 bytes and therefore will pass that value to this function resulting in an
122 // allowed range of [-2^31 + 1, 2^31 - 1]. The requireMinimal flag causes an error to be returned if additional checks
123 // on the encoding determine it is not represented with the smallest possible number of bytes or is the negative 0
124 // encoding, [0x80]. For example, consider the number 127. It could be encoded as [0x7f], [0x7f 0x00], [0x7f 0x00 0x00
125 // ...], etc. All forms except [0x7f] will return an error with requireMinimal enabled. The scriptNumLen is the maximum
126 // number of bytes the encoded value can be before an ErrStackNumberTooBig is returned. This effectively limits the
127 // range of allowed values. WARNING: Great care should be taken if passing a value larger than defaultScriptNumLen,
128 // which could lead to addition and multiplication overflows. See the Hash function documentation for example encodings.
129 func makeScriptNum(v []byte, requireMinimal bool, scriptNumLen int) (scriptNum, error) {
130 // Interpreting data requires that it is not larger than the the passed scriptNumLen value.
131 if len(v) > scriptNumLen {
132 str := fmt.Sprintf("numeric value encoded as %x is %d bytes "+
133 "which exceeds the max allowed of %d", v, len(v),
134 scriptNumLen,
135 )
136 return 0, scriptError(ErrNumberTooBig, str)
137 }
138 // Enforce minimal encoded if requested.
139 if requireMinimal {
140 if e := checkMinimalDataEncoding(v); E.Chk(e) {
141 return 0, e
142 }
143 }
144 // Zero is encoded as an empty byte slice.
145 if len(v) == 0 {
146 return 0, nil
147 }
148 // Decode from little endian.
149 var result int64
150 for i, val := range v {
151 result |= int64(val) << uint8(8*i)
152 }
153 // When the most significant byte of the input bytes has the sign bit set, the result is negative. So, remove the
154 // sign bit from the result and make it negative.
155 if v[len(v)-1]&0x80 != 0 {
156 // The maximum length of v has already been determined to be 4 above, so uint8 is enough to cover the max possible shift value of 24.
157 result &= ^(int64(0x80) << uint8(8*(len(v)-1)))
158 return scriptNum(-result), nil
159 }
160 return scriptNum(result), nil
161 }
162