Space in a blockchain is a scarce resource. Cryptocurrencies today use auctions to decide which transactions get confirmed in the block. Intriguingly, classical auctions fail in such a decentralized environment, since even the auctioneer can be a strategic player. For example, the second-price auction is a golden standard in classical mechanism design. It fails, however, in the blockchain environment since the miner can easily inject a bid that is epsilon smaller than the k-th price where k is the block size. Moreover, the miner and users can also collude through the smart contract mechanisms available in modern cryptocurrencies.

I will talk about a new foundation for mechanism design in a decentralized environment. I will prove an impossibility result which rules out the existence of a dream transaction fee mechanism that incentivizes honest behavior for the user, the miner, and a miner-user coalition at the same time. I will then show how cryptography can help us overcome the impossibility results.