I am sorry to inform you that your state table is not correct.
Marlow
11

Thank you for your comments. You have raised several issues. I think it would be most productive to discuss these one at a time.

Before beginning, please note that I have revised the document, but only for the purpose of replacing the details of references to Feller’s book, to reflect the second edition rather than the third edition, which I had downloaded some time ago and appears to be no longer available for free download on the web.

First is the question of omitting propagation and verification time from node behavior. I omitted them since I believe that the differences involved are small in the present Bitcoin network. If these differences were significant there would be a significant rate of orphans, which at present these are practically zero. It seems unlikely that any such delays will be significant, say, in comparison with estimates of hash rates, which have a lot of variation, being Poisson distributed. If you believe otherwise, then I would be interested in seeing some analysis or simulation of how these factors might be relevant. The art of model building is to make appropriate approximations to gain insight on system behavior, and a good enough model will provide this insight, whereas a more complex model may fail to provide useful information, particularly if it is too complex to complete.

Second is the question of how chain forks are handled. Mining is a Poisson process. It keeps no state. At any instant the next event will be the mining of a block by one type of node or another. In the case of state zero, this is shown by a state transition from 0 back to 0 at probability q in case a small block succeeds, or a state state transition from state 0 to state 2 in case a large block succeeds. Once this happens, then the chain will be forked, and as you suggest, the large block fork will grow at rate p. However, the small block fork will continue to grow at rate q and as the state variable compares the relative size of the two forks the state variable will decrement at rate q. The special case that you mentioned where the large block chain is blind to the activity of the small block chain is modeled in the state diagram by the introduction of state 1. The large block chain continues to grow from this state without being orphaned because the large block nodes already saw a block at the same height, since the state 1 is entered only when the small block chain catches up. (This is an assumption about how Bitcoin is coded. As far as I know all implementations work this way. To work otherwise would be inefficient, because of hysteresis in changing data used by ASICs, which operate based on several levels of queues from the node decision making.) Another point: a correct implementation of the Bitcoin protocol notice when a previous fork has grown to be longer. This is necessary, otherwise Bitcoin would not prune incipient forks into a single chain. So this justifies the transition back to a single chain from state 1 to state 0. At the time of a state transition, the probability that the transition will reflect the creation of a large block has the value p, whereas the probability that the transition will reflect the creation of a small block has the q, as these events are conditioned only on the node actions which are independent Poisson processes.

Third is the question of epochs. As I explained in the paper, whenever the large block chain gets orphaned the system reverts back to a single chain. All nodes are mining on the same block. Because mining is memory less, this means that there is no memory of previous activity and we get a true renewal point.

Finally, I don’t understand your question of how a miner gets so many blocks in so many minutes. My Medium paper discusses events, which relate to the mining of blocks, not the times that it takes to mine these. (Perhaps you were referencing an earlier draft PDF not published on Medium. I removed the times because their calculation was incorrect.)

Finally, as to the negative binomial distribution, this is applicable to calculating the duration of unsuccessful attempts. The appropriate formula for this distribution was used.

If you believe that the state diagram does not accurately reflect the assumptions that I have made, I would appreciate a revised state diagram that we could discuss. The analytic formulas appear to agree with the state diagram, as evidenced by the Python simulation.

Show your support

Clapping shows how much you appreciated tl121’s story.