基于时间排序的监督共识算法

牟 平， 梁鉴如

(上海工程技术大学，上海 201620)

0 引 言

Satoshi Nakamoto在2008年提出了bitcoin[1]，描述了一种全新的电子货币及其算法。它的不可篡改、多方维护的特性，引起了各个领域的广泛关注，其重要底层技术之一的区块链也吸引了诸多研究者关注。

在传统的数据系统中，账本上的一系列信息往往由一个中心服务器进行记录，这种设计特性，节省了使用成本、保证了数据的强一致性、规避了分区容错性但却使得可用性风险极高[2]。在数据储存阶段，采用多备份容灾，足以抵御自然条件下的偶发灾害。相较而言，恶意的节点对传统分布式数据系统造成的问题要严重得多，典型的有DDOS攻击，冒充客户端提交虚假信息，攻击中心服务器篡改用户提交的信息，篡改历史信息等[3-4]。这对新型的数据系统分布式系统带来了以下挑战：在一个无中心，弱信任的分布式系统中，如何让各个节点在指定时间内达成共识[5]。

所谓共识，简单来说就是分布式系统中节点对某个数值或状态的承认[6]。Lynch基于如今的计算机技术和网络技术的结构提出了CAP理论[7]，认为分布式系统不可能同时满足一致性(consistency)、可用性(availability)和分区容错性(partition tolerance)这三个基本需求，最多只能同时满足其中两项。业界在分布式的实际使用中，对CAP特性进行进一步权衡，由Dan Pritchett总结为主要特征为基本可用(basically available)、软状态(soft state)和最终一致性(eventually consistent)的BASE原理。Gray在1978提出了2PC(concurrency control and recovery in database systems)通过两阶段进行事务提交，但如果从节点失效则会发生事务阻塞，使系统崩溃。为增强系统健壮性，Skeen在1981年提出(3PC)通过三阶段进行事务提交，降低了数据不一致的概率。……