Many people have weighed in on the issue of selfish mining. Today, we look at a key aspect of the model proposed by [1]. Interestingly the selfish mining paper utilizes formulas and equations from Feller [3] just as we see in the bitcoin white paper [2]. However, as we demonstrate in this post the authors fail to understand some of the key concepts.
The state machine defined within the selfish mining paper is reliant on a process in probability theory called a Markov process.
Bitcoin mining in its native form, that is without selfish mining or any other supposed attack based on this fallacy is a stochastic process that may be characterized by the term memorylessness.
Much as been said within the bitcoin community about this property recently and it seems that it is a concept that is very poorly understood. In a Markov process, one can predict and model the system based on its present state alone. The result is that any Markov process is independent from history. It is conditional only on the present state of the system in the past and future states remain independent.
When Poisson processes divide and split into two chains we do not need to consider the joint probability as long as these are independent in nature. The problem in calculating values comes when events are no longer independent.
Independence is a critical term here. As we can see reading up a simplified version of this concept in Wikipedia, we know definitively that independence only occurs if one event does not effect the probability of occurrence of the other.
It is easy to see the error created by the layman within the selfish miner paper, if you truly understand Markov processes well. These processes are defined as requiring the following properties:
- Finite number of discrete states,
- Probabilistic transitions between states, and
- Next state determined only by the current state
As we’ve noted, this last property is linked to independence. The reaction of the selfish miner follows that of events that occur from the honest miner. The honest miner does not react when an event happens secretly which can impact the selfish miner alone. The next state in this model is not determined by the current state alone.
Binomial…
Even if we take a more accurate negative binomial model, we have the problem of independence. A more correctly determined formulation would be derived using the negative binomial distribution, this is defined by the “successes in a sequence of independent and identically distributed Bernoulli trials before a specified (non-random) number of failures (denoted r) occurs.”
Again, we run into the problem of independence.Independent and identically distributed random variables (i.i.d. or iid or IID) have the same probability distribution as the other variables and all are mutually independent [5].
So, it seems no matter which simple strategy we choose we end up running into the concept of independence.
Conditional Poisson Processes
Once we are in the realm of non-independent processes, we come into more complex calculations such as conditional probability processes. The table below in figure 1 shows us how we might choose some of the simpler forms of state machines. For a system to be a Markov chain it is required to be fully autonomous.
Unfortunately, in the model created in the selfish mining paper, the system is controlled. We know this as the selfish miner reacts and releases blocks based on the actions of the honest miner. The selfish miner reacts based on a strategy that is determined by conditional events. We also know that the state is not fully observable. The selfish miner hides blocks from the honest miner meaning that the system state is only partly observable. The result is that we cannot use a Markov chain and the simplified mathematics that are entailed within such a system in the computation of the probabilities.
The best case scenario is that we may be able to use system known as a Partially Observable Markov Decision Process and this is only if we take the simplified view of mathematics and instantaneous processes but does not in itself represent bitcoin.
To honestly represent bitcoin we need to also incorporate other reactions from the system. This incorporates miner behaviours as well as the construction of the network and verification times and other delays within propagation. If these are integrated, we are required to use a Partially Observable Stochastic Reference Game. Unfortunately, such a system is generally considered to be intractable and only leads to approximate solutions.
Partially Observable Markov Decision Processes (POMDPs)
Unfortunately for the calculation of values within the selfish mining paper, it is necessary to use a system such as a partially observable Markov decision process. The requirement comes from the interaction of the selfish miner which alters the form of the problem. As explained earlier in this post, a Markov chain (the proposed state machine within the selfish mining problem) must be independent. I shall not delve into the requirement for the model to be identically distributed in this post, but this is also a requirement. The difference in distribution forms as well as the variances in confidence intervals between the different state distributions leads us to see that it is also not identically distributed. This will be covered in a later post.
Independence is very simple. The state cannot be reliant, that is dependent on another event occurring. Selfish mining is a conditional response. In the event that the honest miner discloses a block, the selfish miner responds. The selfish miner never responds before the honest miner preempting the block. This is not the nature of the modelled system and attack. The process is as follows:
- A block is discovered by the honest miner and is propagated across the network.
- If the selfish miner is within certain unknown states (these are unknown states within the determination of the honest miner), then the selfish miner may not release a block. This occurs following the receipt of a block and after a delay for verification and network latency. Unlike the claim made in the selfish mining paper this is not zero.
- The selfish miner selectively reacts based on conditional events. The selfish miner is unable to determine when a block will be discovered by the honest miner and must react following that event.
- The honest miner follows the default strategy what ever the behaviour of the selfish miner.
Even a layman can see that the state of the system is dependent on other results. The earning capability of the honest miner is reliant on the actions of an unknown entity and the reactions of the selfish miner will always follow that of the honest miner.
Back to independence
For a process to be independent it cannot follow a requirement that is dictated by another process. For example, rolling a pair of dice is generally considered to be independent. This is definitively the case if the two die I rolled in conjunction and at the same time. That is if we roll both on the table simultaneously. The results of one do not impact on the results of the other. Conversely, we can see that it could also be dependent if we state a condition. If we state a requirement that the first die will be rolled and if the result is a five or higher on a six sided die that we roll the second die until we gain a value of three or greater then we have a conditional probability distribution. The results are no longer independent.
We can model this simple state system and probability distribution fairly simply. It is far less complicated than the state table associated with selfish mining. The distribution of values obtained in rolling a die is fairly simple — far simpler than any results from a combination of conditional continuous-space-time stochastic processes. An example of such a process would be an Ornstein–Uhlenbeck process.
Conclusion
The jump to false authority is always interesting. The authors of the selfish mining paper are not statisticians or mathematicians and yet they are simply trusted in the determination of the model without any testing in the real world.
Many people have stated how they have tested the model and the results. The problem here is that the model needs to be tested against reality. This is not what people have been doing. The results of such a test shall be forthcoming. These are been run independently from myself. The reality is that the creation of a model must be tested against the system it is set to model. Running a simulation and asserting the functioning of the system is not a scientific process. Testing the process against of model is.
Right now, many people have made the assumption that the mathematics within the selfish mining paper are correct and without error. I have not even questioned the assumptions of independence that are associated with the probability formula used within the paper. In this post I demonstrate that one of the fundamental aspects of a Markov model, independence, has been violated and hence the formula used within the model cannot be relied on.
Even a simple Bayesian system would have been better, however, the authors of the Selfish mining paper have not been able to determine that the processes are dependent and have simply violated the required assumptions.
It is not enough to create a model of what you think a system is nor to test the simulation many times. It is science only when the model has been tested against reality.
References
[1]. https://arxiv.org/pdf/1311.0243.pdf
[2]. https://bitcoin.org/bitcoin.pdf
[3]. W. Feller, “An introduction to probability theory and its applications,” 1957. https://archive.org/details/AnIntroductionToProbabilityTheoryAndItsApplicationsVolume1
[4]. https://en.wikipedia.org/wiki/Markov_chain
[5]. Aaron Clauset. “A brief primer on probability distributions” (PDF). Santa Fe Institute.
[6]. Conditional Poisson Processes
Richard F. Serfozo
Journal of Applied Probability, Vol. 9, №2 (Jun., 1972), pp. 288–302 www.jstor.org/stable/3212799
