Secure High-Rate Transaction Processing in Bitcoin

Bitcoin is a disruptive new crypto-currency based on a decentralized open-source protocol which has been gradually gaining momentum. Perhaps the most important question that will affect Bitcoin’s success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system. We investigate the implications of having a higher transaction throughput on Bitcoin’s security against double-spend attacks. We show that at high throughput, substantially weaker attackers are able to reverse payments they have made, even well after they were considered accepted by recipients. We address this security concern through the GHOST rule, a modification to the way Bitcoin nodes construct and re-organize the block chain, Bitcoin’s core distributed data-structure. GHOST has been adopted and a variant of it has been implemented as part of the Ethereum project, a second generation distributed applications platform.

1. 1.

   Hash collisions are so rare that this hash can be regarded as a unique identifier of the block.

2. 2.

   Merely being included in a block is not sufficient to fully guarantee the irreversibility of a transaction. Transactions become increasingly less likely to be reversed as more blocks are added on top of them to the chain.

3. 3.

   The 50 % attack owes its name to Satoshi’s result showing that the main chain is secure (after sufficient waiting periods) as long as the attacker holds less than 50 % of the computational power. We show in this paper that in fact networks with delays are more vulnerable and can be attacked with less computational power.

4. 4.

   This essentially assumes that all computational assets held by the attacker are centralized and that blocks that it creates are transmitted instantly in its internal network.

5. 5.

   See Theorem 54, Chap. 2 in [17] for the compatibility of these two interpretations of \(\beta \).

6. 6.

   We are in fact interested in the subtree with the hardest combined proof-of-work, but for the sake of conciseness, we write the size of the subtree instead.

7. 7.

   Previous work, such as [12, 16], considered simpler policies that did not take elapsed time into account.

The authors were supported in part by the Israel Science Foundation (Grants 616/13, and 1773/13), and by the Israel Smart Grid (ISG) Consortium.

Authors and Affiliations

1. School of Engineering and Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel

   Yonatan Sompolinsky & Aviv Zohar

2. Microsoft Research, Herzliya, Israel

   Aviv Zohar

Corresponding author

Correspondence to Yonatan Sompolinsky .

Editors and Affiliations

1. University of Innsbruck, Innsbruck, Austria

   Rainer Böhme

2. NTT Laboratories, Tokyo, Japan

   Tatsuaki Okamoto

A Where Is the Attacker in Longest Chain?

From a practical perspective, we must remember that a node listening to the Bitcoin network does not really know the amount of computational power the honest nodes in the network possess. In particular, the attacker may be building blocks along with the network up until the time of the attack, or he may not. Therefore, all that is observed is some amount of computational power which triggers the reported block creation rate \(\lambda _{rep}\). We now ask ourselves what is the worst case when using the longest-chain rule? An attacker who participates or one that does not? Also, what is the right security threshold in terms of \(\lambda _{rep}\) (rather than \(\lambda _h\) which is unknown)?

We begin with the assumption that the attacker has a fraction q of the computational power of the honest network. Denote by \(\lambda _a,\lambda _h\) the block creation rate of the attacker and the honest nodes respectively, and by \(\lambda = \lambda _a+\lambda _h\) their joint rate. Our assumption is \(\lambda _a = q \lambda _h\) as before. \(\lambda _{rep}\) is the observed rate of block creation in the system (before the attack), which is in the range \([ \lambda _h, \lambda _h+\lambda _a ]\). The following proposition shows that for a given threshold q it is enough to use \(\lambda _{rep}\) as a measure of the honest network’s creation rate, as the attacker would only make it harder on itself if it joined the rest of the network and generated blocks before the attack. This is quite counter-intuitive, as the attacker that adds to the rate before the attack fools the network into thinking it is stronger. In reality, it increases the number of its blocks but lowers the network’s efficiency, which is the true measure of resilience to attacks.

Proposition 11

If the network’s observed block rate is \(\lambda _{rep}\), for a given block size, and \(\beta (\lambda _{rep}) \ge q \lambda _{rep}\), then the network is secure against an attacker with computational power lower than \(q\lambda _h\). Furthermore, an attacker is most effective if it does not participate in block mining before the attack.

Proof

If a fraction f of the attacker’s blocks were included in \(\lambda _{rep}\) prior to the attack, then \(\lambda _{rep} = \lambda _{h} + f\cdot \lambda _{a}.\) I.e., \(\lambda _{h} = \lambda _{rep} - f \cdot \lambda _{a} = \lambda _{rep} - f q \lambda _h\). This implies that \(\lambda _h = \frac{\lambda _{rep}}{1+f \cdot q}\). Hence,

meaning that the longest chain of the honest network alone outgrows the block creation rate of the attacker, and thus gives resilience to attacks after some time. In the above, inequality 1 follows from \(\beta \)’s monotonicity, 2 follows from the proposition’s assumption, 3 from the fact that \(\lambda _{rep}\) includes the honest network’s rate, and 4 from the initial assumption on the attacker’s block creation rate.

The attacker’s chain thus grows slower than the longest chain in the honest network’s tree.

The lower f is, the tighter the first inequality, and the smaller the gap between the rate of network and that of the attacker — making the attack easier to carry out. Therefore, an attacker is most effective when \(f=0\).    \(\square \)

B Proof of Lemma 5

Lemma 5 :

Let G=(V,E) be a network graph (a sub-graph of the entire network) which generates blocks at a rate \(\lambda ' = \alpha \cdot \lambda \) with delay diameter D . Then under the longest-chain rule, the rate at which the longest chain grows \(\beta (\lambda ) \ge \frac{\lambda '}{1+\lambda ' \cdot D}\) .

Proof

We follow a sequence of block creation events for blocks \(U_0, U_1,U_2, \ldots \) such that each block \(U_{i+1}\) is the first block to be created after D seconds have passed from the creation of the previous block \(U_i\) (so that there has been sufficient time to send \(U_i\) to all nodes in the network), i.e., the first block B for which \(time(B)-D > time(U_{i})\). Let us now make the following claim.

Claim 12

Let \(U_0,U_1,U_2,\ldots \) be a series of blocks that were created at least D time units apart. Then for all \(n\in \mathbb {N}\): \(Depth(U_n)-Depth(U_0) \ge n\).

The claim can be proven by induction, and we defer its proof to the online full version.

Denote by \(X_i = time(U_i)- time(U_{i-1})\) the random variable representing the time between block creations. Notice that the \(X_i\)’s are i.i.d. random variables (because the time interval they denote is exactly D time units for the block to spread plus an exponentially distributed waiting time for the next block’s creation somewhere in the network). Also note that \(\beta \ge E[\frac{1}{n} \sum _{i=1}^n X_i]^{-1}\), as the chain grows by at least n during the time \(\sum _{i=1}^n X_i\). We therefore have \(\beta \ge \frac{1}{E[X_1]}\). Additionally, we know that \(E[X_1] = D+ E[Y]\), where Y is a random variable with an exponential distribution with parameter \(\lambda '\). As \(E[Y] = \frac{1}{\lambda '}\) we have: \(\beta \ge \frac{1}{D+\frac{1}{\lambda '}} = \frac{\lambda '}{1+ \lambda '\cdot D}\).    \(\square \)

C Proof of Claim 7

Claim 7 :

Let B be a block in tree T in a network as in Lemma 6 , then regardless of history, the expected waiting time for the creation of the last child of B is upper bounded by \(2D+\frac{1}{\lambda '}\) .

Proof

Let C be the first block created after D seconds have passed from B’s creation. Denote by \(\tau \) the time from B’s creation until C has been created and yet another D seconds elapsed. We argue that \(E[\tau ] \le 2D+1/\lambda '\). This is easy to see: It takes \(1/\lambda '\) seconds in expectation to create block C, an event which can only occur after D seconds have passed from B’s creation. Then, we deterministically wait another D seconds to propagate C to the entire network.

We claim that after \(\tau \) seconds from B’s creation, B will have no more children. Let us examine the two possible cases:

Case I: C is a descendant of B. Once C has been propagated to all nodes, no node considers B a leaf, and the GHOST chain selection rule only extends leaves (in the subtree known to the extending node).

Case II: C is not a descendant of B. Because B was propagated to all nodes before C was created, the node that extended C was well aware of B, but did not extend it. It therefore had a strictly heavier subtree than B is part of after the creation of C. D seconds later, block C is known to all other nodes, along with its entire supporting subtree. In this case, B will not be extended directly either – nodes have switched away from B if no other children extend it, or have switched to its descendants if it does have children.    \(\square \)

Reprints and permissions

© 2015 Springer-Verlag Berlin Heidelberg

Policies and ethics