Formalizing a Routing Layer for Cross-Blockchain Communication

Blockchains are isolated by design. Interoperability solutions connect them but differ widely in trust, cost, and security guarantees. Since no single solution connects all blockchains, end-to-end cross-blockchain communication may require composing several of them in sequence. As the number of options grows, the space of possible communication paths increases, making path selection a non-trivial routing problem. To date, there is no formal framework for cross-blockchain routing.

We address this gap by formalizing cross-blockchain routing as a graph-based optimization problem over labeled directed multigraphs. Our abstraction allows applications to define their own vertex semantics and labeling functions. In addition, we propose an online routing algorithm that recomputes routes at each hop to adapt to changing network conditions. We instantiate the framework for three applications with structurally distinct label composition: asset swaps, smart contract orchestration, and message passing. A competitive ratio analysis establishes worst-case performance bounds close to an offline optimum, and simulation experiments for the asset swap instantiation confirm consistent gains of our adaptive approach over non-adaptive routing under realistic conditions.