Handling congestion in blockchain systems is a fundamental problem given that the security and decentralization objectives of such systems lead to designs that compromise on (horizontal) scalability (what sometimes is referred to as the “blockchain trilemma”). Motivated by this, we focus on the question whether it is possible to design a transaction inclusion policy for block producers that facilitates fee and delay predictability while being incentive compatible at the same time. Reconciling these three properties is seemingly paradoxical given that the dominant approach to transaction processing is based on first-price auctions (e.g., as in Bitcoin) or dynamic adjustment of the minimum admissible fee (e.g. as in Ethereum EIP-1559) something that breaks fee predictability. At the same time, in fixed fee mechanisms (e.g., as in Cardano), fees are trivially predictable but are subject to relatively inexpensive bribing or denial of service attacks where transactions may be delayed indefinitely by a well funded attacker, hence breaking delay predictability. In this work, we set out to address this problem by putting forward blockchain space tokenization (BST), namely a new capability of a blockchain system to tokenize its capacity for transactions and allocate it to interested users who are willing to pay ahead of time for the ability to post transactions regularly for a period of time. We analyze our system in the face of worst-case transaction-processing attacks by introducing a security game played between the mempool mechanism and an adversary. Leveraging this framework, we prove that BST offers predictable and asymptotically optimal delays, predictable fees, and is incentive compatible, thus answering the question posed in the affirmative.

We address the problem of Reliable Message Transmission (RMT), in the general adversary model of Hirt and Maurer[2], which subsumes earlier models such as the global or local threshold adversaries. We employ the recently introduced Partial Knowledge Model[8], which captures any case of initial players' topology knowledge. Our main contribution is the determination of a necessary and sufficient condition for achieving RMT in the partial knowledge model with a general adversary. We propose the RMT-Partial Knowledge Algorithm (RMT-PKA), which solves RMT whenever this is possible, therefore it is a unique algorithm, as defined in[10]. To the best of our knowledge, this is the first unique protocol for RMT against general adversaries in the partial knowledge model.