Motivated by the great success and adoption of Bitcoin, a number of cryptocurrencies such as Litecoin, Dogecoin, and Ethereum are becoming increasingly popular. Although existing blockchain-based cryptocurrency schemes can ensure reasonable security for transactions, they do not consider any notion of fairness. Fair exchange allows two players to exchange digital "items", such as digital signatures, over insecure networks fairly, so that either each player gets the other's item, or neither player does. Given that blockchain participants typically do not trust each other, enabling fairness in existing cryptocurrencies is an essential but insufficiently explored problem. In this paper, we explore the solution space for enabling the fair exchange of a cryptocurrency payment for a receipt. We identify the timeliness of an exchange as an important property especially when one of the parties involved in the exchange is resource-constrained. We introduce the notion of strong timeliness for a fair exchange protocol and propose two fair payment-for-receipt protocol instantiations that leverage functionality of the blockchain to achieve strong timeliness. We implement both and compare their security and efficiency.