Satoshi Nakamoto’s math doesn’t quite add up.
In chapter 11 of the Bitcoin white paper, the pseudonymous author explained that an honest mining majority will always outrun a dishonest minority. As a key innovation in digital currency, this ensures transactions are practically irreversible once they have sufficient confirmations, effectively solving the double-spend problem.
However, as first explained by Israeli mathematician Meni Rosenfeld back in 2012, Satoshi made some simplified assumptions. While Bitcoin mining is a random process, Satoshi did not fully take into account that honest miners can be just as lucky or unlucky as dishonest miners can.
Cyril Grunspan, mathematician at École Supérieure d'Ingénieurs Léonard de Vinci, and Ricardo Pérez-Marco, mathematician at the French National Center for Scientific Research, now have taken this randomness into account. The two Parisians published a new paper, finally correcting Satoshi’s “mistake.”
“Satoshi wrongly assumed that honest miners use exactly as much time to find a block as they would on average,” Grunspan told Bitcoin Magazine. “However, this is actually a rough approximation of reality, since the time used by honest miners to mine a block is not deterministic. Therefore, the distribution of the number of blocks mined by the attacker is actually — what is called — a ‘negative binomial distribution.’ Not the assumed ‘Poisson law.’”
In essence, the Bitcoin white paper assumes that two factors are needed to calculate how irreversible a transaction is. Satoshi rightly assumed that the share of total hash power available to the attacker is one factor: as an attacker controls more hash power, more confirmations are needed. And Satoshi rightfully assumed that the number of confirmations is another factor: the more confirmations a transaction has, the more secure it is.
Grunspan and Pérez-Marco now show how a third factor comes into play: the deviation from average mining time — “luck” — the honest miners have in finding blocks. If they are very lucky, and find blocks faster than the average, their chain will probably be further ahead; the attacker will have had less time to secretly mine an alternative chain. On the other hand, if the honest miners are unlucky and find blocks slower than the average, they will probably be less far ahead: thus, the attacker will have had more time to mine an alternative chain.
What This Means
The good news, as now conclusively shown by Grunspan and Pérez-Marco, is that the basic premise of the white paper still holds up. Bitcoin works as intended.
“In this paper, we show that the probability of double spends drops exponentially to zero as the honest mining majority finds more blocks,” Grunspan said. In other words, it becomes increasingly difficult for minority attackers to catch up and overtake the honest majority.
That said, the security assumptions as stated in the white paper need to be tweaked a little. Rather than just accounting for the amount of hash power an attacker has and the number of blocks the attacker is behind, this third factor must also be considered. In their paper, Grunspan and Pérez-Marco have now published exactly how much this matters.
“This is interesting information that can be used by merchants to monitor risk,” Grunspan said on the relevancy of their calculations. “Let’s say a merchant always waits for six confirmations before sending his goods to a customer, as that is the level of risk he is comfortable with. That’s 60 minutes on average. But sometimes he’ll have to wait for two hours before six blocks are found. If that happens, the double-spend risk is also higher. So for the same level of security, he’ll actually have to wait for a seventh confirmation. While if the confirmations come in much faster, he should be fine even with five confirmations.”
As double-spend protection is arguably at the heart of Bitcoin’s innovation, the mathematical simplification in Satoshi’s work is notable, especially for mathematicians. Grunspan does allow, however, that simplifying assumptions in a white paper is also understandable.
And, perhaps, it reveals another hint about Bitcoin’s origins.
“Satoshi was a genius,” concluded Grunspan. “But he was not a mathematician.”