0

I am reading this paper on how information is propagated on the Bitcoin network. The authors present a model to predict the rate at which forks occur in the blockchain which is given as below enter image description here Here, F is the number of conflicting blocks in the network, Pb is the probability of the network finding a block b in a given second (ideally, 1/600 since a block is expected every 10 mins = 600 secs) and f(t) represents the ratio of nodes that hear about the block b in t secs. However, what I cannot understand is how this entire expression is derived. I understand that the term in the exponent represents the mean amount of time it takes for the network to learn about a block (and this value can be derived from a graph given in the paper). I assume 1 - Pb represents the probability of the network finding more blocks in the remaining 599 seconds in the 10-minute interval. Why is this probability raised to the mean amount of time it takes for the network to learn about a block?

Any explanation would be appreciated.

Improve this question

1 Answer 1

Reset to default
2

I haven't read the paper, and I think the expression is only an approximation, but the basic idea is that this is an inhomogeneous Poisson process.

In order for a fork to occur, some unaware node needs to find a block. This is 1 minus the probability that no unaware node will ever find a block. Which itself means that no unaware node finds a block in 1st second, no unaware node find a block in 2nd second, etc. This probability is the product of the probabilities of the individual seconds (since they are all independent).

Each individual probability is roughly (1-P_b)^(1-f(t)) (if f(t)=0 then all nodes are unaware and the probability is the same as no block being found at all a block at all, if f(t)=1 then all nodes are aware and certainly no block will be found by an unaware node, and in between it interpolates. If it's not clear why the interpolation is via a power, keep in mind that for small P_b, the power is irrelevant since the expression is roughly 1-P_b*(1-f(t)).

The combined probability, as mentioned, is the product of probabilities, which is like (1-P_b) to the power of a sum of (1-f(t)), which is like (1-P_b) to the power of an integral.

If it was up to me I would have written the expression differently, but these are the general ideas.

Improve this answer
2
  • That makes a lot of sense now given that the process of finding blocks is independent. In your answer, do you mean to write the exponential term with the integral, as in the original expression? (I know there's no support for MathJax on here unlike MSE; just making sure).
    – an4s
    May 2, 2018 at 23:42
  • @an4s: Actually, there's a paragraph I simply forgot to write which addresses the integral. Added it now. An integral is like a sum, and (1-P_b) to the power of a sum is like a product of terms, each of which is (1-P_b) raised to some power. This was a bit handwavy but may make more sense by reading up on exponential distribution, Poisson process so on. And I'll mention again that to me the expression seems only approximate, (1-P_b) should be replaced with exp(-P_b) where P_b is the block finding rate.
    – Meni Rosenfeld
    May 3, 2018 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.