DLT Interoperability and More ⛓️#14 ⛓️ — SoK: Communication Across Distributed Ledgers

Rafael Belchior
4 min readNov 4, 2022


In this series, we analyze papers on blockchain and interoperability.

This edition covers a cornerstone paper on blockchain interoperability.

➡️ Title: SoK: Communication Across Distributed Ledgers
➡️ Authors: Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, and Aggelos Kiayias

➡️ Paper source: https://arxiv.org/abs/2208.07119

➡️ Background:

Dozens of works summarizing the field of blockchain interoperability exist. In our own, we compared some of the existing surveys.

The paper we discuss today focuses on interoperability across public blockchains, including the usage of techniques such as notary schemes, hashed time lock contracts (HTLCs), and sidechains.

Let us consider two ledgers, la and lb. Let us consider a cross-chain transaction composed of two sub-transactions: ta (in ledger a) and tb (in ledger b). Cross-chain transactions follow a set of cross-chain rules, that are encoded in the transaction “description”: d(ta) and d(tb). E.g., if the cross-chain logic is a lock-mint mechanism, d(ta) would be locking X assets on blockchain A and d(tb) would be unlocking a representation of X assets on blockchain B.

The authors define a cross-chain protocol as having the setup, pre-commit on la, verify and commit phases (which resembles the 2PC protocol, which is in fact used by some interoperability protocols). In the setup, both parties define the scope of the protocol. Then, a transaction happens on la. This transaction can be reverted by issuing a transaction with the contrary effect if needed. On the verify phase, the commit on la is checked. If it happens, a transaction on lb happens. Finally, the commit on lb is verified by la. If everything checks, ta => tb, upon a defined time interval.

➡️ Contributions:

  • The authors formalize the problem of cross-chain communication and explore the particular case of asset transfers.
  • The authors propose a classification of cross-chain protocols, mostly realizing asset transfers across public blockchains.

💪 Strong points:

  • The authors make a bridge between the atomic commit problem from the distributed systems area, to blockchain interoperability. While both rely on atomically asserting as valid or invalid a set of transactions, their security assumptions are different: in the first, the failure mode tolerates crash faults, while for the second, we must tolerate Byzantine faults. However, there are some models for blockchain interoperability that are only crash-fault tolerant (and therefore have a different set of requirements, safety, and liveness properties than the ones discussed here).

🤞 Suggestions for improvement:

  • Not a limitation per se: this study is originally from 2019, where interoperability across public and private blockchains was not a topic of research, nor more general cross-chain interoperability. The latter means that we might have a set of rules extending on N chains (what we call the cross-chain model). This would allow the design of cross-chain use cases such as cross-chain MEV, blockchain migration (1-N), or others, which do not seem to have been included in this study.

🔥 Points of interest:

  • Formalization: According to the authors, correct cross-chain communication has two safety properties (Effectiveness, Atomicity) and one liveness property (Timeliness). Effectiveness states that if a cross-chain transaction is valid, then a sub-transaction ta is included in ledger la implies a sub-transaction tb is included in ledger lb. If the description of a or b is not as expected, both parties abort. Atomicity states if ta is included in la at time t, then tb is included in lb before time t’, similar to the interoperability model using trusted gateways. Timeliness says that the underlying ledgers propagate ta and tb.
  • Big insight: Impossibility of CCC without a Trusted Third Party.
  • Oracle systems are not cross-chain protocols but enable them.
  • In Section 4, the authors put together a systematization of the 4 phases for a cross-chain protocol, illustrating it with examples of deployed systems (Section 5). We can see notary schemes, HTLCs, sidechains, and others.
  • The authors have put together simple cross-chain protocols in the Appendix. Interesting to see how the abstract machinery works.
  • “the absence of a global clock across chains requires CCC participants to either agree on a trusted third party as means of synchronization or to rely on a chain-dependent time definition” — this is interesting to think about for protocol makers. A clock that translates local notions of time (e.g., block numbers) is necessary to implement certain use cases, such as HTLCs. However, the latter could be vulnerable to race conditions coming from a system using subsystems with different notions of time

🚀 How does it relate to our work at Técnico Lisboa, INESC-ID, and Blockdaemon? (views are my own and do not necessarily reflect the opinions of my employer)

  • We work on systematizing and understanding blockchain interoperability so we can build better middleware.



Rafael Belchior

R&D Engineer at Blockdaemon. Opinions and articles are my own and do not necessarily reflect the view of my employer. https://rafaelapb.github.io