Source-linked AI summary
The Consensus Number of a Cryptocurrency (Extended Version)
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Dragos-Adrian Seredinschi
TL;DR
Decentralized asset transfer systems are commonly understood to need consensus to prevent double-spending. This paper models asset transfer as a concurrent object and studies its consensus number in shared memory and Byzantine message passing. It shows that single-owner transfers have consensus number 1, while k-shared transfers have consensus number k, and presents a message-passing implementation that avoids consensus.
Problem
The paper addresses whether consensus is necessary to prevent double-spending in decentralized asset transfer systems.
Method
The paper treats asset transfer as a concurrent object, analyzes it in shared memory, and translates the results into Byzantine message passing.
Results
Single-owner asset transfer has consensus number 1, whereas k-shared asset transfer has consensus number k.
Takeaways & Limitations
Consensus can be avoided for single-owner asset transfers, while k-participant smart-contract-like operations require consensus only among those k participants.
Takeaways & Limitations
The paper focuses on Nakamoto’s original asset-transfer problem and does not address smart contracts for which consensus is necessary.
Abstract
from arXiv · showhide
Many blockchain-based algorithms, such as Bitcoin, implement a decentralized asset transfer system, often referred to as a cryptocurrency. As stated in the original paper by Nakamoto, at the heart of these systems lies the problem of preventing double-spending; this is usually solved by achieving consensus on the order of transfers among the participants. In this paper, we treat the asset transfer problem as a concurrent object and determine its consensus number, showing that consensus is, in fact, not necessary to prevent double-spending. We first consider the problem as defined by Nakamoto, where only a single process---the account owner---can withdraw from each account. Safety and liveness need to be ensured for correct account owners, whereas misbehaving account owners might be unable to perform transfers. We show that the consensus number of an asset transfer object is $1$. We then consider a more general $k$-shared asset transfer object where up to $k$ processes can atomically withdraw from the same account, and show that this object has consensus number $k$. We establish our results in the context of shared memory with benign faults, allowing us to properly understand the level of difficulty of the asset transfer problem. We also translate these results in the message passing setting with Byzantine players, a model that is more relevant in practice. In this model, we describe an asynchronous Byzantine fault-tolerant asset transfer implementation that is both simpler and more efficient than state-of-the-art consensus-based solutions. Our results are applicable to both the permissioned (private) and permissionless (public) setting, as normally their differentiation is hidden by the abstractions on top of which our algorithms are based.
1 INTRODUCTION
The paper argues that preventing double-spending does not require consensus: single-owner asset transfers have consensus number 1, while k-shared transfers have consensus number k. It extends these results to Byzantine message passing with a non-consensus implementation and frames asset transfer as a concurrent data-structure problem.
- 1 INTRODUCTION: Consensus is not essential for preventing double-spending: the single-owner asset-transfer object has consensus number 1.The result challenges the common assumption that total ordering and consensus are necessary for decentralized asset transfers.
- 1 INTRODUCTION: Unique account ownership removes the need for consensus because each owner orders withdrawals from its account, while others validate cross-account causal relations.The implementation validates withdrawals against incoming transfers observed in atomic snapshots and posts validated operations safely.
- 1 INTRODUCTION: A k-shared asset-transfer object, allowing up to k processes to withdraw from one account, has consensus number k.The paper establishes this through reductions between k-shared asset transfer and k-consensus.
- 1 INTRODUCTION: In Byzantine message passing, the proposed asset-transfer implementation avoids consensus and relies on secure broadcast with weak ordering guarantees.For k-shared transfers, consensus is needed only among the k involved participants, so faults in that group do not affect other accounts.
- 1 INTRODUCTION: Treating asset transfer as a concurrent data structure provides a way to measure its difficulty and devise alternative solutions.The paper presents this perspective as the overarching contribution of its shared-memory and message-passing results.
2 SHARED MEMORY MODEL AND ASSET-TRANSFER OBJECT TYPE
The paper formalizes asset transfer as a sequential object in an asynchronous shared-memory model with crash failures and linearizable implementations. Its object model tracks account balances, owner permissions, transfers, reads, and valid state transitions, initially restricting each account to at most one owner.
- 2.1 Definitions: The shared-memory model uses asynchronous processes that communicate through atomic shared-memory operations, with wait-free algorithms under crash failures.Processes are sequential, and every correct process eventually returns from each invoked operation despite other processes crashing.
- 2.1 Definitions: A sequential object type is defined by states, an initial state, operations, responses, and a transition relation governing legal state changes.Histories are legal when invocations and responses respect this transition relation.
- 2.1 Definitions: Linearizability requires every execution history to correspond to a legal sequential history while preserving each process’s order and real-time precedence.Incomplete invocations may be removed or completed when constructing the corresponding legal history.
- 2.2 The asset transfer object type: The asset-transfer object maps accounts to balances and supports transfer(a,b,x) and read(a) operations, with transfers succeeding only for authorized owners with sufficient funds.Successful transfers decrease the source balance by x and increase the destination balance by x; failed transfers leave the state unchanged.
- 2.2 The asset transfer object type: The initial model assumes at most one owner per account and restricts transfers to one source and one destination account.The paper later generalizes the owner map to k-shared asset-transfer objects.
3 ASSET TRANSFER HAS CONSENSUS NUMBER 1
The paper shows that single-owner asset transfer has consensus number 1 and can be implemented wait-free using read-write shared memory. The implementation uses atomic snapshots to validate transfers and preserve linearizability.
- 3 ASSET TRANSFER HAS CONSENSUS NUMBER 1: The asset-transfer object has consensus number 1 because it has a wait-free implementation using only read-write registers.Atomic snapshots provide the needed wait-free implementation in the shared-memory model with crash failures.
- 3 ASSET TRANSFER HAS CONSENSUS NUMBER 1: Each account has at most one owner, so all outgoing transfers from that account appear in the owner’s atomic-snapshot entry.This ownership structure lets the owner determine the order of withdrawals from its account.
- 3 ASSET TRANSFER HAS CONSENSUS NUMBER 1: A read takes a snapshot and computes the initial balance plus incoming transfers minus outgoing transfers, while a transfer succeeds only when the snapshot shows sufficient balance.The owner records a successful transfer through an atomic-snapshot update; otherwise the operation returns false.
- 3 ASSET TRANSFER HAS CONSENSUS NUMBER 1: The implementation remains wait-free because atomic snapshots are wait-free implementable from read-write registers and each operation performs finitely many snapshot accesses.Correct processes eventually complete each invoked operation despite crashes or concurrent invocations.
- 3 ASSET TRANSFER HAS CONSENSUS NUMBER 1: The implementation is linearizable because successful transfers are linearized at their snapshot updates and failed transfers at their balance-check snapshots.The proof shows that each resulting balance remains non-negative.
4 k-SHARED ASSET TRANSFER HAS CONSENSUS NUMBER k
For accounts shared by up to k owners, the paper shows that asset transfer has consensus number k. It establishes both directions by implementing k-process consensus with the object and reducing the object to k-consensus.
- 4 k-SHARED ASSET TRANSFER HAS CONSENSUS NUMBER k: A k-shared object permits at least one account to have k owners while no account has more than k owners.Equivalently, k = max_a∈A |µ(a)|.
- 4 k-SHARED ASSET TRANSFER HAS CONSENSUS NUMBER k: Consensus for k processes is implemented by initializing one shared account to 2^k and having process p attempt to withdraw 2^k − p.At most one withdrawal succeeds, and the remaining balance identifies the successful process, whose announced input becomes the decision value.
- 4 k-SHARED ASSET TRANSFER HAS CONSENSUS NUMBER k: The upper bound reduces k-shared asset transfer to k-consensus objects, associating a series of such objects with each account to order outgoing transfers.Each round uses one k-consensus instance to choose a transfer-result pair, while atomic snapshots maintain the implemented object’s state.
- 4 k-SHARED ASSET TRANSFER HAS CONSENSUS NUMBER k: The reduction provides a wait-free implementation of k-shared asset transfer in read-write shared memory equipped with k-consensus objects.Processes announce transfers, collect concurrent proposals, and decide their order and success or failure through successive consensus instances.
- 4 k-SHARED ASSET TRANSFER HAS CONSENSUS NUMBER k: A k-shared asset-transfer object has consensus number exactly k.The lower bound comes from a consensus implementation, and the upper bound from a reduction to k-consensus.
5 ASSET TRANSFER IN MESSAGE PASSING
The paper implements asset transfer in an asynchronous Byzantine message-passing system without consensus, using secure broadcast and causal dependencies. The implementation provides consistent state views and linearizable successful transfers for correct processes while guaranteeing completion.
- 5 ASSET TRANSFER IN MESSAGE PASSING: Secure broadcast and causal dependencies implement asset transfer without consensus in the Byzantine message-passing model.Transfers carry dependencies that impose a causal order, while secure broadcast supplies reliable delivery and weak ordering.
- 5 ASSET TRANSFER IN MESSAGE PASSING: Correct processes always obtain a consistent system-state view, although faulty senders may fail to complete transfers.Secure broadcast guarantees delivery properties for correct processes but provides liveness only when the sender is correct.
- 5 ASSET TRANSFER IN MESSAGE PASSING: A transfer requires one secure-broadcast invocation and no additional messages beyond those of the underlying primitive.In a preliminary deployment with up to 100 processes, throughput improved by 1.5x to 6x and latency by up to 2x over a consensus-based system.
- 5 ASSET TRANSFER IN MESSAGE PASSING: Successful transfers form a legal sequential history preserving the real-time order required by correct processes.Reads and failed transfers may be based on stale local state under the stated efficiency relaxation.
- 5 ASSET TRANSFER IN MESSAGE PASSING: Every correct-process operation eventually completes, and the algorithm implements the asset-transfer object type.The correctness argument constructs legal sequential histories consistent with global and local process histories.
6 k-SHARED ASSET TRANSFER IN MESSAGE PASSING
For accounts shared by up to k owners, the message-passing design combines per-account BFT ordering with modified secure broadcast. This handles the impossibility of purely asynchronous k-shared transfer while preserving safety and liveness under stated assumptions.
- 6 k-SHARED ASSET TRANSFER IN MESSAGE PASSING: Purely asynchronous k-shared asset transfer is impossible even with benign shared-memory faults, so owner agreement is required.The message-passing design circumvents this limitation by using Byzantine-fault-tolerant state-machine replication among account owners.
- 6 k-SHARED ASSET TRANSFER IN MESSAGE PASSING: If more than one third of account owners are Byzantine, an account may become blocked or compromised and conflicting sequence numbers may occur.The BFT service is safe when more than two thirds of owners are correct.
- 6 k-SHARED ASSET TRANSFER IN MESSAGE PASSING: Account-order broadcast delivers messages for the same account in increasing sequence-number order.A benign process acknowledges a message only after delivering the preceding sequence number for that account.
- 6 k-SHARED ASSET TRANSFER IN MESSAGE PASSING: The k-shared implementation combines one BFT service per account, modified secure broadcast, and a revised transfer protocol.BFT services assign monotonically increasing sequence numbers to outgoing transfers.
- 6 k-SHARED ASSET TRANSFER IN MESSAGE PASSING: The resulting protocol guarantees linearizable successful-transfer histories and completion for transfers on non-compromised accounts.These guarantees rely on consistent service behavior and the account not being compromised.
7 RELATED WORK
The paper distinguishes its consensusless transfer approach from blockchain and DAG systems that still employ consensus. It positions its contribution as the first formal shared-object and consensus-number treatment of asset transfer with deployment-oriented algorithms.
- 7 RELATED WORK: Many permissioned and permissionless systems support asset transfers, while permissionless systems additionally use Sybil-resistance techniques such as proof-of-work or proof-of-stake.The paper’s comparison covers both private systems with external access control and public systems open to the world.
- 7 RELATED WORK: The paper focuses on Nakamoto’s original asset-transfer problem and does not address smart contracts, for some forms of which consensus remains necessary.Operations affecting groups able to solve consensus can be supported, with violations confined to a compromised group.
- 7 RELATED WORK: Unlike DAG-based transfer systems that still employ consensus, this approach uses per-account histories loosely coupled by causal dependencies.Each account owner manages an individual history without depending on a global system view.
- 7 RELATED WORK: The authors identify prior asynchronous broadcast-based transfer insights from 2002 and related Byzantine-tolerant storage and financial-transfer work.They characterize their contribution as formalizing asset transfer as a shared object, determining its consensus number, and building deployable algorithms.