src/crosschain.cpp

   1 #include "cc/eval.h"
   2 #include "crosschain.h"
   3 #include "importcoin.h"
   4 #include "main.h"
   5 #include "notarisationdb.h"
   6
   7 /*
   8  * The crosschain workflow.
   9  *
  10  * 3 chains, A, B, and KMD. We would like to prove TX on B.
  11  * There is a notarisation, nA0, which will include TX via an MoM.
  12  * The notarisation nA0 must fall between 2 notarisations of B,
  13  * ie, nB0 and nB1. An MoMoM including this range is propagated to
  14  * B in notarisation receipt (backnotarisation) bnB2.
  15  *
  16  * A:                 TX   bnA0
  17  *                     \   /
  18  * KMD:      nB0        nA0     nB1      nB2
  19  *              \                 \       \
  20  * B:          bnB0              bnB1     bnB2
  21  */
  22
  23 // XXX: There are potential crashes wherever we access chainActive without a lock,
  24 // because it might be disconnecting blocks at the same time.
  25
  26
  27 int NOTARISATION_SCAN_LIMIT_BLOCKS = 1440;
  28
  29
  30 /* On KMD */
  31 uint256 CalculateProofRoot(const char* symbol, uint32_t targetCCid, int kmdHeight,
  32         std::vector<uint256> &moms, uint256 &destNotarisationTxid)
  33 {
  34     /*
  35      * Notaries don't wait for confirmation on KMD before performing a backnotarisation,
  36      * but we need a determinable range that will encompass all merkle roots. Include MoMs
  37      * including the block height of the last notarisation until the height before the
  38      * previous notarisation.
  39      *
  40      *    kmdHeight      notarisations-0      notarisations-1
  41      *                         *********************|
  42      *        > scan backwards >
  43      */
  44
  45     if (targetCCid < 2)
  46         return uint256();
  47
  48     if (kmdHeight < 0 || kmdHeight > chainActive.Height())
  49         return uint256();
  50
  51     int seenOwnNotarisations = 0;
  52
  53     bool txscl = IsTXSCL(symbol);
  54
  55     for (int i=0; i<NOTARISATION_SCAN_LIMIT_BLOCKS; i++) {
  56         if (i > kmdHeight) break;
  57         NotarisationsInBlock notarisations;
  58         uint256 blockHash = *chainActive[kmdHeight-i]->phashBlock;
  59         if (!GetBlockNotarisations(blockHash, notarisations))
  60             continue;
  61
  62         // See if we have an own notarisation in this block
  63         BOOST_FOREACH(Notarisation& nota, notarisations) {
  64             if (strcmp(nota.second.symbol, symbol) == 0)
  65             {
  66                 seenOwnNotarisations++;
  67                 if (seenOwnNotarisations == 1)
  68                     destNotarisationTxid = nota.first;
  69                 else if (seenOwnNotarisations == 2)
  70                     goto end;
  71                 break;
  72             }
  73         }
  74
  75         if (seenOwnNotarisations == 1) {
  76             BOOST_FOREACH(Notarisation& nota, notarisations) {
  77                 if (IsTXSCL(nota.second.symbol) == txscl)
  78                     if (nota.second.ccId == targetCCid)
  79                         moms.push_back(nota.second.MoM);
  80             }
  81         }
  82     }
  83
  84 end:
  85     return GetMerkleRoot(moms);
  86 }
  87
  88
  89 /*
  90  * Get a notarisation from a given height
  91  *
  92  * Will scan notarisations leveldb up to a limit
  93  */
  94 template <typename IsTarget>
  95 int ScanNotarisationsFromHeight(int nHeight, const IsTarget f, Notarisation &found)
  96 {
  97     int limit = std::min(nHeight + NOTARISATION_SCAN_LIMIT_BLOCKS, chainActive.Height());
  98
  99     for (int h=nHeight; h<limit; h++) {
 100         NotarisationsInBlock notarisations;
 101
 102         if (!GetBlockNotarisations(*chainActive[h]->phashBlock, notarisations))
 103             continue;
 104
 105         BOOST_FOREACH(found, notarisations) {
 106             if (f(found)) {
 107                 return h;
 108             }
 109         }
 110     }
 111     return 0;
 112 }
 113
 114
 115 /* On KMD */
 116 TxProof GetCrossChainProof(const uint256 txid, const char* targetSymbol, uint32_t targetCCid,
 117         const TxProof assetChainProof)
 118 {
 119     /*
 120      * Here we are given a proof generated by an assetchain A which goes from given txid to
 121      * an assetchain MoM. We need to go from the notarisationTxid for A to the MoMoM range of the
 122      * backnotarisation for B (given by kmdheight of notarisation), find the MoM within the MoMs for
 123      * that range, and finally extend the proof to lead to the MoMoM (proof root).
 124      */
 125     EvalRef eval;
 126     uint256 MoM = assetChainProof.second.Exec(txid);
 127
 128     // Get a kmd height for given notarisation Txid
 129     int kmdHeight;
 130     {
 131         CTransaction sourceNotarisation;
 132         uint256 hashBlock;
 133         CBlockIndex blockIdx;
 134         if (!eval->GetTxConfirmed(assetChainProof.first, sourceNotarisation, blockIdx))
 135             throw std::runtime_error("Notarisation not found");
 136         kmdHeight = blockIdx.nHeight;
 137     }
 138
 139     // We now have a kmdHeight of the notarisation from chain A. So we know that a MoM exists
 140     // at that height.
 141     // If we call CalculateProofRoot with that height, it'll scan backwards, until it finds
 142     // a notarisation from B, and it might not include our notarisation from A
 143     // at all. So, the thing we need to do is scan forwards to find the notarisation for B,
 144     // that is inclusive of A.
 145     Notarisation nota;
 146     auto isTarget = [&](Notarisation &nota) {
 147         return strcmp(nota.second.symbol, targetSymbol) == 0;
 148     };
 149     kmdHeight = ScanNotarisationsFromHeight(kmdHeight, isTarget, nota);
 150     if (!kmdHeight)
 151         throw std::runtime_error("Cannot find notarisation for target inclusive of source");
 152
 153     // Get MoMs for kmd height and symbol
 154     std::vector<uint256> moms;
 155     uint256 targetChainNotarisationTxid;
 156     uint256 MoMoM = CalculateProofRoot(targetSymbol, targetCCid, kmdHeight, moms, targetChainNotarisationTxid);
 157     if (MoMoM.IsNull())
 158         throw std::runtime_error("No MoMs found");
 159
 160     // Find index of source MoM in MoMoM
 161     int nIndex;
 162     for (nIndex=0; nIndex<moms.size(); nIndex++) {
 163         if (moms[nIndex] == MoM)
 164             goto cont;
 165     }
 166     throw std::runtime_error("Couldn't find MoM within MoMoM set");
 167 cont:
 168
 169     // Create a branch
 170     std::vector<uint256> vBranch;
 171     {
 172         CBlock fakeBlock;
 173         for (int i=0; i<moms.size(); i++) {
 174             CTransaction fakeTx;
 175             // first value in CTransaction memory is it's hash
 176             memcpy((void*)&fakeTx, moms[i].begin(), 32);
 177             fakeBlock.vtx.push_back(fakeTx);
 178         }
 179         vBranch = fakeBlock.GetMerkleBranch(nIndex);
 180     }
 181
 182     // Concatenate branches
 183     MerkleBranch newBranch = assetChainProof.second;
 184     newBranch << MerkleBranch(nIndex, vBranch);
 185
 186     // Check proof
 187     if (newBranch.Exec(txid) != MoMoM)
 188         throw std::runtime_error("Proof check failed");
 189
 190     return std::make_pair(targetChainNotarisationTxid,newBranch);
 191 }
 192
 193
 194 /*
 195  * Takes an importTx that has proof leading to assetchain root
 196  * and extends proof to cross chain root
 197  */
 198 void CompleteImportTransaction(CTransaction &importTx)
 199 {
 200     TxProof proof;
 201     CTransaction burnTx;
 202     std::vector<CTxOut> payouts;
 203     if (!UnmarshalImportTx(importTx, proof, burnTx, payouts))
 204         throw std::runtime_error("Couldn't parse importTx");
 205
 206     std::string targetSymbol;
 207     uint32_t targetCCid;
 208     uint256 payoutsHash;
 209     if (!UnmarshalBurnTx(burnTx, targetSymbol, &targetCCid, payoutsHash))
 210         throw std::runtime_error("Couldn't parse burnTx");
 211
 212     proof = GetCrossChainProof(burnTx.GetHash(), targetSymbol.data(), targetCCid, proof);
 213
 214     importTx = MakeImportCoinTransaction(proof, burnTx, payouts);
 215 }
 216
 217
 218 bool IsSameAssetChain(const Notarisation &nota) {
 219     return strcmp(nota.second.symbol, ASSETCHAINS_SYMBOL) == 0;
 220 };
 221
 222
 223 /* On assetchain */
 224 bool GetNextBacknotarisation(uint256 kmdNotarisationTxid, Notarisation &out)
 225 {
 226     /*
 227      * Here we are given a txid, and a proof.
 228      * We go from the KMD notarisation txid to the backnotarisation,
 229      * then jump to the next backnotarisation, which contains the corresponding MoMoM.
 230      */
 231     Notarisation bn;
 232     if (!GetBackNotarisation(kmdNotarisationTxid, bn))
 233         return false;
 234
 235     // Need to get block height of that backnotarisation
 236     EvalRef eval;
 237     CBlockIndex block;
 238     CTransaction tx;
 239     if (!eval->GetTxConfirmed(bn.first, tx, block)){
 240         fprintf(stderr, "Can't get height of backnotarisation, this should not happen\n");
 241         return false;
 242     }
 243
 244     return (bool) ScanNotarisationsFromHeight(block.nHeight+1, &IsSameAssetChain, out);
 245 }
 246
 247
 248 /*
 249  * On assetchain
 250  * in: txid
 251  * out: pair<notarisationTxHash,merkleBranch>
 252  */
 253 TxProof GetAssetchainProof(uint256 hash)
 254 {
 255     int nIndex;
 256     CBlockIndex* blockIndex;
 257     Notarisation nota;
 258     std::vector<uint256> branch;
 259
 260     {
 261         uint256 blockHash;
 262         CTransaction tx;
 263         if (!GetTransaction(hash, tx, blockHash, true))
 264             throw std::runtime_error("cannot find transaction");
 265
 266         if (blockHash.IsNull())
 267             throw std::runtime_error("tx still in mempool");
 268
 269         blockIndex = mapBlockIndex[blockHash];
 270         int h = blockIndex->nHeight;
 271         // The assumption here is that the first notarisation for a height GTE than
 272         // the transaction block height will contain the corresponding MoM. If there
 273         // are sequence issues with the notarisations this may fail.
 274         auto isTarget = [&](Notarisation &nota) {
 275             if (!IsSameAssetChain(nota)) return false;
 276             return nota.second.height >= blockIndex->nHeight;
 277         };
 278         if (!ScanNotarisationsFromHeight(blockIndex->nHeight, isTarget, nota))
 279             throw std::runtime_error("backnotarisation not yet confirmed");
 280
 281         // index of block in MoM leaves
 282         nIndex = nota.second.height - blockIndex->nHeight;
 283     }
 284
 285     // build merkle chain from blocks to MoM
 286     {
 287         std::vector<uint256> leaves, tree;
 288         for (int i=0; i<nota.second.MoMDepth; i++) {
 289             uint256 mRoot = chainActive[nota.second.height - i]->hashMerkleRoot;
 290             leaves.push_back(mRoot);
 291         }
 292         bool fMutated;
 293         BuildMerkleTree(&fMutated, leaves, tree);
 294         branch = GetMerkleBranch(nIndex, leaves.size(), tree);
 295
 296         // Check branch
 297         uint256 ourResult = SafeCheckMerkleBranch(blockIndex->hashMerkleRoot, branch, nIndex);
 298         if (nota.second.MoM != ourResult)
 299             throw std::runtime_error("Failed merkle block->MoM");
 300     }
 301
 302     // Now get the tx merkle branch
 303     {
 304         CBlock block;
 305
 306         if (fHavePruned && !(blockIndex->nStatus & BLOCK_HAVE_DATA) && blockIndex->nTx > 0)
 307             throw std::runtime_error("Block not available (pruned data)");
 308
 309         if(!ReadBlockFromDisk(block, blockIndex,1))
 310             throw std::runtime_error("Can't read block from disk");
 311
 312         // Locate the transaction in the block
 313         int nTxIndex;
 314         for (nTxIndex = 0; nTxIndex < (int)block.vtx.size(); nTxIndex++)
 315             if (block.vtx[nTxIndex].GetHash() == hash)
 316                 break;
 317
 318         if (nTxIndex == (int)block.vtx.size())
 319             throw std::runtime_error("Error locating tx in block");
 320
 321         std::vector<uint256> txBranch = block.GetMerkleBranch(nTxIndex);
 322
 323         // Check branch
 324         if (block.hashMerkleRoot != CBlock::CheckMerkleBranch(hash, txBranch, nTxIndex))
 325             throw std::runtime_error("Failed merkle tx->block");
 326
 327         // concatenate branches
 328         nIndex = (nIndex << txBranch.size()) + nTxIndex;
 329         branch.insert(branch.begin(), txBranch.begin(), txBranch.end());
 330     }
 331
 332     // Check the proof
 333     if (nota.second.MoM != CBlock::CheckMerkleBranch(hash, branch, nIndex))
 334         throw std::runtime_error("Failed validating MoM");
 335
 336     // All done!
 337     CDataStream ssProof(SER_NETWORK, PROTOCOL_VERSION);
 338     return std::make_pair(nota.second.txHash, MerkleBranch(nIndex, branch));
 339 }