OSDN Git Service

b736cf6489656f8149a3a38f9a61f5cc5d819f84
[bytom/vapor.git] / protocol / validation / tx.go
1 package validation
2
3 import (
4         "fmt"
5         "math"
6
7         "github.com/vapor/config"
8         "github.com/vapor/consensus"
9         "github.com/vapor/consensus/segwit"
10         "github.com/vapor/errors"
11         "github.com/vapor/math/checked"
12         "github.com/vapor/protocol/bc"
13         "github.com/vapor/protocol/vm"
14 )
15
16 const ruleAA = 142500
17
18 // validate transaction error
19 var (
20         ErrTxVersion                 = errors.New("invalid transaction version")
21         ErrWrongTransactionSize      = errors.New("invalid transaction size")
22         ErrBadTimeRange              = errors.New("invalid transaction time range")
23         ErrEmptyInputIDs             = errors.New("got the empty InputIDs")
24         ErrNotStandardTx             = errors.New("not standard transaction")
25         ErrWrongCoinbaseTransaction  = errors.New("wrong coinbase transaction")
26         ErrWrongCoinbaseAsset        = errors.New("wrong coinbase assetID")
27         ErrCoinbaseArbitraryOversize = errors.New("coinbase arbitrary size is larger than limit")
28         ErrEmptyResults              = errors.New("transaction has no results")
29         ErrMismatchedAssetID         = errors.New("mismatched assetID")
30         ErrMismatchedPosition        = errors.New("mismatched value source/dest position")
31         ErrMismatchedReference       = errors.New("mismatched reference")
32         ErrMismatchedValue           = errors.New("mismatched value")
33         ErrMissingField              = errors.New("missing required field")
34         ErrNoSource                  = errors.New("no source for value")
35         ErrOverflow                  = errors.New("arithmetic overflow/underflow")
36         ErrPosition                  = errors.New("invalid source or destination position")
37         ErrUnbalanced                = errors.New("unbalanced asset amount between input and output")
38         ErrOverGasCredit             = errors.New("all gas credit has been spend")
39         ErrGasCalculate              = errors.New("gas usage calculate got a math error")
40         ErrVotePubKey                = errors.New("invalid public key of vote")
41         ErrVoteOutputAmount          = errors.New("invalid vote amount")
42 )
43
44 // GasState record the gas usage status
45 type GasState struct {
46         BTMValue   uint64
47         GasLeft    int64
48         GasUsed    int64
49         GasValid   bool
50         StorageGas int64
51 }
52
53 func (g *GasState) setGas(BTMValue int64, txSize int64) error {
54         if BTMValue < 0 {
55                 return errors.Wrap(ErrGasCalculate, "input BTM is negative")
56         }
57
58         g.BTMValue = uint64(BTMValue)
59
60         var ok bool
61         if g.GasLeft, ok = checked.DivInt64(BTMValue, consensus.VMGasRate); !ok {
62                 return errors.Wrap(ErrGasCalculate, "setGas calc gas amount")
63         }
64
65         if g.GasLeft > consensus.MaxGasAmount {
66                 g.GasLeft = consensus.MaxGasAmount
67         }
68
69         if g.StorageGas, ok = checked.MulInt64(txSize, consensus.StorageGasRate); !ok {
70                 return errors.Wrap(ErrGasCalculate, "setGas calc tx storage gas")
71         }
72         return nil
73 }
74
75 func (g *GasState) setGasValid() error {
76         var ok bool
77         if g.GasLeft, ok = checked.SubInt64(g.GasLeft, g.StorageGas); !ok || g.GasLeft < 0 {
78                 return errors.Wrap(ErrGasCalculate, "setGasValid calc gasLeft")
79         }
80
81         if g.GasUsed, ok = checked.AddInt64(g.GasUsed, g.StorageGas); !ok {
82                 return errors.Wrap(ErrGasCalculate, "setGasValid calc gasUsed")
83         }
84
85         g.GasValid = true
86         return nil
87 }
88
89 func (g *GasState) updateUsage(gasLeft int64) error {
90         if gasLeft < 0 {
91                 return errors.Wrap(ErrGasCalculate, "updateUsage input negative gas")
92         }
93
94         if gasUsed, ok := checked.SubInt64(g.GasLeft, gasLeft); ok {
95                 g.GasUsed += gasUsed
96                 g.GasLeft = gasLeft
97         } else {
98                 return errors.Wrap(ErrGasCalculate, "updateUsage calc gas diff")
99         }
100
101         if !g.GasValid && (g.GasUsed > consensus.DefaultGasCredit || g.StorageGas > g.GasLeft) {
102                 return ErrOverGasCredit
103         }
104         return nil
105 }
106
107 // validationState contains the context that must propagate through
108 // the transaction graph when validating entries.
109 type validationState struct {
110         block     *bc.Block
111         tx        *bc.Tx
112         gasStatus *GasState
113         entryID   bc.Hash           // The ID of the nearest enclosing entry
114         sourcePos uint64            // The source position, for validate ValueSources
115         destPos   uint64            // The destination position, for validate ValueDestinations
116         cache     map[bc.Hash]error // Memoized per-entry validation results
117 }
118
119 func checkValid(vs *validationState, e bc.Entry) (err error) {
120         var ok bool
121         entryID := bc.EntryID(e)
122         if err, ok = vs.cache[entryID]; ok {
123                 return err
124         }
125
126         defer func() {
127                 vs.cache[entryID] = err
128         }()
129
130         switch e := e.(type) {
131         case *bc.TxHeader:
132                 for i, resID := range e.ResultIds {
133                         resultEntry := vs.tx.Entries[*resID]
134                         vs2 := *vs
135                         vs2.entryID = *resID
136                         if err = checkValid(&vs2, resultEntry); err != nil {
137                                 return errors.Wrapf(err, "checking result %d", i)
138                         }
139                 }
140
141                 if e.Version == 1 && len(e.ResultIds) == 0 {
142                         return ErrEmptyResults
143                 }
144
145         case *bc.Mux:
146                 parity := make(map[bc.AssetID]int64)
147                 for i, src := range e.Sources {
148                         if src.Value.Amount > math.MaxInt64 {
149                                 return errors.WithDetailf(ErrOverflow, "amount %d exceeds maximum value 2^63", src.Value.Amount)
150                         }
151                         sum, ok := checked.AddInt64(parity[*src.Value.AssetId], int64(src.Value.Amount))
152                         if !ok {
153                                 return errors.WithDetailf(ErrOverflow, "adding %d units of asset %x from mux source %d to total %d overflows int64", src.Value.Amount, src.Value.AssetId.Bytes(), i, parity[*src.Value.AssetId])
154                         }
155                         parity[*src.Value.AssetId] = sum
156                 }
157
158                 for i, dest := range e.WitnessDestinations {
159                         sum, ok := parity[*dest.Value.AssetId]
160                         if !ok {
161                                 return errors.WithDetailf(ErrNoSource, "mux destination %d, asset %x, has no corresponding source", i, dest.Value.AssetId.Bytes())
162                         }
163                         if dest.Value.Amount > math.MaxInt64 {
164                                 return errors.WithDetailf(ErrOverflow, "amount %d exceeds maximum value 2^63", dest.Value.Amount)
165                         }
166                         diff, ok := checked.SubInt64(sum, int64(dest.Value.Amount))
167                         if !ok {
168                                 return errors.WithDetailf(ErrOverflow, "subtracting %d units of asset %x from mux destination %d from total %d underflows int64", dest.Value.Amount, dest.Value.AssetId.Bytes(), i, sum)
169                         }
170                         parity[*dest.Value.AssetId] = diff
171                 }
172
173                 for assetID, amount := range parity {
174                         if assetID == *consensus.BTMAssetID {
175                                 if err = vs.gasStatus.setGas(amount, int64(vs.tx.SerializedSize)); err != nil {
176                                         return err
177                                 }
178                         } else if amount != 0 {
179                                 return errors.WithDetailf(ErrUnbalanced, "asset %x sources - destinations = %d (should be 0)", assetID.Bytes(), amount)
180                         }
181                 }
182
183                 for _, BTMInputID := range vs.tx.GasInputIDs {
184                         e, ok := vs.tx.Entries[BTMInputID]
185                         if !ok {
186                                 return errors.Wrapf(bc.ErrMissingEntry, "entry for bytom input %x not found", BTMInputID)
187                         }
188
189                         vs2 := *vs
190                         vs2.entryID = BTMInputID
191                         if err := checkValid(&vs2, e); err != nil {
192                                 return errors.Wrap(err, "checking gas input")
193                         }
194                 }
195
196                 for i, dest := range e.WitnessDestinations {
197                         vs2 := *vs
198                         vs2.destPos = uint64(i)
199                         if err = checkValidDest(&vs2, dest); err != nil {
200                                 return errors.Wrapf(err, "checking mux destination %d", i)
201                         }
202                 }
203
204                 if err := vs.gasStatus.setGasValid(); err != nil {
205                         return err
206                 }
207
208                 for i, src := range e.Sources {
209                         vs2 := *vs
210                         vs2.sourcePos = uint64(i)
211                         if err = checkValidSrc(&vs2, src); err != nil {
212                                 return errors.Wrapf(err, "checking mux source %d", i)
213                         }
214                 }
215
216         case *bc.IntraChainOutput:
217                 vs2 := *vs
218                 vs2.sourcePos = 0
219                 if err = checkValidSrc(&vs2, e.Source); err != nil {
220                         return errors.Wrap(err, "checking output source")
221                 }
222
223         case *bc.CrossChainOutput:
224                 vs2 := *vs
225                 vs2.sourcePos = 0
226                 if err = checkValidSrc(&vs2, e.Source); err != nil {
227                         return errors.Wrap(err, "checking output source")
228                 }
229
230         case *bc.VoteOutput:
231                 if len(e.Vote) != 64 {
232                         return ErrVotePubKey
233                 }
234                 vs2 := *vs
235                 vs2.sourcePos = 0
236                 if err = checkValidSrc(&vs2, e.Source); err != nil {
237                         return errors.Wrap(err, "checking vote output source")
238                 }
239                 if e.Source.Value.Amount < consensus.MinVoteOutputAmount {
240                         return ErrVoteOutputAmount
241                 }
242
243         case *bc.Retirement:
244                 vs2 := *vs
245                 vs2.sourcePos = 0
246                 if err = checkValidSrc(&vs2, e.Source); err != nil {
247                         return errors.Wrap(err, "checking retirement source")
248                 }
249
250         case *bc.CrossChainInput:
251                 // check assetID
252                 assetID := e.AssetDefinition.ComputeAssetID()
253                 if *e.Value.AssetId != *consensus.BTMAssetID && *e.Value.AssetId != assetID {
254                         return errors.New("incorrect asset_id while checking CrossChainInput")
255                 }
256
257                 code := config.FederationProgrom(config.CommonConfig)
258                 prog := &bc.Program{
259                         VmVersion: e.ControlProgram.VmVersion,
260                         Code:      code,
261                 }
262                 _, err := vm.Verify(NewTxVMContext(vs, e, prog, e.WitnessArguments), consensus.DefaultGasCredit)
263                 if err != nil {
264                         return errors.Wrap(err, "checking cross-chain input control program")
265                 }
266
267                 vs2 := *vs
268                 vs2.destPos = 0
269                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
270                         return errors.Wrap(err, "checking cross-chain input destination")
271                 }
272                 vs.gasStatus.StorageGas = 0
273
274         case *bc.Spend:
275                 if e.SpentOutputId == nil {
276                         return errors.Wrap(ErrMissingField, "spend without spent output ID")
277                 }
278
279                 spentOutput, err := vs.tx.IntraChainOutput(*e.SpentOutputId)
280                 if err != nil {
281                         return errors.Wrap(err, "getting spend prevout")
282                 }
283
284                 gasLeft, err := vm.Verify(NewTxVMContext(vs, e, spentOutput.ControlProgram, e.WitnessArguments), vs.gasStatus.GasLeft)
285                 if err != nil {
286                         return errors.Wrap(err, "checking control program")
287                 }
288                 if err = vs.gasStatus.updateUsage(gasLeft); err != nil {
289                         return err
290                 }
291
292                 eq, err := spentOutput.Source.Value.Equal(e.WitnessDestination.Value)
293                 if err != nil {
294                         return err
295                 }
296                 if !eq {
297                         return errors.WithDetailf(
298                                 ErrMismatchedValue,
299                                 "previous output is for %d unit(s) of %x, spend wants %d unit(s) of %x",
300                                 spentOutput.Source.Value.Amount,
301                                 spentOutput.Source.Value.AssetId.Bytes(),
302                                 e.WitnessDestination.Value.Amount,
303                                 e.WitnessDestination.Value.AssetId.Bytes(),
304                         )
305                 }
306                 vs2 := *vs
307                 vs2.destPos = 0
308                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
309                         return errors.Wrap(err, "checking spend destination")
310                 }
311
312         case *bc.VetoInput:
313                 if e.SpentOutputId == nil {
314                         return errors.Wrap(ErrMissingField, "vetoInput without vetoInput output ID")
315                 }
316
317                 voteOutput, err := vs.tx.VoteOutput(*e.SpentOutputId)
318                 if err != nil {
319                         return errors.Wrap(err, "getting vetoInput prevout")
320                 }
321                 if len(voteOutput.Vote) != 64 {
322                         return ErrVotePubKey
323                 }
324
325                 gasLeft, err := vm.Verify(NewTxVMContext(vs, e, voteOutput.ControlProgram, e.WitnessArguments), vs.gasStatus.GasLeft)
326                 if err != nil {
327                         return errors.Wrap(err, "checking control program")
328                 }
329                 if err = vs.gasStatus.updateUsage(gasLeft); err != nil {
330                         return err
331                 }
332
333                 eq, err := voteOutput.Source.Value.Equal(e.WitnessDestination.Value)
334                 if err != nil {
335                         return err
336                 }
337                 if !eq {
338                         return errors.WithDetailf(
339                                 ErrMismatchedValue,
340                                 "previous output is for %d unit(s) of %x, vetoInput wants %d unit(s) of %x",
341                                 voteOutput.Source.Value.Amount,
342                                 voteOutput.Source.Value.AssetId.Bytes(),
343                                 e.WitnessDestination.Value.Amount,
344                                 e.WitnessDestination.Value.AssetId.Bytes(),
345                         )
346                 }
347                 vs2 := *vs
348                 vs2.destPos = 0
349                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
350                         return errors.Wrap(err, "checking vetoInput destination")
351                 }
352
353         case *bc.Coinbase:
354                 if vs.block == nil || len(vs.block.Transactions) == 0 || vs.block.Transactions[0] != vs.tx {
355                         return ErrWrongCoinbaseTransaction
356                 }
357
358                 if *e.WitnessDestination.Value.AssetId != *consensus.BTMAssetID {
359                         return ErrWrongCoinbaseAsset
360                 }
361
362                 if e.Arbitrary != nil && len(e.Arbitrary) > consensus.CoinbaseArbitrarySizeLimit {
363                         return ErrCoinbaseArbitraryOversize
364                 }
365
366                 vs2 := *vs
367                 vs2.destPos = 0
368                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
369                         return errors.Wrap(err, "checking coinbase destination")
370                 }
371                 vs.gasStatus.StorageGas = 0
372
373         default:
374                 return fmt.Errorf("entry has unexpected type %T", e)
375         }
376
377         return nil
378 }
379
380 func checkValidSrc(vstate *validationState, vs *bc.ValueSource) error {
381         if vs == nil {
382                 return errors.Wrap(ErrMissingField, "empty value source")
383         }
384         if vs.Ref == nil {
385                 return errors.Wrap(ErrMissingField, "missing ref on value source")
386         }
387         if vs.Value == nil || vs.Value.AssetId == nil {
388                 return errors.Wrap(ErrMissingField, "missing value on value source")
389         }
390
391         e, ok := vstate.tx.Entries[*vs.Ref]
392         if !ok {
393                 return errors.Wrapf(bc.ErrMissingEntry, "entry for value source %x not found", vs.Ref.Bytes())
394         }
395
396         vstate2 := *vstate
397         vstate2.entryID = *vs.Ref
398         if err := checkValid(&vstate2, e); err != nil {
399                 return errors.Wrap(err, "checking value source")
400         }
401
402         var dest *bc.ValueDestination
403         switch ref := e.(type) {
404         case *bc.VetoInput:
405                 if vs.Position != 0 {
406                         return errors.Wrapf(ErrPosition, "invalid position %d for veto-input source", vs.Position)
407                 }
408                 dest = ref.WitnessDestination
409
410         case *bc.Coinbase:
411                 if vs.Position != 0 {
412                         return errors.Wrapf(ErrPosition, "invalid position %d for coinbase source", vs.Position)
413                 }
414                 dest = ref.WitnessDestination
415
416         case *bc.CrossChainInput:
417                 if vs.Position != 0 {
418                         return errors.Wrapf(ErrPosition, "invalid position %d for cross-chain input source", vs.Position)
419                 }
420                 dest = ref.WitnessDestination
421
422         case *bc.Spend:
423                 if vs.Position != 0 {
424                         return errors.Wrapf(ErrPosition, "invalid position %d for spend source", vs.Position)
425                 }
426                 dest = ref.WitnessDestination
427
428         case *bc.Mux:
429                 if vs.Position >= uint64(len(ref.WitnessDestinations)) {
430                         return errors.Wrapf(ErrPosition, "invalid position %d for %d-destination mux source", vs.Position, len(ref.WitnessDestinations))
431                 }
432                 dest = ref.WitnessDestinations[vs.Position]
433
434         default:
435                 return errors.Wrapf(bc.ErrEntryType, "value source is %T, should be coinbase, cross-chain input, spend, or mux", e)
436         }
437
438         if dest.Ref == nil || *dest.Ref != vstate.entryID {
439                 return errors.Wrapf(ErrMismatchedReference, "value source for %x has disagreeing destination %x", vstate.entryID.Bytes(), dest.Ref.Bytes())
440         }
441
442         if dest.Position != vstate.sourcePos {
443                 return errors.Wrapf(ErrMismatchedPosition, "value source position %d disagrees with %d", dest.Position, vstate.sourcePos)
444         }
445
446         eq, err := dest.Value.Equal(vs.Value)
447         if err != nil {
448                 return errors.Sub(ErrMissingField, err)
449         }
450         if !eq {
451                 return errors.Wrapf(ErrMismatchedValue, "source value %v disagrees with %v", dest.Value, vs.Value)
452         }
453
454         return nil
455 }
456
457 func checkValidDest(vs *validationState, vd *bc.ValueDestination) error {
458         if vd == nil {
459                 return errors.Wrap(ErrMissingField, "empty value destination")
460         }
461         if vd.Ref == nil {
462                 return errors.Wrap(ErrMissingField, "missing ref on value destination")
463         }
464         if vd.Value == nil || vd.Value.AssetId == nil {
465                 return errors.Wrap(ErrMissingField, "missing value on value destination")
466         }
467
468         e, ok := vs.tx.Entries[*vd.Ref]
469         if !ok {
470                 return errors.Wrapf(bc.ErrMissingEntry, "entry for value destination %x not found", vd.Ref.Bytes())
471         }
472
473         var src *bc.ValueSource
474         switch ref := e.(type) {
475         case *bc.IntraChainOutput:
476                 if vd.Position != 0 {
477                         return errors.Wrapf(ErrPosition, "invalid position %d for output destination", vd.Position)
478                 }
479                 src = ref.Source
480
481         case *bc.CrossChainOutput:
482                 if vd.Position != 0 {
483                         return errors.Wrapf(ErrPosition, "invalid position %d for output destination", vd.Position)
484                 }
485                 src = ref.Source
486
487         case *bc.VoteOutput:
488                 if vd.Position != 0 {
489                         return errors.Wrapf(ErrPosition, "invalid position %d for output destination", vd.Position)
490                 }
491                 src = ref.Source
492
493         case *bc.Retirement:
494                 if vd.Position != 0 {
495                         return errors.Wrapf(ErrPosition, "invalid position %d for retirement destination", vd.Position)
496                 }
497                 src = ref.Source
498
499         case *bc.Mux:
500                 if vd.Position >= uint64(len(ref.Sources)) {
501                         return errors.Wrapf(ErrPosition, "invalid position %d for %d-source mux destination", vd.Position, len(ref.Sources))
502                 }
503                 src = ref.Sources[vd.Position]
504
505         default:
506                 return errors.Wrapf(bc.ErrEntryType, "value destination is %T, should be intra-chain/cross-chain output, retirement, or mux", e)
507         }
508
509         if src.Ref == nil || *src.Ref != vs.entryID {
510                 return errors.Wrapf(ErrMismatchedReference, "value destination for %x has disagreeing source %x", vs.entryID.Bytes(), src.Ref.Bytes())
511         }
512
513         if src.Position != vs.destPos {
514                 return errors.Wrapf(ErrMismatchedPosition, "value destination position %d disagrees with %d", src.Position, vs.destPos)
515         }
516
517         eq, err := src.Value.Equal(vd.Value)
518         if err != nil {
519                 return errors.Sub(ErrMissingField, err)
520         }
521         if !eq {
522                 return errors.Wrapf(ErrMismatchedValue, "destination value %v disagrees with %v", src.Value, vd.Value)
523         }
524
525         return nil
526 }
527
528 func checkStandardTx(tx *bc.Tx, blockHeight uint64) error {
529         for _, id := range tx.InputIDs {
530                 if blockHeight >= ruleAA && id.IsZero() {
531                         return ErrEmptyInputIDs
532                 }
533         }
534
535         for _, id := range tx.GasInputIDs {
536                 spend, err := tx.Spend(id)
537                 if err != nil {
538                         continue
539                 }
540
541                 code := []byte{}
542                 outputEntry, err := tx.Entry(*spend.SpentOutputId)
543                 if err != nil {
544                         return err
545                 }
546                 switch output := outputEntry.(type) {
547                 case *bc.IntraChainOutput:
548                         code = output.ControlProgram.Code
549                 case *bc.VoteOutput:
550                         code = output.ControlProgram.Code
551                 default:
552                         return errors.Wrapf(bc.ErrEntryType, "entry %x has unexpected type %T", id.Bytes(), outputEntry)
553                 }
554
555                 if !segwit.IsP2WScript(code) {
556                         return ErrNotStandardTx
557                 }
558         }
559         return nil
560 }
561
562 func checkTimeRange(tx *bc.Tx, block *bc.Block) error {
563         if tx.TimeRange == 0 {
564                 return nil
565         }
566
567         if tx.TimeRange < block.Height {
568                 return ErrBadTimeRange
569         }
570
571         return nil
572 }
573
574 // ValidateTx validates a transaction.
575 func ValidateTx(tx *bc.Tx, block *bc.Block) (*GasState, error) {
576         gasStatus := &GasState{GasValid: false}
577         if block.Version == 1 && tx.Version != 1 {
578                 return gasStatus, errors.WithDetailf(ErrTxVersion, "block version %d, transaction version %d", block.Version, tx.Version)
579         }
580         if tx.SerializedSize == 0 {
581                 return gasStatus, ErrWrongTransactionSize
582         }
583         if err := checkTimeRange(tx, block); err != nil {
584                 return gasStatus, err
585         }
586         if err := checkStandardTx(tx, block.Height); err != nil {
587                 return gasStatus, err
588         }
589
590         vs := &validationState{
591                 block:     block,
592                 tx:        tx,
593                 entryID:   tx.ID,
594                 gasStatus: gasStatus,
595                 cache:     make(map[bc.Hash]error),
596         }
597         return vs.gasStatus, checkValid(vs, tx.TxHeader)
598 }