What is Binomial Random Walk?

(Last Updated on November 6, 2020)

The success event is the honest chain being extended by one block, increasing its lead by +1, and the failure event is the attacker’s chain being extended by one block, reducing the gap by -1.

– Satoshi Nakamoto

Suppose you start at point A and either walk 1 meter to the right or one meter to the left, where there is a 50/50 chance of either choice. Now repeat this process for a total of 100 times. What is your expected distance from the starting point?

This is a basic example of a random walk problem. Define the random variables xi as follows:

image7196

Now let dn = your distance from the starting point after the nth trial. Thus

image7197

How does this affect Bitcoin?

If there was to be a 51% miner attack on the block chain – then the miner would need to consistently battle to stay ahead of the “honest” miners and nodes. The attacker must build an alternate version of the block chain, and do so quickly, before honest miners and nodes may become suspicious and revert to the genuine block chain.

The probability drops exponentially as the number of blocks the attacker has to catch up with increases. With the odds against him, if he doesn’t make a lucky lunge forward early on, his chances become vanishingly small as he falls further behind.

We now consider how long the recipient of a new transaction needs to wait before being sufficiently certain the sender can’t change the transaction. We assume the sender is an attacker who wants to make the recipient believe he paid him for a while, then switch it to pay back to himself after some time has passed. The receiver will be alerted when that happens, but the sender hopes it will be too late.

The receiver generates a new key pair and gives the public key to the sender shortly before signing. This prevents the sender from preparing a chain of blocks ahead of time by working on it continuously until he is lucky enough to get far enough ahead, then executing the transaction at that moment. Once the transaction is sent, the dishonest sender starts working in secret on a parallel chain containing an alternate version of his transaction.

– Satoshi Nakamoto

Chances of this happening out of China?

Slimmer everyday and increasingly difficult with the number of independent nodes popping up around the world to help verify and validate the network. Not only helping secure each block, but giving many individuals a direct portal to transact through Bitcoin.

Heatmap from Cambridge University showing spread of mining activity globally

In prior years Bitcoin mining share was as high as 79% coming out of China.

This was primarily due to the majority of ASIC miners coming out of China – thus having first access to strongest technology and many Chinese taking advantage of cheap electricity locally.

Now we have seen the global mining competition grow larger which secures Bitcoin by diversifying the network.

Currently we are seeing China drop to 65.08% of the Bitcoin mining share and expect it to drop further as China’s monsoon season ends. The end of the rainy season in China has a major impact on mining due to the cheap (almost free) electricity from the excess hydropower.

Q4 of 2020 is going to see some major U.S. miners continue to grow share as they continue to develop more efficient ways of utilizing our gas and oil infrastructures.

Will we see the U.S. take a majority % role in mining?

Probably not, and hopefully we will never see one country with over 50% hashrate in the future. However we should see the United States start rapidly decreasing the mining share that China has held majority for the past handful of years.

One of those companies leading the charge is Core Scientific – recently purchasing over 17,000 S19 Antminers from Bitmain

As the United States develops its energy systems to better suite the Bitcoin mining ecosystem, we will start seeing a major revival of natural gas and other excess energy industries repurposed for mining.

What was Satoshi’s first vision for how these mathematical rules fit into his system?

We have proposed a system for electronic transactions without relying on trust. We started with the usual framework of coins made from digital signatures, which provides strong control of ownership, but is incomplete without a way to prevent double-spending. To solve this, we proposed a peer-to-peer network using proof-of-work to record a public history of transactions that quickly becomes computationally impractical for an attacker to change if honest nodes control a majority of CPU power. The network is robust in its unstructured simplicity. Nodes work all at once with little coordination. They do not need to be identified, since messages are not routed to any particular place and only need to be delivered on a best effort basis. Nodes can leave and rejoin the network at will, accepting the proof-of-work chain as proof of what happened while they were gone. They vote with their CPU power, expressing their acceptance of valid blocks by working on extending them and rejecting invalid blocks by refusing to work on them. Any needed rules and incentives can be enforced with this consensus mechanism.

Satoshi Nakamoto

Perfection. Thank you Satoshi 🙂

References:

If you’d like to read more about Satoshi’s binomial walk problem please check out the original whitepaper at https://nakamotoinstitute.org/bitcoin/

Leave a Comment

Your email address will not be published. Required fields are marked *