智能合约Hash碰撞引发的DoS攻击及其防御

哈希表碰撞攻击的基本原理
哈希表是一种查找效率极高的数据结构，很多语言都在内部实现了哈希表。Solidity中的Mapping可以看作是哈希表，它是一种极为重要的数据结构，同时是一种高效且经济的存储类型为众多开发人员所推崇。
理想情况下哈希表插入和查找操作的时间复杂度均为O(1)，任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值（key），然后在常量时间内定位到一个桶（术语bucket，表示哈希表中的一个位置）。当然这是理想情况下，因为任何哈希表的长度都是有限的，所以一定存在不同的数据项具有相同哈希值的情况，此时不同数据项被定为到同一个桶，称为碰撞（collision）。哈希表的实现需要解决碰撞问题，碰撞解决大体有两种思路，第一种是根据某种原则将被碰撞数据定位到其它桶，例如线性探测——如果数据在插入时发生了碰撞，则顺序查找这个桶后面的桶，将其放入第一个没有被使用的桶；第二种策略是每个桶不是一个

智能合约Hash碰撞引发的DoS攻击及其防御最先出现在Python成神之路。