123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985 |
- // Copyright (c) 2013-2018 The btcsuite developers
- // Copyright (c) 2015-2018 The Decred developers
- // Use of this source code is governed by an ISC
- // license that can be found in the LICENSE file.
- package txscript
- import (
- "bytes"
- "fmt"
- "math/big"
- sha256 "github.com/minio/sha256-simd"
- "github.com/pkt-cash/pktd/btcutil/er"
- "github.com/pkt-cash/pktd/pktlog/log"
- "github.com/pkt-cash/pktd/txscript/opcode"
- "github.com/pkt-cash/pktd/txscript/params"
- "github.com/pkt-cash/pktd/txscript/parsescript"
- "github.com/pkt-cash/pktd/txscript/txscripterr"
- "github.com/pkt-cash/pktd/btcec"
- "github.com/pkt-cash/pktd/wire"
- )
- // 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
- )
- // halforder is used to tame ECDSA malleability (see BIP0062).
- var halfOrder = new(big.Int).Rsh(btcec.S256().N, 1)
- // Engine is the virtual machine that executes scripts.
- type Engine struct {
- scripts [][]parsescript.ParsedOpcode
- scriptIdx int
- scriptOff int
- 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 *parsescript.ParsedOpcode) er.R {
- // Disabled opcodes are fail on program counter.
- if popIsDisabled(pop) {
- str := fmt.Sprintf("attempt to execute disabled opcode %s",
- opcode.OpcodeName(pop.Opcode.Value))
- return txscripterr.ScriptError(txscripterr.ErrDisabledOpcode, str)
- }
- // Always-illegal opcodes are fail on program counter.
- if popAlwaysIllegal(pop) {
- str := fmt.Sprintf("attempt to execute reserved opcode %s",
- opcode.OpcodeName(pop.Opcode.Value))
- return txscripterr.ScriptError(txscripterr.ErrReservedOpcode, str)
- }
- // Note that this includes OP_RESERVED which counts as a push operation.
- if pop.Opcode.Value > opcode.OP_16 {
- vm.numOps++
- if vm.numOps > params.MaxOpsPerScript {
- str := fmt.Sprintf("exceeded max operation limit of %d",
- params.MaxOpsPerScript)
- return txscripterr.ScriptError(txscripterr.ErrTooManyOperations, str)
- }
- } else if len(pop.Data) > params.MaxScriptElementSize {
- str := fmt.Sprintf("element size %d exceeds max allowed size %d",
- len(pop.Data), params.MaxScriptElementSize)
- return txscripterr.ScriptError(txscripterr.ErrElementTooBig, str)
- }
- // Nothing left to do when this is not a conditional opcode and it is
- // not in an executing branch.
- if !vm.isBranchExecuting() && !popIsConditional(pop) {
- 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 <= opcode.OP_PUSHDATA4 {
- if err := popCheckMinimalDataPush(pop); err != nil {
- return err
- }
- }
- return executeOp(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, scriptOff int) string {
- return fmt.Sprintf("%02x:%04x: %s", scriptIdx, scriptOff,
- popPrint(&vm.scripts[scriptIdx][scriptOff], false))
- }
- // validPC returns an error if the current script position is valid for
- // execution, nil otherwise.
- func (vm *Engine) validPC() er.R {
- if vm.scriptIdx >= len(vm.scripts) {
- str := fmt.Sprintf("past input scripts %v:%v %v:xxxx",
- vm.scriptIdx, vm.scriptOff, len(vm.scripts))
- return txscripterr.ScriptError(txscripterr.ErrInvalidProgramCounter, str)
- }
- if vm.scriptOff >= len(vm.scripts[vm.scriptIdx]) {
- str := fmt.Sprintf("past input scripts %v:%v %v:%04d",
- vm.scriptIdx, vm.scriptOff, vm.scriptIdx,
- len(vm.scripts[vm.scriptIdx]))
- return txscripterr.ScriptError(txscripterr.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, off int, err er.R) {
- err = vm.validPC()
- if err != nil {
- return 0, 0, err
- }
- return vm.scriptIdx, vm.scriptOff, 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) er.R {
- if vm.isWitnessVersionActive(0) {
- switch len(vm.witnessProgram) {
- case params.PayToWitnessPubKeyHashDataSize: // P2WKH
- // The witness stack should consist of exactly two
- // items: the signature, and the pubkey.
- if len(witness) != 2 {
- err := fmt.Sprintf("should have exactly two "+
- "items in witness, instead have %v", len(witness))
- return txscripterr.ScriptError(txscripterr.ErrWitnessProgramMismatch, err)
- }
- // Now we'll resume execution as if it were a regular
- // p2pkh transaction.
- pkScript, err := payToPubKeyHashScript(vm.witnessProgram)
- if err != nil {
- return err
- }
- pops, err := parsescript.ParseScript(pkScript)
- if err != nil {
- return err
- }
- // 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 params.PayToWitnessScriptHashDataSize: // P2WSH
- // Additionally, The witness stack MUST NOT be empty at
- // this point.
- if len(witness) == 0 {
- return txscripterr.ScriptError(txscripterr.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) > params.MaxScriptSize {
- str := fmt.Sprintf("witnessScript size %d "+
- "is larger than max allowed size %d",
- len(witnessScript), params.MaxScriptSize)
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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, err := parsescript.ParseScript(witnessScript)
- if err != nil {
- return err
- }
- // 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",
- params.PayToWitnessPubKeyHashDataSize,
- params.PayToWitnessScriptHashDataSize,
- len(vm.witnessProgram))
- return txscripterr.ScriptError(txscripterr.ErrWitnessProgramWrongLength, errStr)
- }
- } else if vm.hasFlag(ScriptVerifyDiscourageUpgradeableWitnessProgram) {
- errStr := fmt.Sprintf("new witness program versions "+
- "invalid: %v", vm.witnessProgram)
- return txscripterr.ScriptError(txscripterr.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) > params.MaxScriptElementSize {
- str := fmt.Sprintf("element size %d exceeds "+
- "max allowed size %d", len(witElement),
- params.MaxScriptElementSize)
- return txscripterr.ScriptError(txscripterr.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, er.R) {
- scriptIdx, scriptOff, err := vm.curPC()
- if err != nil {
- return "", err
- }
- 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, er.R) {
- if idx >= len(vm.scripts) {
- str := fmt.Sprintf("script index %d >= total scripts %d", idx,
- len(vm.scripts))
- return "", txscripterr.ScriptError(txscripterr.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) er.R {
- // Check execution is actually done. When pc is past the end of script
- // array there are no more scripts to run.
- if vm.scriptIdx < len(vm.scripts) {
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.ErrCleanStack, str)
- } else if vm.dstack.Depth() < 1 {
- return txscripterr.ScriptError(txscripterr.ErrEmptyStack,
- "stack empty at end of script execution")
- }
- v, err := vm.dstack.PopBool()
- if err != nil {
- return err
- }
- if !v {
- // Log interesting data.
- log.Tracef("%v", log.C(func() string {
- dis0, _ := vm.DisasmScript(0)
- dis1, _ := vm.DisasmScript(1)
- return fmt.Sprintf("scripts failed: script0: %s\n"+
- "script1: %s", dis0, dis1)
- }))
- return txscripterr.ScriptError(txscripterr.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, err er.R) {
- // Verify that it is pointing to a valid script address.
- err = vm.validPC()
- if err != nil {
- return true, err
- }
- opcode := &vm.scripts[vm.scriptIdx][vm.scriptOff]
- vm.scriptOff++
- // Execute the opcode while taking into account several things such as
- // disabled opcodes, illegal opcodes, maximum allowed operations per
- // script, maximum script element sizes, and conditionals.
- err = vm.executeOpcode(opcode)
- if err != nil {
- return true, err
- }
- // 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 > params.MaxStackSize {
- str := fmt.Sprintf("combined stack size %d > max allowed %d",
- combinedStackSize, params.MaxStackSize)
- return false, txscripterr.ScriptError(txscripterr.ErrStackOverflow, str)
- }
- // Prepare for next instruction.
- if vm.scriptOff >= len(vm.scripts[vm.scriptIdx]) {
- // Illegal to have an `if' that straddles two scripts.
- if err == nil && len(vm.condStack) != 0 {
- return false, txscripterr.ScriptError(txscripterr.ErrUnbalancedConditional,
- "end of script reached in conditional execution")
- }
- // Alt stack doesn't persist.
- _ = vm.astack.DropN(vm.astack.Depth())
- vm.numOps = 0 // number of ops is per script.
- vm.scriptOff = 0
- if vm.scriptIdx == 0 && vm.bip16 {
- vm.scriptIdx++
- vm.savedFirstStack = vm.GetStack()
- } else if vm.scriptIdx == 1 && vm.bip16 {
- // Put us past the end for CheckErrorCondition()
- vm.scriptIdx++
- // Check script ran successfully and pull the script
- // out of the first stack and execute that.
- err := vm.CheckErrorCondition(false)
- if err != nil {
- return false, err
- }
- script := vm.savedFirstStack[len(vm.savedFirstStack)-1]
- pops, err := parsescript.ParseScript(script)
- if err != nil {
- return false, err
- }
- 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 == 1 && vm.witnessProgram != nil) ||
- (vm.scriptIdx == 2 && vm.witnessProgram != nil && vm.bip16) { // Nested P2SH.
- vm.scriptIdx++
- witness := vm.tx.TxIn[vm.txIdx].Witness
- if err := vm.verifyWitnessProgram(witness); err != nil {
- return false, err
- }
- } else {
- vm.scriptIdx++
- }
- // there are zero length scripts in the wild
- if vm.scriptIdx < len(vm.scripts) && vm.scriptOff >= len(vm.scripts[vm.scriptIdx]) {
- vm.scriptIdx++
- }
- vm.lastCodeSep = 0
- if vm.scriptIdx >= len(vm.scripts) {
- return true, nil
- }
- }
- return false, nil
- }
- // 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() (err er.R) {
- done := false
- for !done {
- log.Tracef("%v", log.C(func() string {
- dis, err := vm.DisasmPC()
- if err != nil {
- return fmt.Sprintf("stepping (%v)", err)
- }
- return fmt.Sprintf("stepping %v", dis)
- }))
- done, err = vm.Step()
- if err != nil {
- return err
- }
- log.Tracef("%v", log.C(func() string {
- var dstr, astr string
- // if we're tracing, dump the stacks.
- if vm.dstack.Depth() != 0 {
- dstr = "Stack:\n" + vm.dstack.String()
- }
- if vm.astack.Depth() != 0 {
- astr = "AltStack:\n" + vm.astack.String()
- }
- return dstr + astr
- }))
- }
- return vm.CheckErrorCondition(true)
- }
- // subScript returns the script since the last OP_CODESEPARATOR.
- func (vm *Engine) subScript() []parsescript.ParsedOpcode {
- return vm.scripts[vm.scriptIdx][vm.lastCodeSep:]
- }
- // checkHashTypeEncoding returns whether or not the passed hashtype adheres to
- // the strict encoding requirements if enabled.
- func (vm *Engine) checkHashTypeEncoding(hashType params.SigHashType) er.R {
- if !vm.hasFlag(ScriptVerifyStrictEncoding) {
- return nil
- }
- sigHashType := hashType & ^params.SigHashAnyOneCanPay
- if sigHashType < params.SigHashAll || sigHashType > params.SigHashSingle {
- str := fmt.Sprintf("invalid hash type 0x%x", hashType)
- return txscripterr.ScriptError(txscripterr.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) er.R {
- if vm.hasFlag(ScriptVerifyWitnessPubKeyType) &&
- vm.isWitnessVersionActive(0) && !btcec.IsCompressedPubKey(pubKey) {
- str := "only uncompressed keys are accepted post-segwit"
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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) er.R {
- 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 txscripterr.ScriptError(txscripterr.ErrSigTooShort, str)
- }
- if sigLen > maxSigLen {
- str := fmt.Sprintf("malformed signature: too long: %d > %d", sigLen,
- maxSigLen)
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.ErrSigMissingSTypeID, str)
- }
- if sLenOffset >= sigLen {
- str := "malformed signature: S length missing"
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.ErrSigInvalidRIntID, str)
- }
- // Zero-length integers are not allowed for R.
- if rLen == 0 {
- str := "malformed signature: R length is zero"
- return txscripterr.ScriptError(txscripterr.ErrSigZeroRLen, str)
- }
- // R must not be negative.
- if sig[rOffset]&0x80 != 0 {
- str := "malformed signature: R is negative"
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.ErrSigInvalidSIntID, str)
- }
- // Zero-length integers are not allowed for S.
- if sLen == 0 {
- str := "malformed signature: S length is zero"
- return txscripterr.ScriptError(txscripterr.ErrSigZeroSLen, str)
- }
- // S must not be negative.
- if sig[sOffset]&0x80 != 0 {
- str := "malformed signature: S is negative"
- return txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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 txscripterr.ScriptError(txscripterr.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)
- }
- // 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, er.R) {
- // 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, txscripterr.ScriptError(txscripterr.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, txscripterr.ScriptError(txscripterr.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, txscripterr.ScriptError(txscripterr.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, txscripterr.ScriptError(txscripterr.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([][]parsescript.ParsedOpcode, len(scripts))
- for i, scr := range scripts {
- if len(scr) > params.MaxScriptSize {
- str := fmt.Sprintf("script size %d is larger than max "+
- "allowed size %d", len(scr), params.MaxScriptSize)
- return nil, txscripterr.ScriptError(txscripterr.ErrScriptTooBig, str)
- }
- var err er.R
- vm.scripts[i], err = parsescript.ParseScript(scr)
- if err != nil {
- return nil, err
- }
- }
- // 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++
- }
- if vm.hasFlag(ScriptBip16) && isScriptHash(vm.scripts[1]) {
- // Only accept input scripts that push data for P2SH.
- if !parsescript.IsPushOnly(vm.scripts[0]) {
- return nil, txscripterr.ScriptError(txscripterr.ErrNotPushOnly,
- "pay to script hash is not push only")
- }
- vm.bip16 = true
- }
- if vm.hasFlag(ScriptVerifyMinimalData) {
- vm.dstack.verifyMinimalData = true
- vm.astack.verifyMinimalData = true
- }
- // Check 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, txscripterr.ScriptError(txscripterr.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, txscripterr.ScriptError(txscripterr.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, txscripterr.ScriptError(txscripterr.ErrWitnessMalleatedP2SH, errStr)
- }
- }
- if witProgram != nil {
- var err er.R
- vm.witnessVersion, vm.witnessProgram, err = ExtractWitnessProgramInfo(witProgram)
- if err != nil {
- return nil, err
- }
- } 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, txscripterr.ScriptError(txscripterr.ErrWitnessUnexpected, errStr)
- }
- }
- }
- vm.tx = *tx
- vm.txIdx = txIdx
- return &vm, nil
- }
|