How to read this Markov Chain equation

65 Views Asked by At

I'm having trouble reading this Markov Chain equation. This equation has to do with miners attacking a blockchain.

$k$ is the count of an object (blocks) that belongs to one group 1 (the honest miners)

$ℓ$ is the count (blocks) that belongs to group 2 (the selfish miners)

$λ1$ is the percentage of computing power that belongs to group 1

$λ2$ is the percentage that belongs to group 2

$q((k, ℓ), (k + 1, ℓ)) = λ1, k ≥ 0, ℓ ≥ 0$

$q((k, ℓ), (k, ℓ + 1)) = λ2, k ≥ 0, ℓ ≥ 0$

$q((k, ℓ), (0, 0)) = µ, k \neq ℓ$

What does this mean in English? I get that this is describing state transitions but I'm not sure how.

Additional details for context:

These equations are showing how state can change when a group of miners are engaged in selfish mining against a blockchain. This equation is taken from Bitcoin Blockchain Dynamics: the Selfish-Mine Strategy in the Presence of Propagation Delay

The first two states occur when one of the two groups mine a block.

The third occurs when "communication has occurred when the chain is in a state $(k, ℓ)$ with $k \neq ̸ℓ$." It is possible that the state can transition back to (0,0) if both groups adopt the same blockchain. Group 1 always behaves honestly and will always mine on the chain that is the longest. Group 2 is trying to game the system and attempts to gain a lead of $ℓ + n$ where $n$ is the number blocks they are ahead.

Per the authors on state 3: "This latter rate is a simplification of what could have been assumed: if $|k−ℓ| ≥ 2$, there are multiple communication tasks in progress, reporting the last $|k − ℓ|$ block discoveries in the longest branch and it is only when the communication reporting the discovery of the final block on the longest branch arrives that the state of the system returns to (0, 0). For the sake of tractability in this simple first model, this is the only transition that we have taken into account. As we observed above, states with $|k − ℓ| ≥ 2$ have a very low probability of occurrence and we can expect that this modification will not have a great effect on the stationary distribution."

1

There are 1 best solutions below

1
On BEST ANSWER

It looks like each state is given by a pair of numbers $(k,l)$ that tell us how many objects belong to the two different groups. If your two groups are rival candidates, say, then $(15,12)$ would mean that candidate 1 has gained the support of 15 voters and that candidate 2 has gained the support of 12 voters.

At each transition, the two groups are competing for the vote of another candidate. We can go from $(15,12)$ to $(15,13)$ or from $(15,12)$ to $(16,12)$. That's why you have $(k+1,l)$ or $(k,l+1)$: only one group wins the new vote.

The probability that group 1 wins the vote is equal to the percentage of computing power they have, and the probability that group 1 wins the vote is equal to the percentage of computing power they have.

The last line baffles me. It looks as if there is a possibility $\mu$ that the numbers change from $(15,12)$ to $(0,0)$... but I would have thought that $\lambda_1+\lambda_2=1$ leaving no room for other options. Perhaps $\lambda_1+\lambda_2+\mu=1$, so in the case where neither group gets the vote, the total votes get reset to zero... That doesn't make much sense in any application I can think about.

Can you clarify where the question comes from? Give us some more context?