A Deep Understanding of the Double-Spending Problem in Bitcoin
In the blockchain world, the double-spending problem is not something that can be overlooked. Last month, a malicious miner executed a double-spending attack on the Bitcoin Gold network (BTG), whose digital currency Bitcoin Gold (BTG) is the world’s 26th most valuable cryptocurrency. The miner acquired at least 51 percent of the network’s total hashpower, which provided them with temporary control of the blockchain. Then they deposited BTG on exchanges, withdrew those same crypto coins, and reversed the initial transactions.
The attacker was estimated to steal over 388,200 BTG, or $18.6 million.
Under such circumstances, the blockchain industry needs to understand the double-spending problem in Bitcoin profoundly. DxChain has a deep understanding of this problem. Here is our analysis:
The bitcoin white paper “Bitcoin: A Peer-to-Peer Electronic Cash System” marked the beginning of cryptocurrencies. This paper described the system infrastructure of Bitcoin network extensively from a technical point of view. Many fundamental concepts in the paper, such as transactions, incentive mechanism, and Merkle tree were then adopted by following cryptocurrency systems.
The Bitcoin system is designed to prevent double-spending in a decentralized environment where there is no trusted third party to mediate disputes.
First, let’s figure out what the double-spending problem is. If a crypto coin is used for twice or more times, we call it double-spending. In the real world, we use fiat money — US dollar, Chinese yuan, and Euro — to make an exchange. When we pay someone with $100 in cash, for example, we cannot spend the same $100 somewhere else to make another purchase. And when we use a credit card for the payment, all transactions are recorded in a centralized database by the credit card company.
However, as Bitcoin is neither physical cash nor traded within a centralized database, it raises challenges on preventing the double-spending issue in a Bitcoin system.
Ledger and account are two critical concepts in Bitcoin system. Ledger records how much money each account still has.
Imagine you pay someone with Bitcoins. This transaction will be sent to the whole peer-to-peer network and be recorded in the ledger as a type of verification process, which takes time. That means you might be able to send another payment using the same Bitcoin token you spent in the first transaction. This operation results in one Bitcoin being paid twice. Therefore, you have no ways but wait to confirm the validity of a deal.
Although the Bitcoin white paper gives a mathematical proof, it only results in a simple conclusion. This article will provide you with a more detailed explanation.
The Bitcoin ledger is technically an implementation of the blockchain. As such, a blockchain is also regarded as a distributed ledger. Bitcoin nodes are distributed around the world so different nodes will receive transactions at a different time, generating a variety of blockchains in the system. Bitcoin protocol always selects the longest chain.
In the double-spending problem, payees will wait for a while (the block where its transaction located is very deep in the longest chain) to confirm the validity of the transaction. But how long will the payee have to wait (how deep the block containing its transaction is in a chain) to ensure the security?
Let’s start the proof.
Let’s explain the double-spending problem more technically. When a transaction is recorded in the blockchain, after z blocks appended in the blockchain, attackers start to re-generate a new blockchain. If the new blockchain works faster than the existing one, attackers will get back the coins they spent earlier because Bitcoin protocol will always select the longest chain.
If we describe this problem in a mathematical language: An honest chain is z blocks faster than an attack chain. If the honest chain produces a new block in the next moment, the distance of 2 chains is +1. If the attack chain produces a new block, the distance of 2 chains is -1. The problem is whether the attack chain can catch up with the honest chain.
The Bitcoin white paper gave the following definitions:
We add all the equations in this series together. Then we will get,
We add the first z-1 equations in this series. Similar to the above, we will get the following results,
According to the equations, we discover that if the probability of an honest node finding a block is less or equal than the probability of an attacker node finding a block, the attacker will catch up the honest chain. Otherwise, the probability of the attacker catching up is decreasing exponentially.
The above conclusion is based on two assumptions: 1) we explicitly knew p and q, 2) the attacker starts to generate new block after the honest chain generating Z blocks. Let’s apart from these assumptions. When the attacker sends out a transaction, they(he/she=they) start to generate attacking blocks. After the honest chain generates z blocks, the progress of the attacker chain is k, and the gap between these two chains is z-k. The expectation of k is:
k is represented with Poisson distribution. Under this more realistic scenario, the probability of the attacker catching up is
When q = 0.1, p = 0.9 and z = 6, the probability of the attacker catching up is 0.0002. In the real Bitcoin network, p is much bigger than q. In general, after a payee waited for z=6 blocks, it is very difficult for attackers to double-spend what they paid earlier.
This article explains how the Bitcoin system prevents double-spending problems from mathematical theory. This conclusion lays the theoretical foundation of Proof of Work(PoW) and a good foundation for the future Proof of Stake (PoS) theory. DxChain is standing on the shoulders of giants to develop more useful and efficient system.