Communication across distributed systems, each running its own consensus, is a problem previously studied under the assumption of trust across systems. With the appearance of distributed ledgers or blockchains, numerous protocols have emerged, which attempt to achieve trustless communication between distrusting ledgers and participants. Cross-chain communication thereby plays a fundamental role in cryptocurrency exchanges, sharding, bootstrapping and extension of distributed ledgers. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence on their correctness and to use them as building blocks for new systems.