5-Minute Paper Summary: AT2: Asynchronous Trustworthy Transfers (2019)

AT2: Asynchronous Trustworthy Transfers

The core of decentralized asset transfer systems for crypto assets like Bitcoin is the resolution of the double-spending problem in a P2P setting involving Byzantine failures and asynchronous networks. While it has been thought that a consensus mechanism is essential for such decentralized transfers, this paper argues that this common belief is incorrect. AT2 is a protocol designed to achieve this. Algorithms for both private (permissioned) networks like data centers and public (permissionless) networks like Bitcoin are explained.

The Argument for Why Consensus is Unnecessary

The most striking topic in this paper is the repeatedly mentioned argument that consensus is unnecessary. The reasoning can be summarized as follows.

Double-spending problem: In a distributed system without consistency, different nodes can have different states. For example, in a financial system, node $X$ might move 800,000 yen from account $A$ with a balance of 1 million yen to another account $B$. However, another node $Y$, which does not yet know about that transaction, might see account $A$'s balance as 1 million yen and successfully process another transfer of 600,000 yen. Generally, to prevent such double-spending problems, it is necessary to introduce strong consistency (= consensus, distributed agreement, total ordering) into the system.

However, when specializing in asset transfers, the only constraint that needs to be satisfied is that "the account balance does not become negative." Furthermore, generally, only the account owner has the permission to generate a transfer transaction. In other words, if the account and the account owner are unique, it is sufficient to maintain a history of transfer transactions causally ordered by "happened before" for each account (since they should be serializable by the "account owner"). To achieve this, only asynchronous broadcast (+ the concept of causal consistency) is required, and consensus to guarantee distributed agreement or total ordering for the entire system is unnecessary—this is the fundamental premise of this paper. While it feels a bit rough since real-world transactions might need to wait for sufficient incoming funds before sending, it is generally understandable.

The insight that asynchronous broadcast can be used for such asset transfers was suggested in Pedone and Schiper (2002), and Section 7.2 mentions that Gupta (2016) introduced asset transfers similar to AT2. In fact, the fundamental idea is the same as in DAG-based blockchains like Byteball, where the responsibility for ensuring the processing order for each user lies with the client (although existing DAG types ultimately create a total order through consensus). Additionally, the structure of Stellar Consensus appears to share many similarities with AT2, as it consists only of broadcasting and agreement with neighboring nodes.

Algorithm

Fundamentally, it consists of asynchronous broadcasting and the management of causal consistency histories, such as Version Clocks or Version Vectors, for each account. Since the history is per account, I assume it won't be as complex as a full Vector Clock. The explanation of the algorithm is lengthy, so please refer to the paper.

The paper explains the AT2 algorithm through four variants (which contributes to the overall length of the paper). Each variant differs significantly in its broadcasting properties (communication characteristics), although the fundamental explanations and proofs are similar.

1. ${\sf AT2_{SM}}$: A wait-free algorithm that performs asset transfers asynchronously using shared memory where processes can read/write. This achieves a consensus number = 1.
2. ${\sf AT2_{MP}}$: A general-purpose asynchronous algorithm in a message-passing model that tolerates up to 1/3 Byzantine failures.
3. ${\sf AT2_{D}}$: A deterministic asynchronous algorithm designed for private networks/permissioned settings with tens to hundreds of nodes.
4. ${\sf AT2_{P}}$: A probabilistic asynchronous algorithm designed for public networks/permissionless settings that scales to tens of thousands of nodes, with logarithmic order latency and communication complexity.

It is stated that ${\sf AT2_D}$ uses Malkhi and Reiter (1997) for secure broadcasting, while ${\sf AT2_P}$ uses a version of Erdös-Rényi Gossip that guarantees consistency and safety for probabilistic broadcasting.

Advantages of Consensus-less

While fundamental assumptions are removed, making it impossible to perform tasks like smart contracts, it intuitively seems that there are many systemic benefits.

• There is no need to use heavy and complex distributed consensus protocols such as PoW, BFT, or Paxos for consensus.
• Since it is no longer affected by the FLP Impossibility even in asynchronous environments (<- that's true), there is no need to introduce countermeasures such as randomness, heavy cryptographic processing to guarantee randomness, or timeout mechanisms.
• There is no need to elect committees with static quorums like n=3f+1 for agreement.
• Mechanisms like sharding to resolve inefficiencies are also unnecessary.

The reported results show 1.5 to 6 times the throughput and up to a 2-fold reduction in latency compared to BFT-SMaRt.

Sybil Attack Resistance

While most other strategies rely on verifiable proofs like PoW for Sybil attack resistance, AT2 assumes the uniqueness of the owner. Therefore, it is said to be sufficient to guarantee that A is genuine by periodically sending data (ping?) over the A → B connection (this is reportedly called Proof-of-bandwidth).

GUERRAOUI, Rachid, et al. AT2: asynchronous trustworthy transfers. arXiv preprint arXiv:1812.10844, 2018.