Published in


DLT Interoperability and More ⛓️#8 ⛓️ — Cross-Chain State Machine Replication

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

This edition covers a recent paper on state machine replication.

➡️ Title: Cross-Chain State Machine Replication
➡️ Authors: Yingjie Xue, Maurice Herlihy

➡️ Paper source: Cross-Chain State Machine Replication

➡️ Background:

State machine replication (SMR) is one of the fundamental topics in the research area of distributed systems. We have a free blockchain course that provides an overview of SMR in the first class.

The model:

“The system consists of a set of communicating automata. An automaton is either an active, untrusted agent or a passive, trusted replica. An agent automaton models a blockchain client such as a person or an organization. Agents are untrusted because they model untrusted blockchain clients. A replica automaton models a smart contract (or contract), a chain-resident program that manipulates ledger state. Contract code and state are public, and that code is reliably executed by validators who reach consensus on each call. Replicas are trusted because they model trusted contracts. Reflecting the limitations of today’s blockchains, agents communicate only with replicas (clients can only call contract functions), and replicas do not communicate with other replicas (contracts on distinct chains cannot communicate). Replica 𝐴 can learn of a state change at replica 𝐵 only if some agent explicitly informs 𝐴 of 𝐵’s new state. Of course, 𝐴 must decide whether that agent is telling the truth.”

In this paper, applications such as cross-chain swaps are structured as multi-step protocols where agents take turns transferring assets in and out of escrow accounts. Hence, in this paper, the state machine is structured as a multi-agent game.

➡️ Contributions:

  • The authors propose a new state machine replication protocol for the cross-chain states. The motivation of the authors: “Conventional SMR embraces distribution to make services fault-tolerant. By contrast, individual blockchains are already fault-tolerant. Instead, cross-chain SMR is motivated by the need for interoperability across multiple independent chains.”

💪 Strong points:

  • The background on SMR and its applicability for the cross-chain scenario is elegant.

😞 Limitations:

  • The system considers a synchronous network, where communication is bounded by a delta parameter. However, it is not clear If this is the best model for multiple distributed systems with different clocks running at different rates. Would the notion of a global clock, a “clock of clocks” make sense in this setting, as the unit to synchronize cross-blockchain state?

🔥 Points of interest:

  • The proposed concepts are formalized using items from diverse research areas. Cross-chain scenarios are introduced as games, represented by decision trees. The specification of the state machines that execute each is represented using procedural pseudocode. An example of a swap:

The paper also contains an example of a DAO state machine.

🚀 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)

  • Enabling secure, scalable interoperability is an important part of what we do at Blockdaemon. Studying cheaper ways to perform atomic swaps is of interest to support growing blockchain ecosystems, that take interoperability as an important factor.

🚀 What are the implications for our work?

New to trading? Try crypto trading bots or copy trading



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rafael Belchior

R&D Engineer at Blockdaemon. Opinions and articles are my own and do not necessarily reflect the view of my employer.