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