Alert if it is very likely we are getting a bad chain #5947

gavinandresen commented at 3:37 PM on March 26, 2015: contributor

Create a monitoring task called every ten minutes that counts how many blocks have been found in the last four hours.

If very few or too many have been found, an alert is triggered.

"Very few" and "too many" are set based on a false positive rate of once every fifty years of constant running with constant hashing power, which works out to getting 5 or fewer or 48 or more blocks in four hours (instead of the average of 24).

Only one alert per day is triggered, so if you get disconnected from the network (or are being Sybil'ed) -alertnotify will be triggered after 3.5 hours but you won't get another -alertnotify for 24 hours.

Tested with a new unit test and by running on the main network with -debug=partitioncheck

Run test/test_bitcoin --log_level=message to see the alert messages: WARNING: check your network connection, 3 blocks received in the last 4 hours (24 expected) WARNING: abnormally high number of blocks generated, 60 blocks received in the last 4 hours (24 expected)

The -debug=partitioncheck debug.log messages look like: PartitionCheck : Found 22 blocks in the last 4 hours PartitionCheck : likelihood: 0.0777702

gavinandresen force-pushed on Mar 26, 2015

gavinandresen commented at 6:40 PM on March 26, 2015: contributor

As suggested by @gmaxwell : changed names from "SybilCheck" to "PartitionCheck"

He also suggested replacing the boost::math::poisson calculations with hard-coded constants to get rid of the dependency on boost/math/distributions. I think the purpose of the code is clearer doing the calculations here, and it is easier to update if "we" decide that 4 hours or 1-false-positive-in-50-years either need to change or need to become command-line params. @sipa volunteered in IRC to write a little scheduler to avoid the VM overhead of another boost::thread, this will be rebased if that happens.

laanwj added the label UTXO Db and Indexes on Mar 27, 2015

gavinandresen force-pushed on Mar 27, 2015

in src/main.cpp:None in 687fc39bcc outdated

1704 | +    LogPrint("partitioncheck", "%s : Found %d blocks in the last %d hours\n", __func__, nBlocks, SPAN_HOURS);
1705 | +    LogPrint("partitioncheck", "%s : likelihood: %g\n", __func__, p);
1706 | +
1707 | +    // Aim for one false-positive about every fifty years of normal running:
1708 | +    const int FIFTY_YEARS = 50*365*24*60*60;
1709 | +    double alertThreshold = 1.0 / (FIFTY_YEARS / params.TargetSpacing());

dgenr8 commented at 8:10 PM on March 28, 2015:

The chain target spacing doesn't matter, only the independent sample interval. You are taking an independent sample every SPAN_SECONDS, so this should be

double alertThreshold = 1.0 / (FIFTY_YEARS / SPAN_SECONDS);

This works out to 5 or fewer, or 48 or more blocks. It might be worth randomly using a higher p-value, so an attacker doesn't know exactly what to target.

gavinandresen force-pushed on Mar 30, 2015

gavinandresen commented at 6:05 PM on March 30, 2015: contributor

Fixed the threshold calculation (thanks @dgenr8 ). RE: making the threshold semi-random so attackers don't know exactly what block generation rate to target: block-finding is already a random process, I don't think we need to add more randomness; or, in other words, unless the attacker has an absolutely astounding amount of hashing power (in which case all sorts of assumptions fall apart) their block generation rate will be random anyway.

dgenr8 commented at 9:01 PM on March 30, 2015: contributor

@gavinandresen Ok, it was just a "random" idea anyway ;)

gavinandresen force-pushed on Apr 2, 2015

gavinandresen commented at 6:25 PM on April 2, 2015: contributor

Tweaked to use CScheduler from #5964 instead of spawning Yet Another Thread.

gavinandresen force-pushed on Apr 2, 2015

gavinandresen force-pushed on Apr 3, 2015

dgenr8 commented at 4:00 AM on April 4, 2015: contributor

Looks like the earlier tweak was lost in the rebase.

gavinandresen force-pushed on Apr 7, 2015

gavinandresen force-pushed on Apr 8, 2015

gavinandresen force-pushed on Apr 10, 2015

gavinandresen commented at 5:00 PM on April 10, 2015: contributor

Tweak re-applied; I'm going to wait for #5964 to get merged before rebasing to fix the merge conflict.

gavinandresen force-pushed on Apr 26, 2015

gavinandresen force-pushed on May 12, 2015

gavinandresen commented at 2:43 PM on May 12, 2015: contributor

Rebased on #5964.

Alert if it is very likely we are getting a bad chain

Create a monitoring task that counts how many blocks have been found in the last four hours.

If very few or too many have been found, an alert is triggered.

"Very few" and "too many" are set based on a false positive rate of once every fifty years of constant running with constant hashing power, which works out to getting 5 or fewer or 48 or more blocks in four hours (instead of the average of 24).

Only one alert per day is triggered, so if you get disconnected from the network (or are being Sybil'ed) -alertnotify will be triggered after 3.5 hours but you won't get another -alertnotify for 24 hours.

Tested with a new unit test and by running on the main network with -debug=partitioncheck

Run test/test_bitcoin --log_level=message to see the alert messages:
    WARNING: check your network connection, 3 blocks received in the last 4 hours (24 expected)
    WARNING: abnormally high number of blocks generated, 60 blocks received in the last 4 hours (24 expected)

The -debug=partitioncheck debug.log messages look like:
    ThreadPartitionCheck : Found 22 blocks in the last 4 hours
    ThreadPartitionCheck : likelihood: 0.0777702

36cba8f118

gavinandresen force-pushed on May 14, 2015

laanwj commented at 9:07 AM on May 24, 2015: member

utACK

in src/test/alert_tests.cpp:None in 36cba8f118

   6 | @@ -7,10 +7,13 @@
   7 |  //
   8 |  
   9 |  #include "alert.h"
  10 | +#include "chain.h"
  11 | +#include "chainparams.h"
  12 |  #include "clientversion.h"
  13 |  #include "data/alertTests.raw.h"
  14 |  
  15 |  #include "chainparams.h"

Diapolo commented at 5:42 PM on May 24, 2015:

As I wasn't allowed to sort this ;) just a quick nit, seems you now have a dup include of chainparams.h.

Diapolo commented at 9:00 AM on May 26, 2015:

Seems like we don't care about such nits anymore...

laanwj merged this on May 26, 2015

laanwj closed this on May 26, 2015

laanwj referenced this in commit e9af4e65b5 on May 26, 2015

sipa commented at 1:26 PM on May 26, 2015: member

Maybe my comment got lost in the commits here, but the math is still wrong.

gavinandresen commented at 1:39 PM on May 26, 2015: contributor

@sipa : Your comments did get lost in rebases/commits. Can you submit a fix? I promise to test/ACK quickly...

laanwj commented at 3:49 PM on May 26, 2015: member

@sipa Sorry, I have not not seen your comment (it is not in the thread's history in my mail either). Should this be reverted?

sipa commented at 4:38 PM on May 26, 2015: member

I believe it will just trigger more frequently than intended . I'll improve the calculation next week.

MarcoFalke locked this on Sep 8, 2021