基本思路

矿工在挖矿的时候把交易的依赖关系写入到区块当中，其他节点收到这个新的区块之后根据区块里的依赖关系并行验证交易
1、矿工：依赖生成
2、同步：并行验证

理论支持

1. 普通转账交易：如果两笔交易的发送者和接收者都个不相同，那么可以同时执行这两笔交易（以太坊是基于账户的区块链，转账是一个原子操作：发送者的余额减去一个数字，接收者余额加上这个数字）。
2. 智能合约交易：如果两笔交易在执行过程（可能会调用多个合约，合约调用是产生冲突的根源）中，如果没有产生竟态冲突（在同一个存储树中，读写和写写产生冲突），这两笔交易可以同时执行。

依赖关系建立

以太坊账户定义：

type Account struct {
    Nonce    uint64
    Balance  *big.Int
    Root     common.Hash // merkle root of the storage trie
    CodeHash []byte
}

约定：

1. 同一个区块里的交易记为 {T1，T2...Tn}
2. Tm 依赖于 Tn 视为 Tn 执行完成才能执行 Tm
3. 如果 Tm 和 Tn（m<n）有冲突，视为 Tn 依赖于 Tm（在同一个区块里，交易序号小的先执行是一个隐形规则）

冲突点：

1. 同一个交易发送者
2. 同一个交易接收者
3. 一个交易接收者（发送者）是另一个交易的发送者（接收者）
4. 读写修改或者同时修改了同一个存储树（一个合约账户有一个存储树）

实质：每一次的交易执行本质是对世界树的更改（例如交易 A 转给 B10 个 ETH，则世界树中 A 的 nonce 加一和 balance 减 10,B 的 balance 加 10，这里忽略手续费和奖励）

并行化验证交易框架

1. 在启动时开启 N 个交易处理协程，等待交易到达后并行执行，返回执行结果（正确执行或者错误）
2. 收到一个区块后，从区块中获取交易的依赖关系，把没有依赖的交易发送到交易处理协程去执行
3. 等待执行结果返回，如果有错误返回，终止这个区块验证，返回错误；如果正确返回，去除对这个交易的依赖，找出新的没有依赖的交易去执行
4. 直到所有交易都执行完毕，此区块的交易并行化验证完毕，返回收据等数据

并行化验证更改要点

1. 在 core/state_processor 中，Process 方法线性处理一个区块的交易，在这里添加一个方法 MulProcess 并行验证一个区块的交易。
2. 交易执行可能会写 Log（包含在 Receipt 之中），有一些字段（交易哈希和交易序号等）是 statedb 填充的，需要移到 EVM 中（并行时有一个 statesb 和多个 EVM）
3. 收据的字段 PostState（交易执行后世界树的根）和 CumulativeGasUsed（交易执行后的累计 gas 花费）因为并行化执行交易无法确定，可以废弃甚至去掉这两个字段
4. 并行执行时 gasPool 可能会意外的耗尽（一笔交易执行前先扣除一定 Gas，执行完成会返还未消耗的 Gas，多次扣除还未返还），可以考虑去掉
5. 虽然在理论上底层数据更改不冲突，但是操作同一个 statedb，有一些字段可能线程不安全，针对于多个虚拟机操作同一个 statedb 需要做线程安全化
6. 交易执行失败导致世界恢复的情况比较复杂，以前是基于 statesb 的日志，并行执行后日志恢复不再安全，一是让此交易单独执行（完全依赖），二是把世界恢复移到 EVM 中
7. statedb 存储了交易退费余额，应该考虑移到虚拟机里去

冲突分析

以太坊交易在执行过程中会更改账户的 nonce、balance、code、storageTrie，这些都可能是并行执行交易的冲突点
在交易的执行流程中分析可能产生的地方： 预检查（nonce 和扣 gas） -> evm 执行交易 -> 退还 gas 和激励矿工

1. 交易执行之前需要检查交易发起者的 nonce 是否和世界树的一致和预扣 gas 费用（gasprice × gaslimit）
   caller nonce read
   caller balance write

2. 判断是否合约创建交易（交易接受者为空），决定如何进入到虚拟机里执行交易

   1. 否，将交易发起者的 nonce 加一，执行 call 调用
      caller nonce write
   2. 是，执行 create 调用

3. call 和 create 都是 evm 虚拟机的一个指令，是交易在 evm 里执行的第一个指令，其中可能会加载合约来执行，从而调用所有的 evm 指令

   1. Create 指令

      1. 检查 caller 的 balance 是否足够转账
         caller balance read
      2. caller 的 nonce 加一
         caller nonce write
      3. 验证目标地址是否存在合约且 nonce 等于 0
         addr nonce read
         addr code read
      4. 做一个快照，如果是 eip158 区块则目标地址 nonce 加一
         addr nonce write
      5. caller 向目标地址转一定数量的 ETH，如果转 0 个 ETH？
         caller balance write
         addr balance write
      6. 执行部署合约代码，执行成功则设置目标地址的 code
         addr code write
      7. 扣除已经使用的 gas，如果执行的 code 有错误，使用快照恢复，evm 执行交易完成

   2. Call 指令，中途可能意外结束并返回，另外，CallCode、DelegateCall、StaticCall 等指令与 Call 类似

      1. 检查 caller 的 balance 是否足够转账，做一个快照
         caller balance read
      2. 判断目标地址是否存在（全部字段为 0），有 code 才会有 storageTrie？storageTrie 不必记录？
         addr nonce read
         addr balance read
         addr code read
         1. 如果不存在，且不是无意义的调用（是 eip158 区块和转 0 个 ETH），显式创建空账户，不记录？
      3. caller 向目标地址转一定数量的 ETH，如果转 0 个 ETH？
         caller balance write
         addr balance write
      4. 读取目标地址的 code 来执行，code 可以包括所有的 evm 指令 (code 为空则忽略)
         addr code read
      5. 扣除已经使用的 gas，如果执行的 code 有错误，使用快照恢复，evm 执行交易完成
   3. Balance 指令，获取账户余额，没有设置账户余额的指令，只有执行 Call、Create 才会有转账
      addr balance read
   4. ExtCodeSize、ExtCodeCopy 指令分别获取指定地址的 code 长度和 code，codesize 和 codehash 由 code 而来
      addr code read
   5. ExtCodeHash 指令会先判断账户是否为空再获取 codehash，没有直接设置 code 的指令，Create 才会设置 code
      addr nonce read
      addr balance read
      addr code read
   6. Sload 指令读取指定地址 loc 位置的存储的值
      addr storage loc read
   7. Sstore 指令写入值到指定地址的 loc 位置
      addr storage loc write
   8. Suicide 指令，将指定地址的 ETH 转给调用者，且清空账户（只是做了 suicided 标记，交易执行完成更新世界树才会被删除, 中途还可以操作这个账户？）
      addr nonce write
      addr balance write
      addr code write
      caller balance write

4. 调用 evm 执行交易完成之后，将剩余的 gas 返还给 caller，把用掉的 gas 奖励给矿工
   caller balance write // 前面扣 gas 已经记录，可以不用记录
   coinbase balance write // 区块每笔交易都会加，一般不影响，区块内的交易操作 coinbase 的 balance？

5. 每个指令执行之前会计算 gas 消耗，计算 gas 的方法中可能会查询账户的状态

   1. gasCall，判断目标账户是否存在，Call 指令中都会判断，判断不全？
   2. gasSstore，获取指定位置的初始值和当前值，当前值覆盖初始值？
   3. gasSuicide，判断目标账户是否存在且会返还 ETH，判断不全？