forked from martinboehm/btcd
/
engine.go
1004 lines (873 loc) · 33.6 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"
"github.com/syscoin/btcd/btcec"
"github.com/syscoin/btcd/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 = 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(btcec.S256().N, 1)
// Engine is the virtual machine that executes scripts.
type Engine struct {
scripts [][]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 *parsedOpcode) 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 err := pop.checkMinimalDataPush(); err != nil {
return err
}
}
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 {
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() error {
if vm.scriptIdx >= len(vm.scripts) {
str := fmt.Sprintf("past input scripts %v:%v %v:xxxx",
vm.scriptIdx, vm.scriptOff, len(vm.scripts))
return scriptError(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 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, err error) {
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) 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
}
pops, err := 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 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, err := 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",
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, 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, 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) error {
// 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 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, err := vm.dstack.PopBool()
if err != nil {
return err
}
if !v {
// Log interesting data.
log.Tracef("%v", newLogClosure(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, err error) {
// 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 > MaxStackSize {
str := fmt.Sprintf("combined stack size %d > max allowed %d",
combinedStackSize, MaxStackSize)
return false, scriptError(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, scriptError(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(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 error) {
done := false
for !done {
log.Tracef("%v", newLogClosure(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", newLogClosure(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() []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 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
}
// 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 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) 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 err error
vm.scripts[i], err = 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 !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
}
// 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, 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 err error
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, scriptError(ErrWitnessUnexpected, errStr)
}
}
}
vm.tx = *tx