engine.go

package txscript

import (
	"bytes"
	"crypto/sha256"
	"fmt"
	"math/big"
	
	"github.com/p9c/duod/pkg/wire"
	
	"go.uber.org/atomic"
	
	ec "github.com/p9c/duod/pkg/ecc"
)

// ScriptFlags is a bitmask defining additional operations or tests that will be done when executing a script pair.
type ScriptFlags uint32

const (
	// ScriptBip16 defines whether the bip16 threshold has passed and thus pay-to-script hash transactions will be fully
	// validated.
	ScriptBip16 ScriptFlags = 1 << iota
	// ScriptStrictMultiSig defines whether to verify the stack item used by CHECKMULTISIG is zero length.
	ScriptStrictMultiSig
	// ScriptDiscourageUpgradableNops defines whether to verify that NOP1 through NOP10 are reserved for future
	// soft-fork upgrades. This flag must not be used for consensus critical code nor applied to blocks as this flag is
	// only for stricter standard transaction checks. This flag is only applied when the above opcodes are executed.
	ScriptDiscourageUpgradableNops
	// ScriptVerifyCheckLockTimeVerify defines whether to verify that a transaction output is spendable based on the
	// locktime. This is BIP0065.
	ScriptVerifyCheckLockTimeVerify
	// ScriptVerifyCheckSequenceVerify defines whether to allow execution pathways of a script to be restricted based on
	// the age of the output being spent. This is BIP0112.
	ScriptVerifyCheckSequenceVerify
	// ScriptVerifyCleanStack defines that the stack must contain only one stack
	// element after evaluation and that the element must be true if interpreted as
	// a boolean. This is rule 6 of BIP0062. This flag should never be used without
	// the ScriptBip16 flag nor the ScriptVerifyWitness flag.
	ScriptVerifyCleanStack
	// ScriptVerifyDERSignatures defines that signatures are required to compily with the DER format.
	ScriptVerifyDERSignatures
	// ScriptVerifyLowS defines that signtures are required to comply with the DER format and whose S value is <= order
	// / 2. This is rule 5 of BIP0062.
	ScriptVerifyLowS
	// ScriptVerifyMinimalData defines that signatures must use the smallest push operator. This is both rules 3 and 4
	// of BIP0062.
	ScriptVerifyMinimalData
	// ScriptVerifyNullFail defines that signatures must be empty if a CHECKSIG or CHECKMULTISIG operation fails.
	ScriptVerifyNullFail
	// ScriptVerifySigPushOnly defines that signature scripts must contain only pushed data. This is rule 2 of BIP0062.
	ScriptVerifySigPushOnly
	// ScriptVerifyStrictEncoding defines that signature scripts and public keys must follow the strict encoding
	// requirements.
	ScriptVerifyStrictEncoding
	// ScriptVerifyWitness defines whether or not to verify a transaction output
	// using a witness program template.
	ScriptVerifyWitness
	// ScriptVerifyDiscourageUpgradeableWitnessProgram makes witness program with
	// versions 2-16 non-standard.
	ScriptVerifyDiscourageUpgradeableWitnessProgram
	// ScriptVerifyMinimalIf makes a script with an OP_IF/OP_NOTIF whose operand is anything other than empty vector or
	// [0x01] non-standard.
	ScriptVerifyMinimalIf
	// ScriptVerifyWitnessPubKeyType makes a script within a check-sig operation
	// whose public key isn't serialized in a compressed format non-standard.
	ScriptVerifyWitnessPubKeyType
	// MaxStackSize is the maximum combined height of stack and alt stack during execution.
	MaxStackSize = 1000
	// MaxScriptSize is the maximum allowed length of a raw script.
	MaxScriptSize = 10000
	// payToWitnessPubKeyHashDataSize is the size of the witness program's data push
	// for a pay-to-witness-pub-key-hash output.
	payToWitnessPubKeyHashDataSize = 20
	// payToWitnessScriptHashDataSize is the size of the witness program's data push
	// for a pay-to-witness-script-hash output.
	payToWitnessScriptHashDataSize = 32
)

// halforder is used to tame ECDSA malleability (see BIP0062).
var halfOrder = new(big.Int).Rsh(ec.S256().N, 1)

// Engine is the virtual machine that executes scripts.
type Engine struct {
	scripts         [][]parsedOpcode
	scriptIdx       atomic.Int64
	scriptOff       atomic.Int64
	lastCodeSep     int
	dstack          stack // data stack
	astack          stack // alt stack
	tx              wire.MsgTx
	txIdx           int
	condStack       []int
	numOps          int
	flags           ScriptFlags
	sigCache        *SigCache
	hashCache       *TxSigHashes
	bip16           bool     // treat execution as pay-to-script-hash
	savedFirstStack [][]byte // stack from first script for bip16 scripts
	witnessVersion  int
	witnessProgram  []byte
	inputAmount     int64
}

// hasFlag returns whether the script engine instance has the passed flag set.
func (vm *Engine) hasFlag(flag ScriptFlags) bool {
	return vm.flags&flag == flag
}

// isBranchExecuting returns whether or not the current conditional branch is actively executing. For example, when the
// 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
// encountered. It properly handles nested conditionals.
func (vm *Engine) isBranchExecuting() bool {
	if len(vm.condStack) == 0 {
		return true
	}
	return vm.condStack[len(vm.condStack)-1] == OpCondTrue
}

// executeOpcode peforms execution on the passed opcode. It takes into account whether or not it is hidden by
// conditionals, but some rules still must be tested in this case.
func (vm *Engine) executeOpcode(pop *parsedOpcode) (e error) {
	// Disabled opcodes are fail on program counter.
	if pop.isDisabled() {
		str := fmt.Sprintf(
			"attempt to execute disabled opcode %s",
			pop.opcode.name,
		)
		return scriptError(ErrDisabledOpcode, str)
	}
	// Always-illegal opcodes are fail on program counter.
	if pop.alwaysIllegal() {
		str := fmt.Sprintf(
			"attempt to execute reserved opcode %s",
			pop.opcode.name,
		)
		return scriptError(ErrReservedOpcode, str)
	}
	// Note that this includes OP_RESERVED which counts as a push operation.
	if pop.opcode.value > OP_16 {
		vm.numOps++
		if vm.numOps > MaxOpsPerScript {
			str := fmt.Sprintf(
				"exceeded max operation limit of %d",
				MaxOpsPerScript,
			)
			return scriptError(ErrTooManyOperations, str)
		}
	} else if len(pop.data) > MaxScriptElementSize {
		str := fmt.Sprintf(
			"element size %d exceeds max allowed size %d",
			len(pop.data), MaxScriptElementSize,
		)
		return scriptError(ErrElementTooBig, str)
	}
	// Nothing left to do when this is not a conditional opcode and it is not in an executing branch.
	if !vm.isBranchExecuting() && !pop.isConditional() {
		return nil
	}
	// Ensure all executed data push opcodes use the minimal encoding when the minimal data verification flag is set.
	if vm.dstack.verifyMinimalData && vm.isBranchExecuting() &&
		// pop.opcode.value >= 0 &&
		pop.opcode.value <= OP_PUSHDATA4 {
		if e = pop.checkMinimalDataPush(); E.Chk(e) {
			return e
		}
	}
	return pop.opcode.opfunc(pop, vm)
}

// disasm is a helper function to produce the output for DisasmPC and DisasmScript. It produces the opcode prefixed by
// the program counter at the provided position in the script. It does no error checking and leaves that to the caller
// to provide a valid offset.
func (vm *Engine) disasm(scriptIdx int, scriptOff int) string {
	if scriptIdx >= len(vm.scripts) {
		return fmt.Sprintf("disasm array index out of bounds ERR: %02x:%04x", scriptIdx, scriptOff)
	}
	if scriptOff >= len(vm.scripts[scriptIdx]) {
		return fmt.Sprintf(
			"disasm scriptoff array index out of bounds ERR: %02x:%04x", scriptIdx, scriptOff,
		)
	}
	return fmt.Sprintf(
		"%02x:%04x: %s", scriptIdx, scriptOff,
		vm.scripts[scriptIdx][scriptOff].print(false),
	)
}

// validPC returns an error if the current script position is valid for execution, nil otherwise.
func (vm *Engine) validPC() (E error) {
	if int(vm.scriptIdx.Load()) >= len(vm.scripts) {
		str := fmt.Sprintf(
			"past input scripts %v:%v %v:xxxx",
			vm.scriptIdx.Load(), vm.scriptOff.Load(), len(vm.scripts),
		)
		E = scriptError(ErrInvalidProgramCounter, str)
	}
	if len(vm.scripts) < int(vm.scriptIdx.Load()) &&
		int(vm.scriptOff.Load()) >= len(vm.scripts[vm.scriptIdx.Load()]) {
		str := fmt.Sprintf(
			"past input scripts %v:%v %v:%04d",
			vm.scriptIdx.Load(), vm.scriptOff.Load(), vm.scriptIdx.Load(),
			len(vm.scripts[vm.scriptIdx.Load()]),
		)
		return scriptError(ErrInvalidProgramCounter, str)
	}
	return nil
}

// curPC returns either the current script and offset, or an error if the position isn't valid.
func (vm *Engine) curPC() (script int, off int, e error) {
	e = vm.validPC()
	if e != nil {
		return 0, 0, e
	}
	return int(vm.scriptIdx.Load()), int(vm.scriptOff.Load()), nil
}

// isWitnessVersionActive returns true if a witness program was extracted during
// the initialization of the Engine, and the program's version matches the
// specified version.
func (vm *Engine) isWitnessVersionActive(version uint) bool {
	return vm.witnessProgram != nil && uint(vm.witnessVersion) == version
}

// verifyWitnessProgram validates the stored witness program using the passed
// witness as input.
func (vm *Engine) verifyWitnessProgram(witness [][]byte) (e error) {
	if vm.isWitnessVersionActive(0) {
		switch len(vm.witnessProgram) {
		case payToWitnessPubKeyHashDataSize: // P2WKH
			// The witness stack should consist of exactly two items: the signature, and the
			// pubkey.
			if len(witness) != 2 {
				e := fmt.Sprintf(
					"should have exactly two items in witness, instead have %v", len(witness),
				)
				return scriptError(ErrWitnessProgramMismatch, e)
			}
			// Now we'll resume execution as if it were a regular p2pkh transaction.
			pkScript, e := payToPubKeyHashScript(vm.witnessProgram)
			if e != nil {
				return e
			}
			pops, e := parseScript(pkScript)
			if e != nil {
				return e
			}
			// Set the stack to the provided witness stack, then append the pkScript
			// generated above as the next script to execute.
			vm.scripts = append(vm.scripts, pops)
			vm.SetStack(witness)
		case payToWitnessScriptHashDataSize: // P2WSH
			// Additionally, The witness stack MUST NOT be empty at this point.
			if len(witness) == 0 {
				return scriptError(
					ErrWitnessProgramEmpty, "witness program empty passed empty witness",
				)
			}
			// Obtain the witness script which should be the last element in the passed
			// stack. The size of the script MUST NOT exceed the max script size.
			witnessScript := witness[len(witness)-1]
			if len(witnessScript) > MaxScriptSize {
				str := fmt.Sprintf(
					"witnessScript size %d "+
						"is larger than max allowed size %d",
					len(witnessScript), MaxScriptSize,
				)
				return scriptError(ErrScriptTooBig, str)
			}
			// Ensure that the serialized pkScript at the end of the witness stack matches
			// the witness program.
			witnessHash := sha256.Sum256(witnessScript)
			if !bytes.Equal(witnessHash[:], vm.witnessProgram) {
				return scriptError(
					ErrWitnessProgramMismatch,
					"witness program hash mismatch",
				)
			}
			// With all the validity checks passed, parse the script into individual op-codes so w can execute it as the
			// next script.
			pops, e := parseScript(witnessScript)
			if e != nil {
				return e
			}
			// The hash matched successfully, so use the witness as the stack, and set the
			// witnessScript to be the next script executed.
			vm.scripts = append(vm.scripts, pops)
			vm.SetStack(witness[:len(witness)-1])
		default:
			errStr := fmt.Sprintf(
				"length of witness program "+
					"must either be %v or %v bytes, instead is %v bytes",
				payToWitnessPubKeyHashDataSize,
				payToWitnessScriptHashDataSize,
				len(vm.witnessProgram),
			)
			return scriptError(ErrWitnessProgramWrongLength, errStr)
		}
	} else if vm.hasFlag(ScriptVerifyDiscourageUpgradeableWitnessProgram) {
		errStr := fmt.Sprintf(
			"new witness program versions invalid: %v", vm.witnessProgram,
		)
		return scriptError(ErrDiscourageUpgradableWitnessProgram, errStr)
	} else {
		// If we encounter an unknown witness program version and we aren't discouraging
		// future unknown witness based soft-forks, then we de-activate the segwit
		// behavior within the VM for the remainder of execution.
		vm.witnessProgram = nil
	}
	if vm.isWitnessVersionActive(0) {
		// All elements within the witness stack must not be greater than the maximum
		// bytes which are allowed to be pushed onto the stack.
		for _, witElement := range vm.GetStack() {
			if len(witElement) > MaxScriptElementSize {
				str := fmt.Sprintf(
					"element size %d exceeds "+
						"max allowed size %d", len(witElement),
					MaxScriptElementSize,
				)
				return scriptError(ErrElementTooBig, str)
			}
		}
	}
	return nil
}

// DisasmPC returns the string for the disassembly of the opcode that will be next to execute when Step() is called.
func (vm *Engine) DisasmPC() (string, error) {
	scriptIdx, scriptOff, e := vm.curPC()
	if e != nil {
		return "", e
	}
	return vm.disasm(scriptIdx, scriptOff), nil
}

// DisasmScript returns the disassembly string for the script at the requested offset index. Index 0 is the signature
// script and 1 is the public key script.
func (vm *Engine) DisasmScript(idx int) (string, error) {
	if idx >= len(vm.scripts) {
		str := fmt.Sprintf(
			"script index %d >= total scripts %d", idx,
			len(vm.scripts),
		)
		return "", scriptError(ErrInvalidIndex, str)
	}
	var disstr string
	for i := range vm.scripts[idx] {
		disstr = disstr + vm.disasm(idx, i) + "\n"
	}
	return disstr, nil
}

// CheckErrorCondition returns nil if the running script has ended and was successful, leaving a a true boolean on the
// stack. An error otherwise, including if the script has not finished.
func (vm *Engine) CheckErrorCondition(finalScript bool) (e error) {
	// Chk execution is actually done.  When pc is past the end of script array there are no more scripts to run.
	if int(vm.scriptIdx.Load()) < len(vm.scripts) {
		return scriptError(
			ErrScriptUnfinished,
			"error check when script unfinished",
		)
	}
	// If we're in version zero witness execution mode, and this was the final
	// script, then the stack MUST be clean in order to maintain compatibility with
	// BIP16.
	if finalScript && vm.isWitnessVersionActive(0) && vm.dstack.Depth() != 1 {
		return scriptError(
			ErrEvalFalse, "witness program must have clean stack",
		)
	}
	if finalScript && vm.hasFlag(ScriptVerifyCleanStack) &&
		vm.dstack.Depth() != 1 {
		str := fmt.Sprintf(
			"stack contains %d unexpected items",
			vm.dstack.Depth()-1,
		)
		return scriptError(ErrCleanStack, str)
	} else if vm.dstack.Depth() < 1 {
		return scriptError(
			ErrEmptyStack,
			"stack empty at end of script execution",
		)
	}
	v, e := vm.dstack.PopBool()
	if e != nil {
		return e
	}
	if !v {
		// Log interesting data.
		T.C(
			func() string {
				dis0, _ := vm.DisasmScript(0)
				dis1, _ := vm.DisasmScript(1)
				return fmt.Sprintf(
					"scripts failed: script0: %s\n"+
						"script1: %s", dis0, dis1,
				)
			},
		)
		return scriptError(
			ErrEvalFalse,
			"false stack entry at end of script execution",
		)
	}
	return nil
}

// Step will execute the next instruction and move the program counter to the next opcode in the script, or the next
// script if the current has ended. Step will return true in the case that the last opcode was successfully executed.
// The result of calling Step or any other method is undefined if an error is returned.
func (vm *Engine) Step() (done bool, e error) {
	// Verify that it is pointing to a valid script address.
	e = vm.validPC()
	if e != nil {
		return true, e
	}
	opcode := &vm.scripts[vm.scriptIdx.Load()][vm.scriptOff.Load()]
	vm.scriptOff.Inc()
	// Execute the opcode while taking into account several things such as disabled opcodes, illegal opcodes, maximum
	// allowed operations per script, maximum script element txsizes, and conditionals.
	e = vm.executeOpcode(opcode)
	if e != nil {
		return true, e
	}
	// The number of elements in the combination of the data and alt stacks must not exceed the maximum number of stack
	// elements allowed.
	combinedStackSize := vm.dstack.Depth() + vm.astack.Depth()
	if combinedStackSize > MaxStackSize {
		str := fmt.Sprintf(
			"combined stack size %d > max allowed %d",
			combinedStackSize, MaxStackSize,
		)
		done, e = false, scriptError(ErrStackOverflow, str)
	}
	if e != nil {
		return
	}
	// Prepare for next instruction.
	if int(vm.scriptOff.Load()) >= len(vm.scripts[vm.scriptIdx.Load()]) {
		// Illegal to have an `if' that straddles two scripts.
		if len(vm.condStack) != 0 {
			done, e =
				false,
				scriptError(
					ErrUnbalancedConditional,
					"end of script reached in conditional execution",
				)
			return
		}
		// Alt stack doesn't persist.
		_ = vm.astack.DropN(vm.astack.Depth())
		vm.numOps = 0 // number of ops is per script.
		vm.scriptOff.Store(0)
		if vm.scriptIdx.Load() == 0 && vm.bip16 {
			vm.scriptIdx.Inc()
			vm.savedFirstStack = vm.GetStack()
		} else if vm.scriptIdx.Load() == 1 && vm.bip16 {
			// Put us past the end for CheckErrorCondition()
			vm.scriptIdx.Inc()
			// Check script ran successfully and pull the script out of the first stack and execute that.
			ee := vm.CheckErrorCondition(false)
			if ee != nil {
				E.Ln(e)
				done, e = false, ee
				return
			}
			script := vm.savedFirstStack[len(vm.savedFirstStack)-1]
			pops, er := parseScript(script)
			if er != nil {
				E.Ln(e)
				done, e = false, er
				return
			}
			vm.scripts = append(vm.scripts, pops)
			// Set stack to be the stack from first script minus the script itself
			vm.SetStack(vm.savedFirstStack[:len(vm.savedFirstStack)-1])
			// } else if (vm.scriptIdx.Load() == 1 && vm.witnessProgram != nil) ||
			// 	(vm.scriptIdx.Load() == 2 && vm.witnessProgram != nil && vm.bip16) {
			// 	// Nested P2SH.
			// 	vm.scriptIdx.Inc()
			// 	witness := vm.tx.TxIn[vm.txIdx].Witness
			// 	if er := vm.verifyWitnessProgram(witness); E.Chk(e) {
			// 		done, e = false, er
			// 		return
			// 	}
		} else {
			vm.scriptIdx.Inc()
		}
		// there are zero length scripts in the wild
		if int(vm.scriptIdx.Load()) < len(vm.scripts) &&
			int(vm.scriptOff.Load()) >= len(vm.scripts[vm.scriptIdx.Load()]) {
			vm.scriptIdx.Inc()
		}
		vm.lastCodeSep = 0
		if int(vm.scriptIdx.Load()) >= len(vm.scripts) {
			done, e = true, nil
			return
		}
	}
	return
}

// Execute will execute all scripts in the script engine and return either nil for successful validation or an error if
// one occurred.
func (vm *Engine) Execute() (e error) {
	done := false
	for !done {
		done, e = vm.Step()
		if e != nil {
			return e
		}
		T.C(
			func() string {
				var o string
				dis, e := vm.DisasmPC()
				if e != nil {
					o += "c stepping (" + e.Error() + ")"
				}
				o += "oo stepping " + dis
				var dstr, astr string
				// if we're tracing, dump the stacks.
				if vm.dstack.Depth() != 0 {
					dstr = "\nStack:\n" + vm.dstack.String()
				}
				if vm.astack.Depth() != 0 {
					astr = "\nAltStack:\n" + vm.astack.String()
				}
				return o + dstr + astr
			},
		)
	}
	return vm.CheckErrorCondition(true)
}

// subScript returns the script since the last OP_CODESEPARATOR.
func (vm *Engine) subScript() []parsedOpcode {
	return vm.scripts[vm.scriptIdx.Load()][vm.lastCodeSep:]
}

// checkHashTypeEncoding returns whether or not the passed hashtype adheres to the strict encoding requirements if
// enabled.
func (vm *Engine) checkHashTypeEncoding(hashType SigHashType) (e error) {
	if !vm.hasFlag(ScriptVerifyStrictEncoding) {
		return nil
	}
	sigHashType := hashType & ^SigHashAnyOneCanPay
	if sigHashType < SigHashAll || sigHashType > SigHashSingle {
		str := fmt.Sprintf("invalid hash type 0x%x", hashType)
		return scriptError(ErrInvalidSigHashType, str)
	}
	return nil
}

// checkPubKeyEncoding returns whether or not the passed public key adheres to the strict encoding requirements if
// enabled.
func (vm *Engine) checkPubKeyEncoding(pubKey []byte) (e error) {
	if vm.hasFlag(ScriptVerifyWitnessPubKeyType) &&
		vm.isWitnessVersionActive(0) && !ec.IsCompressedPubKey(pubKey) {
		str := "only uncompressed keys are accepted post-segwit"
		return scriptError(ErrWitnessPubKeyType, str)
	}
	if !vm.hasFlag(ScriptVerifyStrictEncoding) {
		return nil
	}
	if len(pubKey) == 33 && (pubKey[0] == 0x02 || pubKey[0] == 0x03) {
		// Compressed
		return nil
	}
	if len(pubKey) == 65 && pubKey[0] == 0x04 {
		// Uncompressed
		return nil
	}
	return scriptError(ErrPubKeyType, "unsupported public key type")
}

// checkSignatureEncoding returns whether or not the passed signature adheres to the strict encoding requirements if
// enabled.
func (vm *Engine) checkSignatureEncoding(sig []byte) (e error) {
	if !vm.hasFlag(ScriptVerifyDERSignatures) &&
		!vm.hasFlag(ScriptVerifyLowS) &&
		!vm.hasFlag(ScriptVerifyStrictEncoding) {
		return nil
	}
	// The format of a DER encoded signature is as follows:
	//
	// 0x30 <total length> 0x02 <length of R> <R> 0x02 <length of S> <S>
	//   - 0x30 is the ASN.1 identifier for a sequence - Total length is 1 byte and specifies length of all remaining data
	//   - 0x02 is the ASN.1 identifier that specifies an integer follows
	//   - Length of R is 1 byte and specifies how many bytes R occupies
	//   - R is the arbitrary length big-endian encoded number which represents the R value of the
	//   signature. DER encoding dictates that the value must be encoded using the minimum possible number of bytes. This
	//   implies the first byte can only be null if the highest bit of the next byte is set in order to prevent it from
	//   being interpreted as a negative number.
	//   - 0x02 is once again the ASN.1 integer identifier - Length of S is 1 byte
	//   and specifies how many bytes S occupies
	//   - S is the arbitrary length big-endian encoded number which represents
	//   the S value of the signature. The encoding rules are identical as those for R.
	const (
		asn1SequenceID = 0x30
		asn1IntegerID  = 0x02
		// minSigLen is the minimum length of a DER encoded signature and is when both R and S are 1 byte each.
		// 0x30 + <1-byte> + 0x02 + 0x01 + <byte> + 0x2 + 0x01 + <byte>
		minSigLen = 8
		// maxSigLen is the maximum length of a DER encoded signature and is when both R and S are 33 bytes each. It is
		// 33 bytes because a 256-bit integer requires 32 bytes and an additional leading null byte might required if
		// the high bit is set in the value.
		//
		// 0x30 + <1-byte> + 0x02 + 0x21 + <33 bytes> + 0x2 + 0x21 + <33 bytes>
		maxSigLen = 72
		// sequenceOffset is the byte offset within the signature of the expected ASN.1 sequence identifier.
		sequenceOffset = 0
		// dataLenOffset is the byte offset within the signature of the expected total length of all remaining data in
		// the signature.
		dataLenOffset = 1
		// rTypeOffset is the byte offset within the signature of the ASN.1 identifier for R and is expected to indicate
		// an ASN.1 integer.
		rTypeOffset = 2
		// rLenOffset is the byte offset within the signature of the length of R.
		rLenOffset = 3
		// rOffset is the byte offset within the signature of R.
		rOffset = 4
	)
	// The signature must adhere to the minimum and maximum allowed length.
	sigLen := len(sig)
	if sigLen < minSigLen {
		str := fmt.Sprintf(
			"malformed signature: too short: %d < %d", sigLen,
			minSigLen,
		)
		return scriptError(ErrSigTooShort, str)
	}
	if sigLen > maxSigLen {
		str := fmt.Sprintf(
			"malformed signature: too long: %d > %d", sigLen,
			maxSigLen,
		)
		return scriptError(ErrSigTooLong, str)
	}
	// The signature must start with the ASN.1 sequence identifier.
	if sig[sequenceOffset] != asn1SequenceID {
		str := fmt.Sprintf(
			"malformed signature: format has wrong type: %#x",
			sig[sequenceOffset],
		)
		return scriptError(ErrSigInvalidSeqID, str)
	}
	// The signature must indicate the correct amount of data for all elements related to R and S.
	if int(sig[dataLenOffset]) != sigLen-2 {
		str := fmt.Sprintf(
			"malformed signature: bad length: %d != %d",
			sig[dataLenOffset], sigLen-2,
		)
		return scriptError(ErrSigInvalidDataLen, str)
	}
	// Calculate the offsets of the elements related to S and ensure S is inside the signature. rLen specifies the
	// length of the big-endian encoded number which represents the R value of the signature. sTypeOffset is the offset
	// of the ASN.1 identifier for S and, like its R counterpart, is expected to indicate an ASN.1 integer. sLenOffset
	// and sOffset are the byte offsets within the signature of the length of S and S itself, respectively.
	rLen := int(sig[rLenOffset])
	sTypeOffset := rOffset + rLen
	sLenOffset := sTypeOffset + 1
	if sTypeOffset >= sigLen {
		str := "malformed signature: S type indicator missing"
		return scriptError(ErrSigMissingSTypeID, str)
	}
	if sLenOffset >= sigLen {
		str := "malformed signature: S length missing"
		return scriptError(ErrSigMissingSLen, str)
	}
	// The lengths of R and S must match the overall length of the signature. sLen specifies the length of the
	// big-endian encoded number which represents the S value of the signature.
	sOffset := sLenOffset + 1
	sLen := int(sig[sLenOffset])
	if sOffset+sLen != sigLen {
		str := "malformed signature: invalid S length"
		return scriptError(ErrSigInvalidSLen, str)
	}
	// R elements must be ASN.1 integers.
	if sig[rTypeOffset] != asn1IntegerID {
		str := fmt.Sprintf(
			"malformed signature: R integer marker: %#x != %#x",
			sig[rTypeOffset], asn1IntegerID,
		)
		return scriptError(ErrSigInvalidRIntID, str)
	}
	// Zero-length integers are not allowed for R.
	if rLen == 0 {
		str := "malformed signature: R length is zero"
		return scriptError(ErrSigZeroRLen, str)
	}
	// R must not be negative.
	if sig[rOffset]&0x80 != 0 {
		str := "malformed signature: R is negative"
		return scriptError(ErrSigNegativeR, str)
	}
	// Null bytes at the start of R are not allowed, unless R would otherwise be interpreted as a negative number.
	if rLen > 1 && sig[rOffset] == 0x00 && sig[rOffset+1]&0x80 == 0 {
		str := "malformed signature: R value has too much padding"
		return scriptError(ErrSigTooMuchRPadding, str)
	}
	// S elements must be ASN.1 integers.
	if sig[sTypeOffset] != asn1IntegerID {
		str := fmt.Sprintf(
			"malformed signature: S integer marker: %#x != %#x",
			sig[sTypeOffset], asn1IntegerID,
		)
		return scriptError(ErrSigInvalidSIntID, str)
	}
	// Zero-length integers are not allowed for S.
	if sLen == 0 {
		str := "malformed signature: S length is zero"
		return scriptError(ErrSigZeroSLen, str)
	}
	// S must not be negative.
	if sig[sOffset]&0x80 != 0 {
		str := "malformed signature: S is negative"
		return scriptError(ErrSigNegativeS, str)
	}
	// Null bytes at the start of S are not allowed, unless S would otherwise be interpreted as a negative number.
	if sLen > 1 && sig[sOffset] == 0x00 && sig[sOffset+1]&0x80 == 0 {
		str := "malformed signature: S value has too much padding"
		return scriptError(ErrSigTooMuchSPadding, str)
	}
	// Verify the S value is <= half the order of the curve. This check is done because when it is higher, the
	// complement modulo the order can be used instead which is a shorter encoding by 1 byte. Further, without enforcing
	// this, it is possible to replace a signature in a valid transaction with the complement while still being a valid
	// signature that verifies. This would result in changing the transaction hash and thus is a source of malleability.
	if vm.hasFlag(ScriptVerifyLowS) {
		sValue := new(big.Int).SetBytes(sig[sOffset : sOffset+sLen])
		if sValue.Cmp(halfOrder) > 0 {
			return scriptError(
				ErrSigHighS, "signature is not canonical due "+
					"to unnecessarily high S value",
			)
		}
	}
	return nil
}

// getStack returns the contents of stack as a byte array bottom up
func getStack(stack *stack) [][]byte {
	array := make([][]byte, stack.Depth())
	for i := range array {
		// PeekByteArry can't fail due to overflow, already checked
		array[len(array)-i-1], _ = stack.PeekByteArray(int32(i))
	}
	return array
}

// setStack sets the stack to the contents of the array where the last item in the array is the top item in the stack.
func setStack(stack *stack, data [][]byte) {
	// This can not error. Only errors are for invalid arguments.
	_ = stack.DropN(stack.Depth())
	for i := range data {
		stack.PushByteArray(data[i])
	}
}

// GetStack returns the contents of the primary stack as an array. where the last item in the array is the top of the
// stack.
func (vm *Engine) GetStack() [][]byte {
	return getStack(&vm.dstack)
}

// SetStack sets the contents of the primary stack to the contents of the provided array where the last item in the
// array will be the top of the stack.
func (vm *Engine) SetStack(data [][]byte) {
	setStack(&vm.dstack, data)
}

// GetAltStack returns the contents of the alternate stack as an array where the last item in the array is the top of
// the stack.
func (vm *Engine) GetAltStack() [][]byte {
	return getStack(&vm.astack)
}

// SetAltStack sets the contents of the alternate stack to the contents of the provided array where the last item in the
// array will be the top of the stack.
func (vm *Engine) SetAltStack(data [][]byte) {
	setStack(&vm.astack, data)
}

// NewEngine returns a new script engine for the provided public key script, transaction, and input index. The flags
// modify the behavior of the script engine according to the description provided by each flag.
func NewEngine(
	scriptPubKey []byte, tx *wire.MsgTx, txIdx int, flags ScriptFlags,
	sigCache *SigCache, hashCache *TxSigHashes, inputAmount int64,
) (*Engine, error) {
	// The provided transaction input index must refer to a valid input.
	if txIdx < 0 || txIdx >= len(tx.TxIn) {
		str := fmt.Sprintf(
			"transaction input index %d is negative or "+
				">= %d", txIdx, len(tx.TxIn),
		)
		return nil, scriptError(ErrInvalidIndex, str)
	}
	scriptSig := tx.TxIn[txIdx].SignatureScript
	// When both the signature script and public key script are empty the result is necessarily an error since the stack
	// would end up being empty which is equivalent to a false top element. Thus, just return the relevant error now as
	// an optimization.
	if len(scriptSig) == 0 && len(scriptPubKey) == 0 {
		return nil, scriptError(
			ErrEvalFalse,
			"false stack entry at end of script execution",
		)
	}
	// The clean stack flag (ScriptVerifyCleanStack) is not allowed without either
	// the pay-to-script-hash (P2SH) evaluation (ScriptBip16) flag or the Segregated
	// Witness (ScriptVerifyWitness) flag. Recall that evaluating a P2SH script
	// without the flag set results in non-P2SH evaluation which leaves the P2SH
	// inputs on the stack. Thus, allowing the clean stack flag without the P2SH
	// flag would make it possible to have a situation where P2SH would not be a
	// soft fork when it should be. The same goes for segwit which will pull in
	// additional scripts for execution from the witness stack.
	vm := Engine{
		flags:       flags,
		sigCache:    sigCache,
		hashCache:   hashCache,
		inputAmount: inputAmount,
	}
	if vm.hasFlag(ScriptVerifyCleanStack) && (!vm.hasFlag(ScriptBip16) &&
		!vm.hasFlag(ScriptVerifyWitness)) {
		return nil, scriptError(
			ErrInvalidFlags,
			"invalid flags combination",
		)
	}
	// The signature script must only contain data pushes when the associated flag is set.
	if vm.hasFlag(ScriptVerifySigPushOnly) && !IsPushOnlyScript(scriptSig) {
		return nil, scriptError(
			ErrNotPushOnly,
			"signature script is not push only",
		)
	}
	// The engine stores the scripts in parsed form using a slice. This allows multiple scripts to be executed in
	// sequence. For example, with a pay-to-script-hash transaction, there will be ultimately be a third script to
	// execute.
	scripts := [][]byte{scriptSig, scriptPubKey}
	vm.scripts = make([][]parsedOpcode, len(scripts))
	for i, scr := range scripts {
		if len(scr) > MaxScriptSize {
			str := fmt.Sprintf(
				"script size %d is larger than max "+
					"allowed size %d", len(scr), MaxScriptSize,
			)
			return nil, scriptError(ErrScriptTooBig, str)
		}
		var e error
		vm.scripts[i], e = parseScript(scr)
		if e != nil {
			return nil, e
		}
	}
	// Advance the program counter to the public key script if the signature script is empty since there is nothing to
	// execute for it in that case.
	if len(scripts[0]) == 0 {
		vm.scriptIdx.Inc()
	}
	if vm.hasFlag(ScriptBip16) && isScriptHash(vm.scripts[1]) {
		// Only accept input scripts that push data for P2SH.
		if !isPushOnly(vm.scripts[0]) {
			return nil, scriptError(
				ErrNotPushOnly,
				"pay to script hash is not push only",
			)
		}
		vm.bip16 = true
	}
	if vm.hasFlag(ScriptVerifyMinimalData) {
		vm.dstack.verifyMinimalData = true
		vm.astack.verifyMinimalData = true
	}
	// // Chk to see if we should execute in witness verification mode according to
	// // the set flags. We check both the pkScript, and sigScript here since in the
	// // case of nested p2sh, the scriptSig will be a valid witness program. For
	// // nested p2sh, all the bytes after the first data push should *exactly* match
	// // the witness program template.
	// if vm.hasFlag(ScriptVerifyWitness) {
	// 	// If witness evaluation is enabled, then P2SH MUST also be active.
	// 	if !vm.hasFlag(ScriptBip16) {
	// 		errStr := "P2SH must be enabled to do witness verification"
	// 		return nil, scriptError(ErrInvalidFlags, errStr)
	// 	}
	// 	var witProgram []byte
	// 	switch {
	// 	case isWitnessProgram(vm.scripts[1]):
	// 		// The scriptSig must be *empty* for all native witness programs, otherwise we
	// 		// introduce malleability.
	// 		if len(scriptSig) != 0 {
	// 			errStr := "native witness program cannot also have a signature script"
	// 			return nil, scriptError(ErrWitnessMalleated, errStr)
	// 		}
	// 		witProgram = scriptPubKey
	// 	case len(tx.TxIn[txIdx].Witness) != 0 && vm.bip16:
	// 		// The sigScript MUST be *exactly* a single canonical data push of the witness
	// 		// program, otherwise we reintroduce malleability.
	// 		sigPops := vm.scripts[0]
	// 		if len(sigPops) == 1 && canonicalPush(sigPops[0]) &&
	// 			IsWitnessProgram(sigPops[0].data) {
	// 			witProgram = sigPops[0].data
	// 		} else {
	// 			errStr := "signature script for witness nested p2sh is not canonical"
	// 			return nil, scriptError(ErrWitnessMalleatedP2SH, errStr)
	// 		}
	// 	}
	// if witProgram != nil {
	// 	var e error
	// 	vm.witnessVersion, vm.witnessProgram, e = ExtractWitnessProgramI.Ln(witProgram)
	// 	if e != nil {
	// 		return nil, e
	// 	}
	// } else {
	// 	// If we didn't find a witness program in either the pkScript or as a datapush
	// 	// within the sigScript, then there MUST NOT be any witness data associated with
	// 	// the input being validated.
	// 	if vm.witnessProgram == nil && len(tx.TxIn[txIdx].Witness) != 0 {
	// 		errStr := "non-witness inputs cannot have a witness"
	// 		return nil, scriptError(ErrWitnessUnexpected, errStr)
	// 	}
	// }
	// }
	vm.tx = *tx
	vm.txIdx = txIdx
	return &vm, nil
}