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. We're currently taking a look at selfish mining.

We're now on question 2. We've developed preliminaries and notation, and are now ready to write down the full recursive Bellman equation. Take me to the problems

Also, cool thing: based on my understanding of the literature on selfish mining, this approach is new relative to the literature, which did not set up their models with things like continuous time discounting and flow-rate of costs. If we solve this, it could be a genuine contribution to the literature! Since I am not really part of that literature, I am happy for others to take this idea and run with it, or even to collaborate. If no one does, I may do it myself as well.

Model SetupModel Setup

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.

For the purposes of this problem, we'll use the notation set forth in these posts: #1473180, #1475564, and #1477308.

In particular, we'll assume the following:

• Alice has a hash rate of $h_A$, measured in EH/s
• Bob has a hash rate of $h_B$, measured in EH/s
• Alice's hash rate is less than Bob's: $h_A<h_B$
• The effective difficulty is $d$, measured in EH. Effective difficulty is the average number of exahashes required to find a block
• The block reward for a found block is $R$, measured in sats (includes any transaction fees, which we'll assume are constant and deterministic)
• The cost to produce 1 exahash is $c$, measured in sats per EH, for both Alice and Bob
• The discount rate is $r$, measured in percent per year, for both Alice and Bob

For now, we'll ignore difficulty adjustments, ignore block subsidy halvings, and ignore latency.

PreliminariesPreliminaries

Based on the above assumptions, we can say the following:

• Alice's block finding rate is ${\lambda }_A=h_A/d$
• Bob's block finding rate is ${\lambda }_B=h_B/d$
• At any given moment, the probability that Alice finds the next block is $x=\frac{h_A}{h_A+h_B}$
• At any given moment, the probability that Bob finds the next block is $1-x=\frac{h_B}{h_A+h_B}$
• The average amount of time for Alice to find a block is $1/{\lambda }_A$
• The average amount of time for Bob to find a block is $1/{\lambda }_B$

Description of selfish miningDescription of selfish mining

Whenever Alice and Bob are both mining on the same public chain, we'll call that chain C.

If Bob finds the next block, the chain becomes C-B. He immediately publishes it, and both Alice and Bob will mine on that new chain. Since they're both mining on the same chain, we rename C-B → C.

If Alice finds the next block, she now has chain C-A. Since Alice is selfish, she can decide whether to publish it or not.

• If she publishes it, the public chain becomes C-A and both Alice and Bob will mine on it, so we rename C-A → C.
• If, however, Alice decides to hide her private chain, the two miners are now mining on different chains. Alice is now mining on C-A and Bob is now mining on C. If Bob finds the next block after that, Alice now has C-A and Bob has C-B. However, if Alice finds the next block after that, she now has C-A-A while Bob still has C. Alice can again decide whether she wants to publish C-A-A, or to keep it private.

In other words, Bob always publishes any block he finds, and always mines on top of the longest chain. Alice, when she finds a block, may decide whether to keep her chain private and mine on it secretly, or to publicize her chain.

In this series of problems, we're going to derive conditions under which Alice has an incentive to not publish her chain, but rather to mine privately.

Value function and state notationValue function and state notation

The strategic state space can be described by two numbers, a and b. a measures how many blocks Alice has mined on top of C in her private chain, and b measures how many blocks Bob has mined on top of C in the public chain (only when the private chain and the public chain diverge).

So for example:

• If Alice is mining on C-A while Bob is mining on C, then (a,b) = (1,0).
• If Alice is mining on C-A while Bob is mining on C-B, then (a,b) = (1,1).
• If Alice is mining on C-A-A while Bob is mining on C, then (a,b) = (2,0).
• If Alice and Bob are both mining on C, then (a,b) = (0,0).
• In fact, if at any time Alice and Bob are both mining on the same public chain, then (a,b) = (0,0).
• If Alice ever publishes her private chain which is ahead of the public chain, the state resets to (a,b) = (0,0) because Bob always mines on the longest published chain.

Let $V(a,b)$ be Alice's value function in state (a,b) (i.e. the net present value of mining while the state is a, b).

Let $P(a,b)$ be Alice's value function of publishing her private chain while in state (a,b). We note that:

This is because if Alice publishes when $a>b$, then her chain becomes the longest public chain (which Bob now mines on), and she earns the accumulated rewards she had hidden up to this point. But if she publishes when $a\le b$, her chain is not the longest and will not be accepted as the public chain.

ProblemsProblems

1. Write a Bellman equation for the value function $V(0,0)$.
   
   Solved (#1480916):
   $$rV(0,0)=-h_{A}c+{\lambda }_A\left[\max \left\{P(1,0),V(1,0)\right\}-V(0,0)\right]$$
2. Now write the generic Bellman equation for the value function $V(a,b)$ in any state.

Bounty: 1000 sats to the best answer with explanation. 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!

Hint on Bellman equations

If the current state is $x$ that gives flow utility $u(x)$, and two possible events could happen, event 1 and event 2, with Poisson rates ${\lambda }_1$ and ${\lambda }_2$, and event 1 pushes you into state $x_1$ while event 2 pushes you into state $x_2$, the Bellman equation would be: