论文标题
加密技术可以为分散机理设计做什么
What Can Cryptography Do For Decentralized Mechanism Design
论文作者
论文摘要
Roughgarden（EC'21）和Chung and Shi（Soda'23）的最新作品启动了对新的分散机制设计问题的研究，称为交易费用机理设计（TFM）。与经典机制设计文献不同，在分散的环境中，即使拍卖师（即矿工）也可以是战略参与者，甚至可以与由约束侧合同促进的一部分用户共处。 Chung和Shi展示了两个主要的不可能结果，这些结果排除了{\ it Dream} tfm的存在。首先，任何为单个用户和矿工使用者联盟提供激励兼容性的TFM都必须始终具有零矿工收入，无论块大小是有限的还是无限的。其次，假设有有限的块大小，没有非平凡的TFM可以同时为任何个人用户和任何矿工用户联盟提供激励兼容性。 在这项工作中，我们探讨了哪些新模型和有意义的放松可以使我们能够避免Chung和Shi的不可能结果。除了当今不采用密码学的模型外，我们还引入了一个新的MPC辅助模型，其中TFM由矿工中的联合多方计算（MPC）协议实现。我们证明了实现{\ IT严格}和{\ it近似}激励兼容性的几种可行性和不可行结果，在普通模型和MPC辅助模型中。我们表明，尽管密码学不是灵丹妙药，但它确实使我们能够克服与普通模型有关的一些不可能的结果，从而导致具有有用保证的非平凡机制，而这些机制在普通模型中否则是不可能的。我们的工作也是第一个表征在近似激励兼容性以及密码辅助模型中的交易费用机理设计数学格局的设计。
Recent works of Roughgarden (EC'21) and Chung and Shi (SODA'23) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Unlike the classical mechanism design literature, in the decentralized environment, even the auctioneer (i.e., the miner) can be a strategic player, and it can even collude with a subset of the users facilitated by binding side contracts. Chung and Shi showed two main impossibility results that rule out the existence of a {\it dream} TFM. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, no matter whether the block size is finite or infinite. Second, assuming finite block size, no non-trivial TFM can simultaenously provide incentive compatibility for any individual user, and for any miner-user coalition. In this work, we explore what new models and meaningful relaxations can allow us to circumvent the impossibility results of Chung and Shi. Besides today's model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. We prove several feasibility and infeasibility results for achieving {\it strict} and {\it approximate} incentive compatibility, respectively, in the plain model as well as the MPC-assisted model. We show that while cryptography is not a panacea, it indeed allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model. Our work is also the first to characterize the mathematical landscape of transaction fee mechanism design under approximate incentive compatibility, as well as in a cryptography-assisted model.
