Brief Announcement: Brokering with Hashed Timelock Contracts is NP-Hard
Brief Announcement: Brokering with Hashed Timelock Contracts is NP-Hard
复制标题
简短公告：使用散列时间锁合约进行经纪是 NP 难的
DOI：
10.1145/3465084.3467952
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Lesani, Mohsen
中科院分区：
文献类型：
--
作者：
Chan, Eric;Lesani, Mohsen
近年来，许多不同的加密货币越来越受欢迎。由于硬币的法定价值和功能各不相同，因此在它们之间进行安全交换变得非常重要。一种常见的交易方法是哈希时间锁合约（HTLC）。然而，这种方法不支持允许各方利用他们在交易期间获得的资产的经纪交易。我们考虑HTLC与代理。HTLC的交易费用是领导者集大小的直接函数。因此，经纪人感兴趣的是找到给定交易图的最小领导集。我们发现，寻找最小的领导者集一般事务图与经纪是NP-难的。然后，我们介绍花交易图，一种常见的类型的交易图与经纪，并表明，找到最小的领导集的花图也是NP-困难的，通过减少背包问题。
In recent years, many different cryptocurrencies have risen in popularity. Since coins vary in fiat value and functionality, it has become important to securely exchange between them. A common exchange method is hashed timelock contracts (HTLC). However, this method did not support brokerage transactions that allow parties to leverage assets they gain during the transaction. We consider HTLC with brokering. The transaction fees for HTLC is a direct function of the size of the leader set. Thus, brokers are interested in finding the minimum leader set of a given transaction graph. We show that finding the minimum leader set on general transaction graphs with brokering is NP-hard. We then introduce flower transaction graphs, a common type of transaction graphs with brokering, and show that finding the minimum leader set of a flower graph is also NP-hard through a reduction from the knapsack problem.
跨链交易和对抗性商业
DOI：
--
发表时间：
2019
期刊：
The VLDB journal
影响因子：
--
作者：
Maurice Herlihy;B. Liskov;L. Shrira
通讯作者：
L. Shrira