The Double-Spending Attack

Blockchain technology was invented as a solution to the double-spending problem. Before the invention, it was impossible to avoid double-spending on an electronic currency token without the supervision of a central authority. As a consequence, the fundamental attack against the integrity of blockchain systems is the double-spending attack, in which an adversary attempts to use some of the coins for two or more payments.

The double-spending problem

Any digital currency consists of tokens that are composed of a respective digital file that can easily be duplicated. As a direct consequence of the easiness to falsify digital tokens, a double-spending is a potential vulnerability to the integrity of a digital cash scheme and thus a weakness of any digital currency in which the same single digital token can be spent more than once. Previously, the double-spending problem was addressed by clearing all transactions through a trusted third party, such as a financial institution, in order to validate, safeguard and preserve transactions (Michael Crosby et al. (2018)Michael Crosby, Nachiappan, Pradan Pattanayak, Sanjeev Verma, and Vignesh Kalyanaraman. Blockchain technology: Beyond bitcoin. http://scet.berkeley.edu/ wp-content/uploads/AIR-2016-Blockchain.pdf, 2016. Accessed: 2018-07-02.).

Double-spending problem

The double-spending problem is the situation where a user signs two conflicting transactions with the intent to spend the same digital token twice.

Thus, there is a need to ensure that the payee has knowledge that the previous owners of a token didn’t sign any earlier transactions in order to spend the token on another party. Nakamoto (2008) proposed the first solution to solve the double-spending problem through his consensus model (see this lesson) and thus to avoid the need for a trusted third party, whereas the blockchain network offers a public transaction history. The distributed consensus about the order of transactions is reached by synchronizing the whole network by broadcasting a block of verified transactions, which enables the reflection of the common transaction history. From this point of view, the blockchain solves the problem of potential double-spending.

Confirmation security

As soon as a user signs a transaction and broadcasts it to the network, every node collects it to its unconfirmed transaction’s memory pool. As long as a transaction is not included in a block of the authoritative chain, it’s called unconfirmed. But this doesn’t necessarily mean that the recipient has no knowledge about the transaction. The fund may already be added to his wallet as soon as the unconfirmed transaction appears in his own memory pool, as some cryptocurrency wallets take unconfirmed transactions for granted a bit too quickly. These kinds of transactions are called zero-confirmation transactions.

Confirmation

A transaction is called confirmed as soon as it is successfully included in a block of the authoritative chain. Whenever a new subsequent block is added to the chain, the transaction gets reconfirmed.

Bashir (2017)Imran Bashir. Mastering Blockchain. Packt Publishing, Limited, 2017. shows the following steps in a confirmation process:

Confirmation process

A confirmation process has the following steps:

1. A node starts a transaction by signing the transaction with its private key.

2. The transaction is broadcasted to the network by using a flooding algorithm. Every node validates the transaction independently. Afterward, a node will add it to the memory or transaction pool, whereby the transactions in the memory pool are unconfirmed and ready to be recorded in a new block (Andreas M. Antonopoulos (2014)Andreas M. Antonopoulos. Mastering Bitcoin: Unlocking Digital Cryptocurrencies. Sebastopol, CA, 2014. O’Reilly Media.). Note that the benefited party may already see the coins in her wallet at this point if the wallet software allows zero-confirmation transactions!

3. If the transaction was aggregated into a candidate block and a miner solves the PoW, the block is propagated to the network. At this point, the transaction is considered confirmed.

4. The new block is now part of the ledger and the next block will link itself cryptographically back to this block. At this stage, the transaction gets its second confirmation at the block itself gets its first.

5. Transactions are then reconfirmed every time a new block is created and appended to the blockchain.

Note that steps 4 and 5 are non-compulsory. The transaction itself is finalized in step 3. However, zero-confirmation transactions are highly insecure. Karame et al. (2016)Ghassan O. Karame and Elli Androulaki. Bitcoin and Blockchain Security: Artech House information security and privacy series. Norwood, MA, 2016. Artech House Publishers. have shown that double-spending attacks are easily realizable on zero-confirmation transactions with high probability. Thus, a vendor who accepts unconfirmed transactions is highly vulnerable to a double-spend. To defend himself against this attack, a vendor should wait for the transaction to be included in at least one block (Fabin Schär et al. (2017)Fabin Schär and Aleksander Berentsen. Bitcoin, Blockchain und Kryptoassets: Eine umfassende Einführung. Norderstedt, Germany, 2017. Books on Demand.). Since blocks implement a Proof-of-Work, transactions that are included in a block are hard to revert.

Every further confirmation secures the transaction more, because if any node wants to modify a transaction, it doesn’t only have to redo all the work required to compute the block where the transaction was included, but it has also to recompute all the subsequent blocks in the chain. Thus, the deeper a transaction is included in the blockchain, the harder it becomes to modify the transaction and therefore the higher its security. We’ll show in this section that waiting for more confirmations exponentially decreases the probability of a double-spending attack, i.e., the probability of success decreases exponentially with the number of confirmations.

Transaction commitment

As shown in this lesson, the blockchain algorithm implements the so-called longest-chain-criterion, meaning that the network adopts the blockchain data structure that represents the most aggregated computational effort as an authoritative chain. This leads to the most important transaction security theorem of a PoW-based blockchain system:

Theorem 1: transaction commitment

A PoW-based blockchain never commits a transaction definitively. Every transaction can be invalidated if a longer chain that started below the block including the transaction is created (Christian Decker et al. (2016)Christian Decker, Jochen Seidel, and Roger Wattenhofer. Bitcoin meets strong consistency. In Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN '16, pages 13:1-10, New York, NY, USA, 2016. ACM.).

Proof: The proof follows from this theorem :Theorem_Probability_success_attackers in this section.

Note: It’s important to realize that an attacker only has very limited opportunities during an attack. He can’t alter (i.e., they can’t modify the amount or the recipient of arbitrary transactions in the blockchain or generate unwanted transactions of other users since these are protected by their signature and hence by their private key. Thus, an attacker can only perform a double-spend on those funds they have control over.

As stated by Decker et al. (2016)Christian Decker, Jochen Seidel, and Roger Wattenhofer. Bitcoin meets strong consistency. In Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN '16, pages 13:1-10, New York, NY, USA, 2016. ACM., “the existence of blockchain forks is the very reason that transactions are never definitively committed.” Hence, a blockchain fork is a potential vulnerability of the blockchain algorithm, since an adversary could take advantage of the blockchain fork in order to perform a double-spending attack and thus revert its own transactions. During this state, they could try to include a transaction in one chain, and a conflicting transaction in the forked chain. Since only one version of the blockchain will finally prevail, the transaction that is part of the authoritative chain will be valid, while the transaction in the orphaned block will be void.