src/primitives/block.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2014 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #include "primitives/block.h"
   7
   8 #include "hash.h"
   9 #include "tinyformat.h"
  10 #include "utilstrencodings.h"
  11 #include "crypto/common.h"
  12 #include "mmr.h"
  13
  14 extern uint32_t ASSETCHAINS_ALGO, ASSETCHAINS_VERUSHASH;
  15 extern uint160 ASSETCHAINS_CHAINID;
  16 extern uint160 VERUS_CHAINID;
  17
  18 // default hash algorithm for block
  19 uint256 (CBlockHeader::*CBlockHeader::hashFunction)() const = &CBlockHeader::GetSHA256DHash;
  20
  21 // does not check for height / sapling upgrade, etc. this should not be used to get block proofs
  22 // on a pre-VerusPoP chain
  23 arith_uint256 GetCompactPower(const uint256 &nNonce, uint32_t nBits, int32_t version)
  24 {
  25     arith_uint256 bnWork, bnStake = arith_uint256(0);
  26     arith_uint256 BIG_ZERO = bnStake;
  27
  28     bool fNegative;
  29     bool fOverflow;
  30     bnWork.SetCompact(nBits, &fNegative, &fOverflow);
  31
  32     if (fNegative || fOverflow || bnWork == 0)
  33         return BIG_ZERO;
  34
  35     // if POS block, add stake
  36     CPOSNonce nonce(nNonce);
  37     if (nonce.IsPOSNonce(version))
  38     {
  39         bnStake.SetCompact(nonce.GetPOSTarget(), &fNegative, &fOverflow);
  40         if (fNegative || fOverflow || bnStake == 0)
  41             return BIG_ZERO;
  42
  43         // as the nonce has a fixed definition for a POS block, add the random amount of "work" from the nonce, so there will
  44         // statistically always be a deterministic winner in POS
  45         arith_uint256 aNonce;
  46
  47         // random amount of additional stake added is capped to 1/2 the current stake target
  48         aNonce = UintToArith256(nNonce) | (bnStake << (uint64_t)1);
  49
  50         // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
  51         // as it's too large for a arith_uint256. However, as 2**256 is at least as large
  52         // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
  53         // or ~bnTarget / (nTarget+1) + 1.
  54         bnWork = (~bnWork / (bnWork + 1)) + 1;
  55         bnStake = ((~bnStake / (bnStake + 1)) + 1) + ((~aNonce / (aNonce + 1)) + 1);
  56         if (!(bnWork >> 128 == BIG_ZERO && bnStake >> 128 == BIG_ZERO))
  57         {
  58             return BIG_ZERO;
  59         }
  60         return bnWork + (bnStake << 128);
  61     }
  62     else
  63     {
  64         bnWork = (~bnWork / (bnWork + 1)) + 1;
  65
  66         // this would be overflow
  67         if (!((bnWork >> 128) == BIG_ZERO))
  68         {
  69             printf("Overflow\n");
  70             return BIG_ZERO;
  71         }
  72         return bnWork;
  73     }
  74 }
  75
  76 CPBaaSPreHeader::CPBaaSPreHeader(CBlockHeader &bh)
  77 {
  78     hashPrevBlock = bh.hashPrevBlock;
  79     hashMerkleRoot = bh.hashMerkleRoot;
  80     hashFinalSaplingRoot = bh.hashFinalSaplingRoot;
  81     nNonce = bh.nNonce;
  82     nBits = bh.nBits;
  83 }
  84
  85 CMMRPowerNode CBlockHeader::GetMMRNode() const
  86 {
  87     uint256 blockHash = GetHash();
  88
  89     uint256 preHash = Hash(BEGIN(hashMerkleRoot), END(hashMerkleRoot), BEGIN(blockHash), END(blockHash));
  90     uint256 power = ArithToUint256(GetCompactPower(nNonce, nBits, nVersion));
  91
  92     return CMMRPowerNode(Hash(BEGIN(hashMerkleRoot), END(hashMerkleRoot), BEGIN(power), END(power)), power);
  93 }
  94
  95 void CBlockHeader::AddMerkleProofBridge(CMerkleBranch &branch) const
  96 {
  97     // we need to add the block hash on the right
  98     branch.branch.push_back(GetHash());
  99     branch.nIndex = branch.nIndex << 1;
 100 }
 101
 102 void CBlockHeader::AddBlockProofBridge(CMerkleBranch &branch) const
 103 {
 104     // we need to add the block hash on the right
 105     branch.branch.push_back(hashMerkleRoot);
 106     branch.nIndex = branch.nIndex << 1 + 1;
 107 }
 108
 109 uint256 CBlockHeader::GetPrevMMRRoot() const
 110 {
 111     uint256 ret;
 112     CPBaaSBlockHeader pbh;
 113     if (GetPBaaSHeader(pbh, ASSETCHAINS_CHAINID) != -1)
 114     {
 115         ret = pbh.hashPrevMMRRoot;
 116     }
 117     return ret;
 118 }
 119
 120 // checks that the solution stored data for this header matches what is expected, ensuring that the
 121 // values in the header match the hash of the pre-header. it does not check the prev MMR root
 122 bool CBlockHeader::CheckNonCanonicalData() const
 123 {
 124     CPBaaSPreHeader pbph(hashPrevBlock, hashMerkleRoot, hashFinalSaplingRoot, nNonce, nBits);
 125     uint256 dummyMMR;
 126     CPBaaSBlockHeader pbbh1 = CPBaaSBlockHeader(ASSETCHAINS_CHAINID, pbph, dummyMMR);
 127     CPBaaSBlockHeader pbbh2;
 128     int32_t idx = GetPBaaSHeader(pbbh2, ASSETCHAINS_CHAINID);
 129     if (idx != -1)
 130     {
 131         if (pbbh1.hashPreHeader == pbbh2.hashPreHeader)
 132         {
 133             return true;
 134         }
 135     }
 136     return false;
 137 }
 138
 139 // returns -1 on failure, upon failure, pbbh is undefined and likely corrupted
 140 int32_t CBlockHeader::GetPBaaSHeader(CPBaaSBlockHeader &pbh, const uint160 &cID) const
 141 {
 142     // find the specified PBaaS header in the solution and return its index if present
 143     // if not present, return -1
 144     if (nVersion == VERUS_V2)
 145     {
 146         // search in the solution for this header index and return it if found
 147         CPBaaSSolutionDescriptor d = CVerusSolutionVector::solutionTools.GetDescriptor(nSolution);
 148         if (CVerusSolutionVector::solutionTools.IsPBaaS(nSolution) != 0)
 149         {
 150             int32_t len = CVerusSolutionVector::solutionTools.ExtraDataLen(nSolution);
 151             int32_t numHeaders = d.numPBaaSHeaders;
 152             const CPBaaSBlockHeader *ppbbh = CVerusSolutionVector::solutionTools.GetFirstPBaaSHeader(nSolution);
 153             for (int32_t i = 0; i < numHeaders; i++)
 154             {
 155                 if ((ppbbh + i)->chainID == cID)
 156                 {
 157                     pbh = *(ppbbh + i);
 158                     return i;
 159                 }
 160             }
 161         }
 162     }
 163     return -1;
 164 }
 165
 166 // returns the index of the new header if added, otherwise, -1
 167 int32_t CBlockHeader::AddPBaaSHeader(const CPBaaSBlockHeader &pbh)
 168 {
 169     CVerusSolutionVector sv(nSolution);
 170     CPBaaSSolutionDescriptor d = sv.Descriptor();
 171     int32_t retVal = d.numPBaaSHeaders;
 172
 173     // make sure we have space. do not adjust capacity
 174     // if there is anything in the extradata, we have no more room
 175     if (!d.extraDataSize && (uint32_t)(sv.ExtraDataLen() / sizeof(CPBaaSBlockHeader)) > 0)
 176     {
 177         d.numPBaaSHeaders++;
 178         sv.SetDescriptor(d);                            // update descriptor to make sure it will accept the set
 179         sv.SetPBaaSHeader(pbh, d.numPBaaSHeaders - 1);
 180         return retVal;
 181     }
 182
 183     return -1;
 184 }
 185
 186 // add or update the PBaaS header for this block from the current block header & this prevMMR. This is required to make a valid PoS or PoW block.
 187 bool CBlockHeader::AddUpdatePBaaSHeader(const CPBaaSBlockHeader &pbh)
 188 {
 189     CPBaaSBlockHeader pbbh;
 190     if (CConstVerusSolutionVector::Version(nSolution) == CActivationHeight::SOLUTION_VERUSV3)
 191     {
 192         if (int32_t idx = GetPBaaSHeader(pbbh, pbh.chainID) != -1)
 193         {
 194             return UpdatePBaaSHeader(pbh);
 195         }
 196         else
 197         {
 198             return (AddPBaaSHeader(pbh) != -1);
 199         }
 200     }
 201     return false;
 202 }
 203
 204 // add or update the current PBaaS header for this block from the current block header & this prevMMR.
 205 // This is required to make a valid PoS or PoW block.
 206 bool CBlockHeader::AddUpdatePBaaSHeader(uint256 prevMMRRoot)
 207 {
 208     if (CConstVerusSolutionVector::Version(nSolution) == CActivationHeight::SOLUTION_VERUSV3)
 209     {
 210         CPBaaSPreHeader pbph(hashPrevBlock, hashMerkleRoot, hashFinalSaplingRoot, nNonce, nBits);
 211         CPBaaSBlockHeader pbh(ASSETCHAINS_CHAINID, pbph, prevMMRRoot);
 212
 213         CPBaaSBlockHeader pbbh;
 214         int32_t idx = GetPBaaSHeader(pbbh, ASSETCHAINS_CHAINID);
 215
 216         if (idx != -1)
 217         {
 218             return UpdatePBaaSHeader(pbh);
 219         }
 220         else
 221         {
 222             return (AddPBaaSHeader(pbh) != -1);
 223         }
 224     }
 225     return false;
 226 }
 227
 228 uint256 CBlockHeader::GetSHA256DHash() const
 229 {
 230     return SerializeHash(*this);
 231 }
 232
 233 uint256 CBlockHeader::GetVerusHash() const
 234 {
 235     if (hashPrevBlock.IsNull())
 236         // always use SHA256D for genesis block
 237         return SerializeHash(*this);
 238     else
 239         return SerializeVerusHash(*this);
 240 }
 241
 242 uint256 CBlockHeader::GetVerusV2Hash() const
 243 {
 244     if (hashPrevBlock.IsNull())
 245     {
 246         // always use SHA256D for genesis block
 247         return SerializeHash(*this);
 248     }
 249     else
 250     {
 251         if (nVersion == VERUS_V2)
 252         {
 253             // in order for this to work, the PBaaS hash of the pre-header must match the header data
 254             // otherwise, it cannot clear the canonical data and hash in a chain-independent manner
 255             if (CConstVerusSolutionVector::IsPBaaS(nSolution) && CheckNonCanonicalData())
 256             {
 257                 CBlockHeader bh = CBlockHeader(*this);
 258                 bh.ClearNonCanonicalData();
 259                 return SerializeVerusHashV2b(bh);
 260             }
 261             else
 262             {
 263                 return SerializeVerusHashV2b(*this);
 264             }
 265         }
 266         else
 267         {
 268             return SerializeVerusHash(*this);
 269         }
 270     }
 271 }
 272
 273 void CBlockHeader::SetSHA256DHash()
 274 {
 275     CBlockHeader::hashFunction = &CBlockHeader::GetSHA256DHash;
 276 }
 277
 278 void CBlockHeader::SetVerusHash()
 279 {
 280     CBlockHeader::hashFunction = &CBlockHeader::GetVerusHash;
 281 }
 282
 283 void CBlockHeader::SetVerusV2Hash()
 284 {
 285     CBlockHeader::hashFunction = &CBlockHeader::GetVerusV2Hash;
 286 }
 287
 288 // returns false if unable to fast calculate the VerusPOSHash from the header.
 289 // if it returns false, value is set to 0, but it can still be calculated from the full block
 290 // in that case. the only difference between this and the POS hash for the contest is that it is not divided by the value out
 291 // this is used as a source of entropy
 292 bool CBlockHeader::GetRawVerusPOSHash(uint256 &ret, int32_t nHeight) const
 293 {
 294     // if below the required height or no storage space in the solution, we can't get
 295     // a cached txid value to calculate the POSHash from the header
 296     if (!(CPOSNonce::NewNonceActive(nHeight) && IsVerusPOSBlock()))
 297     {
 298         ret = uint256();
 299         return false;
 300     }
 301
 302     // if we can calculate, this assumes the protocol that the POSHash calculation is:
 303     //    hashWriter << ASSETCHAINS_MAGIC;
 304     //    hashWriter << nNonce; (nNonce is:
 305     //                           (high 128 bits == low 128 bits of verus hash of low 128 bits of nonce)
 306     //                           (low 32 bits == compact PoS difficult)
 307     //                           (mid 96 bits == low 96 bits of HASH(pastHash, txid, voutnum)
 308     //                              pastHash is hash of height - 100, either PoW hash of block or PoS hash, if new PoS
 309     //                          )
 310     //    hashWriter << height;
 311     //    return hashWriter.GetHash();
 312     if (nVersion == VERUS_V2)
 313     {
 314         CVerusHashV2Writer hashWriter = CVerusHashV2Writer(SER_GETHASH, PROTOCOL_VERSION);
 315
 316         hashWriter << ASSETCHAINS_MAGIC;
 317         hashWriter << nNonce;
 318         hashWriter << nHeight;
 319         ret = hashWriter.GetHash();
 320     }
 321     else
 322     {
 323         CVerusHashWriter hashWriter = CVerusHashWriter(SER_GETHASH, PROTOCOL_VERSION);
 324
 325         hashWriter << ASSETCHAINS_MAGIC;
 326         hashWriter << nNonce;
 327         hashWriter << nHeight;
 328         ret = hashWriter.GetHash();
 329     }
 330     return true;
 331 }
 332
 333 bool CBlockHeader::GetVerusPOSHash(arith_uint256 &ret, int32_t nHeight, CAmount value) const
 334 {
 335     uint256 raw;
 336     if (GetRawVerusPOSHash(raw, nHeight))
 337     {
 338         ret = UintToArith256(raw) / value;
 339         return true;
 340     }
 341     return false;
 342 }
 343
 344 // depending on the height of the block and its type, this returns the POS hash or the POW hash
 345 uint256 CBlockHeader::GetVerusEntropyHash(int32_t height) const
 346 {
 347     uint256 retVal;
 348     // if we qualify as PoW, use PoW hash, regardless of PoS state
 349     if (GetRawVerusPOSHash(retVal, height))
 350     {
 351         // POS hash
 352         return retVal;
 353     }
 354     return GetHash();
 355 }
 356
 357 uint256 BuildMerkleTree(bool* fMutated, const std::vector<uint256> leaves,
 358         std::vector<uint256> &vMerkleTree)
 359 {
 360     /* WARNING! If you're reading this because you're learning about crypto
 361        and/or designing a new system that will use merkle trees, keep in mind
 362        that the following merkle tree algorithm has a serious flaw related to
 363        duplicate txids, resulting in a vulnerability (CVE-2012-2459).
 364
 365        The reason is that if the number of hashes in the list at a given time
 366        is odd, the last one is duplicated before computing the next level (which
 367        is unusual in Merkle trees). This results in certain sequences of
 368        transactions leading to the same merkle root. For example, these two
 369        trees:
 370
 371                    A                A
 372                  /  \            /    \
 373                 B    C          B       C
 374                / \    \        / \     / \
 375               D   E   F       D   E   F   F
 376              / \ / \ / \     / \ / \ / \ / \
 377              1 2 3 4 5 6     1 2 3 4 5 6 5 6
 378
 379        for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
 380        6 are repeated) result in the same root hash A (because the hash of both
 381        of (F) and (F,F) is C).
 382
 383        The vulnerability results from being able to send a block with such a
 384        transaction list, with the same merkle root, and the same block hash as
 385        the original without duplication, resulting in failed validation. If the
 386        receiving node proceeds to mark that block as permanently invalid
 387        however, it will fail to accept further unmodified (and thus potentially
 388        valid) versions of the same block. We defend against this by detecting
 389        the case where we would hash two identical hashes at the end of the list
 390        together, and treating that identically to the block having an invalid
 391        merkle root. Assuming no double-SHA256 collisions, this will detect all
 392        known ways of changing the transactions without affecting the merkle
 393        root.
 394     */
 395
 396     vMerkleTree.clear();
 397     vMerkleTree.reserve(leaves.size() * 2 + 16); // Safe upper bound for the number of total nodes.
 398     for (std::vector<uint256>::const_iterator it(leaves.begin()); it != leaves.end(); ++it)
 399         vMerkleTree.push_back(*it);
 400     int j = 0;
 401     bool mutated = false;
 402     for (int nSize = leaves.size(); nSize > 1; nSize = (nSize + 1) / 2)
 403     {
 404         for (int i = 0; i < nSize; i += 2)
 405         {
 406             int i2 = std::min(i+1, nSize-1);
 407             if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
 408                 // Two identical hashes at the end of the list at a particular level.
 409                 mutated = true;
 410             }
 411             vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vMerkleTree[j+i]),
 412                                        BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
 413         }
 414         j += nSize;
 415     }
 416     if (fMutated) {
 417         *fMutated = mutated;
 418     }
 419     return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
 420 }
 421
 422
 423 uint256 CBlock::BuildMerkleTree(bool* fMutated) const
 424 {
 425     std::vector<uint256> leaves;
 426     for (int i=0; i<vtx.size(); i++) leaves.push_back(vtx[i].GetHash());
 427     return ::BuildMerkleTree(fMutated, leaves, vMerkleTree);
 428 }
 429
 430
 431 std::vector<uint256> GetMerkleBranch(int nIndex, int nLeaves, const std::vector<uint256> &vMerkleTree)
 432 {
 433     std::vector<uint256> vMerkleBranch;
 434     int j = 0;
 435     for (int nSize = nLeaves; nSize > 1; nSize = (nSize + 1) / 2)
 436     {
 437         int i = std::min(nIndex^1, nSize-1);
 438         vMerkleBranch.push_back(vMerkleTree[j+i]);
 439         nIndex >>= 1;
 440         j += nSize;
 441     }
 442     return vMerkleBranch;
 443 }
 444
 445
 446 std::vector<uint256> CBlock::GetMerkleBranch(int nIndex) const
 447 {
 448     if (vMerkleTree.empty())
 449         BuildMerkleTree();
 450     return ::GetMerkleBranch(nIndex, vtx.size(), vMerkleTree);
 451 }
 452
 453
 454 uint256 CBlock::CheckMerkleBranch(uint256 hash, const std::vector<uint256>& vMerkleBranch, int nIndex)
 455 {
 456     if (nIndex == -1)
 457         return uint256();
 458     for (std::vector<uint256>::const_iterator it(vMerkleBranch.begin()); it != vMerkleBranch.end(); ++it)
 459     {
 460         if (nIndex & 1)
 461             hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash));
 462         else
 463             hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it));
 464         nIndex >>= 1;
 465     }
 466     return hash;
 467 }
 468
 469 std::string CBlock::ToString() const
 470 {
 471     std::stringstream s;
 472     s << strprintf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, hashFinalSaplingRoot=%s, nTime=%u, nBits=%08x, nNonce=%s, vtx=%u)\n",
 473         GetHash().ToString(),
 474         nVersion,
 475         hashPrevBlock.ToString(),
 476         hashMerkleRoot.ToString(),
 477         hashFinalSaplingRoot.ToString(),
 478         nTime, nBits, nNonce.ToString(),
 479         vtx.size());
 480     for (unsigned int i = 0; i < vtx.size(); i++)
 481     {
 482         s << "  " << vtx[i].ToString() << "\n";
 483     }
 484     s << "  vMerkleTree: ";
 485     for (unsigned int i = 0; i < vMerkleTree.size(); i++)
 486         s << " " << vMerkleTree[i].ToString();
 487     s << "\n";
 488     return s.str();
 489 }