1 package txscript
2 3 import (
4 "bytes"
5 "crypto/sha256"
6 "fmt"
7 "math/big"
8 9 "github.com/p9c/p9/pkg/wire"
10 11 "go.uber.org/atomic"
12 13 ec "github.com/p9c/p9/pkg/ecc"
14 )
15 16 // ScriptFlags is a bitmask defining additional operations or tests that will be done when executing a script pair.
17 type ScriptFlags uint32
18 19 const (
20 // ScriptBip16 defines whether the bip16 threshold has passed and thus pay-to-script hash transactions will be fully
21 // validated.
22 ScriptBip16 ScriptFlags = 1 << iota
23 // ScriptStrictMultiSig defines whether to verify the stack item used by CHECKMULTISIG is zero length.
24 ScriptStrictMultiSig
25 // ScriptDiscourageUpgradableNops defines whether to verify that NOP1 through NOP10 are reserved for future
26 // soft-fork upgrades. This flag must not be used for consensus critical code nor applied to blocks as this flag is
27 // only for stricter standard transaction checks. This flag is only applied when the above opcodes are executed.
28 ScriptDiscourageUpgradableNops
29 // ScriptVerifyCheckLockTimeVerify defines whether to verify that a transaction output is spendable based on the
30 // locktime. This is BIP0065.
31 ScriptVerifyCheckLockTimeVerify
32 // ScriptVerifyCheckSequenceVerify defines whether to allow execution pathways of a script to be restricted based on
33 // the age of the output being spent. This is BIP0112.
34 ScriptVerifyCheckSequenceVerify
35 // ScriptVerifyCleanStack defines that the stack must contain only one stack
36 // element after evaluation and that the element must be true if interpreted as
37 // a boolean. This is rule 6 of BIP0062. This flag should never be used without
38 // the ScriptBip16 flag nor the ScriptVerifyWitness flag.
39 ScriptVerifyCleanStack
40 // ScriptVerifyDERSignatures defines that signatures are required to compily with the DER format.
41 ScriptVerifyDERSignatures
42 // ScriptVerifyLowS defines that signtures are required to comply with the DER format and whose S value is <= order
43 // / 2. This is rule 5 of BIP0062.
44 ScriptVerifyLowS
45 // ScriptVerifyMinimalData defines that signatures must use the smallest push operator. This is both rules 3 and 4
46 // of BIP0062.
47 ScriptVerifyMinimalData
48 // ScriptVerifyNullFail defines that signatures must be empty if a CHECKSIG or CHECKMULTISIG operation fails.
49 ScriptVerifyNullFail
50 // ScriptVerifySigPushOnly defines that signature scripts must contain only pushed data. This is rule 2 of BIP0062.
51 ScriptVerifySigPushOnly
52 // ScriptVerifyStrictEncoding defines that signature scripts and public keys must follow the strict encoding
53 // requirements.
54 ScriptVerifyStrictEncoding
55 // ScriptVerifyWitness defines whether or not to verify a transaction output
56 // using a witness program template.
57 ScriptVerifyWitness
58 // ScriptVerifyDiscourageUpgradeableWitnessProgram makes witness program with
59 // versions 2-16 non-standard.
60 ScriptVerifyDiscourageUpgradeableWitnessProgram
61 // ScriptVerifyMinimalIf makes a script with an OP_IF/OP_NOTIF whose operand is anything other than empty vector or
62 // [0x01] non-standard.
63 ScriptVerifyMinimalIf
64 // ScriptVerifyWitnessPubKeyType makes a script within a check-sig operation
65 // whose public key isn't serialized in a compressed format non-standard.
66 ScriptVerifyWitnessPubKeyType
67 // MaxStackSize is the maximum combined height of stack and alt stack during execution.
68 MaxStackSize = 1000
69 // MaxScriptSize is the maximum allowed length of a raw script.
70 MaxScriptSize = 10000
71 // payToWitnessPubKeyHashDataSize is the size of the witness program's data push
72 // for a pay-to-witness-pub-key-hash output.
73 payToWitnessPubKeyHashDataSize = 20
74 // payToWitnessScriptHashDataSize is the size of the witness program's data push
75 // for a pay-to-witness-script-hash output.
76 payToWitnessScriptHashDataSize = 32
77 )
78 79 // halforder is used to tame ECDSA malleability (see BIP0062).
80 var halfOrder = new(big.Int).Rsh(ec.S256().N, 1)
81 82 // Engine is the virtual machine that executes scripts.
83 type Engine struct {
84 scripts [][]parsedOpcode
85 scriptIdx atomic.Int64
86 scriptOff atomic.Int64
87 lastCodeSep int
88 dstack stack // data stack
89 astack stack // alt stack
90 tx wire.MsgTx
91 txIdx int
92 condStack []int
93 numOps int
94 flags ScriptFlags
95 sigCache *SigCache
96 hashCache *TxSigHashes
97 bip16 bool // treat execution as pay-to-script-hash
98 savedFirstStack [][]byte // stack from first script for bip16 scripts
99 witnessVersion int
100 witnessProgram []byte
101 inputAmount int64
102 }
103 104 // hasFlag returns whether the script engine instance has the passed flag set.
105 func (vm *Engine) hasFlag(flag ScriptFlags) bool {
106 return vm.flags&flag == flag
107 }
108 109 // isBranchExecuting returns whether or not the current conditional branch is actively executing. For example, when the
110 // data stack has an OP_FALSE on it and an OP_IF is encountered, the branch is inactive until an OP_ELSE or OP_ENDIF is
111 // encountered. It properly handles nested conditionals.
112 func (vm *Engine) isBranchExecuting() bool {
113 if len(vm.condStack) == 0 {
114 return true
115 }
116 return vm.condStack[len(vm.condStack)-1] == OpCondTrue
117 }
118 119 // executeOpcode peforms execution on the passed opcode. It takes into account whether or not it is hidden by
120 // conditionals, but some rules still must be tested in this case.
121 func (vm *Engine) executeOpcode(pop *parsedOpcode) (e error) {
122 // Disabled opcodes are fail on program counter.
123 if pop.isDisabled() {
124 str := fmt.Sprintf(
125 "attempt to execute disabled opcode %s",
126 pop.opcode.name,
127 )
128 return scriptError(ErrDisabledOpcode, str)
129 }
130 // Always-illegal opcodes are fail on program counter.
131 if pop.alwaysIllegal() {
132 str := fmt.Sprintf(
133 "attempt to execute reserved opcode %s",
134 pop.opcode.name,
135 )
136 return scriptError(ErrReservedOpcode, str)
137 }
138 // Note that this includes OP_RESERVED which counts as a push operation.
139 if pop.opcode.value > OP_16 {
140 vm.numOps++
141 if vm.numOps > MaxOpsPerScript {
142 str := fmt.Sprintf(
143 "exceeded max operation limit of %d",
144 MaxOpsPerScript,
145 )
146 return scriptError(ErrTooManyOperations, str)
147 }
148 } else if len(pop.data) > MaxScriptElementSize {
149 str := fmt.Sprintf(
150 "element size %d exceeds max allowed size %d",
151 len(pop.data), MaxScriptElementSize,
152 )
153 return scriptError(ErrElementTooBig, str)
154 }
155 // Nothing left to do when this is not a conditional opcode and it is not in an executing branch.
156 if !vm.isBranchExecuting() && !pop.isConditional() {
157 return nil
158 }
159 // Ensure all executed data push opcodes use the minimal encoding when the minimal data verification flag is set.
160 if vm.dstack.verifyMinimalData && vm.isBranchExecuting() &&
161 // pop.opcode.value >= 0 &&
162 pop.opcode.value <= OP_PUSHDATA4 {
163 if e = pop.checkMinimalDataPush(); E.Chk(e) {
164 return e
165 }
166 }
167 return pop.opcode.opfunc(pop, vm)
168 }
169 170 // disasm is a helper function to produce the output for DisasmPC and DisasmScript. It produces the opcode prefixed by
171 // the program counter at the provided position in the script. It does no error checking and leaves that to the caller
172 // to provide a valid offset.
173 func (vm *Engine) disasm(scriptIdx int, scriptOff int) string {
174 if scriptIdx >= len(vm.scripts) {
175 return fmt.Sprintf("disasm array index out of bounds ERR: %02x:%04x", scriptIdx, scriptOff)
176 }
177 if scriptOff >= len(vm.scripts[scriptIdx]) {
178 return fmt.Sprintf(
179 "disasm scriptoff array index out of bounds ERR: %02x:%04x", scriptIdx, scriptOff,
180 )
181 }
182 return fmt.Sprintf(
183 "%02x:%04x: %s", scriptIdx, scriptOff,
184 vm.scripts[scriptIdx][scriptOff].print(false),
185 )
186 }
187 188 // validPC returns an error if the current script position is valid for execution, nil otherwise.
189 func (vm *Engine) validPC() (E error) {
190 if int(vm.scriptIdx.Load()) >= len(vm.scripts) {
191 str := fmt.Sprintf(
192 "past input scripts %v:%v %v:xxxx",
193 vm.scriptIdx.Load(), vm.scriptOff.Load(), len(vm.scripts),
194 )
195 E = scriptError(ErrInvalidProgramCounter, str)
196 }
197 if len(vm.scripts) < int(vm.scriptIdx.Load()) &&
198 int(vm.scriptOff.Load()) >= len(vm.scripts[vm.scriptIdx.Load()]) {
199 str := fmt.Sprintf(
200 "past input scripts %v:%v %v:%04d",
201 vm.scriptIdx.Load(), vm.scriptOff.Load(), vm.scriptIdx.Load(),
202 len(vm.scripts[vm.scriptIdx.Load()]),
203 )
204 return scriptError(ErrInvalidProgramCounter, str)
205 }
206 return nil
207 }
208 209 // curPC returns either the current script and offset, or an error if the position isn't valid.
210 func (vm *Engine) curPC() (script int, off int, e error) {
211 e = vm.validPC()
212 if e != nil {
213 return 0, 0, e
214 }
215 return int(vm.scriptIdx.Load()), int(vm.scriptOff.Load()), nil
216 }
217 218 // isWitnessVersionActive returns true if a witness program was extracted during
219 // the initialization of the Engine, and the program's version matches the
220 // specified version.
221 func (vm *Engine) isWitnessVersionActive(version uint) bool {
222 return vm.witnessProgram != nil && uint(vm.witnessVersion) == version
223 }
224 225 // verifyWitnessProgram validates the stored witness program using the passed
226 // witness as input.
227 func (vm *Engine) verifyWitnessProgram(witness [][]byte) (e error) {
228 if vm.isWitnessVersionActive(0) {
229 switch len(vm.witnessProgram) {
230 case payToWitnessPubKeyHashDataSize: // P2WKH
231 // The witness stack should consist of exactly two items: the signature, and the
232 // pubkey.
233 if len(witness) != 2 {
234 e := fmt.Sprintf(
235 "should have exactly two items in witness, instead have %v", len(witness),
236 )
237 return scriptError(ErrWitnessProgramMismatch, e)
238 }
239 // Now we'll resume execution as if it were a regular p2pkh transaction.
240 pkScript, e := payToPubKeyHashScript(vm.witnessProgram)
241 if e != nil {
242 return e
243 }
244 pops, e := parseScript(pkScript)
245 if e != nil {
246 return e
247 }
248 // Set the stack to the provided witness stack, then append the pkScript
249 // generated above as the next script to execute.
250 vm.scripts = append(vm.scripts, pops)
251 vm.SetStack(witness)
252 case payToWitnessScriptHashDataSize: // P2WSH
253 // Additionally, The witness stack MUST NOT be empty at this point.
254 if len(witness) == 0 {
255 return scriptError(
256 ErrWitnessProgramEmpty, "witness program empty passed empty witness",
257 )
258 }
259 // Obtain the witness script which should be the last element in the passed
260 // stack. The size of the script MUST NOT exceed the max script size.
261 witnessScript := witness[len(witness)-1]
262 if len(witnessScript) > MaxScriptSize {
263 str := fmt.Sprintf(
264 "witnessScript size %d "+
265 "is larger than max allowed size %d",
266 len(witnessScript), MaxScriptSize,
267 )
268 return scriptError(ErrScriptTooBig, str)
269 }
270 // Ensure that the serialized pkScript at the end of the witness stack matches
271 // the witness program.
272 witnessHash := sha256.Sum256(witnessScript)
273 if !bytes.Equal(witnessHash[:], vm.witnessProgram) {
274 return scriptError(
275 ErrWitnessProgramMismatch,
276 "witness program hash mismatch",
277 )
278 }
279 // With all the validity checks passed, parse the script into individual op-codes so w can execute it as the
280 // next script.
281 pops, e := parseScript(witnessScript)
282 if e != nil {
283 return e
284 }
285 // The hash matched successfully, so use the witness as the stack, and set the
286 // witnessScript to be the next script executed.
287 vm.scripts = append(vm.scripts, pops)
288 vm.SetStack(witness[:len(witness)-1])
289 default:
290 errStr := fmt.Sprintf(
291 "length of witness program "+
292 "must either be %v or %v bytes, instead is %v bytes",
293 payToWitnessPubKeyHashDataSize,
294 payToWitnessScriptHashDataSize,
295 len(vm.witnessProgram),
296 )
297 return scriptError(ErrWitnessProgramWrongLength, errStr)
298 }
299 } else if vm.hasFlag(ScriptVerifyDiscourageUpgradeableWitnessProgram) {
300 errStr := fmt.Sprintf(
301 "new witness program versions invalid: %v", vm.witnessProgram,
302 )
303 return scriptError(ErrDiscourageUpgradableWitnessProgram, errStr)
304 } else {
305 // If we encounter an unknown witness program version and we aren't discouraging
306 // future unknown witness based soft-forks, then we de-activate the segwit
307 // behavior within the VM for the remainder of execution.
308 vm.witnessProgram = nil
309 }
310 if vm.isWitnessVersionActive(0) {
311 // All elements within the witness stack must not be greater than the maximum
312 // bytes which are allowed to be pushed onto the stack.
313 for _, witElement := range vm.GetStack() {
314 if len(witElement) > MaxScriptElementSize {
315 str := fmt.Sprintf(
316 "element size %d exceeds "+
317 "max allowed size %d", len(witElement),
318 MaxScriptElementSize,
319 )
320 return scriptError(ErrElementTooBig, str)
321 }
322 }
323 }
324 return nil
325 }
326 327 // DisasmPC returns the string for the disassembly of the opcode that will be next to execute when Step() is called.
328 func (vm *Engine) DisasmPC() (string, error) {
329 scriptIdx, scriptOff, e := vm.curPC()
330 if e != nil {
331 return "", e
332 }
333 return vm.disasm(scriptIdx, scriptOff), nil
334 }
335 336 // DisasmScript returns the disassembly string for the script at the requested offset index. Index 0 is the signature
337 // script and 1 is the public key script.
338 func (vm *Engine) DisasmScript(idx int) (string, error) {
339 if idx >= len(vm.scripts) {
340 str := fmt.Sprintf(
341 "script index %d >= total scripts %d", idx,
342 len(vm.scripts),
343 )
344 return "", scriptError(ErrInvalidIndex, str)
345 }
346 var disstr string
347 for i := range vm.scripts[idx] {
348 disstr = disstr + vm.disasm(idx, i) + "\n"
349 }
350 return disstr, nil
351 }
352 353 // CheckErrorCondition returns nil if the running script has ended and was successful, leaving a a true boolean on the
354 // stack. An error otherwise, including if the script has not finished.
355 func (vm *Engine) CheckErrorCondition(finalScript bool) (e error) {
356 // Chk execution is actually done. When pc is past the end of script array there are no more scripts to run.
357 if int(vm.scriptIdx.Load()) < len(vm.scripts) {
358 return scriptError(
359 ErrScriptUnfinished,
360 "error check when script unfinished",
361 )
362 }
363 // If we're in version zero witness execution mode, and this was the final
364 // script, then the stack MUST be clean in order to maintain compatibility with
365 // BIP16.
366 if finalScript && vm.isWitnessVersionActive(0) && vm.dstack.Depth() != 1 {
367 return scriptError(
368 ErrEvalFalse, "witness program must have clean stack",
369 )
370 }
371 if finalScript && vm.hasFlag(ScriptVerifyCleanStack) &&
372 vm.dstack.Depth() != 1 {
373 str := fmt.Sprintf(
374 "stack contains %d unexpected items",
375 vm.dstack.Depth()-1,
376 )
377 return scriptError(ErrCleanStack, str)
378 } else if vm.dstack.Depth() < 1 {
379 return scriptError(
380 ErrEmptyStack,
381 "stack empty at end of script execution",
382 )
383 }
384 v, e := vm.dstack.PopBool()
385 if e != nil {
386 return e
387 }
388 if !v {
389 // Log interesting data.
390 T.C(
391 func() string {
392 dis0, _ := vm.DisasmScript(0)
393 dis1, _ := vm.DisasmScript(1)
394 return fmt.Sprintf(
395 "scripts failed: script0: %s\n"+
396 "script1: %s", dis0, dis1,
397 )
398 },
399 )
400 return scriptError(
401 ErrEvalFalse,
402 "false stack entry at end of script execution",
403 )
404 }
405 return nil
406 }
407 408 // Step will execute the next instruction and move the program counter to the next opcode in the script, or the next
409 // script if the current has ended. Step will return true in the case that the last opcode was successfully executed.
410 // The result of calling Step or any other method is undefined if an error is returned.
411 func (vm *Engine) Step() (done bool, e error) {
412 // Verify that it is pointing to a valid script address.
413 e = vm.validPC()
414 if e != nil {
415 return true, e
416 }
417 opcode := &vm.scripts[vm.scriptIdx.Load()][vm.scriptOff.Load()]
418 vm.scriptOff.Inc()
419 // Execute the opcode while taking into account several things such as disabled opcodes, illegal opcodes, maximum
420 // allowed operations per script, maximum script element txsizes, and conditionals.
421 e = vm.executeOpcode(opcode)
422 if e != nil {
423 return true, e
424 }
425 // The number of elements in the combination of the data and alt stacks must not exceed the maximum number of stack
426 // elements allowed.
427 combinedStackSize := vm.dstack.Depth() + vm.astack.Depth()
428 if combinedStackSize > MaxStackSize {
429 str := fmt.Sprintf(
430 "combined stack size %d > max allowed %d",
431 combinedStackSize, MaxStackSize,
432 )
433 done, e = false, scriptError(ErrStackOverflow, str)
434 }
435 if e != nil {
436 return
437 }
438 // Prepare for next instruction.
439 if int(vm.scriptOff.Load()) >= len(vm.scripts[vm.scriptIdx.Load()]) {
440 // Illegal to have an `if' that straddles two scripts.
441 if len(vm.condStack) != 0 {
442 done, e =
443 false,
444 scriptError(
445 ErrUnbalancedConditional,
446 "end of script reached in conditional execution",
447 )
448 return
449 }
450 // Alt stack doesn't persist.
451 _ = vm.astack.DropN(vm.astack.Depth())
452 vm.numOps = 0 // number of ops is per script.
453 vm.scriptOff.Store(0)
454 if vm.scriptIdx.Load() == 0 && vm.bip16 {
455 vm.scriptIdx.Inc()
456 vm.savedFirstStack = vm.GetStack()
457 } else if vm.scriptIdx.Load() == 1 && vm.bip16 {
458 // Put us past the end for CheckErrorCondition()
459 vm.scriptIdx.Inc()
460 // Check script ran successfully and pull the script out of the first stack and execute that.
461 ee := vm.CheckErrorCondition(false)
462 if ee != nil {
463 E.Ln(e)
464 done, e = false, ee
465 return
466 }
467 script := vm.savedFirstStack[len(vm.savedFirstStack)-1]
468 pops, er := parseScript(script)
469 if er != nil {
470 E.Ln(e)
471 done, e = false, er
472 return
473 }
474 vm.scripts = append(vm.scripts, pops)
475 // Set stack to be the stack from first script minus the script itself
476 vm.SetStack(vm.savedFirstStack[:len(vm.savedFirstStack)-1])
477 // } else if (vm.scriptIdx.Load() == 1 && vm.witnessProgram != nil) ||
478 // (vm.scriptIdx.Load() == 2 && vm.witnessProgram != nil && vm.bip16) {
479 // // Nested P2SH.
480 // vm.scriptIdx.Inc()
481 // witness := vm.tx.TxIn[vm.txIdx].Witness
482 // if er := vm.verifyWitnessProgram(witness); E.Chk(e) {
483 // done, e = false, er
484 // return
485 // }
486 } else {
487 vm.scriptIdx.Inc()
488 }
489 // there are zero length scripts in the wild
490 if int(vm.scriptIdx.Load()) < len(vm.scripts) &&
491 int(vm.scriptOff.Load()) >= len(vm.scripts[vm.scriptIdx.Load()]) {
492 vm.scriptIdx.Inc()
493 }
494 vm.lastCodeSep = 0
495 if int(vm.scriptIdx.Load()) >= len(vm.scripts) {
496 done, e = true, nil
497 return
498 }
499 }
500 return
501 }
502 503 // Execute will execute all scripts in the script engine and return either nil for successful validation or an error if
504 // one occurred.
505 func (vm *Engine) Execute() (e error) {
506 done := false
507 for !done {
508 done, e = vm.Step()
509 if e != nil {
510 return e
511 }
512 T.C(
513 func() string {
514 var o string
515 dis, e := vm.DisasmPC()
516 if e != nil {
517 o += "c stepping (" + e.Error() + ")"
518 }
519 o += "oo stepping " + dis
520 var dstr, astr string
521 // if we're tracing, dump the stacks.
522 if vm.dstack.Depth() != 0 {
523 dstr = "\nStack:\n" + vm.dstack.String()
524 }
525 if vm.astack.Depth() != 0 {
526 astr = "\nAltStack:\n" + vm.astack.String()
527 }
528 return o + dstr + astr
529 },
530 )
531 }
532 return vm.CheckErrorCondition(true)
533 }
534 535 // subScript returns the script since the last OP_CODESEPARATOR.
536 func (vm *Engine) subScript() []parsedOpcode {
537 return vm.scripts[vm.scriptIdx.Load()][vm.lastCodeSep:]
538 }
539 540 // checkHashTypeEncoding returns whether or not the passed hashtype adheres to the strict encoding requirements if
541 // enabled.
542 func (vm *Engine) checkHashTypeEncoding(hashType SigHashType) (e error) {
543 if !vm.hasFlag(ScriptVerifyStrictEncoding) {
544 return nil
545 }
546 sigHashType := hashType & ^SigHashAnyOneCanPay
547 if sigHashType < SigHashAll || sigHashType > SigHashSingle {
548 str := fmt.Sprintf("invalid hash type 0x%x", hashType)
549 return scriptError(ErrInvalidSigHashType, str)
550 }
551 return nil
552 }
553 554 // checkPubKeyEncoding returns whether or not the passed public key adheres to the strict encoding requirements if
555 // enabled.
556 func (vm *Engine) checkPubKeyEncoding(pubKey []byte) (e error) {
557 if vm.hasFlag(ScriptVerifyWitnessPubKeyType) &&
558 vm.isWitnessVersionActive(0) && !ec.IsCompressedPubKey(pubKey) {
559 str := "only uncompressed keys are accepted post-segwit"
560 return scriptError(ErrWitnessPubKeyType, str)
561 }
562 if !vm.hasFlag(ScriptVerifyStrictEncoding) {
563 return nil
564 }
565 if len(pubKey) == 33 && (pubKey[0] == 0x02 || pubKey[0] == 0x03) {
566 // Compressed
567 return nil
568 }
569 if len(pubKey) == 65 && pubKey[0] == 0x04 {
570 // Uncompressed
571 return nil
572 }
573 return scriptError(ErrPubKeyType, "unsupported public key type")
574 }
575 576 // checkSignatureEncoding returns whether or not the passed signature adheres to the strict encoding requirements if
577 // enabled.
578 func (vm *Engine) checkSignatureEncoding(sig []byte) (e error) {
579 if !vm.hasFlag(ScriptVerifyDERSignatures) &&
580 !vm.hasFlag(ScriptVerifyLowS) &&
581 !vm.hasFlag(ScriptVerifyStrictEncoding) {
582 return nil
583 }
584 // The format of a DER encoded signature is as follows:
585 //
586 // 0x30 <total length> 0x02 <length of R> <R> 0x02 <length of S> <S>
587 // - 0x30 is the ASN.1 identifier for a sequence - Total length is 1 byte and specifies length of all remaining data
588 // - 0x02 is the ASN.1 identifier that specifies an integer follows
589 // - Length of R is 1 byte and specifies how many bytes R occupies
590 // - R is the arbitrary length big-endian encoded number which represents the R value of the
591 // signature. DER encoding dictates that the value must be encoded using the minimum possible number of bytes. This
592 // implies the first byte can only be null if the highest bit of the next byte is set in order to prevent it from
593 // being interpreted as a negative number.
594 // - 0x02 is once again the ASN.1 integer identifier - Length of S is 1 byte
595 // and specifies how many bytes S occupies
596 // - S is the arbitrary length big-endian encoded number which represents
597 // the S value of the signature. The encoding rules are identical as those for R.
598 const (
599 asn1SequenceID = 0x30
600 asn1IntegerID = 0x02
601 // minSigLen is the minimum length of a DER encoded signature and is when both R and S are 1 byte each.
602 // 0x30 + <1-byte> + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte>
603 minSigLen = 8
604 // maxSigLen is the maximum length of a DER encoded signature and is when both R and S are 33 bytes each. It is
605 // 33 bytes because a 256-bit integer requires 32 bytes and an additional leading null byte might required if
606 // the high bit is set in the value.
607 //
608 // 0x30 + <1-byte> + 0x02 + 0x21 + <33 bytes> + 0x2 + 0x21 + <33 bytes>
609 maxSigLen = 72
610 // sequenceOffset is the byte offset within the signature of the expected ASN.1 sequence identifier.
611 sequenceOffset = 0
612 // dataLenOffset is the byte offset within the signature of the expected total length of all remaining data in
613 // the signature.
614 dataLenOffset = 1
615 // rTypeOffset is the byte offset within the signature of the ASN.1 identifier for R and is expected to indicate
616 // an ASN.1 integer.
617 rTypeOffset = 2
618 // rLenOffset is the byte offset within the signature of the length of R.
619 rLenOffset = 3
620 // rOffset is the byte offset within the signature of R.
621 rOffset = 4
622 )
623 // The signature must adhere to the minimum and maximum allowed length.
624 sigLen := len(sig)
625 if sigLen < minSigLen {
626 str := fmt.Sprintf(
627 "malformed signature: too short: %d < %d", sigLen,
628 minSigLen,
629 )
630 return scriptError(ErrSigTooShort, str)
631 }
632 if sigLen > maxSigLen {
633 str := fmt.Sprintf(
634 "malformed signature: too long: %d > %d", sigLen,
635 maxSigLen,
636 )
637 return scriptError(ErrSigTooLong, str)
638 }
639 // The signature must start with the ASN.1 sequence identifier.
640 if sig[sequenceOffset] != asn1SequenceID {
641 str := fmt.Sprintf(
642 "malformed signature: format has wrong type: %#x",
643 sig[sequenceOffset],
644 )
645 return scriptError(ErrSigInvalidSeqID, str)
646 }
647 // The signature must indicate the correct amount of data for all elements related to R and S.
648 if int(sig[dataLenOffset]) != sigLen-2 {
649 str := fmt.Sprintf(
650 "malformed signature: bad length: %d != %d",
651 sig[dataLenOffset], sigLen-2,
652 )
653 return scriptError(ErrSigInvalidDataLen, str)
654 }
655 // Calculate the offsets of the elements related to S and ensure S is inside the signature. rLen specifies the
656 // length of the big-endian encoded number which represents the R value of the signature. sTypeOffset is the offset
657 // of the ASN.1 identifier for S and, like its R counterpart, is expected to indicate an ASN.1 integer. sLenOffset
658 // and sOffset are the byte offsets within the signature of the length of S and S itself, respectively.
659 rLen := int(sig[rLenOffset])
660 sTypeOffset := rOffset + rLen
661 sLenOffset := sTypeOffset + 1
662 if sTypeOffset >= sigLen {
663 str := "malformed signature: S type indicator missing"
664 return scriptError(ErrSigMissingSTypeID, str)
665 }
666 if sLenOffset >= sigLen {
667 str := "malformed signature: S length missing"
668 return scriptError(ErrSigMissingSLen, str)
669 }
670 // The lengths of R and S must match the overall length of the signature. sLen specifies the length of the
671 // big-endian encoded number which represents the S value of the signature.
672 sOffset := sLenOffset + 1
673 sLen := int(sig[sLenOffset])
674 if sOffset+sLen != sigLen {
675 str := "malformed signature: invalid S length"
676 return scriptError(ErrSigInvalidSLen, str)
677 }
678 // R elements must be ASN.1 integers.
679 if sig[rTypeOffset] != asn1IntegerID {
680 str := fmt.Sprintf(
681 "malformed signature: R integer marker: %#x != %#x",
682 sig[rTypeOffset], asn1IntegerID,
683 )
684 return scriptError(ErrSigInvalidRIntID, str)
685 }
686 // Zero-length integers are not allowed for R.
687 if rLen == 0 {
688 str := "malformed signature: R length is zero"
689 return scriptError(ErrSigZeroRLen, str)
690 }
691 // R must not be negative.
692 if sig[rOffset]&0x80 != 0 {
693 str := "malformed signature: R is negative"
694 return scriptError(ErrSigNegativeR, str)
695 }
696 // Null bytes at the start of R are not allowed, unless R would otherwise be interpreted as a negative number.
697 if rLen > 1 && sig[rOffset] == 0x00 && sig[rOffset+1]&0x80 == 0 {
698 str := "malformed signature: R value has too much padding"
699 return scriptError(ErrSigTooMuchRPadding, str)
700 }
701 // S elements must be ASN.1 integers.
702 if sig[sTypeOffset] != asn1IntegerID {
703 str := fmt.Sprintf(
704 "malformed signature: S integer marker: %#x != %#x",
705 sig[sTypeOffset], asn1IntegerID,
706 )
707 return scriptError(ErrSigInvalidSIntID, str)
708 }
709 // Zero-length integers are not allowed for S.
710 if sLen == 0 {
711 str := "malformed signature: S length is zero"
712 return scriptError(ErrSigZeroSLen, str)
713 }
714 // S must not be negative.
715 if sig[sOffset]&0x80 != 0 {
716 str := "malformed signature: S is negative"
717 return scriptError(ErrSigNegativeS, str)
718 }
719 // Null bytes at the start of S are not allowed, unless S would otherwise be interpreted as a negative number.
720 if sLen > 1 && sig[sOffset] == 0x00 && sig[sOffset+1]&0x80 == 0 {
721 str := "malformed signature: S value has too much padding"
722 return scriptError(ErrSigTooMuchSPadding, str)
723 }
724 // Verify the S value is <= half the order of the curve. This check is done because when it is higher, the
725 // complement modulo the order can be used instead which is a shorter encoding by 1 byte. Further, without enforcing
726 // this, it is possible to replace a signature in a valid transaction with the complement while still being a valid
727 // signature that verifies. This would result in changing the transaction hash and thus is a source of malleability.
728 if vm.hasFlag(ScriptVerifyLowS) {
729 sValue := new(big.Int).SetBytes(sig[sOffset : sOffset+sLen])
730 if sValue.Cmp(halfOrder) > 0 {
731 return scriptError(
732 ErrSigHighS, "signature is not canonical due "+
733 "to unnecessarily high S value",
734 )
735 }
736 }
737 return nil
738 }
739 740 // getStack returns the contents of stack as a byte array bottom up
741 func getStack(stack *stack) [][]byte {
742 array := make([][]byte, stack.Depth())
743 for i := range array {
744 // PeekByteArry can't fail due to overflow, already checked
745 array[len(array)-i-1], _ = stack.PeekByteArray(int32(i))
746 }
747 return array
748 }
749 750 // setStack sets the stack to the contents of the array where the last item in the array is the top item in the stack.
751 func setStack(stack *stack, data [][]byte) {
752 // This can not error. Only errors are for invalid arguments.
753 _ = stack.DropN(stack.Depth())
754 for i := range data {
755 stack.PushByteArray(data[i])
756 }
757 }
758 759 // GetStack returns the contents of the primary stack as an array. where the last item in the array is the top of the
760 // stack.
761 func (vm *Engine) GetStack() [][]byte {
762 return getStack(&vm.dstack)
763 }
764 765 // SetStack sets the contents of the primary stack to the contents of the provided array where the last item in the
766 // array will be the top of the stack.
767 func (vm *Engine) SetStack(data [][]byte) {
768 setStack(&vm.dstack, data)
769 }
770 771 // GetAltStack returns the contents of the alternate stack as an array where the last item in the array is the top of
772 // the stack.
773 func (vm *Engine) GetAltStack() [][]byte {
774 return getStack(&vm.astack)
775 }
776 777 // SetAltStack sets the contents of the alternate stack to the contents of the provided array where the last item in the
778 // array will be the top of the stack.
779 func (vm *Engine) SetAltStack(data [][]byte) {
780 setStack(&vm.astack, data)
781 }
782 783 // NewEngine returns a new script engine for the provided public key script, transaction, and input index. The flags
784 // modify the behavior of the script engine according to the description provided by each flag.
785 func NewEngine(
786 scriptPubKey []byte, tx *wire.MsgTx, txIdx int, flags ScriptFlags,
787 sigCache *SigCache, hashCache *TxSigHashes, inputAmount int64,
788 ) (*Engine, error) {
789 // The provided transaction input index must refer to a valid input.
790 if txIdx < 0 || txIdx >= len(tx.TxIn) {
791 str := fmt.Sprintf(
792 "transaction input index %d is negative or "+
793 ">= %d", txIdx, len(tx.TxIn),
794 )
795 return nil, scriptError(ErrInvalidIndex, str)
796 }
797 scriptSig := tx.TxIn[txIdx].SignatureScript
798 // When both the signature script and public key script are empty the result is necessarily an error since the stack
799 // would end up being empty which is equivalent to a false top element. Thus, just return the relevant error now as
800 // an optimization.
801 if len(scriptSig) == 0 && len(scriptPubKey) == 0 {
802 return nil, scriptError(
803 ErrEvalFalse,
804 "false stack entry at end of script execution",
805 )
806 }
807 // The clean stack flag (ScriptVerifyCleanStack) is not allowed without either
808 // the pay-to-script-hash (P2SH) evaluation (ScriptBip16) flag or the Segregated
809 // Witness (ScriptVerifyWitness) flag. Recall that evaluating a P2SH script
810 // without the flag set results in non-P2SH evaluation which leaves the P2SH
811 // inputs on the stack. Thus, allowing the clean stack flag without the P2SH
812 // flag would make it possible to have a situation where P2SH would not be a
813 // soft fork when it should be. The same goes for segwit which will pull in
814 // additional scripts for execution from the witness stack.
815 vm := Engine{
816 flags: flags,
817 sigCache: sigCache,
818 hashCache: hashCache,
819 inputAmount: inputAmount,
820 }
821 if vm.hasFlag(ScriptVerifyCleanStack) && (!vm.hasFlag(ScriptBip16) &&
822 !vm.hasFlag(ScriptVerifyWitness)) {
823 return nil, scriptError(
824 ErrInvalidFlags,
825 "invalid flags combination",
826 )
827 }
828 // The signature script must only contain data pushes when the associated flag is set.
829 if vm.hasFlag(ScriptVerifySigPushOnly) && !IsPushOnlyScript(scriptSig) {
830 return nil, scriptError(
831 ErrNotPushOnly,
832 "signature script is not push only",
833 )
834 }
835 // The engine stores the scripts in parsed form using a slice. This allows multiple scripts to be executed in
836 // sequence. For example, with a pay-to-script-hash transaction, there will be ultimately be a third script to
837 // execute.
838 scripts := [][]byte{scriptSig, scriptPubKey}
839 vm.scripts = make([][]parsedOpcode, len(scripts))
840 for i, scr := range scripts {
841 if len(scr) > MaxScriptSize {
842 str := fmt.Sprintf(
843 "script size %d is larger than max "+
844 "allowed size %d", len(scr), MaxScriptSize,
845 )
846 return nil, scriptError(ErrScriptTooBig, str)
847 }
848 var e error
849 vm.scripts[i], e = parseScript(scr)
850 if e != nil {
851 return nil, e
852 }
853 }
854 // Advance the program counter to the public key script if the signature script is empty since there is nothing to
855 // execute for it in that case.
856 if len(scripts[0]) == 0 {
857 vm.scriptIdx.Inc()
858 }
859 if vm.hasFlag(ScriptBip16) && isScriptHash(vm.scripts[1]) {
860 // Only accept input scripts that push data for P2SH.
861 if !isPushOnly(vm.scripts[0]) {
862 return nil, scriptError(
863 ErrNotPushOnly,
864 "pay to script hash is not push only",
865 )
866 }
867 vm.bip16 = true
868 }
869 if vm.hasFlag(ScriptVerifyMinimalData) {
870 vm.dstack.verifyMinimalData = true
871 vm.astack.verifyMinimalData = true
872 }
873 // // Chk to see if we should execute in witness verification mode according to
874 // // the set flags. We check both the pkScript, and sigScript here since in the
875 // // case of nested p2sh, the scriptSig will be a valid witness program. For
876 // // nested p2sh, all the bytes after the first data push should *exactly* match
877 // // the witness program template.
878 // if vm.hasFlag(ScriptVerifyWitness) {
879 // // If witness evaluation is enabled, then P2SH MUST also be active.
880 // if !vm.hasFlag(ScriptBip16) {
881 // errStr := "P2SH must be enabled to do witness verification"
882 // return nil, scriptError(ErrInvalidFlags, errStr)
883 // }
884 // var witProgram []byte
885 // switch {
886 // case isWitnessProgram(vm.scripts[1]):
887 // // The scriptSig must be *empty* for all native witness programs, otherwise we
888 // // introduce malleability.
889 // if len(scriptSig) != 0 {
890 // errStr := "native witness program cannot also have a signature script"
891 // return nil, scriptError(ErrWitnessMalleated, errStr)
892 // }
893 // witProgram = scriptPubKey
894 // case len(tx.TxIn[txIdx].Witness) != 0 && vm.bip16:
895 // // The sigScript MUST be *exactly* a single canonical data push of the witness
896 // // program, otherwise we reintroduce malleability.
897 // sigPops := vm.scripts[0]
898 // if len(sigPops) == 1 && canonicalPush(sigPops[0]) &&
899 // IsWitnessProgram(sigPops[0].data) {
900 // witProgram = sigPops[0].data
901 // } else {
902 // errStr := "signature script for witness nested p2sh is not canonical"
903 // return nil, scriptError(ErrWitnessMalleatedP2SH, errStr)
904 // }
905 // }
906 // if witProgram != nil {
907 // var e error
908 // vm.witnessVersion, vm.witnessProgram, e = ExtractWitnessProgramI.Ln(witProgram)
909 // if e != nil {
910 // return nil, e
911 // }
912 // } else {
913 // // If we didn't find a witness program in either the pkScript or as a datapush
914 // // within the sigScript, then there MUST NOT be any witness data associated with
915 // // the input being validated.
916 // if vm.witnessProgram == nil && len(tx.TxIn[txIdx].Witness) != 0 {
917 // errStr := "non-witness inputs cannot have a witness"
918 // return nil, scriptError(ErrWitnessUnexpected, errStr)
919 // }
920 // }
921 // }
922 vm.tx = *tx
923 vm.txIdx = txIdx
924 return &vm, nil
925 }
926