There are two miners, Alice and Bob. Bob is an honest miner and always mines on the public (longest) chain. Alice is a potentially honest, potentially selfish miner who can decide to mine on the public chain, or to secretly work on a private chain, only to publicly broadcast her private chain later.
Let hash rate units be such that if the total hash rate = 1, then the expected time to the next block is 10 minutes.
Assume Alice has a hash rate of and Bob has a hash rate of .
Let be the block reward.
For now, ignore difficulty adjustments, ignore block subsidy halvings, and ignore latency.
We're currently on question #2.
- Suppose Alice currently has no private chain. Let C be the public chain. Thus, both are mining on top of the public chain.
a. What is the probability that Alice finds the next block? Bob?
b. What is the expected time to the next block?
c. What is the expected value of Alice's reward at the time the next block is found? What about Bob?
Answers:
a. The probability of finding the next block is equal to the share of the hash rate. So for Alice the probability is and for Bob the probability is .
b. Since a total hash rate of 1 is directed at the same chain, the expected time to next block is 10 minutes.
c. The expected value of the next reward is equal to the probability that you win it, times the reward. So for Alice this is and for Bob this is .
- Suppose Alice finds the next block. She now has chain C-A. She now decides whether to publish the block, or to mine secretly on top of C-A.
If she publishes the block, she and Bob now both mine on top of C-A. She earns reward immediately and the game returns to as it was in question 1. (Where both are mining on the same chain.)
If she hides the block, she privately mines on C-A while Bob continues to mine on the public chain C.
a. If Alice hides the block, hash power is now directed separately at two chains. Alice is mining on C-A while Bob is mining on C. What is the expected time until Alice finds C-A-A, and what is the expected time until Bob finds C-B?
b. What is the probability that Alice finds C-A-A before Bob finds C-B? Hint: Look up Poisson processes and competing risks.
This will be a series of increasingly difficult Bitcoin math puzzles, designed to walk through the game theory of various bitcoin scenarios in a formal way.
Bounty: 500 sats (payable by zap) to the best answer after 24 hours. This means you have to not only give a correct answer, but also document your reasoning. Suspected AI use will be ignored.
If I make a mistake in my puzzles, please do let me know. We're working this through together!
The expected time for Alice to find C-A-A is x10min.
The expected time for Bob to find C-B is 1−x10min.
The approximate probability that Alice finds C-A-A before Bob finds C-B is 1−xx.
There is a small mistake in (b). If x approaches 0.5, your solution would imply that Alice wins with near 100% probability.
That sounds like a big mistake, not a small mistake! :grin:
I agree, and retract my guess. I’m gonna have to wait for someone else to correct me, though.
Here's a hint: Is the probability of Alice winning the C-A-A vs. C-B race different from the probability of Alice winning the C-A vs. C-B race?
Ah right, sure. The likelihood of C-A-A being found before C-B should then just be x.
Congrats, this and the above (a) were the correct answers.
Yay. :)
Same as @Murch for a.
b. I'm trying to recall without looking it up. I think it's along the lines of e−1/x+e−1/(1−x)e−1/x, which goes to 1 as x approaches 1, 0 as x approaches 0, and 0.5 when x=0.5.
It doesn't matter how much time has passed since the last block was found. You always expect it to take 10 more minutes to find a block.
I actually had to look it up too. Turns out, the answer is just x. @Murch got it here #1472922
That's funny. I almost landed on that answer a bunch of times and kept talking myself out of it.
@remindme in 2 hours
Adding a more explicit derivation, because "the answer is x" is right but feels surprising until you see why Poisson is doing the work.
Model each miner as an independent Poisson process. Alice's rate is x blocks per 10 minutes, Bob's is (1-x) blocks per 10 minutes. Expected time to Alice's next block is 10/x minutes, expected time to Bob's is 10/(1-x) minutes. That's part a.
For part b, the trap is assuming the answer has to involve both numbers because two different waiting times feel asymmetric. The magic: for independent exponential waiting times T_A ~ Exp(x) and T_B ~ Exp(1-x), the probability P(T_A < T_B) is x / (x + (1-x)) = x. The total rate (x + (1-x)) normalizes out. Whichever event fires first is essentially a weighted coin flip where the weights are the rates.
Crucial subtlety that tripped the original answer: the race isn't Alice-vs-Bob for one block. It's Alice-vs-Bob for Alice's second block versus Bob's first block. But the memoryless property of exponentials saves us. Once Alice mined C-A, the clock resets. The C-A-A vs C-B race is just another exponential race with rates x and (1-x), starting now. So P(C-A-A before C-B) = x, identical to P(Alice wins any one-on-one race).
That memorylessness is load-bearing for the entire selfish-mining analysis, and it's also why difficulty-adjusted hashrate shares map so cleanly to block-share outcomes in the long run. Worth stating out loud because a lot of the intuition for why selfish mining is profitable above a certain threshold comes from realizing that Alice's "lead" isn't a stored asset, it's a probabilistic option she exercises by publishing. Excited for #003 where presumably she starts to think about when to release.