forked from btcsuite/btcd
-
Notifications
You must be signed in to change notification settings - Fork 24
/
engine.go
1279 lines (1124 loc) · 42.8 KB
/
engine.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// 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"
"crypto/sha256"
"fmt"
"math/big"
"strings"
"github.com/lbryio/lbcd/btcec"
"github.com/lbryio/lbcd/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
)
const (
// 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 = 20005
// 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(btcec.S256().N, 1)
// Engine is the virtual machine that executes scripts.
type Engine struct {
// The following fields are set when the engine is created and must not be
// changed afterwards. The entries of the signature cache are mutated
// during execution, however, the cache pointer itself is not changed.
//
// flags specifies the additional flags which modify the execution behavior
// of the engine.
//
// tx identifies the transaction that contains the input which in turn
// contains the signature script being executed.
//
// txIdx identifies the input index within the transaction that contains
// the signature script being executed.
//
// version specifies the version of the public key script to execute. Since
// signature scripts redeem public keys scripts, this means the same version
// also extends to signature scripts and redeem scripts in the case of
// pay-to-script-hash.
//
// bip16 specifies that the public key script is of a special form that
// indicates it is a BIP16 pay-to-script-hash and therefore the
// execution must be treated as such.
//
// sigCache caches the results of signature verifications. This is useful
// since transaction scripts are often executed more than once from various
// contexts (e.g. new block templates, when transactions are first seen
// prior to being mined, part of full block verification, etc).
flags ScriptFlags
tx wire.MsgTx
txIdx int
version uint16
bip16 bool
sigCache *SigCache
hashCache *TxSigHashes
// The following fields handle keeping track of the current execution state
// of the engine.
//
// scripts houses the raw scripts that are executed by the engine. This
// includes the signature script as well as the public key script. It also
// includes the redeem script in the case of pay-to-script-hash.
//
// scriptIdx tracks the index into the scripts array for the current program
// counter.
//
// opcodeIdx tracks the number of the opcode within the current script for
// the current program counter. Note that it differs from the actual byte
// index into the script and is really only used for disassembly purposes.
//
// lastCodeSep specifies the position within the current script of the last
// OP_CODESEPARATOR.
//
// tokenizer provides the token stream of the current script being executed
// and doubles as state tracking for the program counter within the script.
//
// savedFirstStack keeps a copy of the stack from the first script when
// performing pay-to-script-hash execution.
//
// dstack is the primary data stack the various opcodes push and pop data
// to and from during execution.
//
// astack is the alternate data stack the various opcodes push and pop data
// to and from during execution.
//
// condStack tracks the conditional execution state with support for
// multiple nested conditional execution opcodes.
//
// numOps tracks the total number of non-push operations in a script and is
// primarily used to enforce maximum limits.
scripts [][]byte
scriptIdx int
opcodeIdx int
lastCodeSep int
tokenizer ScriptTokenizer
savedFirstStack [][]byte
dstack stack
astack stack
condStack []int
numOps int
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
}
// isOpcodeDisabled returns whether or not the opcode is disabled and thus is
// always bad to see in the instruction stream (even if turned off by a
// conditional).
func isOpcodeDisabled(opcode byte) bool {
switch opcode {
case OP_CAT:
return true
case OP_SUBSTR:
return true
case OP_LEFT:
return true
case OP_RIGHT:
return true
case OP_INVERT:
return true
case OP_AND:
return true
case OP_OR:
return true
case OP_XOR:
return true
case OP_2MUL:
return true
case OP_2DIV:
return true
case OP_MUL:
return true
case OP_DIV:
return true
case OP_MOD:
return true
case OP_LSHIFT:
return true
case OP_RSHIFT:
return true
default:
return false
}
}
// isOpcodeAlwaysIllegal returns whether or not the opcode is always illegal
// when passed over by the program counter even if in a non-executed branch (it
// isn't a coincidence that they are conditionals).
func isOpcodeAlwaysIllegal(opcode byte) bool {
switch opcode {
case OP_VERIF:
return true
case OP_VERNOTIF:
return true
default:
return false
}
}
// isOpcodeConditional returns whether or not the opcode is a conditional opcode
// which changes the conditional execution stack when executed.
func isOpcodeConditional(opcode byte) bool {
switch opcode {
case OP_IF:
return true
case OP_NOTIF:
return true
case OP_ELSE:
return true
case OP_ENDIF:
return true
default:
return false
}
}
// checkMinimalDataPush returns whether or not the provided opcode is the
// smallest possible way to represent the given data. For example, the value 15
// could be pushed with OP_DATA_1 15 (among other variations); however, OP_15 is
// a single opcode that represents the same value and is only a single byte
// versus two bytes.
func checkMinimalDataPush(op *opcode, data []byte) error {
opcodeVal := op.value
dataLen := len(data)
switch {
case dataLen == 0 && opcodeVal != OP_0:
str := fmt.Sprintf("zero length data push is encoded with opcode %s "+
"instead of OP_0", op.name)
return scriptError(ErrMinimalData, str)
case dataLen == 1 && data[0] >= 1 && data[0] <= 16:
if opcodeVal != OP_1+data[0]-1 {
// Should have used OP_1 .. OP_16
str := fmt.Sprintf("data push of the value %d encoded with opcode "+
"%s instead of OP_%d", data[0], op.name, data[0])
return scriptError(ErrMinimalData, str)
}
case dataLen == 1 && data[0] == 0x81:
if opcodeVal != OP_1NEGATE {
str := fmt.Sprintf("data push of the value -1 encoded with opcode "+
"%s instead of OP_1NEGATE", op.name)
return scriptError(ErrMinimalData, str)
}
case dataLen <= 75:
if int(opcodeVal) != dataLen {
// Should have used a direct push
str := fmt.Sprintf("data push of %d bytes encoded with opcode %s "+
"instead of OP_DATA_%d", dataLen, op.name, dataLen)
return scriptError(ErrMinimalData, str)
}
case dataLen <= 255:
if opcodeVal != OP_PUSHDATA1 {
str := fmt.Sprintf("data push of %d bytes encoded with opcode %s "+
"instead of OP_PUSHDATA1", dataLen, op.name)
return scriptError(ErrMinimalData, str)
}
case dataLen <= 65535:
if opcodeVal != OP_PUSHDATA2 {
str := fmt.Sprintf("data push of %d bytes encoded with opcode %s "+
"instead of OP_PUSHDATA2", dataLen, op.name)
return scriptError(ErrMinimalData, str)
}
}
return nil
}
// 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(op *opcode, data []byte) error {
// Disabled opcodes are fail on program counter.
if isOpcodeDisabled(op.value) {
str := fmt.Sprintf("attempt to execute disabled opcode %s", op.name)
return scriptError(ErrDisabledOpcode, str)
}
// Always-illegal opcodes are fail on program counter.
if isOpcodeAlwaysIllegal(op.value) {
str := fmt.Sprintf("attempt to execute reserved opcode %s", op.name)
return scriptError(ErrReservedOpcode, str)
}
// Note that this includes OP_RESERVED which counts as a push operation.
if op.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(data) > MaxScriptElementSize {
str := fmt.Sprintf("element size %d exceeds max allowed size %d",
len(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() && !isOpcodeConditional(op.value) {
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() &&
op.value >= 0 && op.value <= OP_PUSHDATA4 {
if err := checkMinimalDataPush(op, data); err != nil {
return err
}
}
return op.opfunc(op, data, vm)
}
// checkValidPC returns an error if the current script position is not valid for
// execution.
func (vm *Engine) checkValidPC() error {
if vm.scriptIdx >= len(vm.scripts) {
str := fmt.Sprintf("script index %d beyond total scripts %d",
vm.scriptIdx, len(vm.scripts))
return scriptError(ErrInvalidProgramCounter, str)
}
return 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) 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 {
err := fmt.Sprintf("should have exactly two "+
"items in witness, instead have %v", len(witness))
return scriptError(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
}
const scriptVersion = 0
err = checkScriptParses(vm.version, 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, pkScript)
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, assert that the
// script parses without failure.
const scriptVersion = 0
err := checkScriptParses(vm.version, 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, witnessScript)
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) {
if err := vm.checkValidPC(); err != nil {
return "", err
}
// Create a copy of the current tokenizer and parse the next opcode in the
// copy to avoid mutating the current one.
peekTokenizer := vm.tokenizer
if !peekTokenizer.Next() {
// Note that due to the fact that all scripts are checked for parse
// failures before this code ever runs, there should never be an error
// here, but check again to be safe in case a refactor breaks that
// assumption or new script versions are introduced with different
// semantics.
if err := peekTokenizer.Err(); err != nil {
return "", err
}
// Note that this should be impossible to hit in practice because the
// only way it could happen would be for the final opcode of a script to
// already be parsed without the script index having been updated, which
// is not the case since stepping the script always increments the
// script index when parsing and executing the final opcode of a script.
//
// However, check again to be safe in case a refactor breaks that
// assumption or new script versions are introduced with different
// semantics.
str := fmt.Sprintf("program counter beyond script index %d (bytes %x)",
vm.scriptIdx, vm.scripts[vm.scriptIdx])
return "", scriptError(ErrInvalidProgramCounter, str)
}
var buf strings.Builder
disasmOpcode(&buf, peekTokenizer.op, peekTokenizer.Data(), false)
return fmt.Sprintf("%02x:%04x: %s", vm.scriptIdx, vm.opcodeIdx,
buf.String()), 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. In the case of pay-to-script-hash, index 2 is the redeem script once
// the execution has progressed far enough to have successfully verified script
// hash and thus add the script to the scripts to execute.
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 disbuf strings.Builder
script := vm.scripts[idx]
tokenizer := MakeScriptTokenizer(vm.version, script)
var opcodeIdx int
for tokenizer.Next() {
disbuf.WriteString(fmt.Sprintf("%02x:%04x: ", idx, opcodeIdx))
disasmOpcode(&disbuf, tokenizer.op, tokenizer.Data(), false)
disbuf.WriteByte('\n')
opcodeIdx++
}
return disbuf.String(), tokenizer.Err()
}
// 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) error {
// Check execution is actually done by ensuring the script index is after
// the final script in the array script.
if vm.scriptIdx < 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")
}
// The final script must end with exactly one data stack item when the
// verify clean stack flag is set. Otherwise, there must be at least one
// data stack item in order to interpret it as a boolean.
if finalScript && vm.hasFlag(ScriptVerifyCleanStack) &&
vm.dstack.Depth() != 1 {
str := fmt.Sprintf("stack must contain exactly one item (contains %d)",
vm.dstack.Depth())
return scriptError(ErrCleanStack, str)
} else if vm.dstack.Depth() < 1 {
return scriptError(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", newLogClosure(func() string {
var buf strings.Builder
buf.WriteString("scripts failed:\n")
for i := range vm.scripts {
dis, _ := vm.DisasmScript(i)
buf.WriteString(fmt.Sprintf("script%d:\n", i))
buf.WriteString(dis)
}
return buf.String()
}))
return scriptError(ErrEvalFalse,
"false stack entry at end of script execution")
}
return nil
}
// Step executes the next instruction and moves 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 error) {
// Verify the engine is pointing to a valid program counter.
if err := vm.checkValidPC(); err != nil {
return true, err
}
// Attempt to parse the next opcode from the current script.
if !vm.tokenizer.Next() {
// Note that due to the fact that all scripts are checked for parse
// failures before this code ever runs, there should never be an error
// here, but check again to be safe in case a refactor breaks that
// assumption or new script versions are introduced with different
// semantics.
if err := vm.tokenizer.Err(); err != nil {
return false, err
}
str := fmt.Sprintf("attempt to step beyond script index %d (bytes %x)",
vm.scriptIdx, vm.scripts[vm.scriptIdx])
return true, scriptError(ErrInvalidProgramCounter, str)
}
// 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(vm.tokenizer.op, vm.tokenizer.Data())
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 > MaxStackSize {
str := fmt.Sprintf("combined stack size %d > max allowed %d",
combinedStackSize, MaxStackSize)
return false, scriptError(ErrStackOverflow, str)
}
// Prepare for next instruction.
vm.opcodeIdx++
if vm.tokenizer.Done() {
// Illegal to have a conditional that straddles two scripts.
if len(vm.condStack) != 0 {
return false, scriptError(ErrUnbalancedConditional,
"end of script reached in conditional execution")
}
// Alt stack doesn't persist between scripts.
_ = vm.astack.DropN(vm.astack.Depth())
// The number of operations is per script.
vm.numOps = 0
// Reset the opcode index for the next script.
vm.opcodeIdx = 0
// Advance to the next script as needed.
switch {
case vm.scriptIdx == 0 && vm.bip16:
vm.scriptIdx++
vm.savedFirstStack = vm.GetStack()
case vm.scriptIdx == 1 && vm.bip16:
// Put us past the end for CheckErrorCondition()
vm.scriptIdx++
// Check script ran successfully.
err := vm.CheckErrorCondition(false)
if err != nil {
return false, err
}
// Obtain the redeem script from the first stack and ensure it
// parses.
script := vm.savedFirstStack[len(vm.savedFirstStack)-1]
if err := checkScriptParses(vm.version, script); err != nil {
return false, err
}
vm.scripts = append(vm.scripts, script)
// Set stack to be the stack from first script minus the redeem
// script itself
vm.SetStack(vm.savedFirstStack[:len(vm.savedFirstStack)-1])
case vm.scriptIdx == 1 && vm.witnessProgram != nil,
vm.scriptIdx == 2 && vm.witnessProgram != nil && vm.bip16: // np2sh
vm.scriptIdx++
witness := vm.tx.TxIn[vm.txIdx].Witness
if err := vm.verifyWitnessProgram(witness); err != nil {
return false, err
}
default:
vm.scriptIdx++
}
// Skip empty scripts.
if vm.scriptIdx < len(vm.scripts) && len(vm.scripts[vm.scriptIdx]) == 0 {
vm.scriptIdx++
}
vm.lastCodeSep = 0
if vm.scriptIdx >= len(vm.scripts) {
return true, nil
}
// Finally, update the current tokenizer used to parse through scripts
// one opcode at a time to start from the beginning of the new script
// associated with the program counter.
vm.tokenizer = MakeScriptTokenizer(vm.version, vm.scripts[vm.scriptIdx])
}
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 error) {
// All script versions other than 0 currently execute without issue,
// making all outputs to them anyone can pay. In the future this
// will allow for the addition of new scripting languages.
if vm.version != 0 {
return nil
}
done := false
for !done {
log.Tracef("%v", newLogClosure(func() string {
dis, err := vm.DisasmPC()
if err != nil {
return fmt.Sprintf("stepping - failed to disasm pc: %v", err)
}
return fmt.Sprintf("stepping %v", dis)
}))
done, err = vm.Step()
if err != nil {
return err
}
log.Tracef("%v", newLogClosure(func() string {
var dstr, astr string
// Log the non-empty stacks when tracing.
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() []byte {
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 SigHashType) 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
}
// isStrictPubKeyEncoding returns whether or not the passed public key adheres
// to the strict encoding requirements.
func isStrictPubKeyEncoding(pubKey []byte) bool {
if len(pubKey) == 33 && (pubKey[0] == 0x02 || pubKey[0] == 0x03) {
// Compressed
return true
}
if len(pubKey) == 65 {
switch pubKey[0] {
case 0x04:
// Uncompressed
return true
case 0x06, 0x07:
// Hybrid
return true
}
}
return false
}
// checkPubKeyEncoding returns whether or not the passed public key adheres to
// the strict encoding requirements if enabled.
func (vm *Engine) checkPubKeyEncoding(pubKey []byte) error {
if vm.hasFlag(ScriptVerifyWitnessPubKeyType) &&
vm.isWitnessVersionActive(0) && !btcec.IsCompressedPubKey(pubKey) {
str := "only compressed 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) 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)
}