OSDN Git Service

fix(cross_chain): add asset_id check in cross_chain_in request (#177)
[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 check CrossChainInput")
255                 }
256                 code := config.FederationProgrom(config.CommonConfig)
257                 prog := &bc.Program{
258                         VmVersion: e.ControlProgram.VmVersion,
259                         Code:      code,
260                 }
261                 _, err := vm.Verify(NewTxVMContext(vs, e, prog, e.WitnessArguments), consensus.DefaultGasCredit)
262                 if err != nil {
263                         return errors.Wrap(err, "checking cross-chain input control program")
264                 }
265
266                 vs2 := *vs
267                 vs2.destPos = 0
268                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
269                         return errors.Wrap(err, "checking cross-chain input destination")
270                 }
271                 vs.gasStatus.StorageGas = 0
272
273         case *bc.Spend:
274                 if e.SpentOutputId == nil {
275                         return errors.Wrap(ErrMissingField, "spend without spent output ID")
276                 }
277
278                 spentOutput, err := vs.tx.IntraChainOutput(*e.SpentOutputId)
279                 if err != nil {
280                         return errors.Wrap(err, "getting spend prevout")
281                 }
282
283                 gasLeft, err := vm.Verify(NewTxVMContext(vs, e, spentOutput.ControlProgram, e.WitnessArguments), vs.gasStatus.GasLeft)
284                 if err != nil {
285                         return errors.Wrap(err, "checking control program")
286                 }
287                 if err = vs.gasStatus.updateUsage(gasLeft); err != nil {
288                         return err
289                 }
290
291                 eq, err := spentOutput.Source.Value.Equal(e.WitnessDestination.Value)
292                 if err != nil {
293                         return err
294                 }
295                 if !eq {
296                         return errors.WithDetailf(
297                                 ErrMismatchedValue,
298                                 "previous output is for %d unit(s) of %x, spend wants %d unit(s) of %x",
299                                 spentOutput.Source.Value.Amount,
300                                 spentOutput.Source.Value.AssetId.Bytes(),
301                                 e.WitnessDestination.Value.Amount,
302                                 e.WitnessDestination.Value.AssetId.Bytes(),
303                         )
304                 }
305                 vs2 := *vs
306                 vs2.destPos = 0
307                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
308                         return errors.Wrap(err, "checking spend destination")
309                 }
310
311         case *bc.VetoInput:
312                 if e.SpentOutputId == nil {
313                         return errors.Wrap(ErrMissingField, "vetoInput without vetoInput output ID")
314                 }
315
316                 voteOutput, err := vs.tx.VoteOutput(*e.SpentOutputId)
317                 if err != nil {
318                         return errors.Wrap(err, "getting vetoInput prevout")
319                 }
320                 if len(voteOutput.Vote) != 64 {
321                         return ErrVotePubKey
322                 }
323
324                 gasLeft, err := vm.Verify(NewTxVMContext(vs, e, voteOutput.ControlProgram, e.WitnessArguments), vs.gasStatus.GasLeft)
325                 if err != nil {
326                         return errors.Wrap(err, "checking control program")
327                 }
328                 if err = vs.gasStatus.updateUsage(gasLeft); err != nil {
329                         return err
330                 }
331
332                 eq, err := voteOutput.Source.Value.Equal(e.WitnessDestination.Value)
333                 if err != nil {
334                         return err
335                 }
336                 if !eq {
337                         return errors.WithDetailf(
338                                 ErrMismatchedValue,
339                                 "previous output is for %d unit(s) of %x, vetoInput wants %d unit(s) of %x",
340                                 voteOutput.Source.Value.Amount,
341                                 voteOutput.Source.Value.AssetId.Bytes(),
342                                 e.WitnessDestination.Value.Amount,
343                                 e.WitnessDestination.Value.AssetId.Bytes(),
344                         )
345                 }
346                 vs2 := *vs
347                 vs2.destPos = 0
348                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
349                         return errors.Wrap(err, "checking vetoInput destination")
350                 }
351
352         case *bc.Coinbase:
353                 if vs.block == nil || len(vs.block.Transactions) == 0 || vs.block.Transactions[0] != vs.tx {
354                         return ErrWrongCoinbaseTransaction
355                 }
356
357                 if *e.WitnessDestination.Value.AssetId != *consensus.BTMAssetID {
358                         return ErrWrongCoinbaseAsset
359                 }
360
361                 if e.Arbitrary != nil && len(e.Arbitrary) > consensus.CoinbaseArbitrarySizeLimit {
362                         return ErrCoinbaseArbitraryOversize
363                 }
364
365                 vs2 := *vs
366                 vs2.destPos = 0
367                 if err = checkValidDest(&vs2, e.WitnessDestination); err != nil {
368                         return errors.Wrap(err, "checking coinbase destination")
369                 }
370                 vs.gasStatus.StorageGas = 0
371
372         default:
373                 return fmt.Errorf("entry has unexpected type %T", e)
374         }
375
376         return nil
377 }
378
379 func checkValidSrc(vstate *validationState, vs *bc.ValueSource) error {
380         if vs == nil {
381                 return errors.Wrap(ErrMissingField, "empty value source")
382         }
383         if vs.Ref == nil {
384                 return errors.Wrap(ErrMissingField, "missing ref on value source")
385         }
386         if vs.Value == nil || vs.Value.AssetId == nil {
387                 return errors.Wrap(ErrMissingField, "missing value on value source")
388         }
389
390         e, ok := vstate.tx.Entries[*vs.Ref]
391         if !ok {
392                 return errors.Wrapf(bc.ErrMissingEntry, "entry for value source %x not found", vs.Ref.Bytes())
393         }
394
395         vstate2 := *vstate
396         vstate2.entryID = *vs.Ref
397         if err := checkValid(&vstate2, e); err != nil {
398                 return errors.Wrap(err, "checking value source")
399         }
400
401         var dest *bc.ValueDestination
402         switch ref := e.(type) {
403         case *bc.VetoInput:
404                 if vs.Position != 0 {
405                         return errors.Wrapf(ErrPosition, "invalid position %d for veto-input source", vs.Position)
406                 }
407                 dest = ref.WitnessDestination
408
409         case *bc.Coinbase:
410                 if vs.Position != 0 {
411                         return errors.Wrapf(ErrPosition, "invalid position %d for coinbase source", vs.Position)
412                 }
413                 dest = ref.WitnessDestination
414
415         case *bc.CrossChainInput:
416                 if vs.Position != 0 {
417                         return errors.Wrapf(ErrPosition, "invalid position %d for cross-chain input source", vs.Position)
418                 }
419                 dest = ref.WitnessDestination
420
421         case *bc.Spend:
422                 if vs.Position != 0 {
423                         return errors.Wrapf(ErrPosition, "invalid position %d for spend source", vs.Position)
424                 }
425                 dest = ref.WitnessDestination
426
427         case *bc.Mux:
428                 if vs.Position >= uint64(len(ref.WitnessDestinations)) {
429                         return errors.Wrapf(ErrPosition, "invalid position %d for %d-destination mux source", vs.Position, len(ref.WitnessDestinations))
430                 }
431                 dest = ref.WitnessDestinations[vs.Position]
432
433         default:
434                 return errors.Wrapf(bc.ErrEntryType, "value source is %T, should be coinbase, cross-chain input, spend, or mux", e)
435         }
436
437         if dest.Ref == nil || *dest.Ref != vstate.entryID {
438                 return errors.Wrapf(ErrMismatchedReference, "value source for %x has disagreeing destination %x", vstate.entryID.Bytes(), dest.Ref.Bytes())
439         }
440
441         if dest.Position != vstate.sourcePos {
442                 return errors.Wrapf(ErrMismatchedPosition, "value source position %d disagrees with %d", dest.Position, vstate.sourcePos)
443         }
444
445         eq, err := dest.Value.Equal(vs.Value)
446         if err != nil {
447                 return errors.Sub(ErrMissingField, err)
448         }
449         if !eq {
450                 return errors.Wrapf(ErrMismatchedValue, "source value %v disagrees with %v", dest.Value, vs.Value)
451         }
452
453         return nil
454 }
455
456 func checkValidDest(vs *validationState, vd *bc.ValueDestination) error {
457         if vd == nil {
458                 return errors.Wrap(ErrMissingField, "empty value destination")
459         }
460         if vd.Ref == nil {
461                 return errors.Wrap(ErrMissingField, "missing ref on value destination")
462         }
463         if vd.Value == nil || vd.Value.AssetId == nil {
464                 return errors.Wrap(ErrMissingField, "missing value on value destination")
465         }
466
467         e, ok := vs.tx.Entries[*vd.Ref]
468         if !ok {
469                 return errors.Wrapf(bc.ErrMissingEntry, "entry for value destination %x not found", vd.Ref.Bytes())
470         }
471
472         var src *bc.ValueSource
473         switch ref := e.(type) {
474         case *bc.IntraChainOutput:
475                 if vd.Position != 0 {
476                         return errors.Wrapf(ErrPosition, "invalid position %d for output destination", vd.Position)
477                 }
478                 src = ref.Source
479
480         case *bc.CrossChainOutput:
481                 if vd.Position != 0 {
482                         return errors.Wrapf(ErrPosition, "invalid position %d for output destination", vd.Position)
483                 }
484                 src = ref.Source
485
486         case *bc.VoteOutput:
487                 if vd.Position != 0 {
488                         return errors.Wrapf(ErrPosition, "invalid position %d for output destination", vd.Position)
489                 }
490                 src = ref.Source
491
492         case *bc.Retirement:
493                 if vd.Position != 0 {
494                         return errors.Wrapf(ErrPosition, "invalid position %d for retirement destination", vd.Position)
495                 }
496                 src = ref.Source
497
498         case *bc.Mux:
499                 if vd.Position >= uint64(len(ref.Sources)) {
500                         return errors.Wrapf(ErrPosition, "invalid position %d for %d-source mux destination", vd.Position, len(ref.Sources))
501                 }
502                 src = ref.Sources[vd.Position]
503
504         default:
505                 return errors.Wrapf(bc.ErrEntryType, "value destination is %T, should be intra-chain/cross-chain output, retirement, or mux", e)
506         }
507
508         if src.Ref == nil || *src.Ref != vs.entryID {
509                 return errors.Wrapf(ErrMismatchedReference, "value destination for %x has disagreeing source %x", vs.entryID.Bytes(), src.Ref.Bytes())
510         }
511
512         if src.Position != vs.destPos {
513                 return errors.Wrapf(ErrMismatchedPosition, "value destination position %d disagrees with %d", src.Position, vs.destPos)
514         }
515
516         eq, err := src.Value.Equal(vd.Value)
517         if err != nil {
518                 return errors.Sub(ErrMissingField, err)
519         }
520         if !eq {
521                 return errors.Wrapf(ErrMismatchedValue, "destination value %v disagrees with %v", src.Value, vd.Value)
522         }
523
524         return nil
525 }
526
527 func checkStandardTx(tx *bc.Tx, blockHeight uint64) error {
528         for _, id := range tx.InputIDs {
529                 if blockHeight >= ruleAA && id.IsZero() {
530                         return ErrEmptyInputIDs
531                 }
532         }
533
534         for _, id := range tx.GasInputIDs {
535                 spend, err := tx.Spend(id)
536                 if err != nil {
537                         continue
538                 }
539
540                 code := []byte{}
541                 outputEntry, err := tx.Entry(*spend.SpentOutputId)
542                 if err != nil {
543                         return err
544                 }
545                 switch output := outputEntry.(type) {
546                 case *bc.IntraChainOutput:
547                         code = output.ControlProgram.Code
548                 case *bc.VoteOutput:
549                         code = output.ControlProgram.Code
550                 default:
551                         return errors.Wrapf(bc.ErrEntryType, "entry %x has unexpected type %T", id.Bytes(), outputEntry)
552                 }
553
554                 if !segwit.IsP2WScript(code) {
555                         return ErrNotStandardTx
556                 }
557         }
558         return nil
559 }
560
561 func checkTimeRange(tx *bc.Tx, block *bc.Block) error {
562         if tx.TimeRange == 0 {
563                 return nil
564         }
565
566         if tx.TimeRange < block.Height {
567                 return ErrBadTimeRange
568         }
569
570         return nil
571 }
572
573 // ValidateTx validates a transaction.
574 func ValidateTx(tx *bc.Tx, block *bc.Block) (*GasState, error) {
575         gasStatus := &GasState{GasValid: false}
576         if block.Version == 1 && tx.Version != 1 {
577                 return gasStatus, errors.WithDetailf(ErrTxVersion, "block version %d, transaction version %d", block.Version, tx.Version)
578         }
579         if tx.SerializedSize == 0 {
580                 return gasStatus, ErrWrongTransactionSize
581         }
582         if err := checkTimeRange(tx, block); err != nil {
583                 return gasStatus, err
584         }
585         if err := checkStandardTx(tx, block.Height); err != nil {
586                 return gasStatus, err
587         }
588
589         vs := &validationState{
590                 block:     block,
591                 tx:        tx,
592                 entryID:   tx.ID,
593                 gasStatus: gasStatus,
594                 cache:     make(map[bc.Hash]error),
595         }
596         return vs.gasStatus, checkValid(vs, tx.TxHeader)
597 }