The Balance Attack Against Proof-Of-Work Blockchains: The R3 Testbed as an Example

BY KEYHUNTER 06.03.2025
The Balance Attack Against Proof-Of-Work Blockchains: The R3 Testbed as an Example

In this paper, we identify a new form of attack, called the Balance attack, against proof-of-work blockchain systems. The novelty of this attack consists of delaying network communications between multiple subgroups of nodes with balanced mining power. Our theoretical analysis captures the precise tradeoff between the network delay and the mining power of the attacker needed to double spend in Ethereum with high probability.

We quantify our probabilistic analysis with statistics taken from the R3 consortium, and show that a single machine needs 20 minutes to attack the consortium. Finally, we run an Ethereum private chain in a distributed system with similar settings as R3 to demonstrate the feasibility of the approach, and discuss the application of the Balance attack to Bitcoin. Our results clearly confirm that main proof-of-work blockchain protocols can be badly suited for consortium blockchains.

Keywords: Ethereum; proof-of-work, GHOST, Chernoff bounds

I. INTRODUCTION

Blockchain systems are distributed implementations of a chain of blocks. Each node can issue a cryptographically signed transaction to transfer digital assets to another node or can create a new block of transactions, by solving a crypto-puzzle, and append this block to its current view of the chain. Due to the distributed nature of this task, multiple nodes may append distinct blocks at the same index of the chain before learning about the presence of other blocks, hence leading to a forked chain or a tree. For nodes to eventually agree on a unique state of the system, nodes apply a common strategy that selects a unique branch of blocks in this tree.

Bitcoin [23], one of the most popular blockchain systems, selects the longest branch. This strategy has however shown its limitation as it simply wastes all blocks not present in this branch [9], [27], [29], [15], [25]. If an attacker can solve crypto-puzzles fast enough to grow a local branch of the blockchain faster than the rest of the system, then it will eventually impose its own branch to all participants. In particular, by delaying the propagation of blocks in the system, one can increase the amount of wasted blocks and proportionally slow down the growth of the longest branch of the system. This delay presents a serious risk to the integrity of the blockchain, as the attacker does not even need a large fraction of the computational power to exceed the length of the chain, allowing her to double spend in new transactions the coins that she already spent in earlier transactions [28].

Ethereum [32] proposes another selection strategy that copes with this problem. Each node uses an algorithm, called GHOST, that starts from the first block, also called the genesis block, and iteratively selects the root of the heaviest subtree to construct the common branch. Even if nodes create many blocks at the same index of the blockchain, their computational power is not wasted but counted in the selection strategy [29]. In particular, the number of these “sibling” blocks increase the chance that their common ancestor block be selected in favor of another candidate block mined by the attacker. Although it clearly alleviates the Bitcoin limitation discussed above [9], [27], [15], [25] it remains unclear how long an attacker with a low mining power should delay messages to discard previous transactions in Ethereum.

In this paper, we answer this question by demonstrating theoretically and experimentally that an attacker can compensate a low mining power by delaying selected messages in Ethereum. To this end, we propose a simple attack, called the Balance Attack: an attacker transiently disrupts communications between subgroups of similar mining power. During this time, the attacker issues transactions in one subgroup, say the transaction subgroup, and mines blocks in another subgroup, say the block subgroup, up to the point where the tree of the block subgroup outweighs, with high probability, the tree of the transaction subgroup. The novelty of the Balance attack is to leverage the GHOST protocol that accounts for sibling or uncle blocks to select a chain of blocks. This strategy allows the attacker to mine a branch possibility in isolation of the rest of the network before merging its branch to one of the competing blockchain to influence the branch selection process.

We experimented a distributed system running Ethereum in similar settings as R3, a consortium of more than 70 world-wide financial institutions. In January, R3 consisted of eleven banks and successfully collaborated in deploying an Ethereum private chain to perform transactions.\footnote{http://www.ibtimes.co.uk/r3-connects-11-banks-distributed-ledger-using-ethereum-microsoft-azure-1539044.} Since then, R3 has grown and kept experimenting Ethereum\footnote{http://www.coindesk.com/r3-ethereum-report-banks/.} and other technologies while the concept of consortium private chain gained traction for its ability to offer a blockchain system among multiple companies in a private and controlled environment. R3 has just released their own Corda framework. As opposed to a fully private chain scenario, the consortium private chain involves different institutions possibly competing among each other. As they can be located at different places around the world, they typically use Internet to communicate. We illustrate the Balance attack in the R3 testbed setting as of June 2016, by deploying our own private chain on 15 mining virtual machines in Emulab and configuring the network with ns-2.

While disrupting the communication between subgroups of a blockchain system may look difficult, there have been some attacks successfully delaying messages of Bitcoin in the past. In 2014, a BGP hijacker exploited access to an ISP to steal $83000 worth of bitcoins by positioning itself between Bitcoin pools and their miners [19]. Some known attacks against Bitcoin involved partitioning the communication graph at the network level [1] and at the application level [17]. At the network level, a study indicated the simplicity for autonomous systems to intercept a large amount of bitcoins and evaluated the impact of these network attacks on the Bitcoin protocol [1]. At the application level, some work showed that an attacker controlling 32 IP addresses can “eclipse” a Bitcoin node with 85% probability [17]. More generally, man-in-middle attacks can lead to similar results by relaying the traffic between two nodes through the attacker.

One can exploit the Balance attack to violate the persistence of the main branch, hence rewriting previously committed transactions, and allowing the attacker to double spend. As opposed to previous attacks against Bitcoin where the attacker has to expand the longest chain faster than correct miners to obtain this result [28], the novelty of our attack lies in the contribution of the attacker to one of the correct miner chain in order to outweigh another correct miner chain of Ethereum.

We generalize our contribution to proof-of-work algorithms by proposing a simple model for proof-of-work blockchains and specifying Nakamoto’s and GHOST consensus algorithmic differences. We also discuss how to adapt the Balance attack to violate the persistence of Bitcoin main branch. This adaptation requires to mine at the top of one of the correct chains rather than solo-mining a subchain but can lead to similar consequences. More precisely, we make the four following contributions:

  1. We show that the GHOST consensus protocol can be vulnerable to a double spending attack without coalition and with high probability if a single attacker can delay communication between multiple communication subgraphs while owning 5% of the total mining power of the system.
  2. We illustrate the problem in the context of the R3 consortium blockchain, as of June 2016, where we observed 50 nodes among which 15 were mining. We show that one of the nodes can execute a Balance attack by disrupting some communication channels less than 4 minutes.
  3. We demonstrate a tradeoff between the mining power needed and the time selected communication channels have to be delayed to attack Ethereum. This suggests that combining network-level with application-level attacks increases the Ethereum vulnerability.
  4. We generalize this result to Nakamoto’s protocol and propose an adaptation of the Balance attack to double spend in Bitcoin if the attacker can contribute, even with a small power, by mining on top of some of the correct chains.

Section II defines the problem. In Section III, we present the algorithm to run the attack. In Section IV, we show how the analysis affects GHOST. In Section V, we simulate a Balance attack in the context of the R3 consortium network. In Section VI, we present our experiments run in an Ethereum private chain. In Section VII, we discuss the implications of the attack in existing blockchain systems. Section VIII presents the related work. And Section IX concludes. Appendix A includes the missing proofs for the general case.

II. PRELIMINARIES

In this section we model a simple distributed system as a communication graph that implements a blockchain abstraction as a directed acyclic graph. We propose a high-level pseudocode representation of proof-of-work blockchain protocols in this model that allows us to illustrate an important difference between Bitcoin and Ethereum in the selection of a main branch with a persistent prefix.

A. A simple distributed model for blockchains

We consider a communication graph $G = \langle V, E \rangle$ with nodes $V$ connected to each other through fixed communication links $E$. Nodes are part of a blockchain system $S \in {\text{bitcoin, ethereum}}$ and can act as clients by issuing transactions to the system and/or servers by mining, the action of trying to combine transactions into a block. For the sake of simplicity, we consider that each node possesses a single account and that a transaction issued by node $p_i$ is a transfer of digital assets or coins from the account of the source node $p_i$ to the account of a destination node $p_j \neq p_i$. Each transaction is uniquely identified and broadcast to all nodes in a best-effort manner. We assume that a node re-issuing the same transfer multiple times creates as many distinct transactions.

Nodes that mine are called miners. We refer to the computational power of a miner as its mining power and we denote the total mining power $t$ as the sum of the mining powers of all miners in $V$. Each miner tries to group a set $T$ of transactions it heard about into a block $b \geq T$ as long as transactions of $T$ do not conflict and that the account balances remain non-negative. For the sake of simplicity in the presentation, the graph $G$ is static meaning that no nodes can join and leave the system, however, nodes may fail as described in Section II-A2.

Miner must solve a crypto-puzzle to create a new block: Miners provably solve a hashcash crypto-puzzle [3] before creating a new block. Given a global threshold and the block of largest index the miner knows, the miner repeatedly selects…

a nonce and applies a pseudo-random function to this block and the selected nonce until it obtains a result lower than the threshold. Upon success the miner creates a block that contains the successful nonce as a proof-of-work as well as the hash of the previous block, hence fixing the index of the block, and broadcasts the block. As there is no known strategy to solve the crypto-puzzle, the miners simply keep testing whether randomly chosen numbers solve the crypto-puzzle. The mining power is thus expressed in the number of hashes the miner can test per second, or $H/s$ for short. The difficulty of this crypto-puzzle, defined by the threshold, limits the rate at which new blocks can be generated by the network. In the remainder, we refer to $d$ as the difficulty of this crypto-puzzle.

  1. The failure model: We assume the presence of an adversary (or attacker) that can control nodes that together own a relatively small fraction $\rho < 0.5$ of the total mining power of the system. The nodes controlled by the adversary are called malicious and may not follow the protocol specification, however, they cannot impersonate other nodes while issuing transactions. A node that is not malicious is correct. We also assume that the adversary can transiently disrupt communications on a selected subset of edges $E_0$ of the communication graph $G$.
  2. The blockchain abstraction: Let the blockchain be a directed acyclic graph (DAG) $\ell = \langle B, P \rangle$ such that blocks of $B$ point to each other with pointers $P$ (pointers are recorded in a block as a hash of the previous block) and a special block $g \in B$, called the genesis block, does not point to any block.

Algorithm 1 describes the progressive construction of the blockchain at a particular node $p_i$ upon reception of blocks from other nodes by simply aggregating the newly received blocks to the known blocks (lines 3–5). As every added block contains a hash to a previous block that eventually leads back to the genesis block, each block is associated with a fixed index. By convention we consider the genesis block at index 0, and the blocks at $k$ hops away from the genesis block as the blocks at index $k$. As an example, consider the simple blockchain $\ell_1 = \langle B_1, P_1 \rangle$ depicted in Figure 1(a) where $B_1 = {g, b_1}$ and $P_1 = {(b_1, g)}$. The genesis block $g$ has index 0 and the block $b_1$ has index 1.

  1. Forks as disagreements on the blocks at a given index: As depicted by views $\ell_1, \ell_2$ and $\ell_3$ in Figures 1(a), 1(b) and 1(c), respectively, nodes may have a different views of the current state of the blockchain. In particular, it is possible for two miners $p_1$ and $p_2$ to mine almost simultaneously two different blocks, say $b_1$ and $b_2$. If neither block $b_1$ nor $b_2$ was propagated early enough to nodes $p_2$ and $p_1$, respectively, then both blocks would point to the same previous block $g$ as depicted in Figures 1(a) and 1(b). Because network delays are not predictable, a third node $p_3$ may receive the block $b_1$ and mine a new block without hearing about $b_2$. The three nodes $p_1, p_2$ and $p_3$ thus end up having three different local views of the same blockchain, denoted $\ell_1 = \langle B_1, P_1 \rangle$, $\ell_2 = \langle B_2, P_2 \rangle$ and $\ell_3 = \langle B_3, P_3 \rangle$.

We refer to the global blockchain as the directed acyclic graph $\ell_0 = \langle B_0, P_0 \rangle$ representing the union of these local blockchain views, denoted by $\ell_1 \cup \ell_2 \cup \ell_3$ for short, as depicted in Figure 1, and more formally defined as follows:

$$\begin{align*} B_0 &= \cup_{i} B_i, \ P_0 &= \cup_{i} P_i. \end{align*}$$

The point where distinct blocks of the global blockchain DAG have the same predecessor block is called a fork. As an example Figure 1(d) depicts a fork with two branches pointing to the same block: $g$ in this example.

In the remainder of this paper, we refer to the DAG as a tree rooted in $g$ with upward pointers, where children blocks point to their parent block.

  1. Main branch in Bitcoin and Ethereum: To resolve the forks and define a deterministic state agreed upon by all nodes, a blockchain system must select a main branch, as a unique sequence of blocks, based on the tree. Building upon the generic construction (Alg. 1), we present two selections: Nakamoto’s consensus protocol (Alg. 2) present in Bitcoin [23] and the GHOST consensus protocol (Alg. 3) present in Ethereum [32].

a) Nakamoto’s consensus algorithm: The difficulty of the crypto-puzzles used in Bitcoin produces a block every 10 minutes in expectation. The advantage of this long period, is that it is relatively rare for the blockchain to fork because blocks are rarely mined during the time others are propagated to the rest of the nodes.

Algorithm 2 depicts the Bitcoin-specific pseudocode that includes Nakamoto’s consensus protocol to decide on a particular block at index $i$ (lines 8–18) and the choice of parameter $m$ (line 6) explained later in Section II-B. When a fork occurs, Nakamoto’s protocol resolves it by selecting the deepest branch as the main branch (lines 8–15) by iteratively selecting the root of the deepest subtree (line 11). When process $p_i$ is The main difference between Nakamoto’s consensus protocol and GHOST is depicted in Figure 2, where the black blocks represent the main branch selected by Nakamoto’s consensus protocol and the grey blocks represent the main branch selected by GHOST.

Algorithm 2: Nakamoto’s consensus protocol at node $p_i$

  1. $m = 5$, the number of blocks to be appended after the block containing $tx$, for $tx$ to be committed in Bitcoin
  2. $b \leftarrow \text{get-main-branch}(i)$; \hspace{1cm} ▶ select the longest branch
  3. $b \leftarrow \text{genesis-block}(B_i)$; \hspace{1cm} ▶ start from the blockchain root
  4. while $b一件事情的枝はその枝が決定されたと見なされるブロックであり、13個以上の枝を経由する場所ではみられない。ただし、仮想の枝はマイナーが発生する可能性が高いです。

Algorithm 3: The GHOST consensus protocol at node $p_i$

  1. $m = 11$, the number of blocks to be appended after the block containing $tx$, for $tx$ to be committed in Ethereum (since Homestead v1.3.5)
  2. $b \leftarrow \text{get-main-branch}(i)$; \hspace{1cm} ▶ select the branch with the most nodes
  3. $b \leftarrow \text{genesis-block}(B_i)$; \hspace{1cm} ▶ start from the blockchain root
  4. while $b一件事情の枝はその枝が決定されたと見なされるブロックであり、13個以上の枝を経由する場所ではみられない。ただし、仮想の枝はマイナーが発生する可能性が高いです。

B. Decided blocks and committed transactions

A blockchain system $S$ must define when the block at an index is agreed upon. To this end, it has to define a point in its execution where a prefix of the main branch can be “reasonably” considered as persistent. More precisely, there must exist a parameter $m$ provided by $S$ for an application to consider a block as decided and its transactions as committed. This parameter is typically $m_{\text{bitcoin}} = 5$ in Bitcoin (Alg. 2, line 6) and $m_{\text{ethereum}} = 11$ in Ethereum (Alg. 3, line 6).

Definition 1 (Transaction commit). Let $\ell_i = (B_i, P_i’)$ be the blockchain view at node $p_i$ in system $S$. For a transaction $tx$ to be locally committed at $p_i$, the conjunction of the following properties must hold in $p_i$’s view $\ell_i$:

  1. Transaction $tx$ has to be in a block $b_0 \in B_i$ of the main branch of system $S$. Formally, $tx \in b_0 \land b_0 \in B’_i : c_i = (B’_i, P’_i) = \text{get-main-branch}(i)$.
  2. There should be a subsequence of $m$ blocks $b_1, …, b_m$ appended after block $b$. Formally, $\exists b_1, …, b_m \in B_i : \langle b_1, b_0 \rangle, \langle b_2, b_1 \rangle, …, \langle b_m, b_{m-1} \rangle \in P_i$. (In short, we say that $b_0$ is decided.)

A transaction $tx$ is committed if there exists a node $p_i$ such that $tx$ is locally committed.

Property (1) is needed because nodes eventually agree on the main branch that defines the current state of accounts in the system—blocks that are not part of the main branch are ignored. Property (2) is necessary to guarantee that the blocks and transactions currently in the main branch will persist and remain in the main branch. Before these additional blocks are created, nodes may not have reached consensus regarding the unique blocks $b$ at index $j$ in the chain. This is illustrated by the fork of Figure 1 where nodes consider, respectively, the pointer $\langle b_1, g \rangle$ and the pointer $\langle b_2, g \rangle$ in their local blockchain view. By waiting for $m$ blocks were $m$ is given by the blockchain system, the system guarantees with a reasonably high probability that nodes will agree on the same block $b$.

4In theory, there cannot be consensus on a block at a particular index [13], hence preventing persistence, however, applications have successfully used Ethereum to transfer digital assets based on parameter $m_{\text{ethereum}} = 11$ [24].

Algorithm 4 Checking transaction commit at node $p_i$

19: $\text{is-committed}(tx); \triangleright$ check whether transaction is committed 20: $\langle B_i’, P_i’ \rangle \leftarrow \text{get-main-branch}(); \triangleright$ pick main branch with Alg. 2 or 3 21: if $\exists b_0 \in B_i’, tx \in b_0 \wedge \exists b_1, \ldots, b_m \in B_i; \triangleright$ tx in main branch 22: $\langle b_1, b_2, \ldots, b_{m-1} \rangle \in P_i \text{ then } \triangleright$ enough blocks 23: return true 24: else return false

For example, consider a fictive blockchain system with $m_{\text{fictive}} = 2$ that selects the heaviest branch (Alg. 3, lines 8–15) as its main branch. If the blockchain state was the one depicted in Figure 2, then blocks $b_2$ and $b_5$ would be decided and all their transactions would be committed. This is because they are both part of the main branch and they are followed by at least 2 blocks, $b_6$ and $b_{13}$. (Note that we omit the genesis block as it is always considered decided but does not include any transaction.)

III. THE BALANCE ATTACK

In this section, we present the Balance attack, a novel form of attacks that affect proof-of-work blockchains, especially Ethereum. Its novelty lies in identifying subgroups of miners of equivalent mining power and delaying messages between them rather than entering a race to mine blocks faster than others.

The balance attack demonstrates a fundamental limitation of main proof-of-work systems in that they are block oblivious.

Definition 2 (Block Obliviousness). A blockchain system is block oblivious if an attacker can:

  1. make the recipient of a transaction $tx$ observe that $tx$ is committed and
  2. later remove the transaction $tx$ from the main branch, with a probability $1 – \varepsilon$, where $\varepsilon$ is a small constant.

The balance attack is simple: after the attacker introduces a delay between correct subgroups of equivalent mining power, it simply issues transactions in one subgroup. The attacker then mines sufficiently many blocks in another subgroup to ensure with high probability that the subtree of another subgroup outweighs the transaction subgroup’s. Even though the transactions are committed, the attacker can rewrite with high probability the blocks that contain these transactions by outweighing the subtree containing this transaction.

Note that one could benefit from delaying messages only between the merchant and the rest of the network by applying the eclipse attack [17] to Ethereum. Eclipsing one node of Bitcoin appeared, however, sufficiently difficult: it requires to restart the node’s protocol in order to control all the logical neighbors the node will eventually try to connect to. While a Bitcoin node typically connects to 8 logical neighbors, an Ethereum node typically connects to 25 nodes, making the problem even harder. Another option would be to isolate a subgroup of smaller mining power than another subgroup, however, it would make the attack only possible if the recipients of the transactions are located in the subgroup of smaller mining power. Although possible this would limit the generality of the attack, because the attacker would be constrained on the transactions it can override.

Note that the Balance Attack inherently violates the persistence of the main branch prefix and is enough for the attacker to double spend. The attacker has simply to identify the subgroup that contains merchants and create transactions to buy goods from these merchants. After that, it can issue the transactions to this subgroup while propagating its mined blocks to at least one of the other subgroups. Once the merchant shipped goods, the attacker stops delaying messages. Based on the high probability that the tree seen by the merchant is outweighed by another subtree, the attacker could reissue another transaction transferring the exact same coin again.

A. Executing a Balance Attack

For the sake of simplicity, let us fix $k = 2$ and postpone the general analysis for any $k \geq 2$ to Appendix A. We consider subgraphs $G_1 = \langle V_1, E_1 \rangle$ and $G_2 = \langle V_2, E_2 \rangle$ of the communication graph $G = \langle V, E \rangle$ so that each subgraph has half of the mining power of the system as depicted in Figure 3(a) whereas Figure 3(a) illustrates the variant when $k = 4$. Let $E_0 = E \setminus (E_1 \cup E_2)$ be the set of edges that connects nodes of $V_1$ to nodes of $V_2$ in the original graph $G$.

Let $\tau$ be the communication delay introduced by the attacker on the edges of $E_0$.

As indicated in Algorithm 5, the attacker can introduce a sufficiently long delay $\tau$ during which the miners of $G_1$ mine in isolation of the miners of $G_2$ (line 13). As a consequence, different transactions get committed in different series of blocks on the two blockchains locally viewed by the subgraphs $G_1$ and $G_2$. Let $b_2$ be a block present only in the blockchain viewed by $G_2$ but absent from the blockchain viewed by $G_1$. In the meantime, the attacker issues transactions spending coins $C$ in $G_1$ (line 14) and mines a blockchain starting from the Algorithm 5 The Balance Attack initiated by attacker ( p_i )

1: State: 2: ( G = (V, E) ), the communication graph 3: ( \text{pow} ), a mapping from a node in ( V ) to its mining power in ( \mathbb{R} ) 4: ( \ell_i = (B_i, P_i) ), the local blockchain at node ( p_i ) is a directed acyclic graph of blocks ( B_i ) and pointers ( P_i ) 5: ( \rho \in (0; 1) ), the portion of the mining power of the system owned by the attacker ( p_i ), typically ( \rho < 0.5 ) 6: ( d ), the difficulty of the crypto-puzzle currently used by the system 7: ( \text{balance-attack}((V, E)), \quad \text{starts the attack} ) 8: Select ( k \geq 2 ) subgraphs ( G_1 = (V_1, E_1), …, G_k = (V_k, E_k) ): 9: [ \sum_{v \in V_i} \text{pow}(v) \approx \sum_{v’ \in V_i} \text{pow}(v’) ] 10: [ \text{Let } E_0 = E \setminus \bigcup_{0 < i < k} E_i \quad \text{attack communication channels} ] 11: Stop communications on ( E_0 ) during ( \tau \geq \frac{(1 – \rho)6d \log(\frac{4}{\epsilon})}{4d^2} ) seconds 12: Issue transaction ( tx ) crediting a merchant in graph ( G_i ) with coins ( C ) 13: Let ( b_2 ) be a block appearing in ( G_j ) but not in ( G_i ) 14: Start mining on ( \ell_i ) immediately after ( b_2 ) ( \text{contributed to correct chain} ) 15: Send blockchain view ( \ell_i ) to some subgraph ( G_j ) where ( j \neq i ) 16: When ( \tau ) seconds have elapsed, stop delaying communications on ( E_0 ) 17: Issue transaction ( tx’ ) that double spends coins ( C )

Before the delay expires the attacker sends his blockchain to ( G_2 ). After the delay expires, the two local views of the blockchain are exchanged. Once the heaviest branch that the attacker contributed to is adopted, the attacker can simply reuse the coins ( C ) in new transactions (line 19).

B. The knowledge about the network

As indicated by the state of Algorithm 5, an attacker has to be knowledgeable about the current settings of the blockchain system to execute a Balance attack. In fact, the attacker must have information regarding the logical or physical communication graph, the mining power of the miners or pools of miners and the current difficulty of the crypto-puzzle. In particular, this information is needed to delay messages for long enough between selected communication subgraphs. As we will show in the next section, this delay can be overestimated, however, underestimating it may make the attack impossible.

The information regarding the mining power and the difficulty of nodes is generally public information and can often be retrieved online. In particular, we got provided an access to the R3 Ethereum network statistics http://r3n1-utils.gcl.r3cev.com/ that included block propagation delays, the list of connected nodes and their individual mining power, the version of their Ethereum client as well as the current difficulty of the crypto-puzzle. The same statistical information regarding the Ethereum public chain is publicly available online at https://ethstats.net/.

It is more difficult, however, to gather information regarding the communication network. Note that some tools exist to retrieve information regarding the communication topology of blockchain systems. The interesting aspects of the Balance attack is that it can apply to the logical overlay used by the peer-to-peer network of the blockchain system or to the physical overlay. While there exist tools to retrieve the logical overlay topology, like AddressProbe [21] to find some information regarding the peer-to-peer overlay of Bitcoin, it can be easier for an attacker of Ethereum to run a DNS poisoning or a denial-of-service attack rather than a BGP hijacking [19], [1] that requires access to autonomous systems.

IV. VULNERABILITY OF THE HOST Protocol

In this Section, we show that the Balance attack makes a blockchain system based on HOST (depicted in Alg. 3) block oblivious. A malicious user can issue a Balance attack with less than half of the mining power by delaying the network. Let us first summarize previous and new notations in Table I.

NotationDescription
( t )total mining power of the system (in million hashes per second, MH/s)
( d )difficulty of the crypto-puzzle (in million hashes, MH)
( \rho )fraction of the mining power owned by the malicious miner (in percent, %)
( k )number of communication subgraphs
( \tau )time during which communication between subgraphs is disrupted (in seconds, s)
( \mu_c )mean of the number of blocks mined by each communication subgraph during ( \tau )
( \Delta )the maximum difference of mined blocks for the two subgraphs

For the sake of simplicity in the proof, we assume that ( k = 2 ) and ( \sum_{v \in V_i} \text{pow}(v) = \sum_{v’ \in V_i} \text{pow}(v’) ) so that the communication is delayed between only two communication subgraphs of equal mining power. We defer the proof for the general case where ( k \geq 2 ) to Appendix A.

As there is no better strategy for solving the crypto-puzzles than random trials, we consider that subgraphs ( G_1 ) and ( G_2 ) mine blocks during delay ( \tau ). During that time, each of ( G_1 ) and ( G_2 ) performs a series of ( n = \frac{1 – \rho}{\epsilon} t \tau ) independent and identically distributed Bernoulli trials that returns one in case of success with probability ( p = \frac{1}{2} ) and 0 otherwise. Let the sum of these outcomes for subgraphs ( G_1 ) and ( G_2 ) be the random variables ( X_1 ) and ( X_2 ), respectively, each with a binomial distribution and mean:

[ \mu_c = np = \frac{(1 – \rho)t \tau}{2d}. \tag{1} ]

Similarly, the mean of the number of blocks mined by the malicious miner during time ( \tau ) is

[ \mu_m = \frac{\rho t \tau}{d}. \tag{2} ]

From line 13 of Alg. 5, we know that ( \tau \geq \frac{(1 – \rho)6d \log(\frac{4}{\epsilon})}{4d^2} ) which leads to:

[ \frac{(1 – \rho)t \tau}{2d} \geq \frac{3(1 – \rho)^2 \log(\frac{4}{\epsilon})}{4d^2}. \tag{3} ]

By Eq. 4 we have:

[ \begin{align*} \mu_c & \geq \frac{3(1 – \rho)^2 \log (\frac{4}{\varepsilon})}{4 \rho^2}, \ \frac{4 \rho_c^2 \mu_c}{3(1 – \rho)^2} & \geq \log (\frac{4}{\varepsilon}), \ e^{-\frac{4 \rho_c^2 \mu_c}{3(1 – \rho)^2}} & \leq \frac{\varepsilon}{4}, \ 1 – 4e^{-\frac{\rho_c^2 \mu_c}{3(1 – \rho)^2}} & \geq 1 – \varepsilon. \end{align*} ]

(2)

The attack relies on minimizing the difference in mined blocks between any pair of communication subgraphs.

Lemma 3. After the communication is re-enabled, the expectation of the number of blocks mined by the attacker is greater than the difference (\Delta = |X_1 – X_2|) of the number of blocks mined on the two subgraphs (G_1) and (G_2), with probability (1 – \varepsilon).

Proof: The communication is re-enabled at line 18 of Alg. 5. At this point in the execution, the probability that the numbers of blocks mined by each subgraph are within a (\pm \delta) factor from their mean, is bound for (0 < \delta < 1) and (i \in {1, 2}) by Chernoff bounds [22]:

[ \begin{align*} \Pr[|X_i – (1 + \delta)\mu_c| < \delta \mu_c] & \leq e^{-\frac{\delta^2 \mu_c}{4}}, \ \Pr[|X_i – (1 – \delta)\mu_c| < -\delta \mu_c] & \leq e^{-\frac{\delta^2 \mu_c}{4}}. \end{align*} ]

Thus, we have

[ \Pr[|X_i – \mu_c| < \delta \mu_c] > 1 – 2e^{-\frac{\delta^2 \mu_c}{4}}. ]

Observe that the probability that these two random variables are both within a (\pm \delta \mu_c) is lower than the probability that their difference (\Delta) is upper-bounded by (2\delta \mu_c):

[ (\Pr[|X_i – \mu_c| < \delta \mu_c])^2 \leq \Pr[\Delta < 2\delta \mu_c]. ]

Thus, we obtain:

[ \Pr[\Delta < 2\delta \mu_c] > \left(1 – 2e^{-\frac{\delta^2 \mu_c}{4}}\right)^2. ]

As (\mu_c \geq 0), we have that:

[ \begin{align*} -\frac{\delta^2 \mu_c}{3} & \leq 0, \ -e^{-\frac{\delta^2 \mu_c}{4}} & \geq -1, \end{align*} ]

and we can apply the Bernoulli inequality to Eq. 3:

[ \Pr[\Delta < 2\delta \mu_c] > 1 – 4e^{-\frac{\delta^2 \mu_c}{4}}. ]

If we replace (\delta) by (\frac{2\varepsilon}{1 – \rho}), we obtain:

[ \Pr[\Delta < \mu_m] > 1 – 4e^{-\frac{4 \mu_m}{(1 – \rho)^2}}. ]

By Eq. 2, we can see that the expectation of the number of blocks mined by the attacker is strictly greater than (\Delta) with high probability:

[ \Pr[\Delta < \mu_m] > 1 – \varepsilon. ]

Theorem 4. A blockchain system that selects a main branch based on the GHOST protocol (Alg. 3) is block oblivious.

Proof: By lines 17–18 of Alg. 3, we know that GHOST counts every mined blocks to compute the weight of a subtree, and to select one blockchain view and discard the other.

Since the expected number of blocks mined by the attacker is greater than the difference (\Delta) with probability (1 – \varepsilon), we know that when the timer expires at line 18 of Alg. 5, the attacker will make the system discard the blockchain view of either (G_1) or (G_2) by sending its blockchain view to the other subgraph, hence making the blockchain system block oblivious.

V. ANALYSIS OF THE R3 TESTBED

The statistics of the R3 testbed were gathered through the eth-netstat applications at the end of June 2016. As depicted in Figure 4, the network consisted at that time of (|V| = 50) nodes among which only 15 were mining. The mining power of the system was about (20) MH/s and the most powerful miner mines at (2.4) MH/s or (12%) of the total mining power while the difficulty of the crypto-puzzle was observed close to (30) MH.

We assume that the attacker selects communication edges (E_0) between two subgraphs (G_1) and (G_2) so that their mining power is (8.8) MH/s each. The probability (p) of solving the crypto-puzzle per hash tested is (\frac{1}{20\times10^9}) so that the mean is

5http://r3n1-utils.gcl.r3cev.com/. 6http://www.coindesk.com/r3-ethereum-report-banks

TABLE II: The R3 settings used in the analysis

Number of nodes50
Number of miners15
Total mining power (MH/s)20
Mining power of the most powerful miner (MH/s)2.4
Difficulty (MH)30

[ \mu_c = np = 95.3 ] if we wait for 19 minutes and 40 seconds. The attacker creates, in expectation, a block every ( \frac{30}{2.4} = 12.5 ) seconds or ( \lfloor \frac{1180}{12.5} \rfloor = 94 ) blocks during the 19 minutes and 40 seconds. Hence let us select ( \delta ) such that the attacker has a chance to mine more than ( 2\delta \mu_c ) blocks during that period, i.e., ( 94 = 2\delta \mu_c + 1 ) implying that ( \delta = 0.1343 ). The probability of the difference exceeding 94 is upper bounded by ( 4e^{-\frac{\delta^2}{2}\mu_c} ) leading to a bound of 49.86%.

To conclude a single miner of the R3 testbed needs to delay edges of ( E_0 ) during less than 20 minutes to execute a Balance attack and discards blocks that were previously decided (even if ( m = 18 ) was chosen) with a chance of success greater than ( \frac{1}{2} ).

A. Tradeoff between communication delays and mining power

Malicious nodes may have an incentive to form a coalition in order to exploit the Balance attack to double spend. In this case, it is easier for the malicious nodes to control a larger portion of the mining power of the system, hence such a coalition would not need to delay messages as long as in our example of Section V. For simplicity, we again consider the case where the attacker delay messages between ( k = 2 ) communication subgraphs.

To illustrate the tradeoff between communication delay and the portion of the mining power controlled by the attacker, we consider the R3 testbed with a 30 MH total difficulty, a 20 MH/s total mining power and plot the probability as the communication delay increases for different portions of the mining power controlled by the adversary. Figure 5 depicts this result. As expected, the probability increases exponentially fast as the delay increases, and the higher the portion of the mining power is controlled by the adversary the faster the probability increases. In particular, in order to issue a balance attack with 90% probability, 51 minutes are needed for an adversary controlling 12% of the total mining power whereas only 11 minutes are sufficient for an adversary who controls 20% of the mining power.

B. Tradeoff between communication delays and difficulties

Another interesting aspect of proof-of-work blockchain is the difficulty parameter ( d ). As already mentioned, this parameter impacts the expected time it takes for a miner to succeed in solving the crypto-puzzle. When setting up a private chain, one has to choose a difficulty to make sure the miners would mine at a desirable pace. A too high difficulty reduces the throughput of the system without requiring leader election [10] or consensus sharding [20]. A too low difficulty increases the probability for two correct miners to solve the crypto-puzzle before one can propagate the block to the other, a problem of Bitcoin that motivated the GHOST protocol [29].

Figure 6 depicts the probability of the Blockchain anomaly when the communication delay increases for different difficulties without considering the time for a block to be decided. Again, we consider the R3 Ethereum network with a total mining power of 30 MH/s and an attacker owning ( \rho = 12% ) of this mining power and delaying communications between ( k = 2 ) subgraphs of half of the remaining mining power ( \left( 1 – \frac{\rho}{2} = 44% \right) ) each. The curve labelled 4 KH indicates a difficulty of 4000 hashes, which is also the difficulty chosen by default by Ethereum when setting up a new private chain system. This difficulty is dynamically adjusted by Ethereum at runtime to keep the mining block duration constant in.

expectation, however, this adaptation is dependent on the visible mining power of the system. The curve labelled 30 MH indicates the probability for the difficulty observed in the R3 Ethereum network. We can clearly see that the difficulty impacts the probability of the Balance attack. This can be explained by the fact that the deviation of the random variables $X_1, …, X_k$ from their mean $\mu_c$ is bounded for sufficiently large number of mined blocks.

VI. EXPERIMENTING THE BALANCE ATTACK ON AN ETHEREUM PRIVATE CHAIN

In this section, we experimentally produce the attack on an Ethereum private chain involving up to 18 physical distributed machines. To this end, we configure a realistic network with 15 machines dedicated to mining as in the R3 Ethereum network we described in Section V and 3 dedicated network switches.

All experiments were run on 18 physical machines of the Emulab environment where a network topology was configured using ns/2 as depicted in Figure 7. The topology consists of three local area networks configured through a ns/2 configuration file with 20 ms latency and 100 Mbps bandwidth. All miners run the geth Ethereum client v.1.3.6 and the initial difficulty of the crypto-puzzle is set to 40 KH. The communication graph comprises the subgraph $G_1$ of 8 miners that includes the attacker and 7 correct miners and a subgraph $G_2$ of 7 correct miners.

A. Favoring one blockchain view over another

We run our first experiment during 2 minutes. We delayed the link $E_0$ during 60 seconds so that both subgraphs mine in isolation from each other during that time and end up with distinct blockchain views. After the delay we take a snapshot, at time $t_1$, of the blocks mined by each subgraphs and the two subgraphs start exchanging information normally leading to a consensus regarding the current state of the blockchain. At the end of the experiment, after 2 minutes we take another snapshot $t_2$ of the blocks mined by each subgraph.

Table III lists the prefix of the hashes of blocks (excluding uncles) of the blockchain views of $G_1$ and $G_2$ at times $t_1$, while the two subgraphs did not exchange their view, and at time $t_2$, after the subgraphs exchanged their blocks. Note that we did not represent the uncle blocks to focus on the main branches. We observe that the blockchain view of the subgraph $G_1$ was adopted as the valid chain while the other blockchain view of the subgraph $G_2$ was not. For example, one of the listed blocks viewed by $G_1$ at time $t_1$ whose hash starts with $0xfab2$ appears as well in the final blockchain at time $t_2$. More generally, we can see that only blocks of the blockchain view of $G_1$ at time $t_1$ were finally adopted at time $t_2$ as part of the blocks of the global view of the blockchain. All the blocks of $G_2$ at time $t_1$ were discarded from the blockchain by time $t_2$.

B. Blocks mined by an attacker and two subgraphs

We now report the total number of blocks mined, especially focusing on the creation of uncle blocks. More precisely, we compare the number of blocks mined by the attacker against the difference of the number of blocks $\Delta$ mined by each subgraph. We know from the analysis that it is sufficient for…

the attacker to mine at least $\Delta + 1$ blocks in order to be able to discard one of the $k$ blockchain views, allowing for double spending. The experiment is similar to the previous experiment in that we also used Emulab with the same ns/2 topology, however, we did not introduce delays and averaged results over 10 runs of 4 minutes each.

Figure 8 depicts the minimum, maximum and average blocks obtained over the 10 runs. The vertical bars indicate minimum and maximum. First, we can observe that the average difference $\Delta$ is usually close to its minimum value observed during the 10 runs. This is due to having a similar total number of blocks mined by each subgraph in most cases with few rare cases where the difference is larger. As we can see, the total number of blocks (including uncles) mined during the experiment by the attacker is way larger than the difference in blocks $\Delta$ mined by the two subgraphs. This explains the success of the Balance attack as was observed in Section VI-A.

C. The role of uncle blocks in Ethereum

In the previous experiment, we focused on the total number of blocks without differentiating the blocks that are adopted in the main branch and the uncle blocks that are only part of the local blockchain views. The GHOST protocol accounts for these uncle blocks to decide the current state of the blockchain as we explained previously in Section II.

Figure 9 indicates the number of uncle blocks in comparison to the blocks accepted on the current state of the blockchain for subgraphs $G_1$ and $G_2$, and the attacker (referred to as ‘Malicious’). As expected, we can observe that the malicious node does not produce any uncle block because he mines the block in isolation of the rest of the network, successfully appending each mined block consecutively to the latest block of its current blockchain view. We note several uncle blocks in the subgraphs, as correct miners may mine blocks concurrently at the same indices.

Figure 10 depicts the creation of the number of mined blocks (excluding uncle blocks) over time for subgraphs $G_1$ and $G_2$, and the attacker (referred to as ‘Malicious’). As we can see the difference between the number of blocks mined on the subgraphs is significantly smaller than the number of blocks mined by the attacker. This explains why the Balance attack was observed in this setting.

D. Relating connectivity to known blocks

Figure 11 illustrates the execution of two subgraphs resolving connectivity issues and adopting a chain. This experiment outlines one of the fundamental aspects of the balance attack, in which the chosen subgraph resolves the network delay and attempts reconnection with another subgraph.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO