6
$\begingroup$

I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem:

Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the longest blockchain. The system therefore guarantees eventual consistency.

Proof. In order for the fork to continue to exist, pairs of blocks need to be found in close succession, extending distinct branches, otherwise the nodes on the shorter branch would switch to the longer one. The probability of branches being extended almost simultaneously decreases exponentially with the length of the fork, hence there will eventually be a time when only one branch is being extended, becoming the longest branch.

I don't quite understand why the probability decreases exponentially. I think it's quite probable that they happen at the same time, if not that the malicious block is faster and waits.

Improve this question
$\endgroup$
3
  • $\begingroup$ Not an expert here, but for them to happen at the same time, wouldn't two different miners had to mine two different bitcoins at the same time, each of them working on a different fork? Given how hard it is to mine bitcoins, I expect this not happen too often. Also, a malicious block would just mine and extend its fork to make it accepted, would it not? $\endgroup$
    – Ant
    Dec 12, 2017 at 9:57
  • $\begingroup$ @Ant: I just have problems with this theorem. Yes, a powerful machine can do whatever it wants. The eventual consistency's foe is forks. So it's possible that the system won't reach eventual consistency. We are not talking about probability, as the statement of the theorem does not mention it. But the "exponential" part is still not clear. $\endgroup$
    – Zirui Wang
    Dec 12, 2017 at 10:05
  • 1
    $\begingroup$ Expanding a bit on your last sentence, the approach of selfish-mining where malicious miners keep blocks within their pool until someone else announces an extension to the blockchain, at which point the malicious miners release enough of their hidden blocks (which they've had a head start on mining) to regain the longest blockchain position and invalidate the work of others. This paper suggests that collusion of only 1/3rd of the mining power would be necessary to control the blockchain instead of the original view that a majority would be required. $\endgroup$
    – Derek Elkins left SE
    Dec 12, 2017 at 10:16

1 Answer 1

Reset to default
7
$\begingroup$

If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the right number. Let's say there are $N > 1$ possible values only one of which is correct at each minute. Then, in a world with only two miners, each minute there is only a $\frac{1}{N^2}$ chance that both miners will roll the correct value. There's a $1-\frac{3}{N^2}$ chance that neither miner rolls the correct value. There is a $\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2}$ chance that both miners roll the correct value after exactly $k$ steps of both not rolling the correct value. The probability that they will both roll the correct value for the first time at the same time is then $$\sum_{k=0}^\infty\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2} = \left(\frac{1}{1-\left(1-\frac{3}{N^2}\right)}\right)\frac{1}{N^2} = \frac{1}{3}$$

So the odds of them rolling the correct value at the same time $m$ times in a row is $\frac{1}{3^m}$. With more miners, birthday problem aspects enter, but that won't change the exponential nature. (In fact, I don't think the birthday problem really comes into play since each miner still needs to get the correct value not just a value that matches another miner's.)

I'm pretty sure this is the idea the author had in mind. As you say, though, a malicious miner (a selfish miner) can withhold announcing blocks until they notice someone else announcing them. To account for that, you could instead consider (in the two miner world again) what the probability is that the malicious miner finds a block before the honest miner. If the miners are comparable, then that's presumably something like $\frac{1}{2}$. However, things are further complicated by the fact that when the malicious miner does find the correct value first, then that miner also gets a head start on finding the correct value for the next block. Nevertheless, for comparable miners, there is still a good chance that the honest miner will find a block first despite the malicious miner's head start. This reasoning starts to get into the selfish mining aspect I referenced in the comments.

Improve this answer
$\endgroup$

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.