一种基于DAG和分片的区块链异步共识算法

一种基于dag和分片的区块链异步共识算法
技术领域
1.本发明涉及区块链共识算法技术领域，具体的说是一种基于dag和分片的区块链异步共识算法。


背景技术：

2.作为最流行的分布式账本技术之一，区块链能够实现去中心化、透明和不可篡改的交易记账，而无需可信第三方参与，从而改变了传统账本的交易模式。区块链技术已经引起了学术界和各国政府的广泛关注，越来越多的企业和组织正在探索区块链技术在其领域中的应用。共识算法是区块链技术的核心要素,也是近年来分布式系统研究的热点。共识算法影响着区块链的交易处理能力、扩展性和安全性，是区块链技术发展的关建。最初的共识算法研究常常关注于解决同步环境下的共识问题，而严格的同步假设在互联网流行的当下往往难以满足，因此异步环境下的共识算法的研究具有十分重要的意义。现有的异步共识算法仍然是基于相同的线性链结构，限制了开发范围。


技术实现要素：

3.为了解决现有技术中的不足，本发明提供一种基于dag和分片的区块链异步共识算法，能够大幅提升共识效率，缩短共识过程中的通信开销。
4.为了实现上述目的，本发明采用的具体方案为：一种基于dag和分片的区块链异步共识算法，包括：将区块链网络划分为多个分片，每个分片中包含有多个节点；节点根据接收到的交易信息创建区块以及与区块对应的事件；分片中的节点基于dag(有向无环图)结构确定领导者区块，并且基于领导者区块形成片内共识；节点基于领导者区块将多个事件合并为一个批次，并且一个批次的事件在分片之间传播形成片间共识。
5.作为上述基于dag和分片的区块链异步共识算法的进一步优化：节点创建区块的具体方法包括：节点在接收到交易信息后将交易信息有序存放在交易列表中；当节点开始新的轮次时基于交易列表中的交易信息创建区块；创建区块后节点将区块在分片中广播。
6.作为上述基于dag和分片的区块链异步共识算法的进一步优化：节点创建与区块对应的事件的具体方法包括：当节点接收到来自于其它节点的区块时对区块进行验证；当节点验证区块有效时向创建该区块的节点返回签名确认消息；创建区块的节点接收到与区块对应的签名确认消息的数量达到预设的第一阈值时，创建与区块对应的事件并且在分片内广播。
7.作为上述基于dag和分片的区块链异步共识算法的进一步优化：当节点接收到的当前轮次的事件的数量达到预设的第二阈值时结束当前轮次，并且进入新的轮次。
8.作为上述基于dag和分片的区块链异步共识算法的进一步优化：节点确定领导者区块的方法包括：分片中的节点基于本地维护的dag结构，通过随机硬币方式在持有的所有区块中确定领导者区块并且提交。
9.作为上述基于dag和分片的区块链异步共识算法的进一步优化：分片中的节点基于领导者区块形成片内共识的具体方法包括：节点提交领导者区块后，对领导者区块进行路径检查；节点基于领导者区块的关联路径对领导者区块进行排序，得到用于表征领导者区块顺序的领导者序列；基于领导者序列，根据确定性规则对每个领导者区块的祖先区块进行排序，以形成片内共识。
10.作为上述基于dag和分片的区块链异步共识算法的进一步优化：节点基于领导者区块将多个事件合并为一个批次的同时，为同一批次事件赋予编号，当一个批次的事件在分片之间传播时结，接收到事件的节点基于批次的编号进行排序。
11.作为上述基于dag和分片的区块链异步共识算法的进一步优化：当节点接收到来自于其它分片的事件时，若至少两个批次的事件具有相同过的编号，则节点基于哈希值进行重排序。
12.作为上述基于dag和分片的区块链异步共识算法的进一步优化：划分分片时，分片内的节点至少与一个其它分片中的节点为邻居节点。
13.有益效果：本发明基于dag和分片结合的方式实现，在保证安全性的前提下，大大提高了区块链的可扩展性和网络分区的容忍度；在分片内部，使用结构化dag实现并行广播和交易处理，节点只广播和存储本地分片的交易块，提高了交易处理的效率并降低了存储开销；在分片间通信中，节点发送区块事件而不是区块，这可以大幅度的减少分片间的通信开销，并且，批次合并的方式可以降低网络带宽消耗，加快确认速度；通过分片间通信，不同分片内的节点可以维护一致的全局区块事件状态，解决由于分片而导致的安全性降级问题。
附图说明
14.图1为区块链异步共识算法的整体结构图；图2为区块链异步共识算法区块和事件广播图；图3为区块链异步共识算法片内共识提交规则示意图。
具体实施方式
15.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
16.请参阅图1至3，一种基于dag和分片的区块链异步共识算法，包括如下步骤。
17.在构建区块链网络的过程中，将区块链网络划分为多个分片，每个分片中包含有多个节点。分片的数量和每个分片中节点的数量可以根据区块链网络的规模确定。
18.分片形成之后，节点开始运行，运行中的节点根据接收到的交易信息创建区块以及与区块对应的事件。节点创建区块的具体方法包括如下步骤。
19.首先，节点在接收到交易信息后将交易信息有序存放在交易列表中。节点在运行过程中，持续接收来自于客户端的交易信息，并且按照接收到的交易信息的时间将所有交易信息有序存放在交易列表中，后续过程中根据交易信息的顺序对交易信息进行处理，以避免发生遗漏。
20.其次，当节点开始新的轮次时基于交易列表中的交易信息创建区块。在每个轮次中，节点只创建一个区块，从而减少区块的数量，降低区块链网络的处理压力，提升整体效率。每个区块可以包含多个交易信息，区块所能包含的交易信息的数量由区块的大小确定。
21.最后，为了对区块进行验证以确定区块的合法性，创建区块后节点将区块在分片中广播，将区块交由分片内的其它节点验证。
22.节点创建与区块对应的事件的具体方法包括如下步骤。
23.首先，当节点接收到来自于其它节点的区块时对区块进行验证。具体的验证方法可以是预先规定好的验证检查方法，所有节点按照相同的验证检查方法对接收到的区块进行验证。
24.其次，当节点验证区块有效时向创建该区块的节点返回签名确认消息。在验证区块有效时，证明该节点确认了接收到的区块，此时可以向创建该区块的节点返回签名确认消息，使创建该区块的节点确认该区块已经被其它节点验证。
25.最后，创建区块的节点接收到与区块对应的签名确认消息的数量达到预设的第一阈值时，创建与区块对应的事件并且在分片内广播。当创建区块的节点接收到的与区块对应的签名确认消息的数量到达第一阈值时，可以确认该区块已经得到了分片内多数节点的验证，从而确定该区块是合法有效的，此时可以创建与该区块对应的事件，由事件证明区块的合法性。事件创建完成后，节点将事件在分片内广播，使其余所有节点都能确定与事件相对应的区块是合法有效的。第一阈值可以设置为2f+1，其中f的具体数值由分片内的节点数量确定。在本实施例中，事件可以是对区块进行哈希计算得到的哈希值，在其他的实施方式中，也可以采用类似计算方法，在此不再赘述。
26.本发明中，在每个分片的内部，节点只会广播包含具体交易信息的区块和用于表征区块合法有效的事件，从而提高交易处理的效率，并且降低存储开销。
27.在区块和事件创建之后，在分片中的节点基于dag(有向无环图)结构确定领导者区块，并且基于领导者区块形成片内共识。具体地说，每个节点在本地维护一个一致的基于轮次的dag结构，将dag的变化过程分为多个stage(阶段)，每个stage由两个连续的轮次组成，不同节点维护的dag结构在同一时刻可能是相同或者不同的。在片内共识过程中，当节点收到足够多的区块后，会在stage的第二轮中进行随机化，以获得一致的随机硬币，进而在stage第一轮的区块中选择出领导者区块，随机硬币可以通过主动阈值签名方案获得，属于本领域的现有技术，在此不再赘述。如果此领导者区块在stage的第二轮中得到足够的支持(即具有足够的子区块，f+1个)，则提交领导者区块，提交意味着可以对其祖先区块进行
排序。通过路径检查机制，我们可以确保节点拥有一致的领导者区块顺序，从而保证了节点拥有片内一致的区块顺序。因为只有当区块被分片内的多数节点认可后才能够创建事件，进而通过广播事件使所有节点确定接收到的区块的合法有效性，因此节点在片内共识的时候，不需要采用复杂的投票和收集机制，可以直接基于自身维护的dag结构进行，从而有效降低方法的复杂度和通信开销。在本实施例中，分片中的节点基于本地维护的dag结构，通过随机硬币方式确定当前stage的领导者区块并且提交，在本发明其它的实施方式中，也可以采用其它的简单随机方法确定领导者区块。
28.形成片内共识之后，节点基于领导者区块将多个事件合并为一个批次，并且一个批次的事件在分片之间传播形成片间共识。片内共识形成之后，需要在不同的分片之间形成共识，以使整个区块链网络形成共识，通过将多个事件合并为一个批次，进而将一个批次的事件在不同的分片之间传播，可以减少片间共识的次数，降低区块链网络整体的通信开销，并且因为在分片之间传播的是事件而不是完整的区块，因此能够进一步降低通信开销。
29.本发明基于dag和分片结合的方式实现，在保证安全性的前提下，大大提高了区块链的可扩展性和网络分区的容忍度；在分片内部，使用结构化dag实现并行广播和交易处理，节点只广播和存储本地分片的交易块，提高了交易处理的效率并降低了存储开销；在分片间通信中，节点发送区块事件而不是区块，这可以大幅度的减少分片间的通信开销，并且，批次合并的方式可以降低网络带宽消耗，加快确认速度；通过分片间通信，不同分片内的节点可以维护一致的全局区块事件状态，解决由于分片而导致的安全性降级问题。
30.节点更新轮次的具体方法为：当节点接收到的当前轮次的事件的数量达到预设的第二阈值时结束当前轮次，并且进入新的轮次。第二阈值也可以根据分片内节点的数量确定。
31.更进一步的，分片中的节点基于领导者区块形成片内共识的具体方法包括如下步骤。
32.节点提交领导者区块后，对领导者区块进行路径检查。具体的路径检查方法如下。
33.当节点提交一个轮次的领导者区块后，在当前轮次和最后提交领导者区块的轮次的范围内，节点应该从当前轮次的领导者区块开始递归检查和前一个轮次的领导者区块之间是否存在继承关系，即是否至少存在一条路径，例如图3中的红色路径，如果存在，节点应该提交前一个轮次的领导者区块并将其排序在当前轮次的领导者区块之前，然后，从前一个轮次的领导者区块开始继续向其之前的轮次做路径检查。通过继承关系确定的区块，可以定义为领导者区块的祖先区块。
34.节点基于领导者区块的关联路径对领导者区块进行排序，得到用于表征领导者区块顺序的领导者序列。基于领导者序列，根据确定性规则对每个领导者区块的祖先区块进行排序，以形成片内共识。通过上述的路径检查机制，可以确保节点拥有一致的领导者区块顺序，从而保证了节点拥有片内一致的区块顺序。
35.为了保证在片间共识阶段，不同分片内的节点能够正确地对接收到的一个批次的事件进行排序，最终形成正确的片间共识，节点基于领导者区块将多个事件合并为一个批次的同时，为同一批次事件赋予编号，当一个批次的事件在分片之间传播时结，接收到事件的节点基于批次的编号进行排序。为了避免因为编号相同导致节点无法顺利对接收到的不同批次的事件进行排序，进而干扰片间共识的形成，当节点接收到来自于其它分片的事件
时，若至少两个批次的事件具有相同过的编号，则节点基于哈希值进行重排序。哈希函数的防碰撞性确保了节点可以得到一致的批次顺序,所以节点可以获得一致的区块事件的全局链。
36.为了保证节点能够顺利将一个批次的事件传播到其它分片中，划分分片时，分片内的节点至少与一个其它分片中的节点为邻居节点。
37.对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

技术特征：
1.一种基于dag和分片的区块链异步共识算法，其特征在于，包括：将区块链网络划分为多个分片，每个分片中包含有多个节点；节点根据接收到的交易信息创建区块以及与区块对应的事件；分片中的节点基于dag(有向无环图)结构确定领导者区块，并且基于领导者区块形成片内共识；节点基于领导者区块将多个事件合并为一个批次，并且一个批次的事件在分片之间传播形成片间共识。2.如权利要求1所述的一种基于dag和分片的区块链异步共识算法，其特征在于，节点创建区块的具体方法包括：节点在接收到交易信息后将交易信息有序存放在交易列表中；当节点开始新的轮次时基于交易列表中的交易信息创建区块；创建区块后节点将区块在分片中广播。3.如权利要求2所述的一种基于dag和分片的区块链异步共识算法，其特征在于，节点创建与区块对应的事件的具体方法包括：当节点接收到来自于其它节点的区块时对区块进行验证；当节点验证区块有效时向创建该区块的节点返回签名确认消息；创建区块的节点接收到与区块对应的签名确认消息的数量达到预设的第一阈值时，创建与区块对应的事件并且在分片内广播。4.如权利要求3所述的一种基于dag和分片的区块链异步共识算法，其特征在于，当节点接收到的当前轮次的事件的数量达到预设的第二阈值时结束当前轮次，并且进入新的轮次。5.如权利要求1所述的一种基于dag和分片的区块链异步共识算法，其特征在于，节点确定领导者区块的方法包括：分片中的节点基于本地维护的dag结构，通过随机硬币方式在持有的所有区块中确定领导者区块并且提交。6.如权利要求5所述的一种基于dag和分片的区块链异步共识算法，其特征在于，分片中的节点基于领导者区块形成片内共识的具体方法包括：节点提交领导者区块后，对领导者区块进行路径检查；节点基于领导者区块的关联路径对领导者区块进行排序，得到用于表征领导者区块顺序的领导者序列；基于领导者序列，根据确定性规则对每个领导者区块的祖先区块进行排序，以形成片内共识。7.如权利要求1所述的一种基于dag和分片的区块链异步共识算法，其特征在于，节点基于领导者区块将多个事件合并为一个批次的同时，为同一批次事件赋予编号，当一个批次的事件在分片之间传播时结，接收到事件的节点基于批次的编号进行排序。8.如权利要求7所述的一种基于dag和分片的区块链异步共识算法，其特征在于，当节点接收到来自于其它分片的事件时，若至少两个批次的事件具有相同过的编号，则节点基于哈希值进行重排序。9.如权利要求1所述的一种基于dag和分片的区块链异步共识算法，其特征在于，划分
分片时，分片内的节点至少与一个其它分片中的节点为邻居节点。

技术总结
一种基于DAG和分片的区块链异步共识算法，包括：将区块链网络划分为多个分片，每个分片中包含有多个节点；节点根据接收到的交易信息创建区块以及与区块对应的事件；分片中的节点基于DAG(有向无环图)结构确定领导者区块，并且基于领导者区块形成片内共识；节点基于领导者区块将多个事件合并为一个批次，并且一个批次的事件在分片之间传播形成片间共识。本发明提供一种基于DAG和分片的区块链异步共识算法，能够大幅提升共识效率，缩短共识过程中的通信开销。通信开销。通信开销。


技术研发人员：刘扬 彭松 陈静雯 贺金龙 王锋 傅健豪 张苗苗 史士东
受保护的技术使用者：河南工业大学
技术研发日：2023.04.21
技术公布日：2023/7/25