基于分区型区块链医疗电子病历共享方案

李 莉，吴 怡，杨祉坤，陈云鹏

（东北林业大学信息与计算机工程学院，哈尔滨 150040）

0 引言

随着信息科技发展与医疗行业需求剧增，医疗数据电子化成为普遍趋势。医疗电子病历（Medical Electronic Record，MER）以数字化形式存储着患者的诊疗信息，有助于提供更加便利的健康记录存储服务［1］。MER 数据共享被认为是改善医疗服务质量、减少医疗差错和降低医疗成本的一个有效方法［2］，有助于医疗行业的正向发展。但是目前国内许多医院或医疗机构使用传统数据库存储患者信息，不同机构之间无法直接进行数据共享，数据互操作性较差，普遍存在信息孤岛问题［1］；同时，患者的敏感数据统一存储在医院服务器中，患者对自己病历的掌控度低，这就易产生存储安全、隐私泄露等问题。对此，区块链去中心化、可追溯、不可篡改和分布式存储的特点能够满足医疗数据共享的多层要求。

基于区块链的优点，许多研究者就区块链技术在医疗场景的应用上提出共享方案，但是由于区块链自身的性能限制，目前大多数的区块链系统不能提供高吞吐率以及高可伸缩性来满足当前的大数据量或大交易量的处理需求［3］。区块链的“不可能三角”理论［4］表明应用的安全、性能和去中心化很难达到三者的平衡状态，例如比特币系统通过牺牲性能来维护网络安全和去中心化。而在区块链医疗应用场景下，由于潜在用户群体庞大、链上操作较为频繁、数据存储量较大以及对数据流转效率有较高要求等原因，要求底层区块链在不断扩增的用户节点与数据量下，还能保证其交易速度与效率。为了提高区块链吞吐量与可扩展性，将分片（Sharding）技术引入区块链系统进行水平扩容（也称为横向扩展，Scale-Out），使其在保证网络去中心化和安全性的情况下可有 效提高性能，如 Elastico［5］、RapidChain［6］、Omniledger［7］、Monoxide［8］、ZILLIQA［9］等系统就引入了分片技术，由分片技术缓解了单链结构下数据存储与节点共识的压力，并利用分片间的并行特性增大吞吐量，可扩展性也得到了一定程度的提升，但应用到医疗数据共享场景上的并不多见。

针对传统区块链不足以提供性能、效率与可用性高的基础架构的问题，本文基于分区型区块链（Sharding-based Blockchain）提出MER 共享方案，方案中使用周期性哈希算法进行网络分片，同时在分片中引用改进了数字签名的实用拜占庭容错（Pratic Byzantic Fault Torent，PBFT）共识协议，以此来抵抗女巫攻击并降低PBFT 的通信复杂度。在分片间设计了一种双层结构，使用主链达到片间共识，分片中的节点只需存储当前分片的链上数据。最后，在此基础上提出一种基于多关键词可关联检索的医疗数据共享方案。

1 相关工作

1.1 分区型区块链

在区块链中使用分片技术最先由Zilliqa 团队［9］于2015年提出。分区型区块链（Sharding-based Blockchain）主要在系统模型和共识层对区块链进行改造［10］，将全网节点划分到若干分片中，在每个分片中通过共识机制保持数据一致，只验证处理并保存与本分片相关的区块链数据，相当于一个相对独立的小区块链系统。各个分片之间可相互通信，所有分片中的数据可以组成一条完整的区块链，即由多条物理上分区存储的分区链组成逻辑上完整的全局链［10］。

分片架构能并行处理交易，因此分区型区块链的吞吐量会随着网络规模增加而线性增长。

1.1.1 分片技术

分片通常被划分为网络分片、交易分片和状态分片。

1）网络分片（network sharding）。网络分片在网络层将所有节点划分到不同的分片中，是交易分片和状态分片的基础。

2）交易分片（transaction sharding）。交易分片将全网交易划分到不同的分片中验证并打包，全网多个分片可以并行处理不同的交易，从而提升全网的整体性能。

3）状态分片（state sharding）。状态分片将完整的账本信息分别存储到各个分片中，各个节点不再存储完整的区块链状态信息，每个分片内各自维护部分的账本信息。

1.1.2 共识机制

工作量证明（Proof of Work，PoW）是通过算力比拼进行挖矿的一种共识机制。对于采用PoW 共识的含n个分片的区块链来说，算力随全网任务被划分到不同分片中，单个分片只能得到原来1/n的算力保证，恶意节点想攻占单个分片所需的算力只需原来攻占整条区块链的1/n，攻击难度降低。因双花攻击导致的分叉概率增大，系统安全也大打折扣。

实用拜占庭容错（PBFT）要求每个区块必须由共识组中绝大多数诚实节点签署，每个诚实节点通过签名确认其已验证了区块中交易的合法性和有效性。PBFT 可容忍数量小于(n-1)3 的故障节点或作恶节点，节点之间需要进行端到端（Peer to Peer，P2P）的共识同步，提供了交易最终性，不存在分叉问题，对双花攻击有较好抵御能力。由此，有多个分片项目如文献［5-7，9］，在分片内都选择了PBFT 共识机制。

采用PBFT 协议可以避免基于算力的恶意攻击，但是存在面临女巫攻击（Sibyl Attack）的风险，且在其多对多（All-to-All）的消息模式下通信复杂度极高，伴随巨大的通信开销。PBFT 可以利用小规模分片的优势发挥高效能，但是文献［9］表明，每个分片不少于600 个节点时，其至少包含1/3 恶意节点的概率才会降为百万分之一。

可扩展的去中心化信任基础设施区块链（Scalable decentralized Trust inFrastructure for Blockchains，SBFT）［11］基于PBFT 进行设计上的改进，继承其安全特性的同时提高扩展性，吞吐量可达PBFT 的两倍，延迟也更低。SBFT 使用比RSA 更短、更快的BLS 签名算法，其基于椭圆曲线，有更高的实用性和安全性，支持批量验证签名。

区别于多对多消息模式，SBFT 提出了一个使用收集器（Collector）线性通信模式。这种模式下不再将消息发给每一个副本节点，而是发给收集器，再由收集器广播给所有副本节点，同时通过使用门限签名可将消息长度从线性降低到常数，将客户端通信量从O(n)降低到O(1)。

1.2 PECKS

基于公钥密码体制的多关键词关联检索可搜索（Public key Encryption with Conjunctive field Keyword Search，PECKS）加密共享方案的概念源于文献［12］，其目的是在PEKS（Public key Encryption with Keyword Search）的基础上引入多关键词关联检索。在可搜索加密技术中引入非对称密码体制，基于双线性对运算，为不可信服务器的密文检索以及多关键词关联检索提供解决办法。

1.3 双线性映射

定义1令G1和G2为两个阶数为素数q的乘法循环群，定义一个双线性映射e：G1×G1→G2，其满足以下性质：

1）双线性性（Bilinear）：对于任意a，b∈和x，y∈G1，都有e(xa，yb)=e(x，y)ab。

2）非退化 性（Non-degenerate）：存 在x，y∈G1，使 得e(x，y) ≠1；如果g是G1的生成元，那么e(g，g)是G2的生成元。

3）可计算性（Computable）：对于任意x，y∈G1，存在有效算法计算e(x，y)。

1.4 门限签名

对于一个(n，t)门限签名（Threshold Signature）方案，假定存在一个公钥，而n个签名者每人都拥有自己的私钥分片，只要其中至少t个签名者对消息进行部分签名，其中t≤n，那么由这t个部分签名可以得到对消息的完整签名，并且这个完整签名可由公钥来验签。

2 基于分区型区块链MER共享方案设计

2.1 分片构建

本文方案基于跳跃一致性Hash（Jump Consistent Hash）算法［13］实现分片划分，跳跃一致性Hash 算法是一种零内存消耗、均匀分配、高效的一致性Hash 算法［14］，通过加入周期参数，实现分片划分的周期性，预防女巫攻击。

该算法具有：

1）平衡性：把网络节点均匀地分布到所有分片中。

2）单调性：当分片的数量发生变化时，只需要把一些节点从旧分片移动到新分片中，不需要做其他移动。

3）周期性：当处于同一周期，随分片数目的增加分片划分保持单调性，当周期因自适应算法产生变化，则所有节点重新随机划分。

具体算法如算法1 所示。

其中，设r=random.next（）是在［0，1］区间均匀分布的随机数。当输入节点关键值为key，周期参数为period，分片数目为num_buckets时，PeriodJumpConsistentHash（key，period，num_buckets）返回该节点在当前周期内要被划分到的分片编号。跳跃一致性Hash 算法将传统一致性Hash 算法的时间复杂度从O(n)降低到O(logn)。

2.2 共识机制

2.2.1 分片内SBFT共识协议

本文方案基于SBFT［11］实现片内共识。SBFT 有两种区块提交模式，分别为Fast Path 和Linear-PBFT，在新的视图转变协议下支持两种模式同时运行，并无缝切换。SBFT 两模式共识过程如图1 所示。

图1 SBFT共识过程Fig.1 Consensus process of SBFT

分片内共识过程描述如下：

1）预准备阶段：当医生想上传病历数据或数据用户想要进行访问操作时，客户端（Client）向当值主节点（Primary）发起请求，主节点收集达到数量的请求集合后打包成区块，并作为预准备信息广播给分片内的其他副本节点（Replica）。

2）门限签名阶段：副本节点收到预准备信息后，对其进行检查验证，若信息合法则对其哈希运算并进行门限签名（σ(3f+c+1)），将签名消息发送给当前收集器C（CCollector）。收集器C 收集到3f+c+1 个不同的签名消息后整合签名，并发送整合消息给其他副本节点验证。副本节点收到消息后，若检验通过则确认接受，并进行操作。

3）区块提交阶段：分片内达成区块提交共识后，各节点执行块内请求并更新系统状态与状态摘要，对摘要进行门限签名（π(f+1)）后发送消息给收集器E（E-Collector）。收集器E 收集到f+1 个不同的签名消息后整合签名，并发送整合消息给其他副本节点验证，副本节点检查签名决定是否接受；同时给每一个发起操作请求的客户端发送执行确定消息，用户检查消息有效则确认操作已执行。

其中，在当前Fast Path 模式中收集器C 收集的签名足够整合τ签名（τ(2f+c+1)）但不够整合σ签名且等待超时时，就发送准备消息给所有副本节点进入Linear-PBFT 模式。副本节点收到消息并进行检查，若通过则进入阶段2）向收集器C发送签名消息（其中使用τ签名）。

SBFT 在Fast Path 模式下可以在3f+2c+1 个副本节点的系统中容忍c个故障副本节点，在Linear-PBFT 模式下可容忍f+c个。

2.2.2 分片间共识协议

系统初始只存在一个分片，随着加入节点的增多，分片根据自适应算法判断是否需要增加分片。节点根据跳跃一致性Hash 算法被划分到不同的分片中，并定期进行节点的重新划分，划分更新的时间由自适应算法决定。

当分片中确定提交（committed）某个区块后，会更新本分片状态与总系统状态，系统中存在一条总链，整合各个分区的子链信息，分片内节点只需要存储当前分片的区块链数据，使分区型区块链在物理上多链、逻辑上单链，结构模型如图2 所示。

图2 本文双层区块链结构模型Fig.2 The proposed two-layer blockchain structure model

分片中区块结构同传统区块相似，同样使用了默克尔树（Merkle Tree）来认证数据信息，块头中含有块内所含数据涉及的所有病人地址信息与医生地址信息，指向默克尔树中的哈希值，同时包含区块在分片内所处位置标识。总链中区块块头包含该区块在系统区块链中所处位置标识，两标识可互相验证，供周期分片时节点聚合片内信息所用。

分片中committed 的区块的块头被分片主节点上传给主链，系统验证块头哈希、签名的正确性，若验证通过则计算M_Hash=H(s_id‖s_hash‖Pre_Hash‖n‖Tmp)，封装原区块块头并链接主链，同时返回该区块在总链中的序号给分片，更新分片状态。其中：s_id是分片区块位置标识，s_hash是区块在分片中的哈希标识，Pre_Hash是前一个区块哈希标识，n是区块在总链中的位置标识，Tmp是时间戳。分片通过位图B记录并更新分区状态，如B[i]=(n，M_Hash)表示分片内第i个区块在主链中的序号为n，哈希标识为M_Hash，若存在恶意变化则很容易被检测出来。状态更新流程如图3 所示。

图3 区块提交状态更新流程Fig.3 Status update process of block committed

2.3 本文共享方案

本文共享方案基于PECKS［12］构建，适应医疗电子病历共享，各个医疗机构组成联盟链，共享模型如图4所示。

图4 本文共享模型Fig.4 The proposed sharing model

1）系统初始化：Setup(1k)→parameters，给定安全参数1k，系统生成公开参数parameters={p，g，G1，G2，e}，其中G1的生成元为g，e：G1×G1→G2，G2的生成元为e(g，g)，p是大素数。定义哈希函数H1：{0，1}*→G1，同时设置系统医疗关键词集Words。

2）密钥生成：KeyGen(k) →(Rk，Pk)，用户通过医疗机构注册，获得联盟链准入许可。当用户第一次注册进入联盟链，系统根据用户标识idk派发公私钥对(Rk，Pk)，其中Rk=[s1，s2]，Pk=[g，Y1=s1g，Y2=s2g]，s1，s2∈Zp，并将公钥地址作为key值输入对用户节点进行分片划分。

3）数据共享：PECK(Pk，M，D) →(S，MEn)，选择随机数r∈Zp，输入用户公钥以及需要加密的文件M与关联关键词向量集D，生 成S=[A1，A2，…，Am，B，C]，其 中Ai=e(rH(Wi)，Y1)，i∈[1，m]，B=rY2，C=rg，Wi是在D中第i个位置的关键词，H()使用哈希函数SHA256。加密生成MEn=(M)=(U，V)，其中U=rPk，V=M×e(rg，H1(idk))。病人看诊时，由医生生成相应的MER 文件M→{0，1}*，并从系统关键词集Words中选择与MER 文件相关的医疗关键词并形成向量集D=(W1，W2，…，Wm)，其中若有未设关键词位置可设为空。病人使用自己的公钥对MER 文件与相关关键词集进行加密处理。最后得到文件的哈希值hm=Hash(S‖MEn)，病人与医生同时用自己的私钥对其进行聚合签名（ECSchnorr 签名算法）以便之后共识组成员检验，封装后由医生上传至系统分片中。

4）陷门生 成：Trapdoor(Rk，Q) →TQ，选择随机数则陷门TQ=[T1，T2，I1，I2，…，It]，其中查 询Q=(I1，I2，…，It，Ω1，Ω2，…，Ωt)，t是查询Q中的关键词数目，Ii∈[1，m]（i∈[1，t]）是关键词在关键词集中的位置，Ωi是要搜索的关键字。数据使用者希望查找病人的关键词为(Ω1，Ω2，…，Ωt)的相关医疗记录时，病人授权并使用自己的私钥生成相关陷门TQ供其检索，获得加密文件。其中，数据使用者指需要获取相关数据的链上用户，多为需要为病人诊治的医生或病人自己，还包括医疗保险相关人员。

5）多关键词关联检索：Test(Pk，S，TQ)，系统检验×…×AIt=e(T1，B+T2C)是否为真，若为真则返回。查找时，通过分片之间的交互通信，将检索申请广播给每一个分片，多个分片可以并行查找。分片中，先根据块头中的病人公钥地址进行匹配，匹配成功则执行关键词检索，若检索成功且哈希验证正确则返回密文，用病人私钥进行解密。

由正确性分析可知，若=Ωi，i∈[1，t]，则：

6）数据解密：De(MEn，Rk) →M，经检索若有密文返回，病人使用自己的私钥进行数据解密，计算得到明文数据M。由正确性验证得：

3 方案性能分析与对比

3.1 功能性分析

本文共享方案实现多关键词关联检索密文，只有病人的私钥才可以生成检索陷门以及解密，病人对自己隐私数据的掌控度极大提升，同时也减少了数据泄漏的安全隐患问题。对密文进行基于关键词的检索时，多关键词间可以有多种组合，检索更有针对性，实现细粒度安全共享。如表1 是多种方案的功能对比。

表1 不同方案的功能对比Tab.1 Function comparison among different schemes

3.2 安全性分析

3.2.1 安全功效分析

1）隐密性。本文方案对病人敏感数据都进行了加密处理。MER 文件与相关关键词集都由病人密钥进行加密处理，恶意攻击者无法解密获得数据内容，很好地保护了病人隐私。

2）数据可控性。只有病人使用私钥才能生成搜索陷门TQ，也只有其私钥才能通过式（2）解密检索得到MER 密文，有效对数据进行访问控制。

3）数据安全性。数据共享过程中，MER 文件与关键词集都是以密文形式上传、存储，没有私钥则无法解密；而数据在上传并达成区块共识后就不可更改、删除，病人与医生共同对文件哈希hm=Hash(S‖MEn)进行聚合签名，可以同时使用病人与医生的公钥进行验证，同时区块中默克尔树与块头哈希也可验证区块数据的正确性与完整性。

4）不可伪造性。基于区块链可追溯、不可篡改以及哈希函数抗碰撞的特性，其检索结果必然是可信的，用户也可以轻易验证数据有效性。数据一旦被篡改或出现伪造数据，则可通过各处哈希值检验出来。

3.2.2 安全性证明

定 理1基于双 线性映 射e：G1×G1→G2，DBDH（Decisional Bilinear Diffie-Hellman）问题是指可以在多项式时间内区 分五元 组 (g，αg，βg，γg，e(g，g)αβγ)与(g，αg，βg，γg，e(g，g)μ)，其中α，β，γ，μ∈Zp，g，αg，βg，γg∈G1。

定理2假设敌手A 在多项式时间内能以优势ε赢得游戏，则证明挑战者B 能够以至少ε(emqT)的优势解决DBDH困难问题。

该证明基于文献［12］的自适应安全定义，假设A 最多进行qT次门限询问，挑战者B 的目标是在输入(g，αg，βg，γg，X)时若X=e(g，g)αβγ，则输出1，否则输出0。游戏过程如下所示：

1）密钥生成。挑战者B 选择一个随机数s∈Zp，给敌手A 公钥PA=[g，Y1=αg，Y2=sg]，对应的私钥为RA=[α，s]。

2）哈希询问。在任何时候A 可以询问随机H，B 维护了一个初始为空的H-list元组列表，当A 在点Wi∈{0，1}*查询H时，B 的响应如下：

5）挑战。最终A 产生关键词W和希望挑战的位置z，B生成PECK 挑战如下：

B 执行上述算法来相应H查询以获得如H(W)=h的h，令为H-list上的对应元组，如果c=1，则B 失败。

B 选择除Wb，z外的随机关键词Wi，j，其中i∈{0，1}，j∈[1，m]，然后生成Di=(Wi，1，Wi，2，…，Wi，m)，限制是之前的门限无 法区分D0与D1，否则重新生成。给定Wb，j，令是H-list上的对应元组，其中b∈{0，1}。

B 回应挑战[A1，A2，…，Am，B，C]与两个文档D0、D1，则挑战值计 算如下：若cb，j=0 则Aj=，否 则Aj=e(ab，j(γg)，αg)；B=s(γg)，C=γg。

若X=e(g，g)αβγ，则挑战 为 [e(γH(Wb，1)，Y1)，e(γH(Wb，2)，Y1)，…，e(γH(Wb，m)，Y1)，γY2，γg]，对 于Db来说是有效的PECK。

6）更多询问。B 像之前一样对这些询问做出响应，唯一的限制是没有门限查询可以将D0与D1区分开。

7）输出。最后，A 输出b′∈{0，1}，表示挑战是D0还是D1的加密，若b′=b，则B 输出1，表示X=e(g，g)αβγ，否 则输出0。

假设qT足够大，则，此处e 为自然对数底数。又，其中事件η1表示B不会因任何A 的门限查询而中止，事件η2表示在准备对A 的挑战期间B 不会中止。因此，B 可凭借优势解决DBDH 问题。

结论1 假设DBDH 问题是难解决的，则本文方案在语义上对于自适应选择的关键词攻击是安全的。

3.3 性能分析

3.3.1 扩展性分析

本文方案采用分区型区块链构造底层数据结构，将全网节点划分为较小的共识组，每个分片间能够并行处理事务，在可扩展性、吞吐率等性能方面得到很好的提升。同时基于跳跃一致性哈希算法作为网络分片算法，实现轻巧、快速，内存占用小，映射均匀，满足一致性与均匀性［13］以及周期性。

分片间使用总链结构，通过哈希运算封装块头并链接，使各个分片只需存储与本分片相关的区块数据，而不是整个区块链数据，实现物理上多链、逻辑上单链的半状态分片，降低存储压力，提高可扩展性，片内SBFT 机制也实现共识扩展性提高。本文方案使用C++语言，基于Crypto++库、RELIC 密码库，实验环境配置如下：

1）CPU 为Intel Core i7-6700 CPU@3.40 GHz；

2）内存为RAM 8 GB；

3）操作系统为Ubuntu 18.04 over VMware Workstation Pro 16.1.1。

如图5 所示，在非分区方案中，由于共识机制使用了SBFT，通信效率提高，在节点数量控制在200～300 时能够得到较高的吞吐量，但是在节点数量不断增加的情况下，单链的共识效率明显下降，吞吐量随节点倍增而大幅降低；而在本文方案中，以平均200 个节点为一个分区，随着节点增多，分片随之增加，保证片内共识效率的情况下多个分片并行运算，吞吐量也随之得到显著提高。

图5 吞吐量对比Fig.5 Throughput comparison

3.3.2 计算代价分析

表2 为本文方案与各方案计算代价对比，其中：Te代表指数运算时间，Tp代表双线性配对运算时间，Th代表哈希运算时间。加密阶段中m代表关键词向量集中关键字个数，检索阶段中t代表关联检索关键字个数。本文方案无需大量指数运算，加密阶段需要较多次的双线性配对运算，计算代价由关键词向量集大小决定，检索阶段计算代价随关键词关联个数变化。

表2 计算代价对比Tab.2 Comparison of calculation cost

3.3.3 数据检索扩展性分析

本文方案基于分片技术，各分片间可以互相通信且并行运算，在进行数据搜索时各分片可同时进行病人数据匹配，提高搜索效率，检索的时间复杂度从O(n)降为O(logn)。

图6 为在不同关键字检索个数下各方案的时间开销对比，基于本文方案，实验设置5 个分片，分别进行10、50、100和200 个关键字的检索测试。随着关键字检索个数的增加，各方案检索消耗时间都有所增大，在进行单关键字检索时本文方案在该阶段只需花费一次双线性配对运算与两次哈希运算，计算开销略高于文献［16］方案，但总体偏小，因而时间成本增长较为平缓。同时，5 个分片相当于将总链分为区块数据互不相交的5 个子链，可以同时进行关键字的检索匹配，通过并行分摊了检索压力，提高了承载能力，在关键字检索方面有较好的扩展性。

图6 检索时间对比Fig.6 Comparison of retrieval time

4 结语

本文的医疗共享方案在引入区块链的基础上应用分片技术，对底层结构进行水平扩容，提高可扩展性与吞吐率以及并行处理能力，同时使用跳跃一致性哈希算法增加周期性网络分片的随机性、稳定性与均匀性。针对传统PBFT 的网络宽带高负担，分片内使用具有扩展性的SBFT 共识协议，并通过底层主链的双层结构在链接各分片数据的同时降低单分片内节点的存储负担。共享方案基于公钥密码体制，只有病人的私钥才可以生成搜索陷门与对密文解密，同时可以通过多个关键词关联检索进行更有针对性的数据搜索，达成细粒度检索，使共享方案具有高安全度与高可控性。在并行分片中，吞吐率与检索效率等性能明显提高。

本文方案中，由于分片是随着节点增加而产生的，而先产生的分片必然比后产生的分片要生成更多区块，这就会造成区块数据在不同分片中分配不均，从而导致分片负载不均的问题，这是接下来需要继续完善的方向。在下一阶段研究中，可以继续专注于提升区块链性能，同时不降低其安全性，对此考虑对拜占庭节点进行监测，使每次分片时恶意节点尽量均匀分布在各个分片中且不会超过分片承载力，以防止女巫攻击；同时考虑在方案中应用智能合约，提高事务执行效率。