  The recently proposed Transaction Fee Mechanism (TFM) literature studies the
strategic interaction between the miner of a block and the transaction creators
(or users) in a blockchain. In a TFM, the miner includes transactions that
maximize its utility while users submit fees for a slot in the block. The
existing TFM literature focuses on satisfying standard incentive properties --
which may limit widespread adoption. We argue that a TFM is "fair" to the
transaction creators if it satisfies specific notions, namely Zero-fee
Transaction Inclusion and Monotonicity. First, we prove that one generally
cannot ensure both these properties and prevent a miner's strategic
manipulation. We also show that existing TFMs either do not satisfy these
notions or do so at a high cost to the miners' utility. As such, we introduce a
novel TFM using on-chain randomness -- rTFM. We prove that rTFM guarantees
incentive compatibility for miners and users while satisfying our novel
fairness constraints.
