区块链通过块链式数据结构存储并验证数据，辅以密码学^[1-2]方法保证数据传输和访问的安全性，具有高可信^[3]、可回溯、去中心化^[4]等特点，能够很好地解决数据存储对第三方的信任问题^[5]. 随着区块链技术的发展以及各行业数据规模的累计，传统的单链结构区块链系统已经无法满足愈发复杂的领域应用场景，主从区块链（master-slave blockchain，MSBC）结构，如星火链、COSMOS等，开始受到领域专家学者的关注，并逐步在教育、医疗、安全^[6]等领域广泛应用^[7-10]. 主从区块链通常包括主链和从属链2部分，分别由主区块和从属区块组成，每个主区块有且只有一个从属链. 各个主区块和从属区块之间分别通过前一个主区块和从属区块的哈希值相连，主区块与从属链通过唯一的哈希值进行映射.

主从区块链结构可以应对复杂分类场景的应用. 如金融领域中，采用主从区块链构建面向金融活动的企业区块链系统，主链中存储金融企业属性信息，对应的从属链存储其交易事件、金融活动等数据，通过区块链的共识机制^[11-12]保证数据不可篡改.

随着领域数据规模的不断增大，主从区块链系统存在的查询效率低、溯源时间长等问题^[13-14]愈发严重. 而现有区块链索引方法多只适用于单一链结构，且查询效率和索引构建时间均较差. 因此，如何针对主从区块链建立高效、可动态维护的索引结构，成为领域研究的热点和难点.

针对上述问题，本文提出一种面向主从区块链的多级索引构建方法（multi-level index construction method for master-slave blockchain，MSMLI）. 主要贡献有4个方面：

1）综合节点负载、节点信用和网络质量构建权重矩阵，提出一种基于权重矩阵的区块链分片算法（weighted matrix-based blockchain sharding algorithm，WMBS），基于主链特征实现主从区块链结构的动态分片；

2）在此基础上，针对现有区块链索引不适用于主从链结构的问题，提出基于跳跃一致性哈希的主链索引构建算法（master chain index construction algorithm based on jump consistent Hash，JHMI），通过主链的节点关键值与索引槽位映射，实现主链信息的高效查询；

3）结合区块链的数据特点，提出基于改进布隆过滤器的从属链索引构建算法（construction algorithm for subordinate chain indexes based on improved Bloom filters，IBF），优化基于列的选择函数，并给出索引查询方法；

4）在不同约束条件和数据集上与现有方法进行对比实验，验证本文所提方法的有效性.

1.   相关工作

目前，许多学者对于区块链的索引构建问题进行了深入研究，取得了一定研究成果.

文献[15]提出一种多维内存读取优化的索引方法Flood，通过联合优化索引结构和数据存储布局，自动适应特定的数据集和工作负载. 但是该方法无法检测到查询分布何时发生了足够大的变化，需要定期评估当前布局的查询成本对不同的工作负载完全重建索引. 文献[16]提出一种基于B级树的索引方法EBTree，支持对以太坊区块链数据的实时top-k、范围、等价搜索，但是该方法的索引节点均在Level DB中单独存储，且查询效率受节点大小影响较大. 文献[17]提出一种单通道学习索引RS（radix spline）方法，可以在排序数据的单次传递中构建，且只需要2个数据集，对大多数数据集友好，但是该方法会随着数据集的增长降低性能. 文献[18]提出一种基于子链账户交易链的索引方法SCATC，将交易链划分为子链并在每个子链的最后一个区块的账户分支节点上添加哈希指针连接每个子链，通过指针将遍历交易链的查询模式转化为子链查询来减少计算开销，但是该方法仅对较长账户交易链的查询效率有所改善且只针对明文状态下的查询优化，无法保证数据隐私性. 文献[19]提出一种用于大时间序列数据的可扩展分布式索引方法ChainLink，设计了一个2层分布式索引结构，使用单通道签名对数据进行散列，利用分区级数据重组来实现查询操作，但是该方法需要在本地对数据重组，无法保障数据安全性. 文献[20]提出一种基于中间层的可扩展学习索引模型Dabble，使用 K-means聚类算法，根据数据分布将数据集划分为K个区域并分别使用神经网络学习和训练，通过神经网络模型预测数据位置，但是该方法在数据集更新时需要重新训练模型，时效性较差，并且K值对模型的准确性影响较大.

2.   基于主从结构的区块链分片方法

为实现主从区块链结构的高效索引构建和查询处理，基于主链特征对整个主从区块链分片，并对各个分片赋予权重，据此构建整个主从区块链结构的分片权重矩阵；基于权重矩阵确定分片中的节点数目，为主链和从属区块链构建索引提供支撑.

2.1   权重矩阵构建

设主从区块链的节点数目为$x$，主从区块链分为$y{\text{ }}(y \ll x)$个分片，第i个分片为${f_i}(i = 0,1, {\text{…}} ,y - 1)$，各个分片权重为${\omega _i}$. 分片权重由节点负载、节点信用、网络质量3个维度的权重决定，其中节点信用和网络质量与分片权重呈正相关，节点负载与分片权重呈负相关，各项维度的权重由实验效果最佳的比例决定. 在进行分片权重计算前，由于上述3个维度的单位不统一，因此需进行归一化处理. 节点负载的归一化公式为

节点信用和网络质量的归一化公式为

第i个分片的权重为${\omega _i}$，计算公式为

式（1）（2）中的$d_{ij}^\prime$表示节点负载、节点信用和网络质量的原始数值，${d_{ij}}$为归一化后的数值，max和min分别为该项分量最大数值和最小数值. 式（3）中的${\omega _{ij}}$表示各项分量的权重（权重比例选择见4.1节）.

设2维权重矩阵M的各个元素由分片权重组成，获得各个分片的权重后，使用各个分片权重${\omega _i}$构建2维权重矩阵${{\boldsymbol{M}}_{p \times q}}$（其中$p \leqslant \sqrt y$，$q \leqslant \sqrt y + 1$，p，q为整数）. 对于任意一个分片f，都有$M[{f/p}][f\% q] = {\omega _f}$，矩阵中为空的元素置为0.

2.2   基于权重矩阵确定片内节点数目

基于2.1节的权重矩阵，确定各个分片内的节点数目. 首先，对矩阵中的分片权重进行线性归一化处理. 其次，对归一化后的所有分片权重按照比例离散，设离散比例权重值区间为[1,Q]. 最终获得分片比例权重Q－1，即该分片将对应Q－1个节点.

将节点进行编号，序号为0，1，…，$\sum\limits_{i=0}^{x - 1} {{\omega _i} - 1}$，则第k个分片对应的节点序号为$\left[ \sum\limits_{i = 0}^k {{\omega _i}},\;\sum\limits_{i = 0}^{k + 1} {{\omega _i}} - 1\right]$，在获取节点编号后，通过查表法得到分片的编号. 假定${\omega _i}$在进行归一化和离散化处理后得到的分片比例权重为7，则该分片将对应7个节点，并将这7个节点进行编号，编号顺序为0，1，…，6.

线性归一化后的分片权重的公式为

其中的${\omega _{{\text{min}}}}$为所有分片权重${\omega _i}$中的最小值，${\omega _{{\text{max}}}}$为最大值.

基于2.1节的权重矩阵的构建过程，提出了一种基于权重矩阵的区块链分片算法WMBS，其通过跳跃搜索（jump search，JPS）算法快速进行区块链分片与节点的映射，实现了主从区块链结构的分片. WMBS将节点关键值key、随机数r和权重矩阵作为输入，基于JPS使节点与分片逐一映射.key在节点加入区块链时创立，为32 b节点关键值，其由8 b的分片地址码和24 b的节点随机码组成，是节点的唯一标识；r是一个在[0,1]区间内均匀分布的随机数，由线性同余随机数发生器生成. WMBS算法如算法1所示.

算法1. WMBS算法.

输入：节点关键值key，随机数r和权重矩阵${{\boldsymbol{M}}_{p \times q}}$；

输出：节点行列号row，colmun.

① WMBS（key, r, ${{\boldsymbol{M}}_{p \times q}}$）

② int i，j；

③ for i = 0 to p−1

④ 　for j = 0 to q−1

⑤ 　　num_row = sum（M[i][j]）；/* 统计权重矩阵　　　　　　 中每一列的行数 */

⑥ 　end for

⑦ 　row = JPS （key, r, num_row）； /* 在每行均调　　　　　 用JPS算法确定节点所在行 */

⑧ 　row = row×q；/* 获得节点行号 */

⑨ end for

⑩ for i = 0 to q−1

⑪ 　num_col = M[i].length；/* 统计该行列数 */

⑫ 　colmun = JPS （key, r, num_col）；/* 调用JPS　　　　算法确定节点所在列 */

⑬ end for

为优化分片内搜索节点的路径，本文提出算法JPS，降低线性搜索算法的时间复杂度. 如算法2所示.

算法2. JPS算法.

输入：节点关键值key，随机数r和权重矩阵的行数或列数num；

输出：节点行号或列号b.

① JPS（key, r, num）

② int b = 0, j = 0；

③ random.seed（key, r）；/*以key和r为种子生成　　　　 随机数*/

④ while（j＜num）

⑤ 　b = j；

⑥ 　j = floor（（b+1）/random（））；

⑦ end while

⑧ return find_in_table（b）. /* 通过查表法获得分　　　　 片编号 */

3.   多级索引构建方法

由于主从区块链结构的主链和从属链存储的数据规模和信息类型均不同，通过WMBS算法分片后，本文提出一种面向主从区块链的多级索引构建方法（MSMLI），以满足主链和从属链的查询需求. 多级索引构建示意图如图1所示.

图  1  多级索引构建示意图

Figure  1.  Multi-level index construction schematic

下载: 全尺寸图片 幻灯片

如图1所示，在主链中，通过JHMI建立1级索引. 在从属链中，引入IBF建立2级索引，2级索引通过节点关键值进行关联. 当查询发生时，首先在主链索引中检索节点关键值，得到查询结果后，基于该结果在从属链索引中通过节点关键值获得元素信息.

3.1   基于跳跃一致性哈希的主链索引构建

基于主链存储的数据特点，本文引入跳跃一致性哈希算法，提出JHMI，实现主链索引的快速构建. 首先，根据各主链分片上的节点数量确定索引的槽位数量；其次，根据主链存储数据的哈希值确定各个节点关键值；最后，输入节点关键值和索引槽位数量，输出主链索引.

当分片中节点数量发生变化时，节点在索引中发生跳跃变化，部分节点重新映射. 设产生跳跃变化的哈希映射函数为ch（key, num_buckets），key为节点关键值，num_buckets为槽位数量，可得：1）num_buckets = 1时，只有1个槽位，所有key都映射到1个槽位中，即ch（key, num_buckets） = 0，所有节点都划分在0号槽位；2）num_buckets = 2时，有1/2的节点在ch（key, num_buckets） = 0，有K / 2个key重新映射即ch（key, num_buckets） = 1，跳跃到1号槽位；3）当槽位数从n变为n+1时，有n/（n＋1） 的节点所在的槽位保持不变，即ch（key, num_buckets） = n−1，有1/（n+1）个key需要重新映射，即ch（key, num_buckets） = n.

设b为节点上一次跳变的结果，j为发生跳变前最后一次槽位扩充时槽位的数量，当分片内节点数量发生变化时，节点重新映射的示意图如图2所示.

图  2  节点重新映射图

Figure  2.  Diagram of node remapping

下载: 全尺寸图片 幻灯片

由图2可知，对于任意的$i \in [b + 1,j - 1]$，增加节点数量且没有发生跳变的概率为

在[0,1]区间取一个均匀分布的随机数$r$，由式（5）可得，当$r < {{(b + 1)}/r}$时，节点就会跳变成$j$，则$i$的上界为${{(b + 1)} / r}$. 由于对任意的i都有$j \geqslant i$，则$j = floor({{(b + 1)}}/ r)$. JHMI算法如算法3所示.

算法3. JHMI算法.

输入：节点关键值key，槽位数量num_buckets和空主链索引s；

输出：主链索引s.

① JHMI（key, num_buckets, s）

② int b = 1, j = 0；

③ while（j＜num_buckets）

④ 　b = j；

⑤ 　key = key × 2862933555777941757ULL + 1；　　　　　 /* 根据存储数据的哈希值确定各个节点　　　　　 关键值 */

⑥ 　j = （floorb/key）；

⑦ 　s[] = b；

⑧ end while

⑨ return s.

3.2   基于改进布隆过滤器的从属链索引构建

从属链存储的数据具有规模大、多源异构的特点，因此，在从属链索引构建过程中，本文重构布隆过滤器数据结构，提出IBF算法.

首先构建基于改进布隆过滤器的从属链索引的数据结构为2维数组A[p][q]，其中$p = 2{^n}$（n为正整数），q中的数据长度为$l_q$，设$l_q = 32/64$ b，其取值由CPU中通用寄存器的缓存行长度决定，以减少内存访问，提高查询性能. 设改进布隆过滤器的K个哈希函数为Hash（key），其中，key为节点关键值，设一个改进布隆过滤器中可以存储的元素长度为len，则len计算结果为

在完成索引数据结构构建后，将所有位点初始化为0，对每个主区块对应的从属链构建索引，具体有3个步骤：

1）使用选择列的函数，先将元素映射到对应列，该元素将在对应列的位点；

2）通过K个哈希运算函数获得位点；

3）将对应位点置为1.

其中，步骤1中的列选择函数产生了额外的计算开销，为降低计算开销，将优化哈希函数，从属链上存储的交易哈希值是交易经过SHA256哈希函数运算得到的，因此优化步骤1的选择列函数为以SHA256哈希函数为基础，通过取模运算得到选择列的函数. 步骤1中的选择列函数可表示为

步骤2中的K个哈希函数由K个按位与运算组成，可表示为

式（7）中的v为布隆过滤器中的元素，${q_v}$为进行列选择后获得的列号. 在获得元素所在列后，确定该元素在构建和查询时都将被限制在对应列. 式（8）中${p_v}^i$为在获得列号后在该列中通过K次式（8）的运算获得的行号，即对应位点，${k^\prime }$为在通用布隆过滤器中的数组长度. 基于改进布隆过滤器的从属链索引构建算法如算法4所示.

算法4. IBF_Construction算法.

输入：从属链元素集合${V^\prime }$，元素v，改进布隆过滤器数组长度k和通用布隆过滤器数组长度${k^\prime }$；

输出：元素位点p和选择列q.

① IBF_Construction（${V^\prime }$, v, k, ${k^\prime }$）；

② int p = 0，q = 0；

③ for v in ${V^\prime }$

④ 　q = v % ${2^n}$；/* 选择元素所在列 */

⑤ 　p = v & $\sum\limits_{i=i-1}^{i \times \tfrac{{{k^\prime }}}{k} - 1} {{2^{i - 1}}}$；/* 获得元素位点 */

⑥ end for

在构建完从属链的索引后，提出一种根据从属链上节点关键值和选择列函数的基于改进布隆过滤器的从属链索引查询算法，如算法5所示.

算法5. IBF_Query算法.

输入：查询元素v，改进布隆过滤器中的元素V；

输出：判断结果.

① IBF_Query （v, V）；

② int p = 0，q = 0；

③ for v in IBF

④　 q = v % ${2^n}$；/* 选择元素所在列 */

⑤ 　p = v & $\sum\limits_{i=i-1}^{i \times \tfrac{{k'}}{k} - 1} {{2^{i - 1}}}$；/* 获得元素位点 */

⑥ 　if（A[p][q] == 1）

⑦ 　　output yes；

⑧ 　end if

⑨ end for

4.   实　　验

本文实验环境为16台4 TB存储空间，128 GB RAM，16核24线程i9-12900KS CPU的服务器集群，服务器之间通过高速局域网通信，每台服务器均部署Ubuntu 18.04操作系统. 实验采用2个不同的数据集进行实验验证：数据集1为公共以太坊网络中的前3 000 000个区块，数据集1中有15 362 853笔交易；数据集2为Lognormal人工数据集，Lognormal数据集按照对数正态分布，以均值为0、方差为2的方式采样了500万条不重复的数据. 本节将从索引构建时间、查询时间、内存消耗3个方面验证MSMLI的高效性和低内存的优点.

4.1   分片权重比例选择

在分片准备阶段将通过服务器构建10个分片，1个服务器构建1个节点并将节点分配到对应分片. 分片中的节点容量设置为500个节点. 对比节点数目设为100，200，300，400时，分片权重的3个维度节点负载、节点信用、网络质量的比例分别设置为3∶3∶4，4∶3∶3，5∶2∶3三种情况. 实验结果如图3所示.

图  3  分片权重比例

Figure  3.  Shard weight ratio

下载: 全尺寸图片 幻灯片

由图3可知，在节点数量相同时，情况1的实验效果最好，且随着节点负载维度的比例增大时，分片时间增加. 随着节点数量的增多，情况2和情况3的时间明显增加，而情况1的时间增幅不大，维持在5s左右. 因此，本文将按照主区块链对区块链分片时节点负载、节点信用、网络质量的分片权重为3∶3∶4的比例进行.

4.2   索引构建时间对比

为在索引构建时间方面验证本文提出的MSMLI方法的高效性，将分别对比改进区块链结构的EBTree方法和引入神经网络的Dabble模型方法. EBTree方法中的内部节点的能力设置为128，叶节点的能力设置为 16. Dabble模型中的K=100，MSMLI方法的1个分片中的节点数设置为100. 在本节实验中，将分为3种具体情况讨论.

如表1所示，使用2个不同规模的数据集将MSMLI方法与EBTree，Dabble这2种方法进行索引构建时间对比. 索引构建时间对比实验结果如图4、图5所示.

表  1  索引构建时间对比

Table  1.  Index Construction Time Comparison

情况	数据集1				数据集2
	MSMLI	EBTree	Dabble		MSMLI	EBTree	Dabble
情况1	从属区块数据为空，主区块数目分别为500，1000，1500，2000				从属区块数据为空，主区块存储500，1000，1500，2000条数据
情况2	主区块数据为空，从属区块数目为50万、 100万、150万、200万、250万、300万				主区块数据为空，从属区块存储2万、4万、6万、8万、10万条数据
情况3	主从区块数据均非空，主区块数目分别为500， 1000，1500，2000，从属区块数目为50万				主从区块数据均非空，主区块存储500，1000， 1500，2000条数据，从属区块存储2万条数据

下载: 导出CSV 

| 显示表格

图  4  数据集1上索引构建时间对比

Figure  4.  Index construction time comparison on dataset 1

下载: 全尺寸图片 幻灯片

图  5  数据集2上索引构建时间对比

Figure  5.  Index construction time comparison on dataset 2

下载: 全尺寸图片 幻灯片

由图4、图5可知，随着数据量的增大，MSMLI方法与现有方法对比，在索引构建时间方面优化了约9.28%，其中Dabble方法训练神经网络模型需要约15 s，因此，MSMLI方法大大优于Dabble方法.

4.3   查询时间对比

在本节实验中，首先将索引和数据加载进内存，为测试MSMLI方法的查询性能，将使用不同规模数据集和查询条件对比查询响应时间.

4.3.1   大规模数据集查询响应时间对比

使用大规模数据集，数据集1为公共以太坊网络中的前3 000 000个区块. 对比EBTree方法和Dabble方法在主区块数目为50万、100万、150万、200万、250万、300万，从属区块数目为1000时的查询响应时间，实验结果如图6所示.

图  6  大规模数据集索引查询时间对比

Figure  6.  Index query time comparison of large-scale dataset

下载: 全尺寸图片 幻灯片

由图6可知，在大规模数据集上MSMLI方法与现有方法对比，在索引构建时间方面优化了约13.44%，区块数量增大时EBTree方法优势更明显.

4.3.2   小规模数据集查询响应时间对比

使用小规模数据集，数据集2为Lognormal人工数据集，其中具有500万条数据，总大小约24 MB. 对比EBTree方法和Dabble方法在主区块存储10万、20万、30万、40万、50万条数据，以及从属区块存储1000条数据时的查询响应时间，实验结果如图7所示.

图  7  小规模数据集索引查询时间对比

Figure  7.  Index query time comparison of small-scale dataset

下载: 全尺寸图片 幻灯片

由图7可知，在小规模数据集上MSMLI方法与现有方法对比，在查询时间方面优化了约10.71%. 实验结果表明MSMLI方法在数据量大时查询性能更好.

4.4   内存消耗对比

MSMLI方法在分片阶段构建的权重矩阵几乎不占用内存，主链基于跳跃一致性哈希算法构建索引，跳跃一致性哈希对比经典的一致性哈希几乎没有额外内存消耗. 因此MSMLI方法中的内存开销主要考虑从属区块链的索引构建.IBF的假阳性设置为0.0137，$\mathop l\nolimits_q = 64$ b. EBTree方法改写区块链结构，内存消耗主要为区块数据. MSMLI方法与Dabble方法的对比实验结果如表2所示.

表  2  内存消耗对比

Table  2.  Memory Consumption Comparison

索引方法	Lognormal占用内存/MB	方法占用内存/KB
Dabble	24	4
MSMLI	24	2.048

下载: 导出CSV 

| 显示表格

由表2可知，Lognormal数据集占用内存24 MB；Dabble方法占用内存4 KB；对于MSMLI方法，IBF在保证假阳性可允许范围内仍仅占用内存约2.048 KB，即使将IBF与BF在相同假阳性要求下仍能保持相同数量级.

5.   结　　论

随着区块链技术的广泛应用，传统单链结构已逐渐无法满足日益增长的领域数据存储需求，主从区块链开始广泛应用于金融、教育、安全等领域. 针对现有主从区块链系统查询效率低、溯源时间长的问题，本文提出一种面向主从区块链的多级索引构建方法（MSMLI）. 该方法首先将整个主从区块链结构按照主链将结构进行分片，并采用权重矩阵提高分片可维护性，为索引构建提供支持；在此基础上，针对主链和从属链数据规模不同的特征，提出基于跳跃一致性哈希的索引构建方法（JHMI），以及基于改进布隆过滤器的从属链索引构建方法（IBF），提高主从区块链查询效率. 实验结果表明，本文提出的MSMLI方法对比现有方法，在构建时间、查询效率、内存占用方面具有很大优势，为主从区块链的快速检索提供了一条有效途径.

作者贡献声明：王俊陆提出了算法思路和实验方案；张桂月负责完成实验并撰写论文；杜立宽参与了审稿专家提出的关于查询实验部分的修改工作并补充了重要的参考文献；李素参与了审稿专家提出的关于文章具体内容上的修改工作，补充了文章框架和内容；陈廷伟提出指导意见并修改论文.