  Blockchains were originally designed as closed execution environments and
lack the ability to communicate directly with external systems. To overcome
this limitation, many blockchains employ relayers, external applications
capable of transporting data between different blockchains. Typically, the
process of relaying data is permissionless and multiple independent relayers
work concurrently to transport the same information between two blockchains.
While this model increases the reliability of data delivery by providing
redundancy, it also introduces challenges that have not been previously
discussed. In this work, we bridge this gap by discussing the shortcomings of
permissionless cross-chain relaying systems and identifying three issues that
adversely impact their performance, scalability and security. We take the first
step towards addressing issues that hinder performance and scalability by
proposing a novel protocol to enable coordination among independent relayers.
Additionally, we provide an in-depth discussion about the trade-offs associated
with the design of relayer coordination protocols for permissionless settings.
Through this work we provide a foundation for improving cross-chain relaying
services.
