摘要： Hashgraph是一种数据采用有向无环图(DAG)结构的区块链共识算法,Hashgraph引入了虚拟投票的概念,允许节点在无额外通信开销的情况下并发出块,实现异步场景下的拜占庭容错。然而,Hashgraph提出的虚拟投票算法存在算法时间复杂度较高、共识运行逻辑过于复杂等问题。为此,提出一种基于路径存储表的Hashgraph优化方案。首先,提出一种基于顶点可达表的见证人判定方法,通过存储路径的方式实时记录生成事件与历史事件的可达关系,在轮次划分阶段,通过查询顶点事件的可达信息取代回溯算法,降低见证人判断算法的时间复杂度;其次,针对顶点可达表无法跨轮次判断事件关系的问题,提出一种基于历史可达表的知名见证人判定方法,历史可达表将存储见证人与历史事件之间的可达关系,通过查询历史可达表解决知名见证人判定阶段需要反复回溯视图的问题;最后,根据顶点可达表和历史可达表改进Hashgraph中复杂的共识计算,提升算法效率,加快事件确认速度。实验结果表明,所提优化方案与Hashgraph原共识算法相比,算法运行效率提升65.76%,在吞吐量方面平均提升41.27%。

关键词: 区块链, 共识算法, 有向无环图, Hashgraph协议, 拜占庭容错

Abstract: Hashgraph is a blockchain consensus algorithm that uses a Directed Acyclic Graph (DAG) structure in the database. Hashgraph introduces the concept of virtual voting, which allows nodes to send out blocks concurrently without additional communication overheads and achieves Byzantine fault tolerance in asynchronous scenarios. However, the virtual voting algorithm proposed by the Hashgraph has a high algorithmic time complexity, and the consensus operational logic is too complex. Accordingly, this study proposes a Hashgraph optimization scheme based on path storage tables. First, a witness determination method based on a vertex reachability table is proposed. The method records the reachability relationship between the generated and historical events in real time through storage paths. In the round partitioning stage, the backtracking algorithm is replaced by a function that queries the reachability information of the vertex events to reduce the time complexity of the witness determination algorithm. Second, a well-known witness determination method based on a historical reachability table is proposed to address the issue where the vertex reachability table cannot determine event relationships across rounds. The historical reachability table stores the reachability relationship between witnesses and historical events. It solves the problem of repeatedly backtracking views during the well-known witness determination stage by querying the historical reachability table. Finally, based on the vertex and historical reachability tables, the complex consensus calculation in the Hashgraph is improved to enhance the algorithm's efficiency and accelerate event confirmation speed. Experimental results show that, compared with the original Hashgraph consensus algorithm, the proposed optimization scheme improves algorithm efficiency by 65.76% and throughput by an average of 41.27%.

Key words: blockchain, consensus algorithm, Directed Acyclic Graph(DAG), Hashgraph protocol, Byzantine fault tolerance

中图分类号: 

• TP391