text: // Copyright (c) 2009-2012 The Bitcoin developers
  // Distributed under the MIT/X11 software license, see the accompanying
  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  
  #include <boost/assign/list_of.hpp> // for 'map_list_of()'
  #include <boost/foreach.hpp>
  
  #include "checkpoints.h"
  
  #include "txdb.h"
  #include "main.h"
  #include "uint256.h"
  
  namespace Checkpoints
  {
      typedef std::map<int, uint256> MapCheckpoints;
  
      //
      // What makes a good checkpoint block?
      // + Is surrounded by blocks with reasonable timestamps
      //   (no blocks before with a timestamp after, none after with
      //    timestamp before)
      // + Contains no strange transactions
      //
      static MapCheckpoints mapCheckpoints =
          boost::assign::map_list_of
          
           ( 0 , hashGenesisBlock )
           // ( 1 , uint256("0x00001b9a7322210976d18ab02e32ec4fca163b30c9ca20c8297c5907bca0bfa7") )
           // ( 2 , uint256("0x0000230ab04cb64fd75fb445945c4a489ede794286b649e5984bedf254e702b9") )
           // ( 3 , uint256("0x00001c1688fcc6aa8f82d4f063b8675deaebc305fdc1ea520a599ff9a4f59176") )
           // ( 4 , uint256("0x0000019778f3a49180e4deffe7bae62f3e38c84be33b93ff69f8125c02d5ba63") )
           // ( 5 , uint256("0x0000006b0ca4df095393b2fc9ac8426a608a1c7d5fcb44b44d5c2381c4d0d270") )
           // ( 6 , uint256("0x0000028a761ef6a4a496328d1100f459bdbbca6bd9e5b10abccf37c5be7d6a1e") )
           // ( 7 , uint256("0x000000a808886416d26c8e854bb176b81187c0bf6debaea3478533b89304c316") )
           // ( 8 , uint256("0x00000009fc89e4a828154fd85c4ff43229e40b35cfd690c6ac74ec1c5d36e3f6") )
           // ( 9 , uint256("0x0000006003a770dc4b3a5cfc0a401df3a052979419c6969ba6ad2518b3624936") )
           // ( 10 , uint256("0x000000f2e8b8d6cf772d7f7aaf7dc273b9259d91edd9a8b1b3da7f92e9e87335") )
           // ( 20 , uint256("0x000000041864a3a57623f6bf4bfb03c8ad182a1a3070589aeba378894d9311e7") )
           // ( 30 , uint256("0x00000042771e703aaa92a10fd14d442d4613d23281de3271a1968f5f1144bddb") )
           // ( 40 , uint256("0x000000131049a729eea15718a42ff57a187dbe7c9ade84683d45d77d9454e1aa") )
           // ( 50 , uint256("0x00000241bf431d394221cfb13d8cbdaa560dced9e3274dc183377e983017b05c") )
           // ( 60 , uint256("0x0000003441069ca669a97534a1a152c705b28ceffdf02b01ffe3739d1e0bef8d") )
           // ( 70 , uint256("0x00000084bc8bda7e2d406b0458ec658c7580d891e44699963f40ace4044e7506") )
           // ( 80 , uint256("0x000000161ff1967781e99164ebe57b2318f56ca3167efb9a2263907a68829dbb") )
           // ( 90 , uint256("0x0000000d0d1369bcb7bc39c5a21c58ef33f18dd9f5561d56e6d127b5ae39e017") )
           // ( 100 , uint256("0x00000054af449483e6c935bf959fd776f481585295a8005dea36bd1d1272e6fb") )
           // ( 200 , uint256("0x0000007bba3634ea4766808d8ba1fa7e9d9f8ffb9674f959dd8f4daef52adeb3") )
           // ( 300 , uint256("0x0000000633dfc7b0b273dcf6b077b958ae7d432acc1c8175f0e975199936afc4") )
           // ( 400 , uint256("0x0000003a9ac7ae68f69daf0d8760745fe56794d8b9accaf2ab51cdab7430689f") )
           // ( 500 , uint256("0x00000003bf0eded40a8fec943c37e4eee12db5e6620e8ad12ff71a0f89fe1d65") )
           // ( 1000 , uint256("0x000000ae67f731ff9c159326e3e6996392e049808a4680df157628cab1045441") )
           // ( 2000 , uint256("0x00000059c578df580c0bc959ff15c0e5751b8a7541c2dfa572ddd43bc2f9c174") )
           // ( 3000 , uint256("0x000000611705a4bba6e7c0ae5bd7bfc06d9d4ce22c2aecc784768aef57ff80e8") )
           // ( 4000 , uint256("0x0000005ca1e9d3e61ebd7555bc5c50c066173df1e9dd39c6fdb2b3015b46646b") )
           // ( 5000 , uint256("0x0000000000015c3748e38c2565cf3c9e10d9379136d59e0c543c9ca74db2118f") )
           // ( 6000 , uint256("0x0000000000083692fe01b9348b59cdd58e8d6106929ef1b8df11cfc060e71c6b") )
           // ( 6325 , uint256("0x000000000010e152305063e106aa54c84ba7606ecdcaafa32832f1a8bb8c0cc3") )
           // ( 6326 , uint256("0x9cdf7daa209bfec16b1608f1a633c9b399025ca8508c86af7601ef33d8a9ff16") )
           // ( 6365 , uint256("0xd5a1f5c31dd2ed5445dc4631dc80abfc30dd274df480994ccdcc04c852fa9584") )
           // ( 6366 , uint256("0xce0bbebd902ef72992336622b8cbf87513316afaff4be0106c288352fb667dd1") )
           // ( 6367 , uint256("0xe4629ecd00af7b6ea48ba16a1a451e1f56c87e6f2c78d79ef1158bcd997f5d18") )
           // ( 6368 , uint256("0xbf05ca75e200652ad07de304807eb1368b617064fb4d03f671a85d4e00b23231") )
           // ( 6369 , uint256("0xf990be24f3dad91a6bce39a18fd386cc366fc34a887d4cef275094659f7aa88c") )
  ;
  
      // TestNet has no checkpoints
      static MapCheckpoints mapCheckpointsTestnet =
          boost::assign::map_list_of
          ( 0, hashGenesisBlockTestNet )
          ;
  
      bool CheckHardened(int nHeight, const uint256& hash)
      {
          MapCheckpoints& checkpoints = (fTestNet ? mapCheckpointsTestnet : mapCheckpoints);
  
          MapCheckpoints::const_iterator i = checkpoints.find(nHeight);
          if (i == checkpoints.end()) return true;
          return hash == i->second;
      }
  
      int GetTotalBlocksEstimate()
      {
          MapCheckpoints& checkpoints = (fTestNet ? mapCheckpointsTestnet : mapCheckpoints);
  
          return checkpoints.rbegin()->first;
      }
  
      CBlockIndex* GetLastCheckpoint(const std::map<uint256, CBlockIndex*>& mapBlockIndex)
      {
          MapCheckpoints& checkpoints = (fTestNet ? mapCheckpointsTestnet : mapCheckpoints);
  
          BOOST_REVERSE_FOREACH(const MapCheckpoints::value_type& i, checkpoints)
          {
              const uint256& hash = i.second;
              std::map<uint256, CBlockIndex*>::const_iterator t = mapBlockIndex.find(hash);
              if (t != mapBlockIndex.end())
                  return t->second;
          }
          return NULL;
      }
  
      // ppcoin: synchronized checkpoint (centrally broadcasted)
      uint256 hashSyncCheckpoint = 0;
      uint256 hashPendingCheckpoint = 0;
      CSyncCheckpoint checkpointMessage;
      CSyncCheckpoint checkpointMessagePending;
      uint256 hashInvalidCheckpoint = 0;
      CCriticalSection cs_hashSyncCheckpoint;
  
      // ppcoin: get last synchronized checkpoint
      CBlockIndex* GetLastSyncCheckpoint()
      {
          LOCK(cs_hashSyncCheckpoint);
          if (!mapBlockIndex.count(hashSyncCheckpoint))
              error("GetSyncCheckpoint: block index missing for current sync-checkpoint %s", hashSyncCheckpoint.ToString().c_str());
          else
              return mapBlockIndex[hashSyncCheckpoint];
          return NULL;
      }
  
      // ppcoin: only descendant of current sync-checkpoint is allowed
      bool ValidateSyncCheckpoint(uint256 hashCheckpoint)
      {
          if (!mapBlockIndex.count(hashSyncCheckpoint))
              return error("ValidateSyncCheckpoint: block index missing for current sync-checkpoint %s", hashSyncCheckpoint.ToString().c_str());
          if (!mapBlockIndex.count(hashCheckpoint))
              return error("ValidateSyncCheckpoint: block index missing for received sync-checkpoint %s", hashCheckpoint.ToString().c_str());
  
          CBlockIndex* pindexSyncCheckpoint = mapBlockIndex[hashSyncCheckpoint];
          CBlockIndex* pindexCheckpointRecv = mapBlockIndex[hashCheckpoint];
  
          if (pindexCheckpointRecv->nHeight <= pindexSyncCheckpoint->nHeight)
          {
              // Received an older checkpoint, trace back from current checkpoint
              // to the same height of the received checkpoint to verify
              // that current checkpoint should be a descendant block
              CBlockIndex* pindex = pindexSyncCheckpoint;
              while (pindex->nHeight > pindexCheckpointRecv->nHeight)
                  if (!(pindex = pindex->pprev))
                      return error("ValidateSyncCheckpoint: pprev null - block index structure failure");
              if (pindex->GetBlockHash() != hashCheckpoint)
              {
                  hashInvalidCheckpoint = hashCheckpoint;
                  return error("ValidateSyncCheckpoint: new sync-checkpoint %s is conflicting with current sync-checkpoint %s", hashCheckpoint.ToString().c_str(), hashSyncCheckpoint.ToString().c_str());
              }
              return false; // ignore older checkpoint
          }
  
          // Received checkpoint should be a descendant block of the current
          // checkpoint. Trace back to the same height of current checkpoint
          // to verify.
          CBlockIndex* pindex = pindexCheckpointRecv;
          while (pindex->nHeight > pindexSyncCheckpoint->nHeight)
              if (!(pindex = pindex->pprev))
                  return error("ValidateSyncCheckpoint: pprev2 null - block index structure failure");
          if (pindex->GetBlockHash() != hashSyncCheckpoint)
          {
              hashInvalidCheckpoint = hashCheckpoint;
              return error("ValidateSyncCheckpoint: new sync-checkpoint %s is not a descendant of current sync-checkpoint %s", hashCheckpoint.ToString().c_str(), hashSyncCheckpoint.ToString().c_str());
          }
          return true;
      }
  
      bool WriteSyncCheckpoint(const uint256& hashCheckpoint)
      {
          CTxDB txdb;
          txdb.TxnBegin();
          if (!txdb.WriteSyncCheckpoint(hashCheckpoint))
          {
              txdb.TxnAbort();
              return error("WriteSyncCheckpoint(): failed to write to db sync checkpoint %s", hashCheckpoint.ToString().c_str());
          }
          if (!txdb.TxnCommit())
              return error("WriteSyncCheckpoint(): failed to commit to db sync checkpoint %s", hashCheckpoint.ToString().c_str());
  
          Checkpoints::hashSyncCheckpoint = hashCheckpoint;
          return true;
      }
  
      bool AcceptPendingSyncCheckpoint()
      {
          LOCK(cs_hashSyncCheckpoint);
          if (hashPendingCheckpoint != 0 && mapBlockIndex.count(hashPendingCheckpoint))
          {
              if (!ValidateSyncCheckpoint(hashPendingCheckpoint))
              {
                  hashPendingCheckpoint = 0;
                  checkpointMessagePending.SetNull();
                  return false;
              }
  
              CTxDB txdb;
              CBlockIndex* pindexCheckpoint = mapBlockIndex[hashPendingCheckpoint];
              if (!pindexCheckpoint->IsInMainChain())
              {
                  CBlock block;
                  if (!block.ReadFromDisk(pindexCheckpoint))
                      return error("AcceptPendingSyncCheckpoint: ReadFromDisk failed for sync checkpoint %s", hashPendingCheckpoint.ToString().c_str());
                  if (!block.SetBestChain(txdb, pindexCheckpoint))
                  {
                      hashInvalidCheckpoint = hashPendingCheckpoint;
                      return error("AcceptPendingSyncCheckpoint: SetBestChain failed for sync checkpoint %s", hashPendingCheckpoint.ToString().c_str());
                  }
              }
  
              if (!WriteSyncCheckpoint(hashPendingCheckpoint))
                  return error("AcceptPendingSyncCheckpoint(): failed to write sync checkpoint %s", hashPendingCheckpoint.ToString().c_str());
              hashPendingCheckpoint = 0;
              checkpointMessage = checkpointMessagePending;
              checkpointMessagePending.SetNull();
              printf("AcceptPendingSyncCheckpoint : sync-checkpoint at %s\n", hashSyncCheckpoint.ToString().c_str());
              // relay the checkpoint
              if (!checkpointMessage.IsNull())
              {
                  BOOST_FOREACH(CNode* pnode, vNodes)
                      checkpointMessage.RelayTo(pnode);
              }
              return true;
          }
          return false;
      }
  
      // Automatically select a suitable sync-checkpoint 
      uint256 AutoSelectSyncCheckpoint()
      {
          const CBlockIndex *pindex = pindexBest;
          // Search backward for a block within max span and maturity window
          while (pindex->pprev && (pindex->GetBlockTime() + CHECKPOINT_MAX_SPAN > pindexBest->GetBlockTime() || pindex->nHeight + 8 > pindexBest->nHeight))
              pindex = pindex->pprev;
          return pindex->GetBlockHash();
      }
  
      // Check against synchronized checkpoint
      bool CheckSync(const uint256& hashBlock, const CBlockIndex* pindexPrev)
      {
          if (fTestNet) return true; // Testnet has no checkpoints
          int nHeight = pindexPrev->nHeight + 1;
  
          LOCK(cs_hashSyncCheckpoint);
          // sync-checkpoint should always be accepted block
          assert(mapBlockIndex.count(hashSyncCheckpoint));
          const CBlockIndex* pindexSync = mapBlockIndex[hashSyncCheckpoint];
  
          if (nHeight > pindexSync->nHeight)
          {
              // trace back to same height as sync-checkpoint
              const CBlockIndex* pindex = pindexPrev;
              while (pindex->nHeight > pindexSync->nHeight)
                  if (!(pindex = pindex->pprev))
                      return error("CheckSync: pprev null - block index structure failure");
              if (pindex->nHeight < pindexSync->nHeight || pindex->GetBlockHash() != hashSyncCheckpoint)
                  return false; // only descendant of sync-checkpoint can pass check
          }
          if (nHeight == pindexSync->nHeight && hashBlock != hashSyncCheckpoint)
              return false; // same height with sync-checkpoint
          if (nHeight < pindexSync->nHeight && !mapBlockIndex.count(hashBlock))
              return false; // lower height than sync-checkpoint
          return true;
      }
  
      bool WantedByPendingSyncCheckpoint(uint256 hashBlock)
      {
          LOCK(cs_hashSyncCheckpoint);
          if (hashPendingCheckpoint == 0)
              return false;
          if (hashBlock == hashPendingCheckpoint)
              return true;
          if (mapOrphanBlocks.count(hashPendingCheckpoint) 
              && hashBlock == WantedByOrphan(mapOrphanBlocks[hashPendingCheckpoint]))
              return true;
          return false;
      }
  
      // ppcoin: reset synchronized checkpoint to last hardened checkpoint
      bool ResetSyncCheckpoint()
      {
          LOCK(cs_hashSyncCheckpoint);
          const uint256& hash = mapCheckpoints.rbegin()->second;
          if (mapBlockIndex.count(hash) && !mapBlockIndex[hash]->IsInMainChain())
          {
              // checkpoint block accepted but not yet in main chain
              printf("ResetSyncCheckpoint: SetBestChain to hardened checkpoint %s\n", hash.ToString().c_str());
              CTxDB txdb;
              CBlock block;
              if (!block.ReadFromDisk(mapBlockIndex[hash]))
                  return error("ResetSyncCheckpoint: ReadFromDisk failed for hardened checkpoint %s", hash.ToString().c_str());
              if (!block.SetBestChain(txdb, mapBlockIndex[hash]))
              {
                  return error("ResetSyncCheckpoint: SetBestChain failed for hardened checkpoint %s", hash.ToString().c_str());
              }
          }
          else if(!mapBlockIndex.count(hash))
          {
              // checkpoint block not yet accepted
              hashPendingCheckpoint = hash;
              checkpointMessagePending.SetNull();
              printf("ResetSyncCheckpoint: pending for sync-checkpoint %s\n", hashPendingCheckpoint.ToString().c_str());
          }
  
          BOOST_REVERSE_FOREACH(const MapCheckpoints::value_type& i, mapCheckpoints)
          {
              const uint256& hash = i.second;
              if (mapBlockIndex.count(hash) && mapBlockIndex[hash]->IsInMainChain())
              {
                  if (!WriteSyncCheckpoint(hash))
                      return error("ResetSyncCheckpoint: failed to write sync checkpoint %s", hash.ToString().c_str());
                  printf("ResetSyncCheckpoint: sync-checkpoint reset to %s\n", hashSyncCheckpoint.ToString().c_str());
                  return true;
              }
          }
  
          return false;
      }
  
      void AskForPendingSyncCheckpoint(CNode* pfrom)
      {
          LOCK(cs_hashSyncCheckpoint);
          if (pfrom && hashPendingCheckpoint != 0 && (!mapBlockIndex.count(hashPendingCheckpoint)) && (!mapOrphanBlocks.count(hashPendingCheckpoint)))
              pfrom->AskFor(CInv(MSG_BLOCK, hashPendingCheckpoint));
      }
  
      bool SetCheckpointPrivKey(std::string strPrivKey)
      {
          // Test signing a sync-checkpoint with genesis block
          CSyncCheckpoint checkpoint;
          checkpoint.hashCheckpoint = !fTestNet ? hashGenesisBlock : hashGenesisBlockTestNet;
          CDataStream sMsg(SER_NETWORK, PROTOCOL_VERSION);
          sMsg << (CUnsignedSyncCheckpoint)checkpoint;
          checkpoint.vchMsg = std::vector<unsigned char>(sMsg.begin(), sMsg.end());
  
          std::vector<unsigned char> vchPrivKey = ParseHex(strPrivKey);
          CKey key;
          key.SetPrivKey(CPrivKey(vchPrivKey.begin(), vchPrivKey.end())); // if key is not correct openssl may crash
          if (!key.Sign(Hash(checkpoint.vchMsg.begin(), checkpoint.vchMsg.end()), checkpoint.vchSig))
              return false;
  
          // Test signing successful, proceed
          CSyncCheckpoint::strMasterPrivKey = strPrivKey;
          return true;
      }
  
      bool SendSyncCheckpoint(uint256 hashCheckpoint)
      {
          CSyncCheckpoint checkpoint;
          checkpoint.hashCheckpoint = hashCheckpoint;
          CDataStream sMsg(SER_NETWORK, PROTOCOL_VERSION);
          sMsg << (CUnsignedSyncCheckpoint)checkpoint;
          checkpoint.vchMsg = std::vector<unsigned char>(sMsg.begin(), sMsg.end());
  
          if (CSyncCheckpoint::strMasterPrivKey.empty())
              return error("SendSyncCheckpoint: Checkpoint master key unavailable.");
          std::vector<unsigned char> vchPrivKey = ParseHex(CSyncCheckpoint::strMasterPrivKey);
          CKey key;
          key.SetPrivKey(CPrivKey(vchPrivKey.begin(), vchPrivKey.end())); // if key is not correct openssl may crash
          if (!key.Sign(Hash(checkpoint.vchMsg.begin(), checkpoint.vchMsg.end()), checkpoint.vchSig))
              return error("SendSyncCheckpoint: Unable to sign checkpoint, check private key?");
  
          if(!checkpoint.ProcessSyncCheckpoint(NULL))
          {
              printf("WARNING: SendSyncCheckpoint: Failed to process checkpoint.\n");
              return false;
          }
  
          // Relay checkpoint
          {
              LOCK(cs_vNodes);
              BOOST_FOREACH(CNode* pnode, vNodes)
                  checkpoint.RelayTo(pnode);
          }
          return true;
      }
  
      // Is the sync-checkpoint outside maturity window?
      bool IsMatureSyncCheckpoint()
      {
          LOCK(cs_hashSyncCheckpoint);
          // sync-checkpoint should always be accepted block
          assert(mapBlockIndex.count(hashSyncCheckpoint));
          const CBlockIndex* pindexSync = mapBlockIndex[hashSyncCheckpoint];
          return (nBestHeight >= pindexSync->nHeight + nCoinbaseMaturity ||
                  pindexSync->GetBlockTime() + nStakeMinAge < GetAdjustedTime());
      }
  }
  
  // ppcoin: sync-checkpoint master key
  const std::string CSyncCheckpoint::strMasterPubKey = "049F2C10997604217E7238A4C5CF2843570ADA001D1A247B228A7C5583ACD0F762A3130D0C4331EB262E3D0EB516AE6F7B0B1ADA43275013F8552A83A7C621B1D9";
  
  std::string CSyncCheckpoint::strMasterPrivKey = "";
  
  // ppcoin: verify signature of sync-checkpoint message
  bool CSyncCheckpoint::CheckSignature()
  {
      CKey key;
      if (!key.SetPubKey(ParseHex(CSyncCheckpoint::strMasterPubKey)))
          return error("CSyncCheckpoint::CheckSignature() : SetPubKey failed");
      if (!key.Verify(Hash(vchMsg.begin(), vchMsg.end()), vchSig))
          return error("CSyncCheckpoint::CheckSignature() : verify signature failed");
  
      // Now unserialize the data
      CDataStream sMsg(vchMsg, SER_NETWORK, PROTOCOL_VERSION);
      sMsg >> *(CUnsignedSyncCheckpoint*)this;
      return true;
  }
  
  // ppcoin: process synchronized checkpoint
  bool CSyncCheckpoint::ProcessSyncCheckpoint(CNode* pfrom)
  {
      if (!CheckSignature())
          return false;
  
      LOCK(Checkpoints::cs_hashSyncCheckpoint);
      if (!mapBlockIndex.count(hashCheckpoint))
      {
          // We haven't received the checkpoint chain, keep the checkpoint as pending
          Checkpoints::hashPendingCheckpoint = hashCheckpoint;
          Checkpoints::checkpointMessagePending = *this;
          printf("ProcessSyncCheckpoint: pending for sync-checkpoint %s\n", hashCheckpoint.ToString().c_str());
          // Ask this guy to fill in what we're missing
          if (pfrom)
          {
              pfrom->PushGetBlocks(pindexBest, hashCheckpoint);
              // ask directly as well in case rejected earlier by duplicate
              // proof-of-stake because getblocks may not get it this time
              pfrom->AskFor(CInv(MSG_BLOCK, mapOrphanBlocks.count(hashCheckpoint)? WantedByOrphan(mapOrphanBlocks[hashCheckpoint]) : hashCheckpoint));
          }
          return false;
      }
  
      if (!Checkpoints::ValidateSyncCheckpoint(hashCheckpoint))
          return false;
  
      CTxDB txdb;
      CBlockIndex* pindexCheckpoint = mapBlockIndex[hashCheckpoint];
      if (!pindexCheckpoint->IsInMainChain())
      {
          // checkpoint chain received but not yet main chain
          CBlock block;
          if (!block.ReadFromDisk(pindexCheckpoint))
              return error("ProcessSyncCheckpoint: ReadFromDisk failed for sync checkpoint %s", hashCheckpoint.ToString().c_str());
          if (!block.SetBestChain(txdb, pindexCheckpoint))
          {
              Checkpoints::hashInvalidCheckpoint = hashCheckpoint;
              return error("ProcessSyncCheckpoint: SetBestChain failed for sync checkpoint %s", hashCheckpoint.ToString().c_str());
          }
      }
  
      if (!Checkpoints::WriteSyncCheckpoint(hashCheckpoint))
          return error("ProcessSyncCheckpoint(): failed to write sync checkpoint %s", hashCheckpoint.ToString().c_str());
      Checkpoints::checkpointMessage = *this;
      Checkpoints::hashPendingCheckpoint = 0;
      Checkpoints::checkpointMessagePending.SetNull();
      printf("ProcessSyncCheckpoint: sync-checkpoint at %s\n", hashCheckpoint.ToString().c_str());
      return true;
  }
  