PaperlayerView exact revision on arXiv

Source-linked AI summary

The Blockchain Anomaly

Christopher Natoli, Vincent Gramoli

arXiv:1605.05438v1cs.DC

TL;DR

Blockchain consensus guarantees and their limits are difficult to assess in private chains, where conditional transactions depend on the observable committed state. The paper reproduces a Blockchain anomaly on an Ethereum private chain and shows that committed transactions can be reordered; smart contracts may offer a more complex workaround.

  • Problem

    The guarantees of blockchain consensus in private, controlled settings are not well understood, despite companies beginning to deploy private chains.

    Source: §1 · p. 2

  • Method

    The authors stress-test an Ethereum private chain and reproduce an execution with delayed messages and miners operating at different speeds.

    Source: §1 · p. 2

  • Results

    Committed transactions can be reordered after delayed messages arrive, potentially enabling double spending under realistic differences in miners’ capabilities.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Smart contracts may bypass the anomaly in some cases, but add complexity and do not automatically ensure immunity.

    Source: §5.1 · p. 8, §8 · p. 10

    On-chain checking and conditional transfer may reduce the chance of the anomaly, but do not guarantee immunity; formal investigation remains necessary.

    Source: §5.1 · p. 8

Abstract

from arXiv · show

Most popular blockchain solutions, like Bitcoin, rely on proof-of-work, guaranteeing that the output of the consensus is agreed upon with high probability. However, this probability depends on the delivery of messages and that the computational power of the system is sufficiently scattered among pools of nodes in the network so that no pool can mine more blocks faster than the crowd. New approaches, like Ethereum, generalise the proof-of-work approach by letting individuals deploy their own private blockchain with high transaction throughput. As companies are starting to deploy private chains, it has become crucial to better understand the guarantees blockchains offer in such a small and controlled environment. In this paper, we present the \emph{Blockchain Anomaly}, an execution that we experienced when building our private chain at NICTA/Data61. Even though this anomaly has never been acknowledged before, it may translate into dramatic consequences for the user of blockchains. Named after the infamous Paxos anomaly, this anomaly makes dependent transactions, like "Bob sends money to Carole after he received money from Alice" impossible. This anomaly relies on the fact that existing blockchains do not ensure consensus safety deterministically: there is no way for Bob to make sure that Alice actually sent him coins without Bob using an external mechanism, like converting these coins into a fiat currency that allows him to withdraw. We also explore smart contracts as a potential alternative to transactions in order to freeze coins, and show implementations of smart contract that can suffer from the Blockchain anomaly and others that may cope with it.

1 Introduction

The introduction frames private blockchains as a setting where consensus guarantees and their limits need closer examination. It presents the Blockchain anomaly: committed transactions can be reordered, disrupting dependencies and potentially enabling double spending; smart contracts may offer a more complex workaround.

Motivation

  • Private chains offer a controlled environment for multiple companies, motivating an examination of their consensus limits through stress testing.The introduction notes an Ethereum private-chain deployment involving eleven banks.Source: §1 · p. 2

Contributions

  • The Blockchain anomaly can prevent a user from executing a transaction based on the blockchain’s current state, with possible consequences including lost virtual assets or double spending.The paper also provides source code for a more complex smart contract that circumvents a particular example of the anomaly.Source: §1 · p. 2

Background

  • Bitcoin-style blockchains mine transactions into blocks and adopt the longest branch after transient forks are discovered.Forks are assumed to grow only to limited depth; Bitcoin recommends six blocks before treating a transaction as accepted.Source: §1 · p. 2

Motivation

  • The paper contrasts blockchains that may respond incorrectly with foundational consensus algorithms that preserve correctness under message delays by doing nothing in the worst case.Those algorithms sacrifice termination, but can reach consensus if the network later stabilizes and message delivery becomes bounded.Source: §1 · p. 2

Contributions

  • Committed transactions can be reordered after delayed messages arrive, and the authors argue realistic differences in miners’ computing capacity could enable double spending.The authors reproduce the execution on an Ethereum private chain and note that similar issues may apply to proof-of-stake private chains.Source: §1 · p. 2

2 Preliminaries

The preliminaries introduce blockchain structure and consensus, including how block decisions are treated as commits after a system-dependent depth. They also review the Paxos anomaly and set out a proof-of-work ledger model for discussing the Blockchain anomaly.

2 Preliminaries

  • The section establishes blockchain technology, the Paxos anomaly, and key terms as foundations for the paper’s later presentation of the Blockchain anomaly.It also previews Ethereum private-chain experiments and smart-contract approaches to bypassing the anomaly.Source: §2 · p. 3

2.1 Blockchain Systems

  • A blockchain is a replicated state machine whose blocks link to preceding states, with proof-of-work miners solving hashcash puzzles before blocks are appended.Puzzle difficulty limits the rate at which new blocks can be generated.Source: §2.1 · p. 3

2.2 From Nakamoto’s Consensus to Smart Contracts

  • Bitcoin’s Nakamoto consensus offers agreement with probability close to 1, while Ethereum’s faster block production favors transient forks and uses GHOST to retain some uncle blocks.Ethereum also provides a Turing-complete language for smart contracts that define ownership rules.Source: §2.2 · p. 3

2.3 Termination of Consensus

  • Consensus for block index i terminates when blockchain depth reaches i + k, at which point transactions in the decided block are committed.The value of k depends on the blockchain system; merely observing a mined and appended block does not establish that it is decided.Source: §2.3 · p. 3

2.4 The Paxos Anomaly

  • The Paxos anomaly arises when consensus on individual transactions violates their dependency: a later transaction may be decided even if the earlier transaction was not.The Blockchain anomaly shares this concern but can involve transactions issued by different nodes that were not concurrent.Source: §2.4 · p. 4

2.5 General Model

  • The general model treats the ledger as an auditable record of transactions in a linked blockchain and assumes arbitrary peer failures, miners, proof-of-work, and transient forks resolved by reorganisation.Miners select non-conflicting transactions with sufficient funds from the transaction pool and bundle them into blocks.Source: §2.5 · p. 4

3 The Blockchain Anomaly

The Blockchain anomaly arises when delayed messages and chain reorganization undermine the ordering of dependent transactions, with possible consequences including double-spending and undetectable misuse.

3 The Blockchain Anomaly

  • Mainstream blockchain systems whose consensus protocols lack deterministic agreement can exhibit the Blockchain anomaly.The paper presents this as a problem affecting mainstream blockchain systems.Source: §3 · p. 4

3.1 Causes of the Blockchain Anomaly

  • Long message delays can make miners appear to agree separately on branches each longer than k, with eventual message delivery exposing inconsistencies.This can occur even when miners start from the same genesis block; private-chain participants may have direct access to network resources.Source: §3.1 · pp. 4–5

3.2 Uncommitting Transactions

  • A reorganization can remove committed ti while tj is committed in its slot, breaking their dependency; Bitcoin discards ti, while Ethereum may commit it later.The transactions represent Bob receiving money from Alice and then paying Carole.Source: §3.2 · p. 5

3.3 Facilitating a Double-Spending Attack

  • After collecting goods for t1, an attacker can publish a longer chain without it, commit t2, and collect goods again.A later recommitment of t1 is invalidated because the balance is insufficient, but the double-spend has already occurred.Source: §3.3 · p. 5

3.4 Tracking Blockchain Anomalies

  • Once a wrongly committed state is uncommitted, it cannot be observed afterward, and the beneficiaries cannot be tracked down.The authors say this may incentivize private-chain participants to exploit the anomaly.Source: §3.4 · p. 5

4 Experimental Evaluation

Experiments on a private Ethereum chain reproduce an anomaly in which a later dependent transaction can remain committed after the earlier transaction disappears. Automated runs and difficulty sweeps show that swaps persist across mining difficulties, while consensus termination time increases with difficulty.

4.1 Experimental Setup

  • The three-machine private Ethereum setup introduced network delays and made p3 mine faster than p1 using 24 hardware threads versus one.The nodes ran on a local area network; the delay was created by transiently disconnecting connection points.Source: §4.1 · p. 5

4.2 Distributed Execution

  • After t1 appeared committed, t2 was issued; the final 45-block chain committed t2 while leaving t1 uncommitted, violating their required order.The reorganization followed delivery of the third participant's delayed message.Source: §4.2 · p. 6

4.3 Automating the Reproduction of the Anomaly

  • In all eight automated runs, t2 committed after t1 appeared committed while reorganization left t1 uncommitted; mining randomness and network latency varied inclusion and termination times.The experiment used k = 11, requiring 12 mined blocks for consensus termination.Source: §4.3 · pp. 6–7

4.4 Swap Frequency with Different Mining Difficulties

  • Across difficulties 0x2000 to 0x40000, swaps averaged 6 out of 10 with no significant correlation, while consensus termination time increased with difficulty.A network delay greater than the time to mine was foundational to observing the anomaly.Source: Figure 6 · p. 7, §4.4 · pp. 7–8

5 Smart Contracts

Smart contracts can avoid the observed anomaly when their logic keeps a payment check and its conditional transfer together on-chain, but separating those steps can leave the check vulnerable to reorganization. A Bitcoin multisignature joint payment offers another workaround, with different semantics from a conditional transaction.

5.1 On-Chain vs. Off-Chain Computation

  • The anomaly's prevention depends on contract logic; the sendIfReceived example groups the payment check and conditional transfer on-chain, where the authors could not observe the anomaly.The authors caution that this does not establish immunity and say formal investigation is still needed.Source: §5 · p. 8, §5.1 · p. 8
  • Separating the check and transfer into functions leaves the check off-chain, where Alice's payment may be reorganized before the later unconditional transfer.The paper says the on-chain example is not guaranteed immune, and contract inclusion itself may also be reordered.Source: §5.1 · p. 8

5.2 Multisignatures and the Case of Bitcoin

  • A Bitcoin multisignature joint payment can combine the conditional payment and its enabling action, but Bob cannot wait to see Alice's payment before choosing whether to pay Carole.Alice and Bob can sign, or Donald can help resolve the transaction if either refuses.Source: §5.2 · p. 9

6 Discussion

The discussion extends the Blockchain anomaly beyond proof-of-work and distinguishes it from transaction-order changes. Its analysis also depends on treating termination as deterministic while agreement may fail.

6 Discussion

  • A sufficiently scattered mining power makes the anomaly very unlikely in large permissionless systems, but incentives to withhold mined blocks could potentially enable it.The paper also notes that a mining pool controlling more than half of public-chain mining power could produce the anomaly.Source: §6 · p. 9
  • In a 51-percent attack, an attacker can replace a block containing a withdrawal or Alice-to-Bob transfer, potentially keeping coins after withdrawing or overriding the transfer.The attacker forks from the block before the transaction and has the new branch adopted once it becomes longer.Source: §6 · p. 9
  • Proof-of-stake does not necessarily avoid the Blockchain anomaly: Casper favors availability over consistency, while Tendermint favors consistency over availability.The paper notes that the anomaly can apply even to proof-of-stake systems.Source: §6 · p. 9
  • The anomaly is more general than transaction reordering: conflicting transactions can be committed in two different blockchain states, and solving the anomaly would also solve the order-change problem.The cited order-change problem concerns two transfers of $100 from an account initially holding $100.Source: §6 · pp. 9–10
  • In the paper’s formalization, consensus terminates deterministically after the recommended 6 to 12 mined blocks, but agreement can fail; other formalizations treat termination as probabilistic.The paper notes that applications assume termination for responsive service, while the anomaly shows that a private-chain block can be reverted.Source: §6 · p. 10

7 Related Work

Related work contrasts proof-of-work with Byzantine fault-tolerant approaches, describes systems with stronger deterministic guarantees, and distinguishes the Blockchain anomaly from the Paxos anomaly.

7 Related Work

  • Experiments comparing Bitcoin and PBFT across eight locations found PBFT had lower latency and higher throughput, while its authors noted scalability limits and recommended sharding.The comparison evaluated transaction service performance.Source: §7 · p. 10
  • Bitcoin scales beyond 1000 nodes but achieves less than 100 transactions per second with high latency, while standard Byzantine fault-tolerant protocols exceed 10,000 transactions per second but scale only to tens of nodes.The comparison frames proof-of-work as scalable but inefficient and Byzantine agreement as efficient but not scalable.Source: §7 · p. 10
  • PeerCensus combines Byzantine agreement on Bitcoin with Sybil-attack mitigation, strengthening Bitcoin’s guarantees and resolving forks immediately to avoid the Blockchain anomaly.Its voting component makes it difficult for an attacker to create enough identities to outnumber other votes.Source: §7 · p. 10
  • Tendermint requires strictly more than two thirds of processes to be correct for deterministic agreement and validity, and guarantees termination when the network stabilizes and non-faulty nodes exchange messages.The paper describes Tendermint as favoring consistency over availability, opposite to Casper.Source: §7 · p. 10
  • The Paxos anomaly concerns dependent concurrent requests, whereas the Blockchain anomaly can involve transactions from different nodes that are not concurrent and can change index after consensus.For applications without concurrent dependent requests, Paxos is sufficient.Source: §7 · p. 10

8 Conclusion

The conclusion presents the Blockchain anomaly as a barrier to conditional transactions, demonstrated through transaction reordering on an Ethereum private chain. It warns that smart-contract alternatives add complexity and calls for understanding blockchain guarantees.

8 Conclusion

  • The Blockchain anomaly prevents conditional transactions from executing against the current observable committed state or a later state, and the authors reproduced it by reordering committed transactions on an Ethereum private chain.The authors encountered the anomaly while using an Ethereum private chain at NICTA/Data61.Source: §8 · p. 10
  • Smart contracts may offer a way to avoid the anomaly, but they add complexity.Source: §8 · p. 10
  • The authors conclude that users should understand blockchain design principles and guarantees before using blockchain systems.Source: §8 · p. 10
  • Combining fast consensus termination with probabilistic agreement can produce dramatic consequences in private chains.Source: §8 · p. 11
  • The paper focuses on Bitcoin and Ethereum; exploring other alternatives with deterministic guarantees for private chains remains future work.Source: §8 · p. 11
Loading 1605.05438v1…