[论文研读] Enabling Concurrency on SmartContracts Using Multiversion Ordering

目标

矿工产生区块之后，该区块会被多个验证节点进行验证，执行多次，因此提高智能合约的并行化，尤其是验证阶段的并行化，可以提升整个平台的效率和吞吐量。

贡献

提出MVTO并发机制。矿工使用任意的并发控制机制来产生冲突调度，验证者使用MVTO机制确定性并发重放该调度。

方法

矿工：

可以使用任意的并发机制来并发执行交易，执行结束后需要生成以下两个信息：

1. 每笔交易的写集；
2. 所有交易的一个串行序列；（其实主要是为了给有冲突的交易确定顺序）

验证者：

每笔交易的状态有四种：Init、Active、Abort、Commit。

主要做以下几件事情：

1. 根据交易的写集构建共享变量的“写链”；

a:	Node3 -> Node1 -> Node5
b:	Node1 -> Node5 -> Node6
c:	Node3 -> Node2 -> Node4

每个Node主要包含三个item：交易序号、是否已写，新值。

2. 处理读操作

读操作根据共享变量的修改环境，可以分为交易内读操作和交易间读操作。

交易内读操作所获得的数据来自于交易内位于该读操作之前的写操作（同一个共享变量）。对于此类型操作，直接读取当前交易所修改的数据即可。

交易间读操作所获得数据来自于当前交易的上一笔交易（共享变量的写链中）。对于此类型操作，读取过程如下：

        a. 在该共享变量的写链中，找到当前交易的上一笔交易；

       b. 如果没有上一笔交易，说明这是修改该共享变量的第一笔交易，直接读取共享变量的值即可；

        c. 如果有上一笔交易，判断该交易的执行状态： 

执行状态	触发动作
Init	等待
Active	检查该交易的item“是否已写”。如果是已写，则直接读，否则等待；（在该状态下，由于该笔交易有可能在后续操作中被中断，因此读操作所在的交易需要在提交之前检查数据的一致性）
Abort	继续向前查找非Abort状态的交易
Commit	直接读取

3. 处理写操作

        a. 检查写入操作是否合法，合法则写入，否则中断。合法性的判断即在该共享变量的写链中检查是否存在。

测试

变量：负载，中断比例，冲突比例，线程池大小。

这些变量的设置都是通过合约中的功能来控制的。比如“中断比例”，是一定比例的合约在执行完成之后被设置为中断。

变量	MVTO
Workload (15%C，10%A, 3T)	大于4000，比serial更好； 20000时，达到2.5x。
Confict percentage (20000W, 10%A, 3T)	低于60%，比serial更好； 0%时，达到2.5x。
Abort percentage (20000W, 15%C, 3T)	比例越高，提速越多 0%时，最低时2.5x。
Thread pool (20000W, 10%A) CPU只有4核	冲突比例为0%时，随着线程数量提升，从2.5x (3T)最高提升到4x (15T)； 冲突比例为15%时，随着线程数量提升，稳定在2.5x左右。

摘抄

1. Despite having the advantages such as tamper-proof and Byzantine-faulttolerant provided by blockchain, smart contract platforms suffer from the limitation of throughput. This limitation is partly prompted by the lack of concurrent mechanisms in existing smart contracts designs.
2. Furthermore, Ethereum is planning to change its consensus protocol from proof of work (POW) to an energy saving protocol called proof of stake(POS). After switching to POS, Ethereum can significantly save time originally needed in the POW phase. In this trend, Ethereum can execute smart contracts that are more complicated and time-consuming.
3. There are three reasons why smart contracts can not employ naive concurrent solution. First, a smart contract can be called several times by different transactions during a block’s execution and therefore race conditions may occur when those calls of the same contract execute in parallel. Second, smart contracts need to execute transactionally. In other words, if Ethereum executes multiple transactions concurrently, it must produce a conflict-serializable schedule where the final states can be produced by a serial schedule1. Third, validating a block requires deterministic execution which can not be provided by naive concurrency approach.
4. A block only gets executed one time when created by miners. If this block is accepted, every node in the network will validate this block. Thus, improving the efficiency of block validation is more important than block generation in mining phase.
5. A serial schedule is a schedule that meets the following conditions: (i) the actions that belong to the same transaction preserve the order in transaction; (ii) the actions that belong to different transactions don’t interleave with each other.
6. Conflict-Serializable Schedule. Two schedules are conflict-equivalent if they can turn into each other by swapping adjacent non-conflicting data actions. A schedule is conflict-serializable if it is conflict-equivalent to a serial schedule. The serial order of a conflict-serializable schedule is the transaction order of the serial schedule which it conflict-equivalent with.
7. A schedule needs to be recoverable to prevent this dirty data issue. A recoverable schedule is a schedule where each transaction commits only after all its read-from transactions have committed. In this way, the changes made by the transaction that read dirty data are still revertable because the transaction must wait for its read-from transactions to commit.
8. Since smart contracts are written in Turing-compete languages, it is impossible in general to statically determine which data actions a smart contract will perform.