【论文研读】-A Parallel Smart Contract Model

背景

随着区块链技术的飞速发展，区块链成为执行智能合约的良好平台。然而，由于智能合约在区块链上的交易处理性能仍然很低。在某些情况下它不能满足实时要求。本文提出了一种基于区块链的并行智能合约模型，该模型在交易处理方面具有更好的性能。所提出方法的挑战是并行模式的实现和所提出模型的同步问题的解决方案。本文使用多线程技术来实现所提出的模型，其中事务是并行执行的。然后我们提出了一种事务拆分算法来解决同步问题。最后，实验分析证明，这种并行模型正是在事务处理性能上取得了显着的进步。

贡献

本文提出了一种新的智能合约模型。它使用多线程技术 [5] 并行执行智能合约。使用这种新模型处理交易可以降低平均时间成本，并使智能合约在区块链上获得更好的性能。

主要贡献：

我们分析了当前典型的智能合约模型并总结了它的缺点。我们提出了一种并行智能合约模型，在交易处理上具有更好的性能。我们提出了一种交易拆分算法来解决并行智能合约模型中的同步问题。我们测试了我们提出的算法和并行模型的性能。

（个人认为：主要介绍了一种将有共享资源的交易划分为不同的交易集的算法）

合约执行流程和改进后的流程

未改进的智能合约流程

图中分为五步但是总结下来流程如下：

将要处理的交易会调用其相应的合约。通过分析交易内容，EVM 得到来自交易和状态数据库的相应合约代码和合约输入。合约代码在 EVM 中执行，状态变量的更改将被写回状态数据库。当一个区块中的所有交易都已经被执行时，状态数据库的当前状态将被记录在区块链中作为证明。

改进后智能合约流程

执行过程可以概括为：

Step1：当区块链系统从交易池中获得足够多的有效交易时，就会开始处理这些交易。Step2：事务拆分组件对事务进行分析，得到共享变量的信息。然后，该组件将事务分组到不同的集合中，这些集合彼此之间没有相同的共享变量。最后，这些事务集将被发送到多线程处理组件。Step3：多线程处理组件将这些事务处理工作分配给各个线程。Step4：线程开始运行并从状态数据库中获取必要的初始数据，例如合约代码。然后，调用的合约就可以执行了。Step5：合约代码将被执行，然后代码将完成其对应的智能合约的业务逻辑。Step6：智能合约执行会改变一些相关的状态变量，这些改变最终会被写回状态数据库。Step7：当所有智能合约完成后，区块链系统会进行状态数据库的认证（即在以太坊中，状态数据库的认证是MPT的根），然后将所有处理过的交易和认证记录到区块链中.

总结下来：改进后和改进前的区别主要就是两点：一个是引入将有共享资源交易划分为同一个交易集合的交易分割算法，这里作者将有共享资源的交易划分为三类（没有共享资源的交易、有直接共享资源的交易、有间接（两个交易之间没有直接共享资源，需要第三个交易插入才行）共享资源的交易），最后将直接和间接共享资源的交易划分为有关系的交易，划分为一个交易集里，主要介绍了交易分割的算法和算法实现后实验结果对比，成功将之前串行化进行智能合约转化为并行的，减少智能合约执行时间；二个是进行多线程组，将不用的交易集放到不同的线程组里面进行交易（本文并没有进行这个方面的详细阐述）。

交易分割算法的阐述

算法一：用来判断两个交易是否相关，通过输入交易集来获得相关交易集

算法二：在我们得到每个事务的相关集合后，我们可以很容易地将所有事务之间的关系转换为无向图。然后我们设计了一种基于 BFS （广度优先搜索算法）的拆分算法，将相关事务拆分为同一个子集。表 2 显示了伪代码。通过输入交易集和相关集，我们最终可以得到不相关的交易集。（这个我在进行算法实现的时候出现算法本身出现的问题，这个位置的伪代码逻辑上有问题，具体详细的过程应该是在算法一的基础上进行交易的合并，比如交易1和交易2有共享资源，交易2和交易3有共享资源，我们通过他们之间的关系，从而建立起一个集合里面包括交易1、2、3三个交易，这才是算法2应该完成的事情）

发现上述代码无法实现之后，我尝试自己进行重新更改伪代码：

* 伪代码如下：
 * create set N
 * while T is not empty
 *      get a transaction tx from T
 *      create a set Q
 *      txQ
 *      presize=0
 *      while Q.size()>presize
 *          presize=Q.size()
 *          Q→txi
 *          R.iterator()
 *              while(R.hasNext())
 *              if(R.next().contain(txi)){
 *                  Q.add(txi);//txi不同于tx
 *              }
 *      Q→N
 * return N
 */

最后进行代码实现：

public class testAsplitTx {
    /*判断两个交易是否有共享资源*/
    public boolean isRelated(int[] T1,int [] T2){
        int n1=T1.length;
        int n2=T2.length;
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j <n2; j++) {
                if(T1[i]==T2[j]){
                    return true;
                }
            }
        }
        return false;
    }
    /*创建有关系的交易集*/
    public Set<Set<int []>> CreateRelatedTransactionSets(Set<int []> T){
        Set<Set<int []>> R =new HashSet<>();
        Iterator<int []> it=T.iterator();

        while (it.hasNext()){
            Set<int[]> S=new HashSet<>();
            int [] Txi=it.next();
            S.add(Txi);
            Iterator<int []> it1=T.iterator();
            while(it1.hasNext()){
                int[] Txj = it1.next();
                if (isRelated(Txi,Txj)){
                    S.add(Txj);
                }
            }
        R.add(S);
        }
        return R;
    }
    public Set<Set<int []>> splittingTransactions(Set<int []> T,Set<Set<int []>> R){
        /*由于CreateRelatedTransactionSets创建了交易之间彼此的关系，相当于创建了交易上面的FROM到TO的关系，这里我们就是去实现他们之间交易依赖
        关系图，把所有有依赖关系的交易放置到一个集合里面。
        实现方法：利用集合不会再添加的属性，来不断将交易去问询所有的关系依赖图中的交易，直到没有交易增加*/
        Set<Set<int []>> N= new HashSet<>();
        Iterator<int[]> iterator = T.iterator();
        while(iterator.hasNext()){
            int [] Txi=iterator.next();
            Set<int []> Q=new HashSet<>();
            Q.add(Txi);
            int presize=0;
            while (Q.size()>presize){
                presize=Q.size();
                for (int[] temp_Tx:Q){
                    for (Set<int []> next:R){
                        if (next.contains((temp_Tx))){
                            for (int [] temp_Array:next){
                                Q.add(temp_Array);
                            }
                        }
                    }
                }             
            }
            N.add(Q);
        }
        return N;
    }
    public static void main(String[] args) {
    //其中每个数组里面的整型数代表交易里面的资源，有相同的数则代表会有交易上面的依赖冲突
        int [] Tx1={1,2,3};
        int [] Tx2={1,6};
        int [] Tx3={6};
        int [] Tx4={4};
        int [] Tx5={4,7};
        int [] Tx6={5};
        Set<int []> T =new HashSet<>();
        T.add(Tx1);
        T.add(Tx2);
        T.add(Tx3);
        T.add(Tx4);
        T.add(Tx5);
        T.add(Tx6);

        testAsplitTx taspTx=new testAsplitTx();
        Set<Set<int[]>> sets = taspTx.CreateRelatedTransactionSets(T);
        Set<Set<int[]>> sets1 = taspTx.splittingTransactions(T, sets);
        Iterator<Set<int[]>> iterator = sets1.iterator();
        while(iterator.hasNext()){
            Iterator<int[]> iterator1 = iterator.next().iterator();
            while (iterator1.hasNext()){
                int[] next = iterator1.next();
                for (int i = 0; i < next.length ; i++) {
                    System.out.print(next[i]+" ");
                }
            }
            System.out.println();
        }
    }

}

最后输出的结果：

4 4 7 
5 
1 2 3 6 1 6 

结果说明：4代表Tx4，4 7代表Tx5，都是对应上述的main函数里面的各个交易。

最后分析算法复杂度，得出两个结论：

事务拆分算法的时间成本与属于这些事务的共享变量的数量呈正线性相关。交易拆分算法的时间成本与每个区块的交易数量呈正线性相关。 实验结果

主要比较并行化智能合约相较于串行化的时间上优化：

并行模型相较于串行模型时间上的对比

结果阐明： 根据这两种模式的比较。结果表明，我们提出的并行智能合约模型确实比串行智能合约模型具有更好的性能。此外，在每个区块包含 3500 笔交易的情况下，它至少可以节省 23.8% 的时间成本，在每个区块包含 1000 笔交易的情况下，最多可以节省 41.9% 的时间成本。因此，我们最终可以证明，所提出的并行模型比当前的串行智能合约模型具有显着的性能提升。

这篇文章的总结

主要介绍智能合约在静态分下的智能合约并行化的执行的文章，文章行文比较简单，智能合约流程介绍比较清楚，主要改进在对交易的划分和多线程组执行上，但是介绍的交易划分方面主要体现在算法上，对于交易中的共享资源如何进行判断和划分并没有明确的指明，这篇文章比较大的漏洞，还有在多线程上进行不用交易集上的时间长短也会在一定程度上影响智能合约执行i的时间，这个也是没有去考虑的问题，以及提出的交易度的定义和间接有关系的交易图细节上面也存在问题。

建议想要详细阅读这篇文章的读者重点阅读交易分割算法 即可。