src/checkpoints.cpp

   1 // Copyright (c) 2011 The Bitcoin developers
   2 // Copyright (c) 2011-2012 The PPCoin developers
   3 // Distributed under the MIT/X11 software license, see the accompanying
   4 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #include <boost/assign/list_of.hpp> // for 'map_list_of()'
   7 #include <boost/foreach.hpp>
   8
   9 #include "headers.h"
  10 #include "checkpoints.h"
  11
  12 namespace Checkpoints
  13 {
  14     typedef std::map<int, uint256> MapCheckpoints;   // hardened checkpoints
  15
  16     //
  17     // What makes a good checkpoint block?
  18     // + Is surrounded by blocks with reasonable timestamps
  19     //   (no blocks before with a timestamp after, none after with
  20     //    timestamp before)
  21     // + Contains no strange transactions
  22     //
  23     static MapCheckpoints mapCheckpoints =
  24         boost::assign::map_list_of
  25         ( 0, hashGenesisBlock )
  26         ; // ppcoin: no checkpoint yet; to be created in future releases
  27
  28     bool CheckHardened(int nHeight, const uint256& hash)
  29     {
  30         if (fTestNet) return true; // Testnet has no checkpoints
  31
  32         MapCheckpoints::const_iterator i = mapCheckpoints.find(nHeight);
  33         if (i == mapCheckpoints.end()) return true;
  34         return hash == i->second;
  35     }
  36
  37     int GetTotalBlocksEstimate()
  38     {
  39         if (fTestNet) return 0;
  40
  41         return mapCheckpoints.rbegin()->first;
  42     }
  43
  44     CBlockIndex* GetLastCheckpoint(const std::map<uint256, CBlockIndex*>& mapBlockIndex)
  45     {
  46         if (fTestNet) return NULL;
  47
  48         int64 nResult;
  49         BOOST_REVERSE_FOREACH(const MapCheckpoints::value_type& i, mapCheckpoints)
  50         {
  51             const uint256& hash = i.second;
  52             std::map<uint256, CBlockIndex*>::const_iterator t = mapBlockIndex.find(hash);
  53             if (t != mapBlockIndex.end())
  54                 return t->second;
  55         }
  56         return NULL;
  57     }
  58
  59     // ppcoin: synchronized checkpoint (centrally broadcasted)
  60     uint256 hashSyncCheckpoint;
  61     CSyncCheckpoint checkpointMessage;
  62     CSyncCheckpoint checkpointMessagePending;
  63     uint256 hashInvalidCheckpoint = 0;
  64     CCriticalSection cs_hashSyncCheckpoint;
  65
  66     // ppcoin: get last synchronized checkpoint
  67     CBlockIndex* GetLastSyncCheckpoint()
  68     {
  69         CRITICAL_BLOCK(cs_hashSyncCheckpoint)
  70         {
  71             if (!mapBlockIndex.count(hashSyncCheckpoint))
  72                 error("GetSyncCheckpoint: block index missing for current sync-checkpoint %s", hashSyncCheckpoint.ToString().c_str());
  73             else
  74                 return mapBlockIndex[hashSyncCheckpoint];
  75         }
  76         return NULL;
  77     }
  78
  79     // ppcoin: only descendant of current sync-checkpoint is allowed
  80     bool ValidateSyncCheckpoint(uint256 hashCheckpoint)
  81     {
  82         if (!mapBlockIndex.count(hashSyncCheckpoint))
  83             return error("ValidateSyncCheckpoint: block index missing for current sync-checkpoint %s", hashSyncCheckpoint.ToString().c_str());
  84         if (!mapBlockIndex.count(hashCheckpoint))
  85             return error("ValidateSyncCheckpoint: block index missing for received sync-checkpoint %s", hashCheckpoint.ToString().c_str());
  86
  87         CBlockIndex* pindexSyncCheckpoint = mapBlockIndex[hashSyncCheckpoint];
  88         CBlockIndex* pindexCheckpointRecv = mapBlockIndex[hashCheckpoint];
  89
  90         if (pindexCheckpointRecv->nHeight <= pindexSyncCheckpoint->nHeight)
  91         {
  92             // Received an older checkpoint, trace back from current checkpoint
  93             // to the same height of the received checkpoint to verify
  94             // that current checkpoint should be a descendant block
  95             CBlockIndex* pindex = pindexSyncCheckpoint;
  96             while (pindex->nHeight > pindexCheckpointRecv->nHeight)
  97                 if (!(pindex = pindex->pprev))
  98                     return error("ValidateSyncCheckpoint: pprev1 null - block index structure failure");
  99             if (pindex->GetBlockHash() != hashCheckpoint)
 100             {
 101                 hashInvalidCheckpoint = hashCheckpoint;
 102                 return error("ValidateSyncCheckpoint: new sync-checkpoint %s is conflicting with current sync-checkpoint %s", hashCheckpoint.ToString().c_str(), hashSyncCheckpoint.ToString().c_str());
 103             }
 104             return false; // ignore older checkpoint
 105         }
 106
 107         // Received checkpoint should be a descendant block of the current
 108         // checkpoint. Trace back to the same height of current checkpoint
 109         // to verify.
 110         CBlockIndex* pindex = pindexCheckpointRecv;
 111         while (pindex->nHeight > pindexSyncCheckpoint->nHeight)
 112             if (!(pindex = pindex->pprev))
 113                 return error("ValidateSyncCheckpoint: pprev2 null - block index structure failure");
 114         if (pindex->GetBlockHash() != hashSyncCheckpoint)
 115         {
 116             hashInvalidCheckpoint = hashCheckpoint;
 117             return error("ValidateSyncCheckpoint: new sync-checkpoint %s is not a descendant of current sync-checkpoint %s", hashCheckpoint.ToString().c_str(), hashSyncCheckpoint.ToString().c_str());
 118         }
 119         return true;
 120     }
 121
 122     bool AcceptPendingSyncCheckpoint()
 123     {
 124         CRITICAL_BLOCK(cs_hashSyncCheckpoint)
 125         {
 126             if ((!checkpointMessagePending.IsNull()) && mapBlockIndex.count(checkpointMessagePending.hashCheckpoint))
 127             {
 128                 if (!ValidateSyncCheckpoint(checkpointMessagePending.hashCheckpoint))
 129                 {
 130                     checkpointMessagePending.SetNull();
 131                     return false;
 132                 }
 133
 134                 CTxDB txdb;
 135                 CBlockIndex* pindexCheckpoint = mapBlockIndex[checkpointMessagePending.hashCheckpoint];
 136                 if (!pindexCheckpoint->IsInMainChain())
 137                 {
 138                     txdb.TxnBegin();
 139                     if (!Reorganize(txdb, pindexCheckpoint))
 140                     {
 141                         txdb.TxnAbort();
 142                         hashInvalidCheckpoint = checkpointMessagePending.hashCheckpoint;
 143                         return error("ProcessSyncCheckpoint: Reorganize failed for sync checkpoint %s", checkpointMessagePending.hashCheckpoint.ToString().c_str());
 144                     }
 145                 }
 146
 147                 txdb.TxnBegin();
 148                 if (!txdb.WriteSyncCheckpoint(checkpointMessagePending.hashCheckpoint))
 149                 {
 150                     txdb.TxnAbort();
 151                     return error("AcceptPendingSyncCheckpoint() : failed to write to db sync checkpoint %s\n", checkpointMessagePending.hashCheckpoint.ToString().c_str());
 152                 }
 153                 if (!txdb.TxnCommit())
 154                     return error("AcceptPendingSyncCheckpoint() : failed to commit to db sync checkpoint %s\n", checkpointMessagePending.hashCheckpoint.ToString().c_str());
 155                 txdb.Close();
 156
 157                 hashSyncCheckpoint = checkpointMessagePending.hashCheckpoint;
 158                 checkpointMessage = checkpointMessagePending;
 159                 checkpointMessagePending.SetNull();
 160                 printf("AcceptPendingSyncCheckpoint : sync-checkpoint at %s\n", hashSyncCheckpoint.ToString().c_str());
 161                 // relay the checkpoint
 162                 CRITICAL_BLOCK(cs_hashSyncCheckpoint)
 163                     BOOST_FOREACH(CNode* pnode, vNodes)
 164                         checkpointMessage.RelayTo(pnode);
 165                 return true;
 166             }
 167         }
 168
 169         return false;
 170     }
 171
 172     uint256 AutoSelectSyncCheckpoint()
 173     {
 174         // select block roughly 8 hours ago
 175         CBlockIndex *pindex = mapBlockIndex[hashSyncCheckpoint];
 176         while (pindex->pnext && pindex->pnext->GetBlockTime() + AUTO_CHECKPOINT_MIN_SPAN <= GetAdjustedTime())
 177             pindex = pindex->pnext;
 178         return pindex->GetBlockHash();
 179     }
 180
 181     // Check against synchronized checkpoint
 182     bool CheckSync(const uint256& hashBlock, const CBlockIndex* pindexPrev)
 183     {
 184         if (fTestNet) return true; // Testnet has no checkpoints
 185         int nHeight = pindexPrev->nHeight + 1;
 186
 187         CRITICAL_BLOCK(cs_hashSyncCheckpoint)
 188         {
 189             // sync-checkpoint should always be accepted block
 190             assert(mapBlockIndex.count(hashSyncCheckpoint));
 191             const CBlockIndex* pindexSync = mapBlockIndex[hashSyncCheckpoint];
 192
 193             if (nHeight > pindexSync->nHeight)
 194             {
 195                 // trace back to same height as sync-checkpoint
 196                 const CBlockIndex* pindex = pindexPrev;
 197                 while (pindex->nHeight > pindexSync->nHeight)
 198                     if (!(pindex = pindex->pprev))
 199                         return error("CheckSync: pprev null - block index structure failure");
 200                 if (pindex->nHeight < pindexSync->nHeight || pindex->GetBlockHash() != hashSyncCheckpoint)
 201                     return false; // only descendant of sync-checkpoint can pass check
 202             }
 203             if (nHeight == pindexSync->nHeight && hashBlock != hashSyncCheckpoint)
 204                 return false; // same height with sync-checkpoint
 205             if (nHeight < pindexSync->nHeight && !mapBlockIndex.count(hashBlock))
 206                 return false; // lower height than sync-checkpoint
 207         }
 208         return true;
 209     }
 210
 211     bool WantedByPendingSyncCheckpoint(uint256 hashBlock)
 212     {
 213         CRITICAL_BLOCK(cs_hashSyncCheckpoint)
 214         {
 215             if (checkpointMessagePending.IsNull())
 216                 return false;
 217             if (hashBlock == checkpointMessagePending.hashCheckpoint)
 218                 return true;
 219             if (mapOrphanBlocks.count(checkpointMessagePending.hashCheckpoint)
 220                 && hashBlock == WantedByOrphan(mapOrphanBlocks[checkpointMessagePending.hashCheckpoint]))
 221                 return true;
 222         }
 223         return false;
 224     }
 225
 226     // ppcoin: automatic checkpoint (represented by height of checkpoint)
 227     int nAutoCheckpoint = 0;
 228     int nBranchPoint = 0;    // branch point to alternative branch
 229
 230     // ppcoin: check automatic checkpoint
 231     // To pass the check:
 232     //   - All ancestors (including the block itself) have block index already
 233     //   - The immediate ancestor in main chain must not have height less than
 234     //     checkpoint height
 235     bool CheckAuto(const CBlockIndex *pindex)
 236     {
 237         while (pindex)
 238         {
 239             if (pindex->IsInMainChain())
 240             {
 241                 if (pindex->nHeight >= nAutoCheckpoint)
 242                     return true;
 243                 else
 244                 {
 245                     nBranchPoint = pindex->nHeight;
 246                     return error("Checkpoints: new block on alternative branch at height=%d before auto checkpoint at height=%d", pindex->nHeight, nAutoCheckpoint);
 247                 }
 248             }
 249             else
 250                 pindex = pindex->pprev;
 251         }
 252         return error("Checkpoints: failed to find any ancestor on main chain for the new block - internal error");
 253     }
 254
 255     // ppcoin: get next chain checkpoint
 256     int GetNextChainCheckpoint(const CBlockIndex *pindexLast)
 257     {
 258         CBigNum bnTarget;
 259         CBigNum bnTargetMax = 0;  // max target of all blocks since checkpoint
 260         CBigNum bnTargetMin = 0;  // min target of all candidate checkpoints
 261         int nMinTargetHeight = 0; // min target height of candidate checkpoints
 262         int nCheckpointMin = 0;   // minimum candidate checkpoint
 263         int nCheckpointMax = 0;   // maximum candidate checkpoint
 264         int nDepth = pindexLast->nHeight - pindexLast->nCheckpoint;
 265         const CBlockIndex *pindex = pindexLast;
 266         while (nDepth >= 0 && pindex)
 267         {
 268             bnTarget.SetCompact(pindex->nBits);
 269             if (bnTarget > bnTargetMax)
 270                 bnTargetMax = bnTarget;
 271             if (nCheckpointMax > 0 && bnTarget < bnTargetMin)
 272             {
 273                 bnTargetMin = bnTarget;
 274                 nMinTargetHeight = pindex->nHeight;
 275             }
 276             if (nCheckpointMax == 0 && pindexLast->GetBlockTime() - pindex->GetBlockTime() > AUTO_CHECKPOINT_MIN_SPAN)
 277             {
 278                 nCheckpointMax = pindex->nHeight;
 279                 bnTargetMin.SetCompact(pindex->nBits);
 280                 nMinTargetHeight = pindex->nHeight;
 281             }
 282             if (pindexLast->GetBlockTime() - pindex->GetBlockTime() < AUTO_CHECKPOINT_MAX_SPAN)
 283                 nCheckpointMin = pindex->nHeight;
 284             pindex = pindex->pprev;
 285             nDepth--;
 286         }
 287
 288         assert (nDepth == -1);  // arrive at chain checkpoint now
 289
 290         printf("Checkpoints: min=%d max=%d tminheight=%d tmin=0x%08x tmax=0x%08x\n",
 291             nCheckpointMin, nCheckpointMax, nMinTargetHeight,
 292             bnTargetMin.GetCompact(), bnTargetMax.GetCompact());
 293         if (nCheckpointMax == 0) // checkpoint stays if max candidate not found
 294             return pindexLast->nCheckpoint;
 295
 296         if (bnTargetMin * 100 > bnTargetMax * 90)
 297             return nCheckpointMax;
 298         if (bnTarget * 100 > bnTargetMax * 90)
 299             return nMinTargetHeight;
 300         else
 301             return nCheckpointMin;
 302     }
 303
 304     // ppcoin: get next auto checkpoint from the new chain checkpoint
 305     int GetNextAutoCheckpoint(int nCheckpoint)
 306     {
 307         return (std::max(nAutoCheckpoint, nCheckpoint));
 308     }
 309
 310     // ppcoin: advance to next automatic checkpoint
 311     void AdvanceAutoCheckpoint(int nCheckpoint)
 312     {
 313         nAutoCheckpoint = GetNextAutoCheckpoint(nCheckpoint);
 314         printf("Checkpoints: auto checkpoint now at height=%d\n", nAutoCheckpoint);
 315     }
 316
 317     // ppcoin: reset auto checkpoint
 318     bool ResetAutoCheckpoint(int nCheckpoint)
 319     {
 320         if (nCheckpoint <= 0 || nCheckpoint > nBestHeight)
 321             return error("ResetAutoCheckpoint() : new checkpoint invalid");
 322         if (nCheckpoint >= nAutoCheckpoint)
 323             return error("ResetAutoCheckpoint() : new checkpoint not earlier than current auto checkpoint");
 324         CTxDB txdb;
 325         txdb.TxnBegin();
 326         if (!txdb.WriteAutoCheckpoint(nCheckpoint, true))
 327             return error("ResetAutoCheckpoint() : database write failed");
 328         if (!txdb.TxnCommit())
 329             return error("ResetAutoCheckpoint() : database commit failed");
 330         nAutoCheckpoint = nCheckpoint;
 331         nBranchPoint = 0;  // clear branch point
 332
 333         // clear ban list to accept alternative branches
 334         CRITICAL_BLOCK(cs_vNodes)
 335         {
 336             BOOST_FOREACH(CNode* pnode, vNodes)
 337                 pnode->ClearBanned();
 338         }
 339
 340         return true;
 341     }
 342 }
 343
 344 // ppcoin: sync-checkpoint master key
 345 const std::string CSyncCheckpoint::strMasterPubKey = "0424f20205e5da98ba632bbd278a11a6499585f62bfb2c782377ef59f0251daab8085fc31471bcb8180bc75ed0fa41bb50c7c084511d54015a3a5241d645c7268a";
 346
 347 // ppcoin: verify signature of sync-checkpoint message
 348 bool CSyncCheckpoint::CheckSignature()
 349 {
 350     CKey key;
 351     if (!key.SetPubKey(ParseHex(CSyncCheckpoint::strMasterPubKey)))
 352         return error("CSyncCheckpoint::CheckSignature() : SetPubKey failed");
 353     if (!key.Verify(Hash(vchMsg.begin(), vchMsg.end()), vchSig))
 354         return error("CSyncCheckpoint::CheckSignature() : verify signature failed");
 355
 356     // Now unserialize the data
 357     CDataStream sMsg(vchMsg);
 358     sMsg >> *(CUnsignedSyncCheckpoint*)this;
 359     return true;
 360 }
 361
 362 // ppcoin: process synchronized checkpoint
 363 bool CSyncCheckpoint::ProcessSyncCheckpoint(CNode* pfrom)
 364 {
 365     if (!CheckSignature())
 366         return false;
 367
 368     CRITICAL_BLOCK(Checkpoints::cs_hashSyncCheckpoint)
 369     {
 370         if (!mapBlockIndex.count(hashCheckpoint))
 371         {
 372             // We haven't received the checkpoint chain, keep the checkpoint as pending
 373             Checkpoints::checkpointMessagePending = *this;
 374             printf("ProcessSyncCheckpoint: pending for sync-checkpoint %s\n", hashCheckpoint.ToString().c_str());
 375             // Ask this guy to fill in what we're missing
 376             if (pfrom)
 377             {
 378                 pfrom->PushGetBlocks(pindexBest, hashCheckpoint);
 379                 // ask directly as well in case rejected earlier by duplicate
 380                 // proof-of-stake because getblocks may not get it this time
 381                 pfrom->AskFor(CInv(MSG_BLOCK, mapOrphanBlocks.count(hashCheckpoint)? WantedByOrphan(mapOrphanBlocks[hashCheckpoint]) : hashCheckpoint));
 382             }
 383             return false;
 384         }
 385
 386         if (!Checkpoints::ValidateSyncCheckpoint(hashCheckpoint))
 387             return false;
 388
 389         CTxDB txdb;
 390         CBlockIndex* pindexCheckpoint = mapBlockIndex[hashCheckpoint];
 391         if (!pindexCheckpoint->IsInMainChain())
 392         {
 393             // checkpoint chain received but not yet main chain
 394             txdb.TxnBegin();
 395             if (!Reorganize(txdb, pindexCheckpoint))
 396             {
 397                 txdb.TxnAbort();
 398                 Checkpoints::hashInvalidCheckpoint = hashCheckpoint;
 399                 return error("ProcessSyncCheckpoint: Reorganize failed for sync checkpoint %s", hashCheckpoint.ToString().c_str());
 400             }
 401         }
 402
 403         txdb.TxnBegin();
 404         if (!txdb.WriteSyncCheckpoint(hashCheckpoint))
 405         {
 406             txdb.TxnAbort();
 407             return error("ProcessSyncCheckpoint(): failed to write to db sync checkpoint %s", hashCheckpoint.ToString().c_str());
 408         }
 409         if (!txdb.TxnCommit())
 410             return error("ProcessSyncCheckpoint(): failed to commit to db sync checkpoint %s", hashCheckpoint.ToString().c_str());
 411         txdb.Close();
 412
 413         Checkpoints::hashSyncCheckpoint = hashCheckpoint;
 414         Checkpoints::checkpointMessage = *this;
 415         Checkpoints::checkpointMessagePending.SetNull();
 416         printf("ProcessSyncCheckpoint: sync-checkpoint at %s\n", hashCheckpoint.ToString().c_str());
 417     }
 418     return true;
 419 }