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                 //printf("Result from CMMRNodeBranch check: %s\n", hash.GetHex().c_str());
  92                 break;
  93             }
  94             case CMerkleBranchBase::BRANCH_MMRBLAKE_POWERNODE:
  95             {
  96                 hash = ((CMMRPowerNodeBranch *)pProof)->SafeCheck(hash);
  97                 //printf("Result from CMMRPowerNodeBranch check: %s\n", hash.GetHex().c_str());
  98                 break;
  99             }
 100         }
 101     }
 102     return hash;
 103 }
 104
 105 // return the index that would be generated for an mmv of the indicated size at the specified position
 106 uint64_t CMerkleBranchBase::GetMMRProofIndex(uint64_t pos, uint64_t mmvSize, int extrahashes)
 107 {
 108     uint64_t retIndex = 0;
 109     int bitPos = 0;
 110     std::vector<uint64_t> Sizes;
 111     std::vector<unsigned char> PeakIndexes;
 112     std::vector<uint64_t> MerkleSizes;
 113
 114     // printf("%s: pos: %lu, mmvSize: %lu\n", __func__, pos, mmvSize);
 115
 116     // find a path from the indicated position to the root in the current view
 117     if (pos > 0 && pos < mmvSize)
 118     {
 119         Sizes.push_back(mmvSize);
 120         mmvSize >>= 1;
 121
 122         while (mmvSize)
 123         {
 124             Sizes.push_back(mmvSize);
 125             mmvSize >>= 1;
 126         }
 127
 128         for (uint32_t ht = 0; ht < Sizes.size(); ht++)
 129         {
 130             // 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
 131             if (ht == ((uint32_t)Sizes.size() - 1) || (Sizes[ht] & 1))
 132             {
 133                 PeakIndexes.insert(PeakIndexes.begin(), ht);
 134             }
 135         }
 136
 137         // figure out the peak merkle
 138         uint64_t layerNum = 0, layerSize = PeakIndexes.size();
 139         // with an odd number of elements below, the edge passes through
 140         for (int passThrough = (layerSize & 1); layerNum == 0 || layerSize > 1; passThrough = (layerSize & 1), layerNum++)
 141         {
 142             layerSize = (layerSize >> 1) + passThrough;
 143             if (layerSize)
 144             {
 145                 MerkleSizes.push_back(layerSize);
 146             }
 147         }
 148
 149         // add extra hashes for a node on the right
 150         for (int i = 0; i < extrahashes; i++)
 151         {
 152             // move to the next position
 153             bitPos++;
 154         }
 155
 156         uint64_t p = pos;
 157         for (int l = 0; l < Sizes.size(); l++)
 158         {
 159             // printf("GetProofBits - Bits.size: %lu\n", Bits.size());
 160
 161             if (p & 1)
 162             {
 163                 retIndex |= ((uint64_t)1) << bitPos++;
 164                 p >>= 1;
 165
 166                 for (int i = 0; i < extrahashes; i++)
 167                 {
 168                     bitPos++;
 169                 }
 170             }
 171             else
 172             {
 173                 // 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
 174                 if (Sizes[l] > (p + 1))
 175                 {
 176                     bitPos++;
 177                     p >>= 1;
 178
 179                     for (int i = 0; i < extrahashes; i++)
 180                     {
 181                         bitPos++;
 182                     }
 183                 }
 184                 else
 185                 {
 186                     for (p = 0; p < PeakIndexes.size(); p++)
 187                     {
 188                         if (PeakIndexes[p] == l)
 189                         {
 190                             break;
 191                         }
 192                     }
 193
 194                     // p is the position in the merkle tree of peaks
 195                     assert(p < PeakIndexes.size());
 196
 197                     // move up to the top, which is always a peak of size 1
 198                     uint64_t layerNum;
 199                     uint64_t layerSize;
 200                     for (layerNum = -1, layerSize = PeakIndexes.size(); layerNum == -1 || layerSize > 1; layerSize = MerkleSizes[++layerNum])
 201                     {
 202                         // printf("GetProofBits - Bits.size: %lu\n", Bits.size());
 203                         if (p < (layerSize - 1) || (p & 1))
 204                         {
 205                             if (p & 1)
 206                             {
 207                                 // hash with the one before us
 208                                 retIndex |= ((uint64_t)1) << bitPos;
 209                                 bitPos++;
 210
 211                                 for (int i = 0; i < extrahashes; i++)
 212                                 {
 213                                     bitPos++;
 214                                 }
 215                             }
 216                             else
 217                             {
 218                                 // hash with the one in front of us
 219                                 bitPos++;
 220
 221                                 for (int i = 0; i < extrahashes; i++)
 222                                 {
 223                                     bitPos++;
 224                                 }
 225                             }
 226                         }
 227                         p >>= 1;
 228                     }
 229                     // finished
 230                     break;
 231                 }
 232             }
 233         }
 234     }
 235     //printf("retindex: %lu\n", retIndex);
 236     return retIndex;
 237 }