找出bug，这24个ETH就归你了！

偶然在Reddit上看到，一位以太坊发烧友Zac Mitton发布了一个智能合约，如果你能在其中找到bug，智能合约就会自动把奖金转到你的账户！代码地址： https://github.com//zmitton/eth-heap

该合约有效期为30天，初始奖金是10个ETH，并且他承诺每天会增加1ETH的悬赏，到今天为止奖金账户里已经有24个ETH了，价值3万多RMB！刺不刺激？心不心动？我们先来看看到底是怎么一回事吧～

1.Block-Gas-Limit攻击

Zac在Github上提到，做这件事情的初衷是为了验证一种更好的抵御Block-Gas-Limit攻击的方案。

那么什么是Block-Gas-Limit攻击呢？我们知道，以太坊虚拟机执行每条指令都需要消耗一定的油量（gas）的，并且某些指令消耗的油量还比较高，以目前的EIP158为例，参见下表：

假设我们的合约里通过数组存储了一些账户数据，而遍历这些数据时需要使用到上面这些昂贵的指令。那么攻击者就可以往数组中插入足够多的数据，然后通过遍历该数组产生一笔消耗极高油量的交易。每个区块能打包的交易的油量总和是有限的（目前上限是8百万），如果某一笔交易消耗了太多的油量，一个区块可能就只能打包一笔交易了，那么显然以太坊就会拥堵，你的智能合约也无法正常工作，这就 相当于在以太坊上发起了一次DoS攻击 。

当然，攻击者在攻击过程中也需要支付比较高的油费，但是如果攻击能带来非常可观的经济效益，那这点点成本可以忽略不计。有些读者可能反应过来了：前段时间很火的 Fomo3D游戏 ，第一轮结束时黑客不就是用的这种手段嘛！最终黑客收获了 10000+ETH 的奖池，价值 2200多万 ！

那么如何抵御这种攻击呢？以太坊并没有提出比较好的方案，有一种提案是限制每次合约调用可以从存储中读取的字节数，但是听起来不是什么好主意。Zac兄弟就思考良久，一拍大腿，用二叉堆啊！

2.二叉堆

我们先来回忆一下数据结构相关的内容：首先，啥叫个堆？

堆是一棵完全树，但是是用数组形式表示的。可以分为2种类型：

• 大顶堆：堆中任意节点总是大于它的子节点的值

• 小顶堆：堆中任意节点总是大于它的子节点的值

比如下图就是一个大顶堆：

可以看到，其实就是把数据按层顺序存储到数组里。如果节点的索引为 i ，那么它的左孩子的索引就是 2i ，右孩子的索引就是 2i+1 。（这里跟Zac的代码实现保持一致，抛弃数组的第一个元素）

二叉堆的核心是在“插入节点”和“删除节点”后如何保证堆的“大顶”或者“小顶”特性。以大顶堆为例，我们依次分析一下。

2.1插入节点

假设我们要把22插入堆中，首先我们把22添加到末尾：

然后通过“索引/2”找到父节点，如果值大于父节点的值，跟父节点交换：

继续通过“索引/2”找到父节点，值仍大于父节点的值，跟父节点交换：

插入完成，最终结果如上图所示。这一步骤可以被形象地称为“ 向上冒泡 ”。

2.2删除节点

假设我们要上图的基础上，删除最上面的100这个节点。首先把100从堆中删除，然后把最后一个元素填充到原先100所在的位置：

然后通过“索引2i和2i+1”找到它的左右孩子，挑比较大的那个进行交换：

继续通过“索引2i和2i+1”找到它的左右孩子，挑比较大的那个进行交换：

删除完成，最终结果如上图所示。这一步骤可以被形象地称为“ 向下冒泡 ”。

当然，如果你要删除中间某个节点，有可能需要向上冒泡，也有可能需要向下冒泡，需要具体情况具体处理。

聊完了基础知识，让我们再回到智能合约上来吧。

3.怎么找bug？

Zac希望通过二叉堆，将查找的时间复杂度从O(N)降低到到O(logN)，这样就可以大大降低交易消耗的油量，从而抵御Block-Gas-Limit攻击。更进一步，他认为这种算法还可以被用于实现去中心化交易协议！在交易撮合过程中，我们需要根据买单的价格，寻找相匹配的价格最高的卖单。我们并不需要对堆进行完全排序，因为如果价格最高的卖单不满足要求的话，交易撮合就失败了，我们并不需要查找价格第二高的卖单。

因此，他亲自实现了这份极具价值的代码，并发起了这个悬赏计划。可以通过下面的命令下载代码：

npm install eth-heap --save

实际上他写了两个合约：核心算法Heap.sol仅有110行代码，而BountyHeap.sol则封装了一些堆操作API方便挑战者们调用，同时提供了一些校验API，如果校验API发现某些属性出现异常，就会直接把奖金从合约账户中转给交易发起者！具体来说，分为以下三类属性的校验：

• 堆属性：如果发现某个节点的值小于它的子节点的值，则打破了该属性，挑战成功
• 完全属性：堆是一棵完全树，如果树的中间出现了空洞，则打破了该属性，挑战成功
• ID维护属性：如果出现了重复的节点ID，或者某个ID指向空节点，则打破了该属性，挑战成功

也就是说，你可以通过堆操作API进行插入、删除、查询等操作，如果成功造成了堆状态异常，则可以调用校验API直接提取奖金，无需任何人的授权～

4.成本评估

发起交易调用智能合约是需要消耗油费的，因此大家肯定很关心成本评估问题。Zac在GitHub上晒出了500个节点情况下执行操作需要消耗的油量的均值：

extractById()
insert()
extractMax()

另外，根据Zac的测试，数据两每增大一倍，消耗的油量就要增加20000：

好了，就说到这里吧，我要赶着去撸合约代码了，祝各位好运～ :smiley:

更多文章欢迎关注“鑫鑫点灯”专栏： https://blog.csdn.net/turkeycock

或关注飞久微信公众号：