protocol/vm/vm.go

   1 package vm
   2
   3 import (
   4         "encoding/hex"
   5         "fmt"
   6         "io"
   7         "strings"
   8
   9         "github.com/blockchain/errors"
  10 )
  11
  12 const initialRunLimit = 10000
  13
  14 type virtualMachine struct {
  15         context *Context
  16
  17         program      []byte // the program currently executing
  18         pc, nextPC   uint32
  19         runLimit     int64
  20         deferredCost int64
  21
  22         expansionReserved bool
  23
  24         // Stores the data parsed out of an opcode. Used as input to
  25         // data-pushing opcodes.
  26         data []byte
  27
  28         // CHECKPREDICATE spawns a child vm with depth+1
  29         depth int
  30
  31         // In each of these stacks, stack[len(stack)-1] is the top element.
  32         dataStack [][]byte
  33         altStack  [][]byte
  34 }
  35
  36 // ErrFalseVMResult is one of the ways for a transaction to fail validation
  37 var ErrFalseVMResult = errors.New("false VM result")
  38
  39 // TraceOut - if non-nil - will receive trace output during
  40 // execution.
  41 var TraceOut io.Writer
  42
  43 func Verify(context *Context) (err error) {
  44         defer func() {
  45                 if r := recover(); r != nil {
  46                         if rErr, ok := r.(error); ok {
  47                                 err = errors.Sub(ErrUnexpected, rErr)
  48                         } else {
  49                                 err = errors.Wrap(ErrUnexpected, r)
  50                         }
  51                 }
  52         }()
  53
  54         if context.VMVersion != 1 {
  55                 return ErrUnsupportedVM
  56         }
  57
  58         vm := &virtualMachine{
  59                 expansionReserved: context.TxVersion != nil && *context.TxVersion == 1,
  60                 program:           context.Code,
  61                 runLimit:          initialRunLimit,
  62                 context:           context,
  63         }
  64
  65         args := context.Arguments
  66         for i, arg := range args {
  67                 err = vm.push(arg, false)
  68                 if err != nil {
  69                         return errors.Wrapf(err, "pushing initial argument %d", i)
  70                 }
  71         }
  72
  73         err = vm.run()
  74         if err == nil && vm.falseResult() {
  75                 err = ErrFalseVMResult
  76         }
  77
  78         return wrapErr(err, vm, args)
  79 }
  80
  81 // falseResult returns true iff the stack is empty or the top
  82 // item is false
  83 func (vm *virtualMachine) falseResult() bool {
  84         return len(vm.dataStack) == 0 || !AsBool(vm.dataStack[len(vm.dataStack)-1])
  85 }
  86
  87 func (vm *virtualMachine) run() error {
  88         for vm.pc = 0; vm.pc < uint32(len(vm.program)); { // handle vm.pc updates in step
  89                 err := vm.step()
  90                 if err != nil {
  91                         return err
  92                 }
  93         }
  94         return nil
  95 }
  96
  97 func (vm *virtualMachine) step() error {
  98         inst, err := ParseOp(vm.program, vm.pc)
  99         if err != nil {
 100                 return err
 101         }
 102
 103         vm.nextPC = vm.pc + inst.Len
 104
 105         if TraceOut != nil {
 106                 opname := inst.Op.String()
 107                 fmt.Fprintf(TraceOut, "vm %d pc %d limit %d %s", vm.depth, vm.pc, vm.runLimit, opname)
 108                 if len(inst.Data) > 0 {
 109                         fmt.Fprintf(TraceOut, " %x", inst.Data)
 110                 }
 111                 fmt.Fprint(TraceOut, "\n")
 112         }
 113
 114         if isExpansion[inst.Op] {
 115                 if vm.expansionReserved {
 116                         return ErrDisallowedOpcode
 117                 }
 118                 vm.pc = vm.nextPC
 119                 return vm.applyCost(1)
 120         }
 121
 122         vm.deferredCost = 0
 123         vm.data = inst.Data
 124         err = ops[inst.Op].fn(vm)
 125         if err != nil {
 126                 return err
 127         }
 128         err = vm.applyCost(vm.deferredCost)
 129         if err != nil {
 130                 return err
 131         }
 132         vm.pc = vm.nextPC
 133
 134         if TraceOut != nil {
 135                 for i := len(vm.dataStack) - 1; i >= 0; i-- {
 136                         fmt.Fprintf(TraceOut, "  stack %d: %x\n", len(vm.dataStack)-1-i, vm.dataStack[i])
 137                 }
 138         }
 139
 140         return nil
 141 }
 142
 143 func (vm *virtualMachine) push(data []byte, deferred bool) error {
 144         cost := 8 + int64(len(data))
 145         if deferred {
 146                 vm.deferCost(cost)
 147         } else {
 148                 err := vm.applyCost(cost)
 149                 if err != nil {
 150                         return err
 151                 }
 152         }
 153         vm.dataStack = append(vm.dataStack, data)
 154         return nil
 155 }
 156
 157 func (vm *virtualMachine) pushBool(b bool, deferred bool) error {
 158         return vm.push(BoolBytes(b), deferred)
 159 }
 160
 161 func (vm *virtualMachine) pushInt64(n int64, deferred bool) error {
 162         return vm.push(Int64Bytes(n), deferred)
 163 }
 164
 165 func (vm *virtualMachine) pop(deferred bool) ([]byte, error) {
 166         if len(vm.dataStack) == 0 {
 167                 return nil, ErrDataStackUnderflow
 168         }
 169         res := vm.dataStack[len(vm.dataStack)-1]
 170         vm.dataStack = vm.dataStack[:len(vm.dataStack)-1]
 171
 172         cost := 8 + int64(len(res))
 173         if deferred {
 174                 vm.deferCost(-cost)
 175         } else {
 176                 vm.runLimit += cost
 177         }
 178
 179         return res, nil
 180 }
 181
 182 func (vm *virtualMachine) popInt64(deferred bool) (int64, error) {
 183         bytes, err := vm.pop(deferred)
 184         if err != nil {
 185                 return 0, err
 186         }
 187         n, err := AsInt64(bytes)
 188         return n, err
 189 }
 190
 191 func (vm *virtualMachine) top() ([]byte, error) {
 192         if len(vm.dataStack) == 0 {
 193                 return nil, ErrDataStackUnderflow
 194         }
 195         return vm.dataStack[len(vm.dataStack)-1], nil
 196 }
 197
 198 // positive cost decreases runlimit, negative cost increases it
 199 func (vm *virtualMachine) applyCost(n int64) error {
 200         if n > vm.runLimit {
 201                 return ErrRunLimitExceeded
 202         }
 203         vm.runLimit -= n
 204         return nil
 205 }
 206
 207 func (vm *virtualMachine) deferCost(n int64) {
 208         vm.deferredCost += n
 209 }
 210
 211 func stackCost(stack [][]byte) int64 {
 212         result := int64(8 * len(stack))
 213         for _, item := range stack {
 214                 result += int64(len(item))
 215         }
 216         return result
 217 }
 218
 219 type Error struct {
 220         Err  error
 221         Prog []byte
 222         Args [][]byte
 223 }
 224
 225 func (e Error) Error() string {
 226         dis, err := Disassemble(e.Prog)
 227         if err != nil {
 228                 dis = "???"
 229         }
 230
 231         args := make([]string, 0, len(e.Args))
 232         for _, a := range e.Args {
 233                 args = append(args, hex.EncodeToString(a))
 234         }
 235
 236         return fmt.Sprintf("%s [prog %x = %s; args %s]", e.Err.Error(), e.Prog, dis, strings.Join(args, " "))
 237 }
 238
 239 func wrapErr(err error, vm *virtualMachine, args [][]byte) error {
 240         if err == nil {
 241                 return nil
 242         }
 243         return Error{
 244                 Err:  err,
 245                 Prog: vm.program,
 246                 Args: args,
 247         }
 248 }