0 概述

区块链是一种集网络通信、加密算法、共识机制及智能合约等技术于一体的新兴信息技术, 具有去中心化、防篡改、可追溯等特点^[1]。区块链是一种分布式账本技术, 属于分布式系统, 因此, 确保各个节点数据的一致性是一个关键问题。一致性是指对于分布式系统中的各个节点, 给定一系列操作, 在约定协议的保障下, 使得它们对处理结果达成“某种程度”的共识。在区块链中, 数据一致性通过共识算法实现。

共识算法主要有PoW算法^[2]、PoS算法^[3]、Raft算法^[4]和PBFT算法等^[5-6], 其中, PBFT算法由于能够解决拜占庭问题^[7], 因此许多联盟链应用都采用PBFT算法作为系统的共识算法。目前已有许多学者对PBFT算法进行研究, 如基于Gossip协议的PBFT共识算法^[8]、基于信用的改进PBFT共识算法^[9]、基于动态授权的PBFT共识算法^[10]、基于聚合签名的PBFT共识算法^[11]、适用于可信日志存储与验证系统的PBFT共识算法^[12]以及适用于多中心动态许可链的PBFT共识算法^[13]等。

环签名是一种特殊的数字签名方式, 由RIVES T R等人于2001年提出^[14]。环签名的主要特点是能够实现签名成员的无条件匿名性, 即无法从签名结果得知签名者的身份, 但可以有效地对签名进行认证。环签名的无条件匿名性有利于实现去中心化^[15]。

本文通过对环签名相关理论进行分析, 提出一种基于ElGamal数字签名算法的环签名方案。根据环签名方案对PBFT算法进行改进, 并分析改进PBFT算法的优缺点。

1 相关预备知识 1.1 环签名技术

在进行环签名时, 环内用户可以自发组织, 也可通过预先设定的方案进行组环。假设存在n个用户, 每个用户u_i都拥有一个公钥y_i和私钥x_i。一般地, 一个环签名方案包括以下3个部分^[16]:

1) 密钥生成算法KeyGen。环内的签名者采用某一种密钥生成算法(如ECDSA、RSA、ElGamal算法等)生成公私钥。

2) 环签名算法RSign。产生环签名的算法, 输入待签名消息m、环内n个签名者的公钥集合L={y₁, y₂, …, y_n}以及该环内的实际签名发起者T的私钥x_T, 输出该环对消息m的环签名R_m。

3) 环签名验证算法RVerify。验证环签名的算法, 输入是被签名的消息m和对该消息进行的环签名R_m, 输出验证结果, 验证通过为1, 不通过为0。

1.2 ElGamal数字签名算法

ElGamal算法属于基于离散对数问题的签名算法, 主要包括参数与密钥生成、签名算法以及验证算法3个部分^[17]。

1.2.1 参数与密钥生成

首先设P是一个大素数, 并且在Z_p中求解离散对数困难问题, 然后选一个生成元g∈Z_p^*和随机数x∈Z_p-1^*, 计算:

$ y=g^{x} \bmod P $

(1)

其中, 公钥为(y, g, P), 私钥为x。

1.2.2 签名算法

假设需要进行签名的消息为M, 签名者选择秘密随机数k∈Z_P^*, 计算:

$ r=g^{k} \bmod P $

(2)

$ s=(h(m)-x r) k^{-1} \bmod (P-1) $

(3)

则对M的签名为(s, r), 其中, h是Hash函数。

1.2.3 验证算法

签名的接收者拥有公钥(y, g, P), 收到消息M的签名(s, r)之后, 首先计算h(m), 然后验证:

$ y^{r} r^{s} \equiv g^{h(m)} \bmod P $

(4)

如果式(4)成立, 则数字签名有效, 否则签名无效。

1.3 PBFT共识机制

PBFT是一种用于解决拜占庭将军问题的算法, 其能够在网络中存在恶意节点的情况下保证各个节点间的一致性。在PBFT算法中存在3种角色:客户端(Client), 主节点, 从节点, 其中主节点和从节点都进行数据备份。在进行PBFT过程时, 一个主节点领导的共识过程处于一个视图中。视图是PBFT共识机制中节点关系的定义, 视图的编号记为v。在一个视图中, 不同的节点具有不同的编号, 每个视图中有且仅有一个主节点。如果发生主节点故障、共识过程超时等情况, 需要根据PBFT共识机制中的视图切换协议切换主节点, 生成新的视图v+1, 并在该视图下继续共识过程^[18]。

1) 请求阶段。客户端发送请求m:〈REQUEST, o, t, c〉。

2) 预准备阶段。主节点对接收到的请求赋予一个编号n, 并广播预准备消息, 格式为〈〈PRE-PREPARE, v, n, d〉, m〉, 其中, d是请求m的摘要值, 使用一种安全的Hash函数生成。

3) 准备阶段。接收到预准备消息的节点对预准备消息中的d进行验证, 验证通过则进入准备阶段。准备阶段广播准备消息, 格式为〈PREPARE, v, n, d, i〉, i是节点自身编号。广播的同时将PRE-PREPARE和PREPARE消息写入日志。当主节点收到2f+1个不同节点的PRE-PREPARE和PREPARE消息并验证通过时, 准备阶段完成, 主要验证v、n与d。

4) 确认阶段。节点完成准备阶段后, 进入确认阶段, 广播确认消息, 格式为〈COMMIT, v, n, D(m), i〉, 其中, D(m)是从节点签名集合。对COMMIT消息进行确认时, 主要对D(m)、v进行验证。当收到包括自身在内的2f+1个确认消息并通过验证时, 完成确认阶段。

5) 回复阶段。回复格式为〈REPLY, v, t, c, i, r〉, 其中, r是请求的执行结果, 客户端在接收到f+1个不同节点的同样请求结果时, 认为网络达成了此次共识。

PBFT流程如图 1所示。

2 基于ElGamal数字签名算法的环签名方案 2.1 基于ElGamal算法的环签名方案

基于ElGamal算法的环签名方案主要由系统建立、密钥生成、签名与验证3个部分组成。

1) 系统建立

假设环内共有n个用户, 根据第2节中对环签名的介绍, 在进行环签名时, 可以通过预定方案或用户自发组成环。环内的n个签名用户身份信息组成一个群。设P是一个大素数, 并且在Z_p中求解离散对数困难, 然后选一个生成元g∈Z_p^*, H是一个安全的Hash函数。

2) 密钥生成算法

参考ElGamal算法, 按照以下步骤生成密钥:首先签名者选择随机数x∈Z_p-1^*作为私钥, 然后计算y=g^xmod P作为私钥。

3) 环签名生成算法

假设待签名的消息为m, 某个签名者需要对m发起环签名, 首先从具有签名资格的用户中选择并组成环, 身份信息R={ID₁, ID₂, …, ID_n}。用户u_s进行环签名时的步骤如下:

步骤1  u_t选择随机数t∈Z_q^*, 且环内除u_t以外的用户选择随机数σ_i∈Z_q^*作为临时私钥, 并根据密钥生成临时公钥y_i。

步骤2  计算h=H(m‖R)。

步骤3  计算$v = {x_s} + \sum\limits_{i \ne s}^n {{\sigma _i}} $。

步骤4  计算r=g^x_stmod P。

步骤5  计算l=(h-rv)(x_st)-1mod P。

步骤6  输出对于消息m的环签名σ=(y₁, y₂, …, y_n, m, r, l, v)。

4) 环签名验证算法

在验证消息m的环签名时, 验证者已知环内用户的公钥y、身份信息R={ID₁, ID₂, …, ID_n}和消息m的环签名σ=(y₁, y₂, …, y_n, m, r, l, v)。验证时的步骤如下:

步骤1  计算h=H(m‖R)。

步骤2  验证$ {\left( {\prod\limits_{i = 1}^n {{y_i}} } \right)^r}{r^l} \equiv {g^h}\, \bmod \, P$是否成立。若成立, 则接受签名; 否则不接受签名。

2.2 环签名方案分析 2.2.1 正确性分析

将环签名方案的签名算法步骤5变形可以得到:

$ x_{s} t l=(h-r v) $

(5)

将环签名验证算法步骤2中的$\prod\limits_{i=1}^{n} y_{i} $和r使用密钥生成算法, 可得:

$ g^{r v} g^{x_{s} t l} \equiv g^{h} \bmod P $

(6)

继续变形得:

$ {g^{rv + {x_s}^{tl}}} \equiv {g^h}\, \bmod \, P $

(7)

根据ElGamal算法证明可知:

$ r v+x_{s} t l=h \bmod P $

(8)

最后根据环签名生成算法中的步骤4可知:

$ r v+x_{s} t(h-r v)\left(x_{s} t\right)-1 \bmod P=h \bmod P $

(9)

式(9)即验证公式。因此, 证明了环签名由环签名生成算法计算得到。

2.2.2 匿名性分析

在环签名生成算法RSign中, 环内除签名者之外的所有人员都选取了随机数σ_i∈Z_q^*, 签名者签名的私钥x∈Z_p^*也是随机数, 且在签名算法步骤3中对x和σ_i进行了混合并且将其公开, 因此, 从环签名σ=(y₁, y₂, …, y_n, m, r, l, v)中无法得知具体的签名者。即使用户身份R={ID₁, ID₂, …, ID_n}泄露, 也无法确定签名者的身份, 满足无条件匿名性。

2.2.3 不可伪造性分析

环签名的不可伪造性安全模型主要有Model1、Model2和Model3^[19]3种。下文将证明本文提出的环签名方案满足Model1不可伪造性安全。

本节基于ElGamal数字签名算法提出了环签名方案。ElGamal数字签名算法的安全性基于求离散对数的困难性, 因此, 在本节环签名方案中, 攻击者想要通过签名者的公钥以及系统参数求解签名者私钥的困难性等同于求解离散对数问题, 已有研究证明求解概率较低, 可忽略不计^[20]。

在环签名σ=(y₁, y₂, …, y_n, m, r, l, v)中, 由于计算时用到的随机数t没有公开, 而在计算签名l时, 没有直接使用签名者的私钥x_s, 而是将x_s与秘密随机数t的整体x_st进行求逆, 因此通过环签名σ破解私钥的概率是可忽略的。假设A为攻击者, S为签名者, 攻击者得到了一个公钥集合Y={y₁, y₂, …, y_s}。A向S进行至多s次的关于L_i的环签名请求, 在得到响应(L_i, σ_i)后, 根据前文分析, 求解离散对数问题的难度较大, A不可能以不可忽略的概率产生消息m的环签名(L′, σ), 其中, L′⊆L, A∉L′, 即满足安全模型Model1。

3 基于环签名的PBFT算法改进方案

针对PBFT算法中视图切换时效率低下及无法支持节点动态加入或退出网络的问题, 采用本文提出的环签名方案对PBFT算法进行改进, 改进后的PBFT算法步骤如下:

步骤1  任意节点提出提交数据的请求, 并将请求消息〈REQUEST, o, t, c〉广播全网, 同时其他节点接收到该请求后立刻返回一个反馈消息〈RESPONSE, q, b, t〉, 其中, q是发送反馈消息的节点编号, b表示收到了请求。

步骤2  请求发起节点从发出请求消息REQUEST时开始计时, 经过时间Δt后, 请求发起节点接收到m条消息, 节点编号分别为q₁, q₂, …, q_m。

步骤3  请求发起节点将自身与节点q₁, q₂, …, q_m组成一个环, 采用本文的环签名方案生成环签名σ, 并将确认消息〈COMMIT, v, n, σ〉广播。当请求发起节点收到包括自身在内的2f+1个确认消息并通过验证时, 认为达成共识。

步骤4  将要写入区块的数据进行全网广播, 并在全网节点达成共识, 将数据区块发布。

改进PBFT算法采用环签名技术, 签名发起者可以自发地组成一个环, 因此每次签名时环内用户可以根据收到反馈消息的情况自发地组成环, 不需要进行过多的视图切换, 影响共识效率, 同时解决了对于网络条件不良、节点动态加入退出频繁的情况下的共识问题。相比原PBFT算法, 基于环签名的PBFT算法增加了计算复杂度, 同时环签名的数据量具有更多的签名, 在一定程度上降低节点间的通信效率。因此, 本文方案更适用于网络状况不良且规模较小的联盟链。

4 本文改进方案的实验验证

Hyperledger Fabric是一个支持模块可插拔的区块链开发平台, 采用Go语言对方案进行实现, 验证改进方案是否能解决节点的动态加入与退出问题。然后使用Fabric中的区块链性能测试框架Caliper对改进方案进行性能测试, 实验验证环境如表 1所示。

首先进行动态加入退出的共识正确性验证。在区块链网络中有A、B、C、D 4个节点, E、F 2个节点作为动态加入或退出的自由节点。将E、F 2个节点采用不同方式加入或退出网络, 在本文提出的改进方案下进行实验验证。同时对方案采用Caliper框架进行性能测试。实验验证结果如表 2所示, 其中, √为达成共识。

由表 2可以看出, 通过进行多种网络节点变化方式, 本文提出的PBFT共识算法改进方案可以较好地解决节点动态加入或退出问题。

对改进PBFT算法的拜占庭容错率进行验证。按照原PBFT算法, 如果网络中的错误节点数为f, 则网络中的正确节点数n必须满足n≥3f+1, 才能够保证网络各个节点达成正确的共识。在进行实验时, 共有A、B、C、D、E、F、G、H 8个节点, 分别对错误节点数为0、1、2、3、4时的5种情况采用本文的改进PBFT算法进行实验验证, 结果如表 3所示, 其中, √为达成共识, ×为未达成共识。

从表 3可以看出, 当错误节点数f≤2时, 网络中各个节点能够达成共识, 当错误节点数f≥3时, 吞吐量为0, 说明此时无法达成共识, 满足原PBFT算法1/3的拜占庭容错率。

5 结束语

本文针对区块链中常用的PBFT共识算法无法支持节点动态加入或退出网络以及共识超时进行视图切换效率低下的问题, 提出一种基于ElGamal数字签名算法的环签名方案。根据环签名方案对PBFT算法进行改进, 通过环签名时节点自行组成环的方式, 使PBFT算法支持节点的动态加入与退出, 在一定程度上能够提高因为共识超时导致的视图切换效率低下的问题。实验结果表明, 该算法能够较好地解决节点动态加入或退出网络的问题, 且能达到传统PBFT算法的1/3拜占庭容错率。本文改进方案适用于网络状况不良且规模较小的联盟链网络, 并给出数字签名算法与共识算法相结合的研究方式。下一步将对PBFT算法流程进行优化设计, 增强签名的安全性, 以提高达成共识的速度及吞吐量。