原文标题：《Effective Scheme against 51% Attach on Proof-of-Work Blockchain with History Weighted Information》
原文作者：杨歆乐 陈扬 陈小虎
中文翻译：李预清、李晓强
翻译申明：翻译完成后未经原作者审核，如发现错误，读者可留言反馈。
【摘要】
PoW(工作量证明)是区块链系统中广泛使用的协议，用于解决双花难题。但是，如果攻击者拥有超过全网哈希算力的一半，那么该攻击者就可以发起双花攻击或51%攻击。如果哈希算力足够强大，那么发起攻击的成本会低的惊人，这将会对众多PoW区块链造成巨大威胁。
我们提出了一种技术方案，将矿工的挖矿历史权重信息与总计算难度相结合，以达到缓解51%攻击的问题。分析表明，使用这种新技术，将会使传统攻击的成本增加两个数量级。
【关键词】
区块链 51%攻击 挖矿 双花攻击
1 介绍
比特币由中本聪于2009年开发，是第一个去中心化的公共账本系统，自那时起，出现了许多基于区块链的加密货币。区块链是一个分布式数据处理协议，用于在P2P网络中保存一个公共分布式账本。交易数据记录在区块中，这些区块形成一个链表，网络中的每个节点都存储并维护一个完整的账本副本，而无需中心化授权。在基于区块链的加密货币中，每个块都包含前一个块的哈希值，导致很难操纵内部交易。通常采用共识协议来保证区块链P2P网络节点间的数据完整性，不同类型的区块链，会采用不同的共识协议。
PoW(工作量证明)是当前基于区块链的加密货币中最常用的共识协议。主流区块链如比特币和以太坊，就是使用的PoW共识协议。在POW协议中，每个节点竞争着找到一个nonce的值来生成满足特定条件的哈希,找到这样的一个nonce值的难度可以根据哈希值的条件来计算。当找到这样的一个nonce值时，将生成一个块并向P2P网络广播。根据协议的不同类型，对等节点通常会接受最长的链或总难度最大的链来不断地扩展区块链，POW利用这一机制来确定哪个节点有资格打包一个块，这个过程也称为挖矿。
在这种机制中，计算速度较大(有时称为哈希算力)的节点可以比计算速度较慢的节点更快地计算出nonce值，从而有更高的概率获得打包资格。然而，这种机制有一个缺点：一个自私节点的哈希算力比其余节点哈希算力的总和还要高，就会导致双花问题和自私挖矿，从而危害区块链系统，这通常被称为51%攻击。一些学者已经提出了避免此类攻击的方法，Eyal和Sirer在2014年提出了一个两阶段PoW(2P-PoW)的解决方案，防止了具有巨大哈希算力的矿场的形成。在这个方案中，第二阶段的PoW需要挖矿地址的私钥签名，第二阶段的PoW非常困难，矿池操作者必须向矿工开放这个私钥，以便于比其他节点更快地进行计算。Ruffing et al. 等人在2015年提出了一份合约来惩罚实施双花攻击的攻击者。Solat和Potop-Butucaru在2016年提出了ZeroBlock，在ZeroBlock机制中，要求一个块在块的时间戳之后的特定时间间隔内被对等节点接受，否则该块就会过期无效。这种机制可以防止攻击节点在很长一段时间内进行自私挖掘。J. Bae和H. Lim在2018年提出了一种解决方案，随机选择某一组矿工，让他们有权挖出下一个区块。
在本篇论文中，我们提出一种通过历史权重难度决定区块链总难度的新解决方案。在这个优化过的算法中，一个分支区块链上的矿工如果在之前的区块中有更高的打包出块率，它就在这个分支区块链上拥有更高的总历史权重。该算法会使进行51%攻击的财力成本和时间成本增加两个数量级。
2 51%攻击和成本
首先，让我们回顾一下51%攻击的图谋。假设当前的哈希算力是Po，攻击者有更强的哈希算力Pa(Pa>Po)，并且通过这种更强的哈希算力计算出了一个隐藏分支Ba，攻击者就在两个分支上造成了双花攻击。然后攻击者暴露较长的隐藏分支Ba，并使原始分支Bo中的所有交易无效，这就是所谓的51%攻击，产生的成本如下：
P是token在交易所的价格，R是块的奖励，f是块的生成速度，t代表攻击的持续时间。做一个该成本的简化估算，这里我们假设挖矿token的价格接近挖矿的成本。对于许多小区块链来说，执行这样的攻击只需要几百或几千美元。
另一个让情况变得更糟的因素是，任何能够支付合适价格的人都可以很容易地获得哈希算力，NiceHash为哈希算力交换提供了一个开放的市场，任何人都可以轻松地使用加密货币付费租用哈希算力在目标区块链挖矿。因此一个攻击者可以在短时间内累积哈希算力以超过51%的阈值。攻击者可以通过中心化交易将token双花。整个流程只需要大约50-500个块。之后，攻击者可以释放所租用的哈希算力并带走利润。
最近，以太坊经典受到了攻击。攻击的分支长度大约在50 ~ 150，大量的ETC被双花。
3 历史权重难度
我们提出了一种改进计算分支总难度的方法，这种技术考虑到了挖矿地址在区块链的最后一定数量块中的分布情况。我们将这种协议称为基于历史权重难度的工作量证明(HWD-PoW)。假设在一个诚实的区块链分支中，新区块的挖矿者很可能是之前某些区块的挖矿者，其分布情况将反映历史挖矿的比率。而在一个恶意区块链分支中，新区块的挖矿者分布情况很有可能被攻击者控制，这与历史上常规的挖矿者分布情况不同。因此，当考虑历史矿工的分布时，人们可以很容易地将诚实的区块链分支与恶意的区块链分支区分开来。
在这种机制下，在以前的块中具有较少代表性的分支将在总难度计算中获得更少的权重。因此，要执行51%的攻击，恶意的矿工有两种选择：要么挖掘一个更长的分支，要么在以前的块中建立矿工形象从而建立信誉。
现在，让我们看看历史权重难度模式是如何防卫51%攻击的：
a)首先，在历史窗口期W记录每个矿工的块生成频率：
这里：
b)然后，每个块由挖矿者的私钥签名。这样，挖矿者就不能伪造矿工身份。虽然这可能会暴露矿工的私钥;不过也有方法解决，只要token一被挖出，马上把token从挖矿者的账户转到冷钱包里。
c)当检测到分叉裂时，通过下面的方法来计算每个节点上的每个分支的历史权重难度(HWD)：
对于B分支中的唯一矿工K，
Rk是历史窗口期W中块的生成频率，Dk是块k的难度，L是分支长度。
请注意，只进行了一个矿工的生成频率计算。如果一个矿工地址挖掘多个块，它只计算一次。通过抑制单一的高哈希算力的矿工，从而鼓励了采矿的分散化。这也就增加了攻击的难度。
d)每个节点都会比较来自两个分支的两个不同HWD值，带有更高HWD值的分支将会被选中。
这种机制的结果很明确：如果攻击者增加新的临时哈希算力，但新分支的矿工对系统来说是相对较新的，其区块的ri值会非常低，相应的HWD相对于原始分支会非常小。原始分支中的任何节点都不会切换到攻击者分支。这个方案可以很容易地防范”rent and attach攻击。
如果攻击者想让节点切换到他的恶意分支，他就需要产生更高的HWD值。攻击者需要在原始分支中挖一段时间，使自己包含在历史中。因此，当它切换到隐藏分支时，它的HWD会更高。
假设Pa是攻击者的哈希算力，Po是原始的诚实矿工的哈希算力：
在原分支中，攻击者需要花费哈希算力Pa和时间t, Pa的最优开销为W/2周期，然后在攻击的时候将Pa切换到隐藏分支，如图Fig.1所示;为了攻击成功，我们需要满足：
结果，公开的恶意分支Ba将比原来的分支Bo长，在公布时，原始分支的HWD为：
其中δ为节点接受的最小边缘差分。所以，恶意分支的HWD是：
因此，我们需要：
因为Da和Do在这种情况下无限接近，我们可以简化方程：
并且可以得出：
总之，攻击者的最小代价是在时间窗口 ( W - L) 开销哈希算力 Po * ( 1/2 + l/( 4W - 21 ))。
对于典型的攻击，需要大约50-500个块才能使token从token交易所套现。从下面的分析来看，矿工的切换并不频繁，我们可以很容易地设置W > 1个月来增加历史权重。当W = 100,000块时，对攻击的鲁棒性(编者注：指系统在扰动或不确定的情况下仍能保持它们的特征行为)提高了100倍以上。
虽然我们不能完全避免51%攻击，但是我们可以大幅增加攻击者的资金成本和时间成本到两个数量级以上。由于攻击者需要花费相当长的时间来准备，所以攻击发生的可能性要小得多，因为长时间的攻击会导致大量的机会成本和不确定性。上述的HWD方案对比，额外的改善方案进一步增加了攻击成本。
4 额外的改善方案
以上是HWD方案，额外的改善方案会在之前的基础上更多地增加攻击者的成本。
与第一种方案是发布Ri < Rc的上限，这意味着即使在历史窗口中生成了更多的块，单个矿工的数量也不会超过Rc。这种方法将鼓励更多样化的矿池。同时，矿工可以有目的地将挖矿哈希算力分割为多个挖矿者，以确保每个挖矿者都低于Rc。这将绕过多样化需求，但这仍然是有效的，它增加了攻击者维护多个矿工账户的成本。
第二种方案是在两个分叉的分支之间增加一个矿工重叠(miner overlap)需求。为了将攻击成本降到最低，攻击者通常会将其所有的哈希算力都放在恶意分支中。重叠需求则要求一些采矿者同时在两个分支挖矿。在这种情况下，为了实现分支切换，不仅需要满足HWD条件：
同时，两组矿工之间的重叠度需要大于s：
其中Ri为原始分支的矿工频率，Rk为攻击者分支的矿工频率，s为重叠阈值。
这意味着，该系统不鼓励哈希算力突然从一组矿工切换到另一组不同的矿工。
有了这样一个增强的要求，如果 s = 0.25，则攻击者需要在持续时间w内拥有当前哈希算力的三倍。这意味着攻击者需要在原始分支中保留一些哈希算力，并在恶意分支中保留两倍以上的哈希算力。因此，通过引入这样一个方案，我们将执行对原始的历史权重难度算法的攻击的时间成本和金钱成本分别提高了一倍和两倍。对于更高的s值，攻击者甚至需要花费更多的哈希算力。
5 HWD算法
在本节中，我们将介绍基于分支选择的HWD算法。
下面是计算HWD的伪代码：
6 来自以太坊的真实数据统计
我们选择了一个著名的PoW区块链平台(以太坊)Ethereum。我们分析了前6,000,000个区块的区块信息，这些大约有3年的开采历史。第一个任务是找出具有较大哈希算力的矿工的分布情况。分析表明，矿工分布与过去的历史有很强的相关性。在块 # 2,000,000、# 4,000,000、#6,000,000处，分析了其下的360个块。在这360块和2M块中的矿工权重如下所示:
360块挖矿者的总权重与历史窗口的分布有很强的相关性，即使我们使用的历史是200万块(M)长(大约一年)。结果如下图所示：
这支持了我们的假设，诚实矿工的参与率是相对稳定的。因此，矿工的历史权重是一个有价值的信息，我们可以利用它来对抗51%的攻击。我们还观察到，新矿工与前200万块的相关性逐步增强，表明以太坊矿挖矿正走向集中化。
请注意，在table II中，一个地址为0x829b....a830的矿工的权重在这360个区块之中的2M-4M范围里发生了较大的变化。然而，之前200万块矿工的总权重仍然在70%以上。这表明，个别的矿工可能会大幅度地改变他们的开采参与率，但这并没有改变一个真实分支的总的历史权重。
我们进一步模拟了51%攻击，在块#2M、 #4M 和 #6M上进行模拟攻击，并监听计算了1M和2M窗口的结果。如果攻击分支的HWD高于原始分支的HWD，则视为成功的攻击。
在理想情况下，准备工作至少应该比指定的窗口时间长。但是，考虑到分布的相关性，准备周期略短。我们对每个窗口进行了多次模拟，以获得平均累积成本。在这里，我们忽略了随着时间的推移挖矿奖励减半的效应。结果如下图所示：
结果表明，在HWD方案中，如果将窗口大小设置为1M或2M块，攻击以太坊主网区块链的代价将增加100倍以上。在实际应用中，窗口可以更短，以加快进程。我们建议窗口大小至少是100万，使攻击的成本增加100倍以上。
7 结论
在本篇论文中，我们提出了一种基于PoW区块链协议的方案，以增加攻击者成功进行双花攻击和51%攻击的成本。该方案利用计算历史区块中的矿工分布比率和历史权重难度总数来确定是否有切换分支的必要。我们在三个真实的以太坊主网场景中的实验结果证明，采用HWD-PoW方案，攻击成本提高了100多倍。
我们的HWD-PoW方案可以应用于所有基于PoW的区块链。这可以大大提高较小的区块链的安全性，且易于整合。
致谢
这项工作得到了MOAC基金会和MOAC区块链技术公司的支持。我们感谢Andrew Champagne帮助我们进行校对。
文献参考
[1] S. Nakamoto,“Bitcoin: A peer-to-peer electronic cash system,” 2008.
[2] Z. Zheng, S. Xie, H. Dai, X. Chen, and H. Wang, “Blockchain challenges and opportunities: A survey,” Int. J. Web Grid Serv., 2016.
[3] M. Conti, S. Kumar E, C. Lal, and S. Ruj, “A survey on security and privacy issues of Bitcoin,” arXiv preprint arXiv:1706.00916, 2017.
[4] Eyal, I. and Sirer, E.G. (2014) “Majority is not enough: Bitcoin mining is vulnerable”, Proceedings of International Conference on Financial Cryptography and Data Security, Berlin, Heidelberg, pp.436–454.
[5] I. Eyal and E. G. Sirer, “How to disincentivize large Bitcoin mining pools,” 2014.
[6] T. Ruffing et al., “Liar, liar, coins on fire!: Penalizing equivocation by loss of Bitcoins,” ACM Conf. Comput. Commun. Secur., Oct. 2015.
[7] S. Solat and M. Potop-Butucaru,“ZeroBlock: Preventing selfish mining in Bitcoin,” arXiv preprint arXiv:1605.02435, 2016.
[8] J. Bae and H. Lim, “Random Mining Group Selection to Prevent 51% Attacks on Bitcoin,” 2018 48th Annual IEEE/IFIP International Con- ference on Dependable Systems and Networks Workshops (DSN-W), Luxembourg City, 2018, pp. 81-82. doi: 10.1109/DSN-W.2018.00040
[9] PoW 51% attack cost, https://www.crypto51.app
[10] NiceHash - Largest Crypto-Mining Marketplace to sell or purchase hash power, https://www.nicehash.com/
[11] Deep Chain Reorganization Detected on Ethereum Classic (ETC), https://blog.coinbase.com/ethereum-classic-etc-is-currently-being-51- attacked-33be13ce32de
相关阅读：
MOAC宣讲《POW有效抵御51%攻击的历史权重方案》
论文原文：
电科技（）是一家专注于全球TMT行业的领先资讯媒体。
作为今日头条青云计划、百家号百+计划获得者，2019百度数码年度作者、百家号科技领域最具人气作者、2019搜狗科技文化作者、2021百家号季度影响力创作者，曾荣获2013搜狐最佳行业媒体人、2015中国新媒体创业大赛北京赛季军、 2015年度光芒体验大奖、2015中国新媒体创业大赛总决赛季军、2018百度动态年度实力红人等诸多大奖。
投稿、商务合作请联络微信公众号
声明：本站原创文章文字版权归电科技所有，转载务必注明作者和出处；本站转载文章仅仅代表原作者观点，不代表电科技立场，图文版权归原作者所有。如有侵权，请联系我们删除。
