Defending Hash Tables from Subterfuge with Depth Charge
Defending Hash Tables from Subterfuge with Depth Charge
复制标题
DOI：
10.1145/3631461.3631550
复制
发表时间：
2023-08
期刊：
影响因子：
--
通讯作者：
Trisha Chakraborty;Jared Saia;Maxwell Young
中科院分区：
文献类型：
--
作者：
Trisha Chakraborty;Jared Saia;Maxwell Young
我们考虑保护哈希表免受试图降低查询、插入和删除操作性能的拜占庭攻击者的攻击的问题。我们的防御利用资源燃烧（RB）-网络资源的可验证支出-其中请求的发出者会产生一些RB成本。我们的算法Depth Charge根据对象在表中散列到的列表中的适当对象的深度，对操作收取RB成本。通过适当地设置RB成本，我们的算法减轻了攻击者对哈希表性能的影响。特别是，在一个显着的攻击的存在下，我们的算法产生的成本是渐近小于攻击者的成本。
We consider the problem of defending a hash table against a Byzantine attacker that is trying to degrade the performance of query, insertion and deletion operations. Our defense makes use of resource burning (RB)—the verifiable expenditure of network resources—where the issuer of a request incurs some RB cost. Our algorithm, Depth Charge, charges RB costs for operations based on the depth of the appropriate object in the list that the object hashes to in the table. By appropriately setting the RB costs, our algorithm mitigates the impact of an attacker on the hash table’s performance. In particular, in the presence of a significant attack, our algorithm incurs a cost which is asymptotically less that the attacker’s cost.