src/mmr.cpp

   1 /********************************************************************
   2  * (C) 2020 Michael Toutonghi
   3  *
   4  * Distributed under the MIT software license, see the accompanying
   5  * file COPYING or http://www.opensource.org/licenses/mit-license.php.
   6  *
   7  */
   8
   9 #include "mmr.h"
  10
  11 // just used for setting breakpoints that may be hard to set and printing messages
  12 void ErrorAndBP(std::string msg)
  13 {
  14     printf("%s\n", msg.c_str());
  15     LogPrintf("%s\n", msg.c_str());
  16 }
  17
  18
  19 void CMMRProof::DeleteProofSequence()
  20 {
  21     // delete any objects that may be present
  22     for (int i = proofSequence.size() - 1; i >= 0 && proofSequence[i]; i--)
  23     {
  24         CMerkleBranchBase *pProof = proofSequence[i];
  25         switch(pProof->branchType)
  26         {
  27             case CMerkleBranchBase::BRANCH_BTC:
  28             {
  29                 delete (CBTCMerkleBranch *)pProof;
  30                 break;
  31             }
  32             case CMerkleBranchBase::BRANCH_MMRBLAKE_NODE:
  33             {
  34                 delete (CMMRNodeBranch *)pProof;
  35                 break;
  36             }
  37             case CMerkleBranchBase::BRANCH_MMRBLAKE_POWERNODE:
  38             {
  39                 delete (CMMRPowerNodeBranch *)pProof;
  40                 break;
  41             }
  42             default:
  43             {
  44                 ErrorAndBP("ERROR: likely double-free or memory corruption, unrecognized object in proof sequence");
  45                 // this is likely a memory error
  46                 // delete pProof;
  47             }
  48         }
  49         proofSequence.pop_back();
  50     }
  51 }
  52
  53 const CMMRProof &CMMRProof::operator<<(const CBTCMerkleBranch &append)
  54 {
  55     CMerkleBranchBase *pNewProof = new CBTCMerkleBranch(append);
  56     pNewProof->branchType = CMerkleBranchBase::BRANCH_BTC;
  57     proofSequence.push_back(pNewProof);
  58     return *this;
  59 }
  60
  61 const CMMRProof &CMMRProof::operator<<(const CMMRNodeBranch &append)
  62 {
  63     CMerkleBranchBase *pNewProof = new CMMRNodeBranch(append);
  64     pNewProof->branchType = CMerkleBranchBase::BRANCH_MMRBLAKE_NODE;
  65     proofSequence.push_back(pNewProof);
  66     return *this;
  67 }
  68
  69 const CMMRProof &CMMRProof::operator<<(const CMMRPowerNodeBranch &append)
  70 {
  71     CMerkleBranchBase *pNewProof = new CMMRPowerNodeBranch(append);
  72     pNewProof->branchType = CMerkleBranchBase::BRANCH_MMRBLAKE_POWERNODE;
  73     proofSequence.push_back(pNewProof);
  74     return *this;
  75 }
  76
  77 uint256 CMMRProof::CheckProof(uint256 hash) const
  78 {
  79     for (auto &pProof : proofSequence)
  80     {
  81         switch(pProof->branchType)
  82         {
  83             case CMerkleBranchBase::BRANCH_BTC:
  84             {
  85                 hash = ((CBTCMerkleBranch *)pProof)->SafeCheck(hash);
  86                 break;
  87             }
  88             case CMerkleBranchBase::BRANCH_MMRBLAKE_NODE:
  89             {
  90                 hash = ((CMMRNodeBranch *)pProof)->SafeCheck(hash);
  91                 break;
  92             }
  93             case CMerkleBranchBase::BRANCH_MMRBLAKE_POWERNODE:
  94             {
  95                 hash = ((CMMRPowerNodeBranch *)pProof)->SafeCheck(hash);
  96                 break;
  97             }
  98         }
  99     }
 100     return hash;
 101 }
 102
 103 // return the index that would be generated for an mmv of the indicated size at the specified position
 104 uint64_t CMerkleBranchBase::GetMMRProofIndex(uint64_t pos, uint64_t mmvSize, int extrahashes)
 105 {
 106     uint64_t retIndex = 0;
 107     int bitPos = 0;
 108     std::vector<uint64_t> Sizes;
 109     std::vector<unsigned char> PeakIndexes;
 110     std::vector<uint64_t> MerkleSizes;
 111
 112     // printf("%s: pos: %lu, mmvSize: %lu\n", __func__, pos, mmvSize);
 113
 114     // find a path from the indicated position to the root in the current view
 115     if (pos > 0 && pos < mmvSize)
 116     {
 117         Sizes.push_back(mmvSize);
 118         mmvSize >>= 1;
 119
 120         while (mmvSize)
 121         {
 122             Sizes.push_back(mmvSize);
 123             mmvSize >>= 1;
 124         }
 125
 126         for (uint32_t ht = 0; ht < Sizes.size(); ht++)
 127         {
 128             // if we're at the top or the layer above us is smaller than 1/2 the size of this layer, rounded up, we are a peak
 129             if (ht == ((uint32_t)Sizes.size() - 1) || (Sizes[ht] & 1))
 130             {
 131                 PeakIndexes.insert(PeakIndexes.begin(), ht);
 132             }
 133         }
 134
 135         uint64_t layerNum = 0, layerSize = Sizes[0];
 136         // with an odd number of elements below, the edge passes through
 137         for (bool passThrough = (layerSize & 1); layerNum == 0 || layerSize > 1; passThrough = (layerSize & 1), layerNum++)
 138         {
 139             layerSize = (layerSize >> 1) + passThrough;
 140             if (layerSize)
 141             {
 142                 MerkleSizes.push_back(layerSize);
 143             }
 144         }
 145
 146         // add extra hashes for a node on the right
 147         for (int i = 0; i < extrahashes; i++)
 148         {
 149             // move to the next position
 150             bitPos++;
 151         }
 152
 153         uint64_t p = pos;
 154         for (int l = 0; l < Sizes.size(); l++)
 155         {
 156             // printf("GetProofBits - Bits.size: %lu\n", Bits.size());
 157
 158             if (p & 1)
 159             {
 160                 retIndex |= ((uint64_t)1) << bitPos++;
 161                 p >>= 1;
 162
 163                 for (int i = 0; i < extrahashes; i++)
 164                 {
 165                     bitPos++;
 166                 }
 167             }
 168             else
 169             {
 170                 // make sure there is one after us to hash with or we are a peak and should be hashed with the rest of the peaks
 171                 if (Sizes[l] > (p + 1))
 172                 {
 173                     bitPos++;
 174                     p >>= 1;
 175
 176                     for (int i = 0; i < extrahashes; i++)
 177                     {
 178                         bitPos++;
 179                     }
 180                 }
 181                 else
 182                 {
 183                     for (p = 0; p < PeakIndexes.size(); p++)
 184                     {
 185                         if (PeakIndexes[p] == l)
 186                         {
 187                             break;
 188                         }
 189                     }
 190
 191                     // p is the position in the merkle tree of peaks
 192                     assert(p < PeakIndexes.size());
 193
 194                     // move up to the top, which is always a peak of size 1
 195                     uint64_t layerNum;
 196                     uint64_t layerSize;
 197                     for (layerNum = -1, layerSize = PeakIndexes.size(); layerNum == -1 || layerSize > 1; layerSize = MerkleSizes[++layerNum])
 198                     {
 199                         // printf("GetProofBits - Bits.size: %lu\n", Bits.size());
 200                         if (p < (layerSize - 1) || (p & 1))
 201                         {
 202                             if (p & 1)
 203                             {
 204                                 // hash with the one before us
 205                                 retIndex |= ((uint64_t)1) << bitPos;
 206
 207                                 for (int i = 0; i < extrahashes; i++)
 208                                 {
 209                                     bitPos++;
 210                                 }
 211                             }
 212                             else
 213                             {
 214                                 // hash with the one in front of us
 215                                 bitPos++;
 216
 217                                 for (int i = 0; i < extrahashes; i++)
 218                                 {
 219                                     bitPos++;
 220                                 }
 221                             }
 222                         }
 223                         p >>= 1;
 224                     }
 225                     // finished
 226                     break;
 227                 }
 228             }
 229         }
 230     }
 231     //printf("retindex: %lu\n", retIndex);
 232     return retIndex;
 233 }