  Blockchains deploy Transaction Fee Mechanisms (TFMs) to determine which user
transactions to include in blocks and determine their payments (i.e.,
transaction fees). Increasing demand and scarce block resources have led to
high user transaction fees. As these blockchains are a public resource, it may
be preferable to reduce these transaction fees. To this end, we introduce
Transaction Fee Redistribution Mechanisms (TFRMs) -- redistributing VCG
payments collected from such TFM as rebates to minimize transaction fees.
Classic redistribution mechanisms (RMs) achieve this while ensuring Allocative
Efficiency (AE) and User Incentive Compatibility (UIC). Our first result shows
the non-triviality of applying RM in TFMs. More concretely, we prove that it is
impossible to reduce transaction fees when (i) transactions that are not
confirmed do not receive rebates and (ii) the miner can strategically
manipulate the mechanism. Driven by this, we propose \emph{Robust} TFRM
(\textsf{R-TFRM}): a mechanism that compromises on an honest miner's individual
rationality to guarantee strictly positive rebates to the users. We then
introduce \emph{robust} and \emph{rational} TFRM (\textsf{R}$^2$\textsf{-TFRM})
that uses trusted on-chain randomness that additionally guarantees miner's
individual rationality (in expectation) and strictly positive rebates. Our
results show that TFRMs provide a promising new direction for reducing
transaction fees in public blockchains.
