基于进化算法优化区块链系统的能源消耗

陈立军， 潘正军， 陈孝如

(广州软件学院 软件工程系， 广州 510990)

0 引 言

2008年,本聪描述了一种称为“比特币”的电子货币及其算法，其依赖于区块链技术，区块链引起了研究界和工业界的极大兴趣，已被应用于金融、制造业和学术界等多个领域。尽管区块链技术具有巨大的潜力，但存在能耗太高的问题[1]。基于区块链系统所消耗的能量至关重要，一个比特币交易使用的能量大约相当于1个英国家庭平均8周消耗的能量，此外，截至2021年3月31日，剑桥比特币电力消耗指数估计，比特币网络每年消耗137.20太瓦时的电力[2]。

在基于区块链的系统中，有一些相互冲突的目标，包括安全性、可扩展性、能源消耗、性能、分化和信任，虽然有不同的优化技术显示出解决许多领域优化问题的希望，但基于区块链系统的能源消耗最小化还没有被解决。由于工作证明(Proof of work，PoW)的能源消耗过高，学者提出了几种共识算法，如通过减少矿工的数量来降低能源消耗，提高环境的可持续性，这些算法在一段时间内跟踪矿工的行为，然后计算他们的信誉或信任值，这些值用于允许矿工添加块。在Bahri等[3]提出了一种新的共识算法信任证明(Proof of trust, PoT)，根据矿工网络构建的信任图随机选择矿工。Zhuang等[4]提出的一种共识算法，基于节点的交易活动、资产和共识参与来评估节点的声誉。由于共识算法是基于区块链系统的基本组成部分，一些研究提出了替代的共识算法来降低此类系统的能量消耗，例如权益证明(Proof of stake，PoS)，它使用矿工的股份决定哪些矿工应该添加下一个区块。其他技术要求矿工投资于特定的硬件，如高存储设备(如Proof of space)，或特殊的基于英特尔的硬件(如Proof of luck)。

笔者提出利用基于搜索的软件工程(Search-based software engineering，SBSE)技术来解决区块链的能源消耗问题，在SBSE中，软件工程问题被转化为搜索问题，然后使用基于搜索的优化算法寻找最优和接近最优的解决方案。提出使用进化算法优化基于区块链系统的能源消耗，通过选择矿工最小化能源使用和碳排放，同时最大化其他冲突的目标。

1 共识算法的优化

假设在基于区块链的系统中，信任供应是昂贵的，无论是在计算方面还是在能源方面，这些系统中管理信任所消耗的能量是一个优化问题，该问题表示为参与区块链系统的矿工子集选择问题，为了解决上述能源消耗和其他冲突目标之间的权衡问题，提出了一种新的优化模型，可以提高区块链系统环境的可持续性。模型采用了静态优化风格，首先执行优化，然后应用。虽然研究人员试图缩短创建一个新的区块[5]所需的时间，由于优化模型选择最优矿工和将交易添加到链中所花费的时间，导致大量的交易将等待很长时间，特别是对于基于区块链的大用户系统。将基于区块链的系统视为一个实体，将矿工视为一个代理，在基于区块链的系统中，矿工的数量、能源消耗、去中心化和矿工的声誉之间存在着一种内在的平衡，区块链网络的矿工越多，消耗的能源就越多，碳排放水平也就越高，它的分散性和信任度也就越高。此外，采矿者的更大权力下放导致对审查个别交易的更大阻力，从而使人们更信任这个系统。

1.1 解决方案表示

解决方案表示决定了问题在进化算法中的结构，以及可以使用的遗传算子，在所提出的模型中，染色体表示一个节点数组，代表区块链网络中的一组矿工，染色体的长度(基因的数量)正好等于参与挖矿过程的矿工数量，每个基因Xi都有一个布尔值，用于确定是否包含矿工。

1.2 优化模型

在这个模型中，设计了4个目标函数，这些函数用数学公式表示，以最小化基于区块链系统产生的总能源消耗和总碳排放量。

1.2.1 能耗目标

通过去中心化和公开透明的特性对碳排放量与每一笔交易信息进行溯源，避免数据被随意篡改的风险。文中的重点是通过节约矿工在计算过程中使用的能量，提高区块链系统的可持续性，这占了区块链系统的大部分能量消耗，功率是一个系统在一段时间内消耗能量或做功的速率度量，能量消耗的计算方法为。通过节约矿工在计算过程中使用的能量，提高区块链系统的可持续性，这占了区块链系统的大部分能量消耗，功率是一个系统在一段时间内消耗能量或做功的速率度量，能量消耗的计算方法为

(1)

式中：Pi——1个挖矿设备i所使用的包括处理器和内存在内的组件所需要的功率；

Ti——每天参与区块链网络的小时数；

mD——挖矿设备的数量。

由于优化目标是使帕累托(是博弈论中的重要概念)阵线的解决方案中，所有参与矿工的总能耗最小，能量值越小，解决方案就越合适，能源消耗最小化的优化公式为

(2)

式中：m——组成区块链网络的矿工总数；

Xi——解决方案表示中每个基因的值，它可以是“1”，表示选择矿工参与下一个区块的挖掘过程，也可以是“0”，表示未选择矿工。

1.2.2 碳排放目标

电力碳排放可以定义为生产或使用一定量电力所排放的温室气体，这表明基于区块链的系统降低能源使用，实际上会减少温室气体排放，因此，由采矿设备使用电力引起的碳排放可以定义为

C=EF×E,

(3)

式中：C——矿工产生的温室气体排放量；

EF——矿工所在地的电力排放因子；

E——使用式(2)计算的每个矿工的能源消耗。

文中优化了帕累托前沿解决方案中所有参与矿工产生的总碳排放最小化为

(4)

1.2.3 去中心化目标

由于去中心化是区块链的核心特征之一，文中希望将这一有价值的特征作为模型的一个目标，使用香农熵量化基于矿工算力分布的去中心化D，以防止一名矿工开采所有区块并控制基于区块链的系统(即51%攻击)，该目标最大化优化为

(5)

式中：m——基于区块链系统中的矿工数量；

Hi——帕累托前沿解决方案中矿工哈希率的分数。

Hi的计算公式为

(6)

式中：hi——每个矿工的算力；

ht——参与解决方案的矿工的总算力。

1.2.4 信誉目标

在文中模型中，矿工的数量将减少，因此需要通过提高基于区块链系统的信任级别支持PoW共识算法，可以通过计算每个矿工的信誉值提高信任级别，可以使用一定的可信度评估模型，将一个矿工的历史活动压缩成每个矿工的信誉值，由于建立信任或声誉模型不是本文的重要贡献，所以只采用受PoW和PoS思想启发的简单模型。

在优化模型中，使用一个sigmoid函数评估区块链网络中每个发布块之后的矿工可信度，收集关于每个矿工的两个特征，并使用它们计算声誉值，第一个特征是挖掘器添加到区块链的块数量，第二个特征是挖掘器拥有的权益，与PoW类似，假设矿工在完成大量具有重要需求的工作后不会攻击网络，矿机对货币数量的所有权应该是对网络攻击的一种保护，因为矿机不希望失去他们的货币，就像PoS一样，在这个模型中，矿机的声誉值是每个特征的sigmoid函数的和，因此，区块链网络中每个矿机R的信誉值可以计算为

(7)

式中：B——区块链中挖掘的块总数；

b——矿工挖掘的块数；

s——矿工获得的费用和奖励的总和。

最后一个最大化的目标是参与帕累托阵线解决方案的矿工的总声誉最大化RT，这反过来最大化了区块链网络的可信度为

(8)

1.2.5 适应度函数

式(2)、(4)、(5)和(8)具有相同的约束条件分别为

Xi∈{1,0}，

式中：hi——区块链网络中矿工i的哈希率；

Hc——将与其他矿工哈希率进行比较的当前矿工的哈希率；

TL——决策者必须为系统确定的百分比容差水平，决策者可以确定TL为50%或更低。

这些约束确保一个矿工的哈希率应该小于TL，例如单个解决方案中所有其他矿工的总哈希率的50%或30%，当恶意矿工的总哈希能力超过整个网络哈希能力的50%或30%时，可能会发起双重开销攻击或自私的挖掘攻击[6]，因此，此约束可确保避免此类漏洞。此外，他们还确保不止一名矿工参与采矿过程，以防止中央化。

该研究利用上述目标形成了4个适应度函数：能量与声誉、能量与碳的相对声誉、能量与分散声誉、能量与碳的相对分散声誉，在每个适应度函数中，至少有一对相互冲突的目标。

2 实 验

2.1 问题研究

在本文中，提出的模型旨在通过使用进化算法寻找一组矿工改善基于区块链系统的环境可持续性，本研究试图回答下面4个研究问题：

问题1优化模型能在多大程度上降低基于区块链系统的能耗；

问题2优化模型能在多大程度上减少基于区块链系统的碳排放；

问题3与随机搜索(Random search，RS)相比，选择的进化算法是否能有效解决区块链矿工选择问题；

问题4在使用的算法中，哪种算法的性能最好。

2.2 评估程序

2.2.1 能源消耗和碳排放

为了回答问题1和问题2，比较了每种算法在能源使用和碳排放方面的最佳解决方案，以及与原始解决方案相比冲突目标的退化情况，最初的解决方案是基于区块链系统中的一整套矿工。

2.2.2 绩效指标

2.3 部分进化算法

由于引入了一个新的优化问题(区块链矿工选择问题)，将提出的适应度函数整合到5个进化算法中，每个进化算法都有不同的机制保持解决方案的多样性，如非主导排序遗传算法II(NSGA-II)通过计算每个解决方案的拥挤距离来创建壁龛，在其选择运算符中使用拥挤距离来促进多样性[11]。

为了使解决方案多样化，帕累托进化算法2(SPEA2)[12]使用一个外部档案来存储非主导的解决方案，SPEA2还使用近邻密度估计技术来有效指导搜索，与SPEA2类似，帕累托存档进化策略(PAES)[13]是一种仅有变异的算法，当它创建新的解决方案时，使用一个d维的档案(d为目标数)作为参考集，为了促进多样性，PAES将目标空间划分为网格，并根据每个解决方案的目标值将其置于某个网格中，使用每个网格中的解决方案的密度来计算拥挤度，拥挤度量被用于对非支配性的解决方案进行排序，以优先考虑属于最不拥挤区域的非支配性解决方案。

超体积是一个主要的性能指标，它通过已找到的解计算搜索空间的主导比例，超体积越大，算法的性能越好，基于指标的进化算法 (IBEA)[14]使用超体积指标对解决方案进行排序。对于多目标问题等，Binh等[15]使用非支配排序遗传算法III (NSGA-III)，该算法利用预定义的搜索点将搜索空间划分为多个目标搜索，而不是一个大规模的搜索空间，通过从不同的壁龛中选择解决方案，而不是计算拥挤距离，解决了计算每个解决方案的多样性得分的问题。此外，它减少了多目标问题中大量的非支配解，因为每个最优解对应一个目标搜索段，使用上面讨论的算法，因为它们有不同的机制来保持解的多样性，这有助于有效地导航搜索空间[16]。文中的重点是在多目标函数优化开源框架(MOEA)内实现的本地算法，这些算法支持MOEA进化算法框架提供的所有功能，所选算法非常适合于解决与文献[17]类似的问题。

2.4 实现细节

实现细节的参数：矿工的数量为160，网络总块数为4 073，比特币奖励为6.25 BTC，比特币费用为0.000 281 88 BTC，采矿设备哈希率为110 TH/s，采矿设备功率为3 250 W，矿工运行时间为24 h，容忍度为50%。

2.4.1 比特币模拟器设置

文使用了一个名为 Bitcoin-Simulator[18]的区块链模拟框架，该框架使用真实和人工数据，例如矿工的哈希率和位置的分布，它是一种广泛使用的区块链环境模拟器，Bitcoin-Simulator模拟使用PoW共识算法及其网络层的基于区块链系统的工作，模拟器可以跟踪数以千计的节点和交易，它通过为每个矿工分配特定的挖矿哈希率和位置来为区块链网络中的矿工复制PoW过程，数据收集涉及模拟器以挖掘4 073个区块，相当于一个月的挖掘，模拟中有160名矿工，将基于区块链的系统中的百分比容忍度设置为50%，以防止矿工进行双重花费攻击。

为了复制一个基于区块链系统的真实场景，本文使用了比特币网络的基本属性，如表1所示的哈希率、奖励和费用。使用比特币，因为它是最广为人知的基于区块链的系统，根据从文献[4]中发布的CBECI检索到的信息来确定矿工位置的分布及其哈希率百分比，表1展示了挖掘者的位置分布和他们的哈希率占比特币网络哈希率的百分比w，矿工位置分在16个国家，每个国家有10个挖掘者。

表1 矿工的位置分布及其哈希率百分比

2.4.2 模型假设

在区块链网络中，无法准确估计挖矿操作使用了多少电力，因为无法确定网络中有多少台矿机或哪些机器在任何给定时间处于活动状态，为了确定区块链网络中的挖矿设备数量，首先假设所有矿工都使用效率最高的挖矿设备，并且随着矿工哈希率的增加，他们的设备数量也会增加，此假设基于这样一个事实，即使用效率低下的设备会因为没有从成功地从挖矿中获得利润而导致离开网络，此外，本文不认为矿工会拥有大量使用CPU和GPU的传统设备，因为它们与当前最先进的专用集成电路(ASIC)相比效率低下，因此，每个矿工的设备数量是通过将每个矿工的哈希率除以所选采矿设备类型的哈希率来找到的，该设备的功率还用于计算每个矿工的能耗，使用比特大陆科技控股公司(Bitmain 4)生产的Antminer S19算力，算力可达110 TH/s，算力3 250 W。

此外，假设矿工尝试开采区块24 h，为了计算碳排放，首先使用从CBECI检索并设置到模拟器中的矿工位置分布，然后，使用矿工的位置来计算每个矿工产生的碳排放，使用文献[19]中为矿工所在国家/地区发布的排放因子。

2.4.3 实验设置

将1.2节中讨论的提出的适应度函数模型与5种进化算法相结合，使用随机搜索(RS)作为比较的基准，对于算法实现，使用了基于Java的多目标进化算法框架(MOEA进化算法框架)，对于每个算法，将所有变异算子和变异概率保留为其默认值，每个算法运行40 000次适应度评估，考虑到所用算法的随机性，运行每个算法100次，所有实验均在具有24 GB内存和Intel i7-6700 CPU 时钟的Windows 10机器上进行(CPU主频为3.4 GHz)。

3 结果和讨论

为了研究算法在现实世界区块链矿工选择问题上的性能，需要计算真正的帕累托前沿，与文献[20]类似，通过组合每个提议的适应度函数的算法的500次独立运行的结果来计算帕累托前沿解决方案。

3.1 目标空间结果

3.1.1 能量和声誉目标空间

图1为利用5种算法对能量与信誉进行权衡的结果。其中：黑色为帕累托正面；蓝色显示了每个算法在100次运行期间找到的近似帕累托前沿；RT表示帕累托前沿解决方案中所有参与矿工的总声誉；E表示所有参与矿工的总能耗(kWh)；x轴表示能量消耗；y轴表示信誉分数。可以看出，NSGA-II、SPEA2、IBEA和NSGA-III不断地从帕累托阵线找到更好的非支配解决方案，显然，PAES的非主导解决方案与帕累托阵线相差很远，这表明只有一个突变算子会促进开发而不是探索，这是因为突变操作符利用当前解决方案的邻近区域，而交叉操作符在搜索空间中创建跳跃，以便更好地探索；在能量消耗最小化和信誉最大化方面，RS算法表现最差，NSGA-II、SPEA2和NSGA-III的分布优于IBEA，这是因为IBEA算法在其选择操作符中使用了超体积指示器，它的大多数非支配解(85%)占据了搜索空间中超容量最大的区域，IBEA的这种行为也在其他实验中被观察到。

图1 利用5种算法对能量与信誉进行权衡的结果Fig. 1 Trade-offs between energy and reputation using five algorithms

3.1.2 能源、碳和声誉目标空间

每个算法在100次运行中找到的近似帕累托前沿和计算的帕累托前沿如图2所示。其中：圆点标记为帕累托前沿；RT表示帕累托前沿解决方案中所有参与矿工的总声誉；E表示所有参与矿工的总能耗(kWh)；CT表示帕累托前沿解决方案中所有参与矿工产生的总碳排放量(gCO2eq/kWh)，分别用x轴和y轴表示能源使用和信誉评分。由图2可以看出，与其他算法相比，NSGA- II和SPEA2创建的非支配解覆盖了计算得到的帕累托前沿的更大部分，有趣的是，NSGA-III的非主导解决方案与帕累托前沿的距离略远，在能量和声誉维度上，它们比NSGA-II、SPEA2和IBEA更分散。此外，由于IBEA算法在其选择算子中使用了超体积指标，其大部分非支配解(85%)占据了搜索空间中超体积最大的区域，与能量—声誉实验结果相似，PAES和RS算法在覆盖帕累托前沿方面表现较差。

图2 利用5种算法对能源与碳和信誉进行权衡的结果Fig. 2 Trade-offs of energy against carbon and reputation using five algorithms

3.1.3 能量、去中心化和声誉目标空间

图3为最小化能源使用的结果。其中，帕累托前沿显示使用点标记。同时最大化分散和矿工集合的声誉，x轴和y轴分别代表能源使用和声誉得分，每个点的颜色尺度代表去中心化得分，算法的总体结果与图2相似。但NSGA-III算法覆盖的帕累托前沿区域较少。此外，还可以观察到，与NSGA-II、SPEA2和IBEA相比，它的解决方案在范围的末端，即声誉分数最大的地方，与帕累托阵线略有距离。因此，本文可以得出：在基于区块链的系统中，在矿工的数量、能量消耗、去中心化和矿工声誉之间确实存在着一种内在的平衡。

图3 五种算法对能量进行分散和代表的结果分析Fig. 3 Analysis of the results of energy dispersion and representation using five algorithms

3.1.4 能源、碳、去中心化和声誉目标空间

图4为多目标优化实验结果。其中，帕累托前沿使用点标记显示，x轴、y轴和z轴分别代表能源使用、声誉和分散得分，结果按碳值进行了颜色编码。可以看出，NSGA-II和SPEA2非支配集包含了更多的帕累托前沿解，然而，随着问题维数的增加,一直找到帕累托前沿的解决方案的能力降低，另一方面，IBEA非支配解决方案的多样性较低(就客观价值而言)，但它们位于帕累托前沿，NSGA-III非支配集比IBEA的非支配集覆盖的帕累托前沿区域略多，PAES和RS算法发现的帕累托前沿解的数量最少，前者是一种基于变异的算法，它有效地探索有希望的解决方案的邻居，然而，随着问题维数的增加，算法的有效性会降低。

图4 使用5种算法权衡能源与碳、去中心化和声誉的结果Fig. 4 Results of using five algorithms to weigh energy versus carbon, decentralization, and reputation

3.2 研究问题回答

3.2.1 能源消耗与碳排放

为了回答问题1和问题2，将原始解决方案的目标值(即包括所有矿工)与使用进化算法找到的解决方案的目标值进行比较，报告的结果是解决方案的目标分数与原始解决方案的目标分数的比率，总体而言，使用提出的适应度函数有助于优化器探索搜索空间并找到有关能源消耗和碳排放的最佳解决方案(即能源消耗和碳排放的有效解决方案)，在实现了节能和低碳排放的同时，相互冲突的目标也有所下降，基于帕累托的算法用于为决策者生成非支配解决方案。

在节能方面，使用第一个适应度函数(即能量VS声誉)探索搜索空间，IBEA在能耗方面为最佳解决方案，以仅40%的整体声誉为代价，将能源效率提高了88%，其大大减少了能源使用，但是，声誉下降了95%以上，其他算法(除了RS)设法找到了与IBEA的最佳解决方案具有相似能效的解决方案，与其他MO进化算法相比，IBEA的非支配集非常有限，尽管与能源使用相冲突的目标(即声誉和权力下放)的退化是相当大的，但具有这种目标价值的解决方案可以用于私有或基于联盟区块链的系统。

在文中的模型中，打算通过平衡其他相互冲突的目标来减少碳排放，虽然在图2和图4中，矿工产生的碳排放率似乎严格遵循能源消耗以相同的速度增长，但这并不意味着与其他消耗低能源的矿工相比，消耗高能源的矿工会产生高碳排放，在某些情况下，本文可以让矿工消耗少量能源，但位于碳强度高的国家，导致矿工产生高碳排放，反之亦然，因此，能源消耗和碳排放可以被视为相互矛盾的目标，能源增加后的图2和图4中的碳排放结果表明优化器有利地选择了来自相同地区的具有相同碳强度的矿工。

与使用PoW的传统基于区块链的系统相比，使用本文的优化模型可以将某些解决方案中的碳排放量减少90%以上，例如使用第二个适应度函数(即能源VS碳VS 声誉)探索搜索空间，IBEA在碳排放方面的最佳解决方案以仅40%的成本，降低了92%的碳排放量，与原始解决方案相比，能耗相当于12%的整体声誉，虽然其他算法大大减少了碳排放，但声誉下降了95%以上，除了PAES降低了52%的声誉，与节能类似，显著降低整体声誉的解决方案可用于私有或联盟基于区块链的系统。

3.2.2 性能分析

为了回答问题3，将每个算法的非支配集的超体积与RS的非支配集的超体积进行比较，使用阈值为p=0.05(p为前面两个样本的显著性水平差异)的Wilcoxon秩和检验来进行比较，为了计算差异，本文使用Vargha和Delaney效应大小，此外，对每对算法进行了比较来回答问题4。

图5显示了统计测试的结果以及使用4个建议的适应度函数对每个算法性能的影响大小，在每个单元格中，标签S表示显著差异，而标签I表示非显著差异，单元格颜色显示效果大小。

图5 算法影响大小和P值Fig. 5 Algorithm impact size and P-value

如图5所示，在所有适应度函数中，每个算法的超体积都明显大于RS。此外，RS性能与其他算法的差异很大，这与图1、2和3中算法的非支配集的视觉表示是一致的。

现在回答问题4，在适应度函数1(即能量VS声誉)和适应度函数3(即能量VS去中心化VS声誉)中，NSGA-II的性能是所有算法中最好的，这表明它产生了最多样化、非支配集，在其他非支配集中覆盖搜索空间的最大部分，P进化算法S的性能第二差，这是由于其探索搜索空间的机制，在所有使用的算法中，IBEA在使用适应度函数2(即能量VS碳VS声誉)探索搜索空间方面的表现最好。本文研究了它的非支配解决方案，发现它们集中在超体积最大化的区域中，这是由于解决方案中的算法选择偏好更喜欢更大的超体积，然而，如图3所示，这种机制限制了适应度环境中的解决方案多样性。

SPEA2在使用适应度函数4(能量VS碳VS去中心化VS声誉)探索解决方案空间方面具有最佳性能，然而，在运行时间方面，SPEA2的运行时间仅次于PAES算法，本文的结果表明，SPEA2在本文提出的多目标问题中优于其他算法。

4 结 论

(1)文中提出了4个不同的适应度函数，在声誉(非功能属性)减少40%的情况下，能源使用量减少了高达88%。此外，使用基于私有区块链的系统，其中矿工是已知的，可以节省90%以上的能源。

(2)为了评估文中提出的模型，比较了具有多样性保护机制的5种不同的进化算法，没有一种算法在使用其默认设置的情况下始终具有优势。目前的研究工作试图使用不同的方法来减少基于区块链系统的能量消耗，然而，这些方法大多集中在提出替代性的共识算法，如PoS和PoT，这些方法是有限的，因为它们不能帮助决策者为他们的首选标准选择最佳解决方案。

(3)与每个模型一样，文中提出的模型也有一些局限性，例如，目前的模型是静态的，将其用在离线优化的情况下，即先优化，然后部署，但该模型可以用在动态优化场景中，环境会随着时间的推移而变化。在未来的工作中，计划将进化算法和学习算法结合起来，创建自适应的方法，以处理矿工或采矿政策在基于区块链的系统运行期间会发生变化的情况。