一种基于带权重的随机洗牌算法的抽签方法及应用

摘要

本发明公开了一种基于带权重的随机洗牌算法的抽签方法及应用，本方法包括抽签过程和验证过程两部分，给出了洗牌方法用于决定区块链出块者序列，若共识的节点不能出块，则由排在第二位的节点出块，依次类推；并且，采用了带权重的随机洗牌函数，可以保证输出优先级顺序概率与持有的权益成正比。本抽签方法可用于leader节点选举和委员会节点选举。本发明可以实现异步网络中的出块共识，无须多轮共识，对网络同步要求大大降低，并且，可以抵抗女巫攻击，大大提高了安全性。

说明书

技术领域

本发明涉及一种抽签方法，尤其涉及一种基于带权重的随机洗牌算法的抽签方法及应用。

背景技术

区块链是继大数据和人工智能之后的又一项互联网革命，融合了分布式计算、加密技术和可证明安全等多项技术。区块链技术为去中心系统提供了一种可行方案。区块链中的一个核心步骤是共识，即如何在多个矿工生成区块的情况下决定哪个矿工的区块被接收到链上。

比特币是第一个得到广泛应用的区块链系统，采用了PoW共识机制。在PoW共识机制中，算力是出块的决定因素，即算得最快的节点，其区块更容易上链并得到奖励。在该体制下，由于每次只能有一个节点的出块被接受到链上，其他的算力都都浪费掉，由此，PoS体制被提出并被区块链系统接受。

在PoS体制中，节点出块的概率与其占有的某项资源相关，该资源可以是其持有的代币、拥有的内存或者存储资源。与PoW相比，PoS不会出现分叉，不需要大量的计算，节省了能源。

但为了防止女巫攻击，PoS要求节点获得出块的概率与其持有的资源成正比，与其分拆和合并没有关系。在实际系统中往往采用PoS+PoW共识机制，即出块节点仍然需要一定的计算量，但比传统PoW体制计算量要小得多。在PoS体制中，核心问题是如何设计高效、公平的共识算法。

针对上述核心问题，现有技术提出了一种Algorand共识机制，是一种基于可验证随机函数(VRF)的抽签算法，可以公平地决定胜出节点，从而共识出块节点。然而，该方法对网络同步有一定要求，即要求网络节点时延，出块节点在一段时间内能够保持在线，如果网络不能同步，则共识失败，进入viewchange(转换等待)，等待下一轮共识。此外，传统的基于随机洗牌算法的共识方法缺乏安全性证明，存在安全隐患。

发明内容

为了解决上述技术所存在的不足之处，本发明提供了一种基于带权重的随机洗牌算法的抽签方法及应用。

为了解决以上技术问题，本发明采用的技术方案是：一种基于带权重的随机洗牌算法的抽签方法，包括抽签过程和验证过程两部分；

抽签过程包括以下步骤：

S1：拼接字符串；

S2：以拼接得到的字符串和当前用户的私钥sk

S3：对指定范围内的每个数值，利用哈希函数计算哈希值；设指定范围为1-w

S4：用带权重的随机洗牌函数进行随机洗牌，生成一个优先级列表；

S5：用带权重的随机洗牌函数对默认列表进行随机置换；

S6：当前用户将自身置于生成的列表的最高优先级位置，得到列表list

S7：广播hash

所述验证过程包括以下步骤：

S8：验证π

S9：验证hash

S10：验证τ

S11：取验证通过的与随机数r差值最小的τ

S12：若节点i在线，则i为抽签胜出节点，否则list

进一步地，字符串的拼接方式为：将字符串magic和nonce拼接为一个字符串m，即m＝magic|nonce，其中，magic为一个固定的字符串，nonce为一个变化的字符串。

进一步地，S3中，采用的哈希函数为哈希函数SM3。

进一步地，S3中，对1-w

进一步地，S5中，随机置换是将用户顺序随机打乱的过程，包括初始化和排序两个步骤。

进一步地，初始化的处理为：设网络中有N个节点，分别记为1、2、...、N，初始化数组a[M]，其中，

其中，w

排序的处理过程为：

1)对当前数值i，生成随机数r，交换a[i]和a[r]的值；

2)对数值i从1到M，执行上述过程1)；

3)去掉数组a[M]中的重复元素，对于重复的元素，只保留第一个出现的元素；

3)最终生成的数组a[N]为随机洗牌后的结果。

进一步地，S9中，用可验证随机函数、用户的公钥和proof

一种基于带权重的随机洗牌算法的抽签方法：令抽签胜出节点为learder节点，使本基于带权重的随机洗牌算法直接应用到leader选举中。

一种基于带权重的随机洗牌算法的抽签方法，将抽签中的前m个节点设置为胜出节点，使本基于带权重的随机洗牌算法直接应用到委员会节点选举中，其中委员会节点个数为m。

本发明公开了一种基于带权重的随机洗牌算法的抽签方法，优化了优先级的随机性，可以在异步网络中快速实现出块共识，在当前出块节点出现故障后，无须多轮共识，即可快速决定下一个出块节点，解决了传统共识方法对网络同步性要求过高的问题；并且，采用了带权重的随机洗牌函数，可以保证输出的优先级顺序改了与持有权益成正比，从而可以抵抗女巫攻击，保证安全性。

具体实施方式

下面具体实施方式对本发明作进一步详细的说明。

首先，对文中出现的专业术语进行解释：

PoW：Proof of work，计算力证明；

PoS：Proof of Stake，权益证明；

ViewChange：转换等待，共识失败后的一种机制，等待下一轮共识；

VRF：可验证随机函数；

|：表示拼接，即将|前后的两个数据拼接；由于字符串可以用ASCII码表示成数字，因此|既可以数字的拼接，也可以表示字符串的拼接；

Hash(·)：哈希函数，本专利中采用SM3函数，是我国商用哈希函数标准、ISO标准；

SM3()：用SM3函数计算的哈希值；

epoch：当前共识所处的阶段；

w

对于本发明公开了一种基于带权重的随机洗牌算法的抽签方法，包括抽签过程和验证过程两部分；首先，规定与特定随机书差较小的值具有较高的优先级。例如，以数值A、数值B的优先级比较为例，先指定随机数r，若A-r|＜|B-r|，则称B的优先级大于A，反之，则称A的优先级大于B；

对于抽签过程，包括以下步骤：

S1：拼接字符串；字符串拼接是将字符串magic和nonce拼接为一个字符串m，即m＝magic|nonce，其中，magic为一个固定的字符串，如在电子选举中可以用”leader”字符串；nonce为一个变化的字符串，如在共识中可以取共识轮数和epoch的值，在电子选举中可以为上一个胜出节点的哈希值。该字符串拼接方式并不唯一，理论上可以采用任意的字符串拼接方式，只需要保证所有节点采用相同的字符串拼接方式即可。如在委员会节点选举中，可以magic可以用”committee”字符串，在出块共识中用”block”字符串。

S2：以拼接得到的字符串m和当前用户的私钥sk

可验证随机函数根据输入和用户私钥生成哈希值和一个证明，该哈希值可以被网络中其他节点用该用户的公钥和证明进行验证。

S3：对指定范围内的每个数值，利用哈希函数计算哈希值；设指定范围为1-w

本专利采用哈希函数SM3进行计算；例如，以数值s为例，对1-w

S4：用带权重的随机洗牌函数进行随机洗牌，生成一个优先级列表；

S5：用带权重的随机洗牌函数对默认列表进行随机置换；

随机洗牌函数是将用户顺序随机打乱的过程，即随机置换，本专利提出了带权重的随机洗牌函数。假设网络中有N个节点，分别记为1、2、...、N，节点i持有的份额为w

第一步：初始化

初始化数组a[M]，其中，

其中，w

第二步：排序

1)对当前数值i，生成随机数r，交换a[i]和a[r]的值；

2)对数值i从1到M，执行上述过程1)；

3)去掉数组a[M]中的重复元素，对于重复的元素，只保留第一个出现的元素；

3)最终生成的数组a[N]为随机洗牌后的结果。

S6：当前用户将自身置于生成的列表的最高优先级位置，得到列表list

S7：广播hash

对于验证过程包括以下步骤：

S8：验证π

S9：用可验证随机函数、用户的公钥和proof

S10：验证τ

S11：取验证通过的与随机数r差值最小的τ

S12：若节点i在线，则i为抽签胜出节点，否则list

对于本发明所公开的基于带权重的随机洗牌算法的抽签方法可应用到leader选举、委员会节点选举。

(1)为了提高共识的速度，现在很多基于PoS机制的区块链采用分片网络，在分片中应用leader节点选举和委员会节点选举。令抽签胜出算法为learder节点，则本发明的抽签方法可以直接应用到leader选举中。

(2)委员会节点选举是一种特殊的leader节点选举机制。在委员会节点选举中，选举多个胜出节点而不是一个胜出节点。可以将抽签中的前m个节点设置为胜出节点，从而，本发明的该抽签算法可以应用到委员会节点选举中，其中，委员会节点个数为m。

综上，对于本发明所公开的基于带权重的随机洗牌算法的抽签方法，给出了洗牌方法用于决定区块链出块者序列，该方法可以实现异步网络中的出块共识，无须多轮共识。

同时，采用了带权重的随机洗牌函数，可以保证输出优先级顺序概率与持有的权益成正比。具体有：

每个节点胜出的概率与之有的份额成正比，这个已经由Micali等人在A1gorand共识机制，即基于可验证随机函数(VRF)的抽签算法中证明。

在随机洗牌函数中，数组中元素排在最高位的概率与该元素的个数成正比；数组中的元素为节点编号。由于初始化中节点序号出现的个数为该节点的份额，因此节点排在最高位的概率与节点的份额成正比。同理，排在第二位的概率与剩下的节点持有的份额成正比。以此类推，得证。

由于节点胜出的概率和每个节点在洗牌函数的输出列表中的排序均与节点持有的份额成正比，从而可以证明最终输出的优先级顺序与节点持有的份额成正比。

与现有技术相比，本发明的所公开的基于带权重的随机洗牌算法的抽签方法具有以下优势：

(1)可以解决异步网络中的共识问题，若共识出的节点不能出块，则由排在第二位的节点出块，以此类推，所以对网络同步要求大大降低。同时，该方法不需要知道全网的份额信息，在变化的网络中可以降低通信开支。在Algorand的抽签体制中，每个节点在执行抽签算法的时候需要知道自己份额与全网份额的必中，在变化的网络中，全网份额可能会发生改变，这时候需要通信节点的份额信息。在本发明的抽签算法中，节点只需要知道自己的份额，而不需要知道全网的份额信息，从而可以避免这种通信开支。

(2)带权重的随机洗牌函数可以保证获得优先权的概率与持有的权益成正比，从而可以证明抵抗女巫攻击，进而有效提高了安全性。

上述实施方式并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的技术人员在本发明的技术方案范围内所做出的变化、改型、添加或替换，也均属于本发明的保护范围。