9

I read through How is difficulty calculated? and want to understand where the "off-by-one" bug is in calculating difficulty. Here is a Matlab snipet I wrote to calculate difficulty. What are the correct block step intervals that I should use? Note: minv and maxv are the block heights (plus 1) of the interval. Thus, time stamps from block heights 0 and 2015 are used in the first difficulty calculation.

% Calculate difficulty
num = floor(length(block_chain)/2016);
minv = 1;
maxv = 2016;
target = 1209600;
difficulty = ones(num,4);
delta = zeros(num,1);
timedif = delta;

for i = 1:num
    if i == 1
        difficulty(1,3) = 1;
        timedif(i) = block_chain(maxv,2) - block_chain(minv,2);
    else
        timedif(i) = block_chain(maxv,2) - block_chain(minv,2);
        delta(i) = max(0.25,min(target/timedif(i),4));
        difficulty(i,3) = max(1,difficulty(i-1,3)*delta(i));
    end
    difficulty(i,:) = [block_chain(minv,1), block_chain(maxv,1),...
        difficulty(i,3), timedif(i)];
    minv = maxv + 1;
    maxv = maxv + 2016;
end

2 Answers 2

5

From Litecoin wiki:

Time warp bug[14]: the Bitcoin difficulty calculation is off by one block, so an attacker can repeatedly try to generate the last block of each retarget window, and use a fabricated timestamp of 2 hours into the future in order to make the time difference from the first block in the retarget window high, thus lowering the difficulty by 0.5%. Because of the bug, the bogus timestamp isn't used as the first block in the next retarget window, and therefore the 2 extra hours aren't being compensated for in the next difficulty calculation. Once the difficulty is low, the attacker can mine many fast coins, or in the case of a small chain, an attacker with 51% hash power could reduce the difficulty to 1 and mine a new fork from the genesis block. This isn't a feasible attack on Bitcoin, because the probability of repeatedly generating the last block once every 2 weeks at such high difficulties is negligible. Although fixing this issue in Bitcoin is possible, it should be done carefully (by adding rules that encourage nodes to upgrade over time) so to avoid a chain fork, i.e. old clients who didn't upgrade might operate with another difficulty and therefore disagree regarding which blocks are valid. In Litecoin this bug is fixed

The "off-by-one" or Time Warp Bug is caused because the difficulty calculation algorithm is not using overlapping periods, for the first recalc it uses blocks 1 up to 2016 and for the second it uses blocks 2017 up to 4032.

This alone is not a problem at all, but as the protocol has some allowance for time differences between the nodes this makes possible to lower the difficulty forging blocks with resolution time in the future.

The algorithm uses T(2016) - T(1) to calculate the speed of the network if block 2016 is created with a timestamp 2 hours in the future (max allowed by the protocol) then the difficulty will be a 0.5% lower of what it should be.

If then block 2017 is found and the time is real (T(2017) can be less than T(2016)) then the extra time added to block 2016 will not be compensated in the next recalculation as it would be if for block 2 used T(4032) - T(2016) to find the speed.

A more detailed attack scheme can be found at: https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772

5
  • Interesting. I am still not clear how this is necessarily a problem even after reading bitcointalk. This is a local time perturbation and will force an even higher difficulty of next block as competition for these easier blocks will be higher. Sounds like my calc may be correct, but I still have 0.4% error in my difficulty.
    – Cal Abel
    Jan 16, 2014 at 20:17
  • The target should be 1209000 as there are only 2015 time intervals in the generation of a 2016 blockchain.
    – frisco
    Jan 17, 2014 at 21:29
  • The main problem is that miners could work together to stablish a lower difficulty. The big issue is that an attacker with a really high hashing power can create a fork larger than the main one without publishing the blocks and then replace the main one, "erasing" all previous transactions and getting all the mininig rewards. If you check the message from ArtForz you can see that as the limits for travelling back in time are not fixed, you can forge a chain lowering the difficulty (the 2nd period lowers the diff by half), overtaking the main and then you can publish and replace the main one.
    – frisco
    Jan 17, 2014 at 21:44
  • It looked like there was an attack of this sort in the block chain around a block ID of 200,000 or so. It looked like two parallel chains developing, and then the forked chains ending up being orphaned. But as the other miners didn't accept the forked chain (some 60 blocks or so) the fork died. Thanks for the follow up.
    – Cal Abel
    Jan 20, 2014 at 1:09
  • I ran it the difficulty calculated for blocks 278318-280223 was 1.7023E9 which is much too low.
    – Cal Abel
    Jan 20, 2014 at 1:12
4

The retarget calculation is off-by-one. But it is not because it takes the difference between the time of the last block of the period and the time of the second block of this period (for instance block 2015 and block 1 for the first period) as it's often reported. This would make it an off-by-two!

To determine how long it took to mine 2016 blocks, the retarget calculation algorithm takes the difference between the time of the last block in the period and the time of the first block in the period. For instance for the very first period it takes the difference between blocks 2015 and 0. For the second period between blocks 4031 and 2016. And so on...

However, this computes how long it took to mine 2015 blocks! To see why consider we are interested in counting the intervals between the blocks. If we take the difference between block 2016 and block 0 we are counting the following intervals:

  • #1: Block 0 to block 1
  • #2: Block 1 to block 2
  • #3: Block 2 to block 3
  • ...
  • #2015: Block 2014 to block 2015

That's only 2015 block intervals counted. Counting 2016 intervals would have required taking the difference between the timestamp of the last block of this period and the last block of the previous period. I believe this is why Satoshi made the mistake: this would have needed to special case the very first period.

As the algorithm will compare this time to the expected 2 weeks it should have taken to mine 2016 blocks, the difficulty adjustment will have a small bias toward increasing the difficulty more than necessary. That's fine. A more serious concern is how this off-by-one makes the retarget periods not overlap, which enables the Timewarp attack.

0

Your Answer

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

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