Building trustless cross-blockchain trading protocols is challenging. Centralized exchanges thus remain the preferred route to execute transfers across blockchains. However, these services require trust and therefore undermine the very nature of the blockchains on which they operate. To overcome this,several decentralized exchanges have recently emerged which offer support for atomic cross-chain swaps (ACCS). ACCS enable the trustless exchange of cryptocurrencies across blockchains,and are the only known mechanism to do so. However, ACCS suffer significant limitations; they are slow, inefficient and costly,meaning that they are rarely used in practice.We present XCLAIM: the first generic framework for achieving trustless and efficient cross-chain exchanges using cryptocurrency-backed assets(CBAs). XCLAIM offers protocols for issuing,transferring, swapping and redeeming CBAs securely in anon-interactive manner on existing blockchains. We instanti-ate XCLAIM between Bitcoin and Ethereum and evaluate our implementation; it costs less than USD 0.50 to issue an arbi-trary amount of Bitcoin-backed tokens on Ethereum. We show XCLAIMis not only faster, but also significantly cheaper than atomic cross-chain swaps. Finally, XCLAIMis compatible with the majority of existing blockchains without modification, and enables several novel cryptocurrency applications, such as cross-chain payment channels and efficient multi-party swaps