Topic: Bug in Bitcoin Discovered by PMC Community - Altcoins Affected As Well (Read 2678 times)

Assumption is the mother of all fok ups.

My earlier posting was pretty good except for the following part:

"
So what we need to calculate now is the number of times this 21m number can be halved.

Which is log10(21m) / log10(2) = 24.323885992102934376117624838116

So that's roughly:
24.32 * 210k blocks = 5108016.0583416162189847012160044 blocks.

5.1m blocks will be mined and then the rewards should go to zero.
"

This is wrong.

It's not the supply that's being halved... it's the reward that's being halved:

50 * COIN

COIN is defined as 1 0000 0000  (without the space)

So the function starts with 50 0000 0000

It is then right shifted by:

BlockNumber / 210000

So the question is then at what block number will the reward go to zero or near zero ?

The answer is:

Step 1. Figure out how many times 50 0000 0000 can be shifted right. It turns out this is 33.

(Note... this is over the safety range of 0..31 for shift values... so any 32 bit software version of bitcoin might be unsafe).

Step 2. Calculate which block turns into zero reward or problem:

33 * 210000 = 6930000

Another little bit of interesting tid bit is:

5.000.000.000 is already over the 32 bit safety limit.

Another little bit of interesting information is, this table below is wrong...

https://en.bitcoin.it/wiki/Controlled_supply#Projected_Bitcoins_Long_Term

The reward will not be 1 but 0.

At least according to windows calculator !

It's very funny to see how hard it is to get it right... but I am trying to get it right this time ! =D

(I am also glad I can login again ! password reset working =D)

The correct shift value to still get an reward is 32...

Anyway block 6930000 should probably be the first block to have a reward of zero. Thus shift value 33 is reward = 0.

When will reward go to zero 4*210k so 4x33 = 132 years from genesis or so... maybe sooner or later... correct calculation would be taking the 10 minutes... too lazy now to do that... maybe later.

However point is: for 32 bit software it would already go undefined sooner... at 32:  32x4 = 128 years from genesis.

So let's step:

Step 3. Multiple by halving time (expressed in dividing block number by 210.000 which more or less equals 4 years):

ShiftValue * 210.000 = X

So see above.

Bit vague posting maybe... but I am not too sharp anymore... heat, sleep lol but it's pretty good anyway.

But strange maybe... but true: 210.000 and 4 years related to each other.

I will leave it at that for now... just to correct my posting a little bit.

"To the moon!"

http://www.virginiaedition.com/media/spaceelevators.pdf

This is like driving at a wall with a ferrari and then hitting the breaks at the very last moment

Dogecoin NOT impacted by this.

https://github.com/dogecoin/dogecoin/blob/f1677f31296daaa00e074bd9a6be14c4425b4a96/src/main.cpp#L1089

 

Title should be changed to PMC community "discovers" bug already known (with potential fix) in 2012.

Yes, bitcoin may have a lot of time left to fix this.

Don't forget though that pretty much all coins are bitcoin clones, and there are many different block times. Probably there will be quite some coins who reach 64 times block halving way before bitcoin does.

Corrected it for you! no thanks necessary!

Ok people, let's speculate what the price will be at that point!

I say $1.000.000.000.000.000 per !

If we reach that point we won't need new coins because the block will have a pretty big value from fees!

 

Better to fix it today than waiting 200 years and having the whole United Federation of Planets update every client on every planet and every spaceship

The problem occurs when the block reward has been halved 63 or 64 times (including after the reward is already 0). That won't happen for another 200 to 250 years.

(from older bitcoin code: bitcoin-0.5.1-win32-original):

main.cpp

int64 static GetBlockValue(int nHeight, int64 nFees)
{
    int64 nSubsidy = 50 * COIN;

    // Subsidy is cut in half every 4 years
    nSubsidy >>= (nHeight / 210000);

    return nSubsidy + nFees;
}

(from newest bitcoin code: 1 march 2014):

int64_t GetBlockValue(int nHeight, int64_t nFees)
{    
   int64_t nSubsidy = 50 * COIN;    
   
   // Subsidy is cut in half every 210,000 blocks which will occur approximately every 4 years.    
   nSubsidy >>= (nHeight / Params().SubsidyHalvingInterval());    
   
   return nSubsidy + nFees;
}


So code seems to be something like:

Reward = Reward >> SomeValue; // de-obfuscated

What will happen depends on how this will be compiled to instructions and how those instructions behave.

For now x86 and x64/amd64 is popular so a good guess is intel's instruction manual.

Two possible instructions are likely chosen by a C compiler:

1. shld
2. shr

shld may produce undefined results so the reward could be even higher than the default.

however shr is probably chosen by compilers, and shld will probably also behave as if the shift value was masked.

And that is what happens for both instructions, the shift value is masked by 5 bits or 6 bits all being 1's depending on if it's 32 bit or 64 bit mode.

However I think bitcoin is probably compiled to run on 32 bit operating systems as well, which might mean that shld was used or perhaps some compiler specific 64 bit software implementation of shr.

One would have to look at the instructions generated for this specific function to be sure what's going to happen... but since it was tested... we kinda know.

Theoretically at least the shifter is wrapping back as follows:

64 mod 64 = 0  so no shift happens.

Which is the same as
64 and 111111b  

This explains the reward of 50 * COIN

So to calculate when this wrap around of the shift value would happen requires this to be solved:

nHeight / 210000 = 64

which leads to:

nHeight = 64 * 210000

which gives:

13440000

^ the block count/number mentioned.

nHeight is probably the block number and each block is generated every 10 minutes.

The 210k is not exactly 4 years so that a bit sloppy.

Anyway one year is: 365.25 * 24 * 60 / 10 = 52596 blocks.

So this block number will be reached from genesis at:

13440000 / 52596 = 255.5 years.

4 years is: 210384

Perhaps 210k was chosen a bit sloppy to offset that blocks are found a bit faster than 10 minutes, probably not the reason though... just sloppy.

In reality this block number will be reached a bit faster probably because of investments in new hardware and so forth... though nobody can predict the future lol.

Now for some interesting questions... how to fix this ?

There are supposed to be only 21 million coins or something... so that means:

21.000.000 / 50 = 420000 blocks. though... the number of blocks will be much higher because rewards will be cut in half and so forth... each 4 years...

So this makes it a bit more difficult but still kinda easy to calculate:

First 210k blocks: 50 coins
Second 210k blocks: 25 coins
Third 210k blocks: 12.5 coins
Fourth 210k blocks:  6.25 coins
Fiveth 210k blocks: 3.125 coins
Sixth 210k blocks: 1.5625 coins.

So let's start:
210.000 x 50 = 21000000 - 10500000 = 10500000
210.000 x 25 = 10500000 - 5250000 = 5250000
210.000 x 12.5 = 5250000 - 2625000 = 2625000
210.000 x 6.25 = 2625000 - 1312500 = 1312500
and so forth...

So what we need to calculate now is the number of times this 21m number can be halved.

Which is log10(21m) / log10(2) = 24.323885992102934376117624838116

So that's roughly:
24.32 * 210k blocks = 5108016.0583416162189847012160044 blocks.

5.1m blocks will be mined and then the rewards should go to zero.

Putting this back into the function gives:

5108016.0583416162189847012160044 / 210000 = 24.323885992102934376117624838116

The shift value of 24 is therefore well in range of the 0 to 31 or 63 bit value range.

However... just because no more rewards are given out doesn't actually stop the block number from going up...
blocks will still be mined just no more rewards given... so that is indeed a bit of a problem.

After 255 years... a bit of a lol there... suddenly rewards would be given out which would be funny... or perhaps even unspecified ammounts of rewards.

Anyway a simple sloppy fix could be something like:

if nHeight <= 5109017 then
  // calculate reward
else
  // no reward.

I am not sure about that fractional part

So just to be fair to whoever mines it last... perhaps one extra block for you... perhaps max will be slightly over 21m or slightly under depending on what you guys would want.
if it must stay under 21m then:

if nHeight <= 5109016 then
  // calculate reward
else
  // no reward.

So from this little inspection there does seem to be a little problem with bitcoin... it won't actually produce 21m bitcoins exactly... but something near it... unless it's somehow solved to give that tiny little fraction to the last block or so... or perhaps it will fit perfect by chance/rounding me not sure... would be nice if someone investigates that further just for the fun of it

However the future is not certain... perhaps 10 or 20 years from now intel is dead and this code might behave totally different

Or how about this for something really cool:

if nHeight <= 5109016 then
  // calculate reward
if nHeight = 5109017 then
  // calculate bitcoins remaining of that 21m and give it to the last block, risky but cool (if calculation fucks up that would be one wealthy block )
  // probably safest to perform this calculation offline and just put a constant here or so
else
  // no reward.

I also wonder if old clients that may be used by then would be exploiteable... perhaps they would assume rewards were given out... perhaps there are other checks in bitcoin or perhaps not...

Would be fun for those future programmers/hackers to exploit old clients like that bihihi... some old clients would then maybe accept payments from those blocks

Perhaps some bitcoin vending machines/atms/hardware.. though commercial interests would probably update those... though bitcoin hardware still a good guess... stuffed away somewhere in some bank

Bye,
  Skybuck.

Indeed, very title, much scary!!! 

Actually, the problem will occur in 140 years!!!

Title is a little alarmist. The bug is not really a problem right now. We don't know if Bitcoin is going to be here 2 years from now, let alone when the block reward gets to zero in a hundred years.

The standard for computing the block reward is to use integral satoshis as the units. A block reward of less than a satoshi is not currently possible.

In the current bitcoin standard, the satoshi is the smallest unit and cannot be sub-divided. Amounts are stored as satoshis in integer form in the block chain and elsewhere. It is possible to change this standard in the future, but changing the computation of the block reward would be a separate change.

I guess i was wrong, there will only ever be 20,999,999.999999999496 bitcoins.

Source: https://en.bitcoin.it/wiki/FAQ#How_long_will_it_take_to_generate_all_the_coins.3F

This is a known bug. It was discussed here: https://bitcointalksearch.org/topic/where-is-the-block-reward-function-130614

Even though this bug was already found, the work by Premine is still appreciated.

Yup, its compiler specific how operator ">>=" is implemented, so maybe lil bit more accurate defining is needed.