This paper investigates the design of transaction fee mechanisms (TFMs) in cryptocurrencies that are both incentive compatible and resistant to collusion between users and miners. The authors address a key open question posed by Roughgarden [Rou21], which asks whether there exists a TFM that is incentive compatible for both users and miners and also resistant to off-chain agreements (OCAs) between these parties. They show that OCA-proofness and side-channel proofness (SCP) are distinct concepts, with SCP being strictly stronger. The paper fully characterizes the intersection of deterministic dominant strategy incentive-compatible (DSIC) and OCA-proof mechanisms, as well as deterministic myopic miner incentive-compatible (MMIC) and OCA-proof mechanisms. It shows that only the trivial mechanism is DSIC, MMIC, and OCA-proof. For randomized mechanisms, the paper shows that the trivial mechanism is the only DSIC + MMIC + OCA-proof, scale-invariant mechanism. It also demonstrates that no randomized DSIC + MMIC + OCA-proof mechanism is efficient in the worst case, and that the efficiency approximation is at most 0.842. The paper also explores the economic literature on collusion, particularly focusing on user-user collusion and miner-user collusion. It discusses the implications of collusion in auction design and the challenges of designing collusion-resistant mechanisms. The paper also considers the dynamic setting of blockchain transactions and the role of randomness in transaction fee mechanisms. It highlights the challenges of achieving incentive compatibility and collusion resistance in randomized mechanisms, and shows that deterministic mechanisms are more likely to achieve these properties. The paper concludes that while deterministic mechanisms are more effective in achieving these properties, randomized mechanisms may still be viable in certain contexts.This paper investigates the design of transaction fee mechanisms (TFMs) in cryptocurrencies that are both incentive compatible and resistant to collusion between users and miners. The authors address a key open question posed by Roughgarden [Rou21], which asks whether there exists a TFM that is incentive compatible for both users and miners and also resistant to off-chain agreements (OCAs) between these parties. They show that OCA-proofness and side-channel proofness (SCP) are distinct concepts, with SCP being strictly stronger. The paper fully characterizes the intersection of deterministic dominant strategy incentive-compatible (DSIC) and OCA-proof mechanisms, as well as deterministic myopic miner incentive-compatible (MMIC) and OCA-proof mechanisms. It shows that only the trivial mechanism is DSIC, MMIC, and OCA-proof. For randomized mechanisms, the paper shows that the trivial mechanism is the only DSIC + MMIC + OCA-proof, scale-invariant mechanism. It also demonstrates that no randomized DSIC + MMIC + OCA-proof mechanism is efficient in the worst case, and that the efficiency approximation is at most 0.842. The paper also explores the economic literature on collusion, particularly focusing on user-user collusion and miner-user collusion. It discusses the implications of collusion in auction design and the challenges of designing collusion-resistant mechanisms. The paper also considers the dynamic setting of blockchain transactions and the role of randomness in transaction fee mechanisms. It highlights the challenges of achieving incentive compatibility and collusion resistance in randomized mechanisms, and shows that deterministic mechanisms are more likely to achieve these properties. The paper concludes that while deterministic mechanisms are more effective in achieving these properties, randomized mechanisms may still be viable in certain contexts.