Abstract: In cryptocurrencies, transaction fees are typically exclusively paid in the native platform currency. This restriction causes a wide range of challenges, such as deteriorated user experience, mandatory rent payments by decentralized applications, and blockchain community rivalries (e.g., coinism). Ideally, in a truly permissionless blockchain, transaction fees should be payable in any other cryptocurrency via so-called metatransactions. In this paper, we formalize metatransactions, review existing ideas, and describe novel metatransaction design approaches. Under the assumption of sufficient market liquidity, we argue that meta-transactions do not lower the security of cryptocurrency platforms. However, without changing the underlying blockchain, metatransaction designs typically increase transaction costs and reduce the blockchain transaction throughput.