Announcing a Return to our Roots: The All-New Bitcoin Magazine

How Satoshi Messed Up His Math (and How These Academics Just Fixed It)

by

         How Satoshi Messed Up His Math (and How These Academics Just Fixed It)

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.”

Recommended

Syncing Data Between Bitcoin Nodes Is About to Get Easier

The minisketch open-source initiative is designed to achieve set reconciliation between the mempools of each full node.

Colin Harper

Blockstream Satellites Now Cover Asia Pacific, Send Messages With Lightning

Orbiting in our planet’s exosphere, Blockstream's satellites broadcast the Bitcoin blockchain in North and South America, Europe, Africa — and now Asia Pacific.

Colin Harper

The Lightning Network's First ERC-20 to Bitcoin Atomic Swap Has Taken Place

Thanks to researchers at TenX's CoBloX, the world's first solution for ERC-20-to-bitcoin atomic swaps on Lightning has arrived.

Colin Harper

Bitcoin’s Tech Trends of 2018: What This Year Brought Us (Part 1)

Where 2017’s dizzying price highs embedded “hodl” into the public consciousness, 2018 was the year in which “buidl" became a trend in the crypto-industry — and Bitcoin was no exception.

Aaron van Wirdum