Why the 25% Bitcoin Attack is not a Problem

Recently, there was a paper which outlined a vulnerability in the Bitcoin protocol.  This paper claimed that with a share of the computing power of the network adding up to only 25%, "Selfish" Miners could take advantage of the rest of the network and take more bitcoins from the block reward than their fair share.

The paper is wrong.  They fail to take into consideration the extra amount of time it takes to generate blocks.

Let's assume for a moment that a pool has 25% of the mining power.  If this is true, then they expect to finish 25% of the blocks everyday, which yields an expected daily income of 900 BTC from block rewards.  While it is true that more or fewer blocks can be finished in one day, the assumption of the 25% computing power share renders that irrelevant.

The paper states "We assume that miners are rational; that is, they try to maximize their revenue, and may deviate from the protocol to do so."

If this is true, then a strategy which yields an expected daily income of less than 900 BTC would not be followed by a rational miner, selfish or not.

This is a simplification of Selfish Mining.  Circles are blocks and vertices are the periods of time between completed blocks.  The paper assumes that each round takes 10 minutes.  This is false.  By this false assumption, the expected daily income of a Selfish Miner is 1,008 BTC, which we can see is bigger than 900 BTC.

As said before, the paper does not take into account the extra time for blocks to finish if you're not following the protocol in this manner.

Here's what the strategy actually yields:

The 3 minutes and 20 seconds extra on the 4th block is when the 25% selfish pool is waiting for the rest of the network to catch up in order to cause a fork event.  The 6 extra minutes on the 5th block is because on average, they will force half of the network to work on their "false" fork.

While they expect to receive 25 BTC on the 4th block, they can only expect to receive 40% of the revenue from the 5th block.  Not only this, but 37.5% of the time they won't get anything because the public block finished first, causing everyone to continue to work on it.

As a result, their expected earnings per event are 21.875 BTC, and due to the extra time, we can expect ~24.27 of these events to occur per day, which leaves an expected daily income of ~530.90 BTC, which is ~369.10 BTC less than if they were honest.

Conclusion:  Miners can be expected to not follow this strategy since it yields less income.

Comment? Concerns?  Leave a comment below.

tl;dr Miners lose by following the "Selfish Mining" technique by about a 41% decrease in expected income if they control 25% of the network.

Why Ruby’s Binary Search is Meh

As of Ruby 2.0.0, the Array#bsearch and Range#bsearch instance methods have been added to do binary searching within an array or a range.

While this awesome algorithm is much welcomed, Ruby has it implemented in a slightly broken manner, (in my probably silly opinion).

First, let’s look at how it works, and by works I mean works in the way expected and produces a meaningful and reasonable result.

some_array = [ 0, 1, 4, 7, 10, 15, 99, 100 ]

Let’s try to find the first element in the array that is bigger than or equal to 72.

some_array.bsearch { |i| i >= 72 }

#=> 99

Cool!  And if the algo is running the way it should, that took 3 iterations, instead of the 7 iterations a linear search might take.

Now, this only works if the array is sorted, which is a requirement of the binary search algorithm in general.  Let’s see why:

The binary search algorithm works as fast as it does because it makes assumptions.  It assumes that the values are in order, because it uses this assumption to “throw away” portions of the collection at a time.  In our example, it did something like this:

[ 0, 1, 4, 7, 10, 15, 99, 100 ]
hmm, some_array is 8 elements large. I’m gonna check the middle first.

okay, the middle has the number 10.  well, 10 is NOT greater than or equal to 72, and since everything is in order, everything below it is useless too, so my new array is… 
[ 15, 99, 100 ]

okay, this is 3 values large, so I’ll check the middle again

99 IS larger than or equal to 72, so everything bigger than it can suck it!
New array is:

[ 15 ] 
well, the only element in this one is LESS than 72, so that 99 was the right answer!

Okay, this works nicely.  But what if I set the condition to be the last guy less than 7?

That should be 4, the third element of the array.

Unfortunately, you can’t tell it to give you “the last element which…”, but only “the first element which…”

And even if you try to use this logic, you’ll get unexpected results.

Let’s try to find the first guy less than 7.  Should be 0, right?

[ 0, 1, 4, 7, 10, 15, 99, 100 ] 
hmm, some_array is 8 elements large. I’m gonna check the middle first.

okay, the middle has the number 10.  well, 10 is NOT less than 7, and since everything is in order, everything below it is useless too, so my new array is… 
[ 15, 99, 100 ]

Wait, wha…?  It still threw away the bottom half!  That’s where the 0 was...

[ 15, 99, 100 ]

okay, this is 3 values large, so I’ll check the middle again

99 is NOT less than 7, so everything bigger than it can suck it!
New array is:

[ 15 ] 
well, the only element in this one is BIGGER 7, so there is no right answer!

I’d better tell the user the answer is nil.

Okay, that’s not quite what I wanted.  Is there a better way to do this?  Should the search ‘save’ the other half and look through it if the right hand fails?  Should there be other bsearch-type methods that work a little differently (like bsearch_max or something)?

Feel free to comment below to tell me why I'm wrong or what should be done.

Cheers!