以太坊黄皮书详解（三）

2018-06-12

Ethereum

六、虚拟机的执行模型

上文三四五部分都是从流程上对交易执行（包括合约创建和合约调用）进行了介绍。本章节介绍以太坊中的虚拟机执行的流程。以太坊虚拟机EVM是图灵完备虚拟机器。EVM存在而典型图灵完备机器不存在的唯一限制就是EVM本质上是被gas束缚。因此，可以完成的计算总量本质上是被提供的gas总量限制的。

6.1 基本模型

EVM是基于栈（先进后出）的架构。EVM中每个堆栈项的大小为256位，堆栈有一个最大的大小，为1024位。
EVM有内存，项目按照可寻址字节数组来存储。内存是易失性的，也就是数据是不持久的。
EVM也有一个存储器。不像内存，存储器是非易失性的，并作为系统状态的一部分进行维护。EVM分开保存程序代码，在虚拟ROM 中只能通过特殊指令来访问。
EVM同样有属于它自己的语言：“EVM字节码”，在以太坊上运行的智能合约时，通常都是用高级语言例如Solidity来编写代码。然后将它编译成EVM可以理解的EVM字节码。

// EVM is the Ethereum Virtual Machine base object and provides
// the necessary tools to run a contract on the given state with
// the provided context. It should be noted that any error
// generated through any of the calls should be considered a
// revert-state-and-consume-all-gas operation, no checks on
// specific errors should ever be performed. The interpreter makes
// sure that any errors generated are to be considered faulty code.
//
// The EVM should never be reused and is not thread safe.
type EVM struct {
	// Context provides auxiliary blockchain related information
	Context
	// StateDB gives access to the underlying state
	StateDB StateDB
	// Depth is the current call stack
	depth int

	// chainConfig contains information about the current chain
	chainConfig *params.ChainConfig
	// chain rules contains the chain rules for the current epoch
	chainRules params.Rules
	// virtual machine configuration options used to initialise the
	// evm.
	vmConfig Config
	// global (to this context) ethereum virtual machine
	// used throughout the execution of the tx.
	interpreter *Interpreter
	// abort is used to abort the EVM calling operations
	// NOTE: must be set atomically
	abort int32
	// callGasTemp holds the gas available for the current call. This is needed because the
	// available gas is calculated in gasCall* according to the 63/64 rule and later
	// applied in opCall*.
	callGasTemp uint64
}

// Interpreter is used to run Ethereum based contracts and will utilise the
// passed environment to query external sources for state information.
// The Interpreter will run the byte code VM based on the passed
// configuration.
type Interpreter struct {
	evm      *EVM
	cfg      Config
	gasTable params.GasTable
	intPool  *intPool  //栈

	readOnly   bool   // Whether to throw on stateful modifications
	returnData []byte // Last CALL's return data for subsequent reuse
}

6.2 费用

以太坊虚拟机执行过程中，主要有3类费用。

执行过程中的运算费用。
创建或者调用其他合约消耗的费用。
新增的存储的费用。

6.3 运行环境

合约执行过程中的运行环境包括：系统状态$\sigma$,可用gas值g，以及其他包含在I中的一些值，在第四和第五部分也都有涉及到。

$I_a$为合约执行的当前账户。对于合约创建则为新创建的合约账户，如果是合约调用，则为接收者账户。
$I_o$为原始调用者，即该条交易的发送者。
$I_p$为gas价格。
$I_d$为合约执行的输入数据。
$I_s$为合约当前调用者，如果是条简单的交易，则为交易的发送者。
$I_v$为value，单位为Wei，即要转移给当前账户的以太币。
$I_b$需要被执行的机器码。合约创建的时候该处即为初始化合约的字节码。
$I_H$当前区块的header。
$I_e$当前的栈深度。
$I_w$相关权限。

执行模型可以用公式121表示。其中子状态如公式122所示。（该处子状态定义和之前是相同的） $\begin{equation} (\boldsymbol{\sigma}', g', A, \mathbf{o}) \equiv \Xi(\boldsymbol{\sigma}, g, I) \tag{121} \end{equation}$ $\begin{equation} A \equiv (\mathbf{s}, \mathbf{l}, \mathbf{t}, r) \tag{122} \end{equation}$

6.4 执行过程

执行刚开始时，内存和堆栈都是空的，程序计数器为0。
然后EVM开始递归的执行交易，为每个循环计算系统状态和机器状态。系统状态也就是以太坊的全局状态(global state)。机器状态包含：可获取的gas，程序计数器，内存的内容，内存中字的活跃数，堆栈的内容。
堆栈中的项从栈顶被删除（POP）或者添加（PUSH）。
每个循环，剩余的gas都会被减少相应的量，程序计数器也会增加。

在每个循环的结束，都有四种可能性：

机器到达异常状态（err != nil 的情况。例如 gas不足，无效指令，堆栈项不足，堆栈项会溢出1024，无效的JUMP/JUMPI目的地等等）因此停止，并丢弃任何的更改进入后续处理下一个循环。
机器到达了受控停止（到达执行过程的终点，halts或者revert），整个结束了，机器就会产生一个合成状态，执行之后的剩余gas、产生的子状态、以及组合输出。
假设执行没有遇到异常状态，继续循环执行下一步。

// Run loops and evaluates the contract's code with the given input data and returns
// the return byte-slice and an error if one occurred.
//
// It's important to note that any errors returned by the interpreter should be
// considered a revert-and-consume-all-gas operation except for
// errExecutionReverted which means revert-and-keep-gas-left.
func (in *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err error) {
	// Increment the call depth which is restricted to 1024
	in.evm.depth++
	defer func() { in.evm.depth-- }()

	// Reset the previous call's return data. It's unimportant to preserve the old buffer
	// as every returning call will return new data anyway.
	in.returnData = nil

	// Don't bother with the execution if there's no code.
	if len(contract.Code) == 0 {
		return nil, nil
	}

	//机器状态包含：可获取的gas，程序计数器pc，内存的内容mem，内存中字的活跃数，堆栈的内容stack。
	var (
		op    OpCode        // current opcode
		mem   = NewMemory() // bound memory
		stack = newstack()  // local stack
		// For optimisation reason we're using uint64 as the program counter.
		// It's theoretically possible to go above 2^64. The YP defines the PC
		// to be uint256. Practically much less so feasible.
		pc   = uint64(0) // program counter
		cost uint64
		// copies used by tracer
		pcCopy  uint64 // needed for the deferred Tracer
		gasCopy uint64 // for Tracer to log gas remaining before execution
		logged  bool   // deferred Tracer should ignore already logged steps
	)
	contract.Input = input

	if in.cfg.Debug {
		defer func() {
			if err != nil {
				if !logged {
					in.cfg.Tracer.CaptureState(in.evm, pcCopy, op, gasCopy, cost, mem, stack, contract, in.evm.depth, err)
				} else {
					in.cfg.Tracer.CaptureFault(in.evm, pcCopy, op, gasCopy, cost, mem, stack, contract, in.evm.depth, err)
				}
			}
		}()
	}
	// 循环直到三种结束状态中的一种。
	// 1.异常情况，各种不合法的情况出现时，或者执行出错，会直接return
	// 2.执行中返回REVERT错误。
	// 3.执行中中断。 
	// The Interpreter main run loop (contextual). This loop runs until either an
	// explicit STOP, RETURN or SELFDESTRUCT is executed, an error occurred during
	// the execution of one of the operations or until the done flag is set by the
	// parent context.
	for atomic.LoadInt32(&in.evm.abort) == 0 {
		if in.cfg.Debug {
			// Capture pre-execution values for tracing.
			logged, pcCopy, gasCopy = false, pc, contract.Gas
		}

		// Get the operation from the jump table and validate the stack to ensure there are
		// enough stack items available to perform the operation.
		// 获取当前要执行的操作
		op = contract.GetOp(pc)
		// 确认操作是否在操作集合表中
		operation := in.cfg.JumpTable[op]
		if !operation.valid {
			return nil, fmt.Errorf("invalid opcode 0x%x", int(op))
		}
		// 确保目前栈满足操作要求，比方说有些操作是二元的，那么栈中至少要有两个数据。
		if err := operation.validateStack(stack); err != nil {
			return nil, err
		}
		// If the operation is valid, enforce and write restrictions
		if err := in.enforceRestrictions(op, operation, stack); err != nil {
			return nil, err
		}

		var memorySize uint64
		// calculate the new memory size and expand the memory to fit
		// the operation
		// 计算新操作需要的内存空间
		if operation.memorySize != nil {
			memSize, overflow := bigUint64(operation.memorySize(stack))
			if overflow {
				return nil, errGasUintOverflow
			}
			// memory is expanded in words of 32 bytes. Gas
			// is also calculated in words.
			if memorySize, overflow = math.SafeMul(toWordSize(memSize), 32); overflow {
				return nil, errGasUintOverflow
			}
		}
		// consume the gas and return an error if not enough gas is available.
		// cost is explicitly set so that the capture state defer method can get the proper cost
		// 消耗gas
		cost, err = operation.gasCost(in.gasTable, in.evm, contract, stack, mem, memorySize)
		if err != nil || !contract.UseGas(cost) {
			return nil, ErrOutOfGas
		}
		if memorySize > 0 {
			mem.Resize(memorySize)
		}

		if in.cfg.Debug {
			in.cfg.Tracer.CaptureState(in.evm, pc, op, gasCopy, cost, mem, stack, contract, in.evm.depth, err)
			logged = true
		}

		// execute the operation
		// 执行具体的操作，比方说加法，就是从栈中取出两个值后相加
		res, err := operation.execute(&pc, in.evm, contract, mem, stack)
		// verifyPool is a build flag. Pool verification makes sure the integrity
		// of the integer pool by comparing values to a default value.
		if verifyPool {
			verifyIntegerPool(in.intPool)
		}
		// if the operation clears the return data (e.g. it has returning data)
		// set the last return to the result of the operation.
		if operation.returns {
			in.returnData = res
		}

		switch {
		case err != nil:
			return nil, err
		case operation.reverts:
			return res, errExecutionReverted
		case operation.halts:
			return res, nil
		case !operation.jumps:
			pc++ //计数器加一，接着执行
		}
	}
	return nil, nil
}

6.4.1 整体流程的形式化表示

虚拟机行执行合约的整体流程可以看作是输入系统状态$\sigma$,可用gas值g，输入项I，可以获取到的账户集合T。经过虚拟机函数$\Xi$后，得到新的系统状态$\sigma’$,执行剩余可用gas$\mu_g’$,交易子状态A和组合输出$\mathbf{o}$。如公式123所示。

执行的过程是一个迭代执行的过程，定义X为该迭代函数。如公式124所示。

其中机器状态$\mu$,包括：

可用gas值g，初始值即为输入的可用gas值，公式125。
程序计数器pc，初始值为0，公式126。
内存内容m，初始为全0，公式127。
内存内容中活跃的字数i，初始为0，公式128。
栈s，初始为空的栈，公式129。
组合输出，初始为空，公式130.

$\begin{eqnarray} \Xi(\boldsymbol{\sigma}, g, I, T) & \equiv & (\boldsymbol{\sigma}', \boldsymbol{\mu}'_{\mathrm{g}}, A, \mathbf{o}) \tag{123}\\ (\boldsymbol{\sigma}', \boldsymbol{\mu}', A, ..., \mathbf{o}) & \equiv & X\big((\boldsymbol{\sigma}, \boldsymbol{\mu}, A^0, I)\big) \tag{124}\\ \boldsymbol{\mu}_{\mathrm{g}} & \equiv & g \tag{125}\\ \boldsymbol{\mu}_{\mathrm{pc}} & \equiv & 0 \tag{126}\\ \boldsymbol{\mu}_{\mathbf{m}} & \equiv & (0, 0, ...) \tag{127}\\ \boldsymbol{\mu}_{\mathrm{i}} & \equiv & 0 \tag{128}\\ \boldsymbol{\mu}_{\mathbf{s}} & \equiv & () \tag{129}\\ \boldsymbol{\mu}_{\mathbf{o}} & \equiv & () \tag{130} \end{eqnarray}$ $\begin{equation} \label{eq:X-def} X\big( (\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I) \big) \equiv \begin{cases} \big(\varnothing, \boldsymbol{\mu}, A^0, I, \varnothing\big) & \text{if} \quad Z(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \\ \big(\varnothing, \boldsymbol{\mu}', A^0, I, \mathbf{o}\big) & \text{if} \quad w = {\small REVERT} \\ O(\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I) \cdot \mathbf{o} & \text{if} \quad \mathbf{o} \neq \varnothing \\ X\big(O(\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I)\big) & \text{otherwise} \\ \end{cases} \tag{131} \end{equation}$ $\begin{eqnarray} \mathbf{o} & \equiv & H(\boldsymbol{\mu}, I) \tag{132}\\ (a, b, c, d) \cdot e & \equiv & (a, b, c, d, e) \tag{133}\\ \boldsymbol{\mu}' & \equiv & \boldsymbol{\mu}\ \text{except:} \tag{134}\\ \boldsymbol{\mu}'_{\mathrm{g}} & \equiv & \boldsymbol{\mu}_{\mathrm{g}} - C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \tag{135} \end{eqnarray}$

迭代函数X定义如公式131-135所示。

如果迭代过程中遇到异常，即$Z(\boldsymbol{\sigma}, \boldsymbol{\mu}, I)$,异常的具体情况见下一小节。则迭代结束，返回空的状态集$\varnothing$，原始机器状态$\boldsymbol{\mu}$，空的子状态$A^0$,空的组合输出$\varnothing$。
如果执行中隐式中断，当前要执行的操作为revert，则迭代结束，返回空的状态集$\varnothing$，临时机器状态$\boldsymbol{\mu’}$（扣除了gas消耗公式134-135），空的子状态$A^0$,组合输出$\mathbf{o}$。
如果执行过程正常，且达到了受控停止的状态，即组合输出$\mathbf{o}$不为空，则返回执行结果以及组合输出。组合输出由$H(\boldsymbol{\mu}, I)$确定公式132，详解见后文6.4.4。
如果执行过程正常，且组合输出为空，继续进行下一轮迭代。

当前要被执行的操作定义如公式136.

当程序计数器小于虚拟机字节码时，当前要执行的操作为字节码中对应操作。
否则为STOP

$\begin{equation}\label{eq:currentoperation} w \equiv \begin{cases} I_{\mathbf{b}}[\boldsymbol{\mu}_{\mathrm{pc}}] & \text{if} \quad \boldsymbol{\mu}_{\mathrm{pc}} < \lVert I_{\mathbf{b}} \rVert \\ {\small STOP} & \text{otherwise} \end{cases} \tag{136} \end{equation}$

6.4.2异常的形式化定义

虚拟机执行过程中的异常有以下几种情况,如公式137： $\begin{equation} Z(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \equiv \begin{array}[t]{l} \boldsymbol{\mu}_g < C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \quad \vee \\ \mathbf{\delta}_w = \varnothing \quad \vee \\ \lVert\boldsymbol{\mu}_\mathbf{s}\rVert < \mathbf{\delta}_w \quad \vee \\ ( w = {\small JUMP} \quad \wedge \quad \boldsymbol{\mu}_\mathbf{s}[0] \notin D(I_\mathbf{b}) ) \quad \vee \\ ( w = {\small JUMPI} \quad \wedge \quad \boldsymbol{\mu}_\mathbf{s}[1] \neq 0 \quad \wedge \quad \boldsymbol{\mu}_\mathbf{s}[0] \notin D(I_\mathbf{b}) ) \quad \vee \\ ( w = {\small RETURNDATACOPY} \quad \wedge \quad \boldsymbol{\mu}_{\mathbf{s}}[1] + \boldsymbol{\mu}_{\mathbf{s}}[2] > \lVert\boldsymbol{\mu}_{\mathbf{o}}\rVert) \quad \vee \\ \lVert\boldsymbol{\mu}_\mathbf{s}\rVert - \mathbf{\delta}_w + \mathbf{\alpha}_w > 1024 \quad \vee \\ (\neg I_{\mathrm{w}} \wedge W(w, \boldsymbol{\mu})) \end{array} \tag{137} \end{equation}$

$\begin{equation} W(w, \boldsymbol{\mu}) \equiv \begin{array}[t]{l} w \in \{ {\small CREATE}, {\small SSTORE}, {\small SELFDESTRUCT}\} \ \vee \\ {\small LOG0} \le w \wedge w \le {\small LOG4} \quad \vee \\ w \in \{ {\small CALL}, {\small CALLCODE}\} \wedge \boldsymbol{\mu}_{\mathbf{s}}[2] \neq 0 \end{array} \tag{138} \end{equation}$

gas值不足以支付花费。即$\boldsymbol{\mu}_g < C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I)$。

func (in *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err error) {
  //...
  for atomic.LoadInt32(&in.evm.abort) == 0 {
      //...
      // gas值不足以支付花费
      cost, err = operation.gasCost(in.gasTable, in.evm, contract, stack, mem, memorySize)
      if err != nil || !contract.UseGas(cost) {
          return nil, ErrOutOfGas
      }
      //...
  }
}

当前的操作是无效的。$\mathbf{\delta}_w = \varnothing$。当前操作w对应的字节码为空。

func (in *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err error) {
  //...
  for atomic.LoadInt32(&in.evm.abort) == 0 {
      //...
      // 获取当前要执行的操作
      op = contract.GetOp(pc)
      // 确认操作是否在操作集合表中
      operation := in.cfg.JumpTable[op]
      if !operation.valid {
          return nil, fmt.Errorf("invalid opcode 0x%x", int(op))
      }
      //...
  }
}

当前栈不合法（比方说二元操作，栈里只有一个数据）$\lVert\boldsymbol{\mu}_\mathbf{s}\rVert < \mathbf{\delta}_w$

func (in *Interpreter) Run(contract *Contract, input []byte) (ret []byte, err error) {
  //...
  for atomic.LoadInt32(&in.evm.abort) == 0 {
      //...
      // 确保目前栈满足操作要求，比方说有些操作是二元的，那么栈中至少要有两个数据。
      if err := operation.validateStack(stack); err != nil {
          return nil, err
      }
      // If the operation is valid, enforce and write restrictions
      if err := in.enforceRestrictions(op, operation, stack); err != nil {
          return nil, err
      }
      //...
  }
}

当前操作为跳转，但是跳转到的地方不合法 $( w = {\small JUMP} \wedge \boldsymbol{\mu}_\mathbf{s}[0] \notin D(I_\mathbf{b}) ) (w = {\small JUMPI} \wedge \boldsymbol{\mu}_\mathbf{s}[1] \neq 0 \wedge \boldsymbol{\mu}_\mathbf{s}[0] \notin D(I_\mathbf{b}) )$

//跳转操作
func opJump(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
	pos := stack.pop()
	if !contract.jumpdests.has(contract.CodeHash, contract.Code, pos) {
		nop := contract.GetOp(pos.Uint64())
		return nil, fmt.Errorf("invalid jump destination (%v) %v", nop, pos)
	}
	*pc = pos.Uint64()

	evm.interpreter.intPool.put(pos)
	return nil, nil
}

func opJumpi(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
	pos, cond := stack.pop(), stack.pop()
	if cond.Sign() != 0 {
		if !contract.jumpdests.has(contract.CodeHash, contract.Code, pos) {
			nop := contract.GetOp(pos.Uint64())
			return nil, fmt.Errorf("invalid jump destination (%v) %v", nop, pos)
		}
		*pc = pos.Uint64()
	} else {
		*pc++
	}

	evm.interpreter.intPool.put(pos, cond)
	return nil, nil
}

当前操作为返回数据操作，但是返回的数据长度超过了允许长度。 $( w = {\small RETURNDATACOPY} \wedge \boldsymbol{\mu}_{\mathbf{s}}[1] + \boldsymbol{\mu}_{\mathbf{s}}[2] > \lVert\boldsymbol{\mu}_{\mathbf{o}}\rVert)$

func opReturnDataCopy(pc *uint64, evm *EVM, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
	var (
		memOffset  = stack.pop()
		dataOffset = stack.pop()
		length     = stack.pop()

		end = evm.interpreter.intPool.get().Add(dataOffset, length)
	)
	defer evm.interpreter.intPool.put(memOffset, dataOffset, length, end)
	//判断返回数据长度是否超过允许长度
	if end.BitLen() > 64 || uint64(len(evm.interpreter.returnData)) < end.Uint64() {
		return nil, errReturnDataOutOfBounds
	}
	memory.Set(memOffset.Uint64(), length.Uint64(), evm.interpreter.returnData[dataOffset.Uint64():end.Uint64()])

	return nil, nil
}

新的栈的大小大于1024,$\lVert\boldsymbol{\mu}_\mathbf{s}\rVert - \mathbf{\delta}_w + \mathbf{\alpha}_w > 1024$
没用权限却尝试非静态调用$\neg I_{\mathrm{w}} \wedge W(w, \boldsymbol{\mu})$。其中非静态调用有，CREATE，SSTORE，SELFDESTRUCT，LOG0，LOG1，LOG2，LOG3，LOG4，以及CALL和CALLCHAINCODE，如公式138。

func (in *Interpreter) enforceRestrictions(op OpCode, operation operation, stack *Stack) error {
	if in.evm.chainRules.IsByzantium {
		if in.readOnly {
			// If the interpreter is operating in readonly mode, make sure no
			// state-modifying operation is performed. The 3rd stack item
			// for a call operation is the value. Transferring value from one
			// account to the others means the state is modified and should also
			// return with an error.
			if operation.writes || (op == CALL && stack.Back(2).BitLen() > 0) {
				return errWriteProtection
			}
		}
	}
	return nil
}

6.4.3 跳转表的形式化定义

$\begin{equation} D(\mathbf{c}) \equiv D_{J}(\mathbf{c}, 0) \tag{139} \end{equation}$ $\begin{equation} D_{J}(\mathbf{c}, i) \equiv \begin{cases} \{\} & \text{if} \quad i \geqslant |\mathbf{c}| \\ \{ i \} \cup D_{J}(\mathbf{c}, N(i, \mathbf{c}[i])) & \text{if} \quad \mathbf{c}[i] = {\small JUMPDEST} \\ D_{J}(\mathbf{c}, N(i, \mathbf{c}[i])) & \text{otherwise} \\ \end{cases} \tag{140} \end{equation}$

$\begin{equation} N(i, w) \equiv \begin{cases} i + w - {\small PUSH1} + 2 & \text{if} \quad w \in [{\small PUSH1}, {\small PUSH32}] \\ i + 1 & \text{otherwise} \end{cases} \tag{141} \end{equation}$ 公式139-141为对跳转表的定义。

跳转到c，指跳转到c的第0个指令。公式140.
跳转到c的第i个指令，如果i大于等于c的长度，则跳转到空，否则跳转到i的下一个有效指令的位置。公式140.

其中$N(i,w)$指下一个有效的操作指令的位置，因为是找有效的指令，和不是数据，所以遇到push指令的时候需要跳过push进去的数据。

如果当前命令为PUSHX，则跳转到i+X+1（因为栈里接下来全是push进去的数据，寻找指令，要跳过这些数据）。
否则为i + 1.

6.4.4 正常的可控中断的形式化定义

正常的可控中断有以下三种：

当前的操作为RETURN或者REVERT，相应的进行返回。
当前操作为STOP或者SELFDESTRUCT。
其他情况返回空。

注：这里STOP或者SELFDESTRUCT返回的并不是空，所以在6.1中也是o不为空的情况。

$\begin{equation} H(\boldsymbol{\mu}, I) \equiv \begin{cases} H_{ {\tiny RETURN}}(\boldsymbol{\mu}) \ \text{if} \quad w \in \, {\small REVERT}\} &\\ () \quad\quad\ \text{if} \quad w \in \{ {\small {STOP}}, {\small {SELFDESTRUCT}} \} &\\ \varnothing \quad\quad\ \text{otherwise}& \end{cases} \tag{142} \end{equation}$

6.5 执行的生命周期的形式化表示

执行过程中栈元素从栈顶入栈和出栈（黄皮书中栈顶元素为0），每次从栈顶取出操作执行，并根据操作进行相应的出栈和入栈操作。栈中其余的元素不变。如公式143-146所示。

$\begin{eqnarray} O\big((\boldsymbol{\sigma}, \boldsymbol{\mu}, A, I)\big) & \equiv & (\boldsymbol{\sigma}', \boldsymbol{\mu}', A', I) \tag{143}\\ \Delta & \equiv & \mathbf{\alpha}_{w} - \mathbf{\delta}_{w} \tag{144}\\ \lVert\boldsymbol{\mu}'_{\mathbf{s}}\rVert & \equiv & \lVert\boldsymbol{\mu}_{\mathbf{s}}\rVert + \Delta \tag{145}\\ \quad \forall x \in [\mathbf{\alpha}_{w}, \lVert\boldsymbol{\mu}'_{\mathbf{s}}\rVert): \boldsymbol{\mu}'_{\mathbf{s}}[x] & \equiv & \boldsymbol{\mu}_{\mathbf{s}}[x-\Delta] \tag{146} \end{eqnarray}$ 公式143表示，每次操作原先的状态$\boldsymbol{\sigma}$,原先的机器状态$\boldsymbol{\mu}$,原先的子状态A,原先的参数I，执行后为新临时状态$\boldsymbol{\sigma}’$,新的机器状态$\boldsymbol{\mu}’$,新的子状态A’,参数I不变。

公式144表示，栈的变化，其中 $\mathbf{\alpha}_{w}$ 为当前操作的入栈集合,$\mathbf{\delta}_{w}$为当前操作的出栈集合。

公式145表示，栈的长度，即为在原先栈的长度+变化的长度。

公式146表示，栈中的元素，除了新增的元素$\mathbf{\alpha}_{w}$，其余的不变。（黄皮书中栈顶是0，所以如果入栈元素多于出栈元素，则原先元素的索引都会加相应偏移）。 $\begin{eqnarray} \quad \boldsymbol{\mu}'_{g} & \equiv & \boldsymbol{\mu}_{g} - C(\boldsymbol{\sigma}, \boldsymbol{\mu}, I) \label{eq:mu_pc} \tag{147} \\ \quad \boldsymbol{\mu}'_{\mathrm{pc}} & \equiv & \begin{cases} {J_{\text{JUMP}}}(\boldsymbol{\mu}) & \text{if} \quad w = {\small JUMP} \\ {J_{\text{JUMPI}}}(\boldsymbol{\mu}) & \text{if} \quad w = {\small JUMPI} \\ N(\boldsymbol{\mu}_{\mathrm{pc}}, w) & \text{otherwise} \end{cases} \tag{148} \end{eqnarray}$ 公式147-148表示每一次迭代gas和程序计数器pc的变化。其中gas值为原有gas减去当前操作的花费，pc在JUMP和JUMPI的时候是跳转到相应位置，其余情况是加一，到下一条指令。

$\begin{eqnarray} \boldsymbol{\mu}'_{\mathbf{m}} & \equiv & \boldsymbol{\mu}_{\mathbf{m}} \tag{149}\\ \boldsymbol{\mu}'_{\mathrm{i}} & \equiv & \boldsymbol{\mu}_{\mathrm{i}} \tag{150}\\ A' & \equiv & A \tag{151}\\ \boldsymbol{\sigma}' & \equiv & \boldsymbol{\sigma} \tag{152} \end{eqnarray}$ 公式149-152，假设操作对其余的元素都不产生影响。实际上不同操作会对不同部分有影响。

七、区块的最终确定

在区块的生成过程中，更多的时候是一棵树状的结构。为了在树形结构中确认一条链作为区块链，在以太坊中定义“最重”的链为主链。这里的重指的是累计难度（td，total difficulty定义如公式153-154），也就是td最大的链为主链。 $\begin{eqnarray} B_{\mathrm{t}} & \equiv & B'_{\mathrm{t}} + B_{\mathrm{d}} \tag{153}\\ B' & \equiv & P(B_{H}) \tag{154} \end{eqnarray}$ 公式153-154表示当前区块的累积难度td值为其父区块的累积难度td值加上当前区块的难度值。

区块的最终确定涉及到四个阶段：

校验ommers。
校验交易。
计算和提交奖励。
验证世界状态和区块的nonce值。

// ValidateBody validates the given block's uncles and verifies the the block
// header's transaction and uncle roots. The headers are assumed to be already
// validated at this point.
func (v *BlockValidator) ValidateBody(block *types.Block) error {
	// Check whether the block's known, and if not, that it's linkable
	if v.bc.HasBlockAndState(block.Hash(), block.NumberU64()) {
		return ErrKnownBlock
	}
	// 验证父区块是否存在
	if !v.bc.HasBlockAndState(block.ParentHash(), block.NumberU64()-1) {
		if !v.bc.HasBlock(block.ParentHash(), block.NumberU64()-1) {
			return consensus.ErrUnknownAncestor
		}
		return consensus.ErrPrunedAncestor
	}
	// 验证ommers
	// Header validity is known at this point, check the uncles and transactions
	header := block.Header()
	if err := v.engine.VerifyUncles(v.bc, block); err != nil {
		return err
	}
	if hash := types.CalcUncleHash(block.Uncles()); hash != header.UncleHash {
		return fmt.Errorf("uncle root hash mismatch: have %x, want %x", hash, header.UncleHash)
	}
	// 验证交易的hash值
	if hash := types.DeriveSha(block.Transactions()); hash != header.TxHash {
		return fmt.Errorf("transaction root hash mismatch: have %x, want %x", hash, header.TxHash)
	}
	return nil
}

7.1 Ommer的校验

Ommer或者说uncle是指父区块的兄弟区块，以太坊中block的uncles字段用以存储uncle区块，在区块的最终确定的时候需要对ommer进行校验。

// VerifyUncles verifies that the given block's uncles conform to the consensus
// rules of the stock Ethereum ethash engine.
func (ethash *Ethash) VerifyUncles(chain consensus.ChainReader, block *types.Block) error {
	// If we're running a full engine faking, accept any input as valid
	if ethash.config.PowMode == ModeFullFake {
		return nil
	}
	// 每个区块最多有两个uncle区块
	// Verify that there are at most 2 uncles included in this block
	if len(block.Uncles()) > maxUncles {
		return errTooManyUncles
	}
	// Gather the set of past uncles and ancestors
	uncles, ancestors := set.New(), make(map[common.Hash]*types.Header)

	// 统计七代以内的区块
	number, parent := block.NumberU64()-1, block.ParentHash()
	for i := 0; i < 7; i++ {
		ancestor := chain.GetBlock(parent, number)
		if ancestor == nil {
			break
		}
		ancestors[ancestor.Hash()] = ancestor.Header()
		for _, uncle := range ancestor.Uncles() {
			uncles.Add(uncle.Hash())
		}
		parent, number = ancestor.ParentHash(), number-1
	}
	ancestors[block.Hash()] = block.Header()
	uncles.Add(block.Hash())

	// 确认该节点
	// Verify each of the uncles that it's recent, but not an ancestor
	for _, uncle := range block.Uncles() {
		// Make sure every uncle is rewarded only once
		hash := uncle.Hash()
		if uncles.Has(hash) {
			return errDuplicateUncle
		}
		uncles.Add(hash)

		// Make sure the uncle has a valid ancestry
		// 确认uncle区块是确实是uncle区块
		if ancestors[hash] != nil {
			return errUncleIsAncestor
		}
		if ancestors[uncle.ParentHash] == nil || uncle.ParentHash == block.ParentHash() {
			return errDanglingUncle
		}
		// 验证uncle区块的header
		if err := ethash.verifyHeader(chain, uncle, ancestors[uncle.ParentHash], true, true); err != nil {
			return err
		}
	}
	return nil
}

$\begin{equation} \lVert B_{\mathbf{U}} \rVert \leqslant 2 \bigwedge_{\mathbf{U} \in B_{\mathbf{U}}} {V({\mathbf{U}}})\; \wedge \; k({\mathbf{U}}, P(\mathbf{B}_{\mathbf{H}})_{\mathbf{H}}, 6) \tag{155} \end{equation}$

$\begin{equation} k(U, H, n) \equiv \begin{cases} false & \text{if} \quad n = 0 \\ s(U, H) \; \vee \; k(U, P(H)_{H}, n - 1) & \text{otherwise} \end{cases} \tag{156} \end{equation}$

$\begin{equation} s(U, H) \equiv (P(H) = P(U)\; \wedge \; H \neq U \; \wedge \; U \notin B(H)_{\mathbf{U}}) \tag{157} \end{equation}$ 在以太坊中一个区块的

兄弟区块$s(U, H)$定义如公式157，兄弟区块是指与区块自身有不同，且父区块相同$(P(H) = P(U) \wedge H \neq U $；并且该兄弟区块不在自己的uncles区块中$U \notin B(H)_{\mathbf{U}}$
U是否是H的n代以内uncle定义如公式156，若n为0，则返回false（没有0代的概念），否则要么U是H的兄弟区块（一代），要么U是H的父区块的n-1代叔区块。
uncle区块数目不超过2个，$\lVert B_{\mathbf{U}} \rVert \leqslant 2$,公式155
uncle区块为7代以内的区块, ${V({\mathbf{U}}})\; \wedge \; k({\mathbf{U}}, P(\mathbf{B}_{\mathbf{H}})_{\mathbf{H}}, 6)$ （公式里为父区块的6代以内,即自己的兄弟区块是不会包含在内的）

7.2 校验交易

$\begin{equation} {B_{H}}_{\mathrm{g}} = {\ell}({\mathbf{R})_{\mathrm{u}}} \tag{158} \end{equation}$

校验block中的txHash是否为block.Transaction的hash。见本章开始部分代码中ValidateBody的最后部分。
虚拟机逐条执行交易，执行后校验所用的gas值是否和区块的已用gas值相同，见公式158.
校验虚拟机执行后的bloom以及receipt是否与区块头中的bloom以及receiptHash相同。
校验虚拟机执行之后的世界状态的树的根是否与区块头中的Root相同。

// ValidateState validates the various changes that happen after a state
// transition, such as amount of used gas, the receipt roots and the state root
// itself. ValidateState returns a database batch if the validation was a success
// otherwise nil and an error is returned.
func (v *BlockValidator) ValidateState(block, parent *types.Block, statedb *state.StateDB, receipts types.Receipts, usedGas uint64) error {
	header := block.Header()
	// 校验交易的usedGas是否为区块的GasUsed
	if block.GasUsed() != usedGas {
		return fmt.Errorf("invalid gas used (remote: %d local: %d)", block.GasUsed(), usedGas)
	}
	// Validate the received block's bloom with the one derived from the generated receipts.
	// For valid blocks this should always validate to true.
	rbloom := types.CreateBloom(receipts)
	if rbloom != header.Bloom {
		return fmt.Errorf("invalid bloom (remote: %x  local: %x)", header.Bloom, rbloom)
	}

	// 校验收款的hash值
	// Tre receipt Trie's root (R = (Tr [[H1, R1], ... [Hn, R1]]))
	receiptSha := types.DeriveSha(receipts)
	if receiptSha != header.ReceiptHash {
		return fmt.Errorf("invalid receipt root hash (remote: %x local: %x)", header.ReceiptHash, receiptSha)
	}
	// 校验state
	// Validate the state root against the received state root and throw
	// an error if they don't match.
	if root := statedb.IntermediateRoot(v.config.IsEIP158(header.Number)); header.Root != root {
		return fmt.Errorf("invalid merkle root (remote: %x local: %x)", header.Root, root)
	}
	return nil
}

7.3 计算奖励

$\begin{eqnarray} \Omega(B, \boldsymbol{\sigma}) & \equiv & \boldsymbol{\sigma}': \boldsymbol{\sigma}' = \boldsymbol{\sigma} \quad \text{except:} \tag{159}\\ \qquad\boldsymbol{\sigma}'[{\mathbf{B}_{H}}_{\mathrm{c}}]_{\mathrm{b}} & = & \boldsymbol{\sigma}[{\mathbf{B}_{H}}_{\mathrm{c}}]_{\mathrm{b}} + \left(1 + \frac{\lVert \mathbf{B}_{\mathbf{U}}\rVert}{32}\right)R_{\mathrm{block}} \tag{160}\\ \qquad\forall_{\mathbf{U} \in \mathbf{B}_{\mathbf{U}}}: \tag{161}\\ \nonumber \boldsymbol{\sigma}'[\mathbf{U}_{\mathrm{c}}] & = & \begin{cases} \varnothing &\text{if}\ \boldsymbol{\sigma}[\mathbf{U}_{\mathrm{c}}] = \varnothing\ \wedge\ R = 0 \\ \mathbf{a}' &\text{otherwise} \end{cases} \\ \mathbf{a}' &\equiv& (\boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathrm{n}}, \boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathrm{b}} + R, \boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathbf{s}}, \boldsymbol{\sigma}[U_{\mathrm{c}}]_{\mathrm{c}}) \tag{162}\\ R & \equiv & \left(1 + \frac{1}{8} (U_{\mathrm{i}} - {B_{H}}_{\mathrm{i}})\right) R_{\mathrm{block}} \tag{163} \end{eqnarray}$

$\begin{equation} \text{Let} \quad R_{\mathrm{block}} = 3 \times 10^{18} \tag{164} \end{equation}$

矿工的奖励为固定奖励$R_{block}$如公式164,如果区块uncles不为空，则每个uncle会带来额外32分之一的$R_{block}$奖励。如公式160，矿工的余额为原余额加上奖励。
对于该区块中的uncles，每个uncle块，计算其矿工的奖励，如公式163，是根据uncle块与当前块的代差来计算的。例如差1代，uncle块为当前块父区块的兄弟，那么该uncle块的矿工可以拿到八分之七的$R_{block}$奖励。差的代数越多，拿到的奖励越少。

// AccumulateRewards credits the coinbase of the given block with the mining
// reward. The total reward consists of the static block reward and rewards for
// included uncles. The coinbase of each uncle block is also rewarded.
func accumulateRewards(config *params.ChainConfig, state *state.StateDB, header *types.Header, uncles []*types.Header) {
	// Select the correct block reward based on chain progression
	blockReward := FrontierBlockReward
	if config.IsByzantium(header.Number) {
		blockReward = ByzantiumBlockReward
	}
	// Accumulate the rewards for the miner and any included uncles
	reward := new(big.Int).Set(blockReward)
	// 计算uncle块中矿工的奖励
	r := new(big.Int)
	for _, uncle := range uncles {
		r.Add(uncle.Number, big8)
		r.Sub(r, header.Number)
		r.Mul(r, blockReward)
		r.Div(r, big8)
		state.AddBalance(uncle.Coinbase, r)

		r.Div(blockReward, big32)
		reward.Add(reward, r)
	}

	// 当前矿工的奖励为固定奖励加上跟uncle区块数量相关的一部分奖励
	state.AddBalance(header.Coinbase, reward)
}

7.4 校验state和nonce

区块执行前的世界状态定义为$\Gamma(B)$,如公式165，即执行Process之前的世界状态。
执行即对区块的每条交易，运行交易转换函数（虚拟机执行，ApplyTrasaction）如公式170，每条交易执行完后，走区块的转换函数（Finalize，增加矿工奖励等），如公式169和174所示。
执行交易过程中会产生交易的收据证明，相关内容如公式171-173所示。

执行后的区块与最终区块的主要区别为区块头中的nonce值，mixHash值，如公式166-168所示。

// Process processes the state changes according to the Ethereum rules by running
// the transaction messages using the statedb and applying any rewards to both
// the processor (coinbase) and any included uncles.
//
// Process returns the receipts and logs accumulated during the process and
// returns the amount of gas that was used in the process. If any of the
// transactions failed to execute due to insufficient gas it will return an error.
func (p *StateProcessor) Process(block *types.Block, statedb *state.StateDB, cfg vm.Config) (types.Receipts, []*types.Log, uint64, error) {
  var (
      receipts types.Receipts
      usedGas  = new(uint64)
      header   = block.Header()
      allLogs  []*types.Log
      gp       = new(GasPool).AddGas(block.GasLimit())
  )
  // Mutate the the block and state according to any hard-fork specs
  if p.config.DAOForkSupport && p.config.DAOForkBlock != nil && p.config.DAOForkBlock.Cmp(block.Number()) == 0 {
      misc.ApplyDAOHardFork(statedb)
  }
  // Iterate over and process the individual transactions
  for i, tx := range block.Transactions() {
      // 虚拟机执行每条交易
      statedb.Prepare(tx.Hash(), block.Hash(), i)
      receipt, _, err := ApplyTransaction(p.config, p.bc, nil, gp, statedb, header, tx, usedGas, cfg)
      if err != nil {
          return nil, nil, 0, err
      }
      // 得到交易的收据与日志
      receipts = append(receipts, receipt)
      allLogs = append(allLogs, receipt.Logs...)
  }
  // Finalize the block, applying any consensus engine specific extras (e.g. block rewards)
  p.engine.Finalize(p.bc, header, statedb, block.Transactions(), block.Uncles(), receipts)

  return receipts, allLogs, *usedGas, nil
}

$\begin{equation} \Gamma(B) \equiv \begin{cases} \boldsymbol{\sigma}_0 & \text{if} \quad P(B_{H}) = \varnothing \\ \boldsymbol{\sigma}_{\mathrm{i}}: \mathtt{\small {TRIE}}(L_{S}(\boldsymbol{\sigma}_{\mathrm{i}})) = {P(B_{H})_{H}}_{\mathrm{r}} & \text{otherwise} \end{cases} \tag{165} \end{equation}$ 公式165定义区块执行前的世界状态为$\Gamma(B)$，如果父区块为空，则世界状态为创世块状态，否则执行前的世界状态为其父区块头对应的世界状态树。 $\begin{eqnarray} \Phi(B) & \equiv & B': \quad B' = B^* \quad \text{except:} \tag{166}\\ B'_{\mathrm{n}} & = & n: \quad x \leqslant \frac{2^{256}}{H_{\mathrm{d}}} \tag{167}\\ B'_{\mathrm{m}} & = & m \quad \text{with } (x, m) = \mathtt{PoW}(B^*_{\cancel {n}}, n, \mathbf{d}) \tag{168}\\ B^* & \equiv & B \quad \text{except:} \quad {B^*_{\mathrm{r}}} = {r}({\Pi}(\Gamma(B), B)) \tag{169} \end{eqnarray}$ 公式166-169定义了区块的世界状态为在执行了转换函数之后${\Pi}$，其nonce值和mixHash值需要满足PoW即难度需求。 $\begin{equation} \boldsymbol{\sigma}[n] = \begin{cases} {\Gamma}(B) & \text{if} \quad n < 0 \\ {\Upsilon}(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n]) & \text{otherwise} \end{cases} \tag{170} \end{equation}$

公式170定义了第n条交易时的世界状态。当n小于0时，世界状态如前定义为${\Gamma}(B)$,否则第n条交易时的世界状态为在第n-1条交易的基础上应用交易转变函数（执行交易）。

$\begin{equation} \mathbf{R}[n]_{\mathrm{u}} = \begin{cases} 0 & \text{if} \quad n < 0 \\ \begin{array}[b]{l} \Upsilon^g(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n]) + \mathbf{R}[n-1]_{\mathrm{u}} \end{array} & \text{otherwise} \end{cases} \tag{171} \end{equation}$ $\begin{equation} \mathbf{R}[n]_{\mathbf{l}} = \Upsilon^{\mathbf{l}}(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n]) \tag{172} \end{equation}$ $\begin{equation} \mathbf{R}[n]_{\mathrm{z}} = \Upsilon^{\mathrm{z}}(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n]) \tag{173} \end{equation}$

$\mathbf{R}[n]_{\mathrm{z}},\mathbf{R}[n]_{\mathrm{l}},\mathbf{R}[n]_{\mathrm{u}}$ 分别表示对应的第n条交易的状态码，日志，以及累积消耗的gas值。

$\mathbf{R}[n]_{\mathrm{u}}$ 的计算如公式171所示，为第n-1个的累积消耗 $\mathbf{R}[n-1]_{\mathrm{u}}$ , 加上当前交易的消耗 $\Upsilon^g(\boldsymbol{\sigma}[n - 1], B_{\mathbf{T}}[n])$ 。
$\mathbf{R}[n]_{\mathrm{l}}$为在原先的日志基础上增加相应的交易日志。
$\mathbf{R}[n]_{\mathrm{z}}$为在原先的状态码列表上增加相应的状态码。

$\begin{equation} \Pi(\boldsymbol{\sigma}, B) \equiv {\Omega}(B, \ell(\boldsymbol{\sigma})) \tag{174} \end{equation}$ 公式174表示最终的区块为在最后交易后的世界状态上$\ell(\boldsymbol{\sigma})$,使用完善区块的转化函数${\Omega}$（即本章的内容，计算奖励等等）

 以太坊黄皮书详解（二）搭建以太坊私链环境 