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