src/merkleblock.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2015 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 #ifndef BITCOIN_MERKLEBLOCK_H
   7 #define BITCOIN_MERKLEBLOCK_H
   8
   9 #include "serialize.h"
  10 #include "uint256.h"
  11 #include "primitives/block.h"
  12 #include "bloom.h"
  13
  14 #include <vector>
  15
  16 /** Data structure that represents a partial merkle tree.
  17  *
  18  * It represents a subset of the txid's of a known block, in a way that
  19  * allows recovery of the list of txid's and the merkle root, in an
  20  * authenticated way.
  21  *
  22  * The encoding works as follows: we traverse the tree in depth-first order,
  23  * storing a bit for each traversed node, signifying whether the node is the
  24  * parent of at least one matched leaf txid (or a matched txid itself). In
  25  * case we are at the leaf level, or this bit is 0, its merkle node hash is
  26  * stored, and its children are not explorer further. Otherwise, no hash is
  27  * stored, but we recurse into both (or the only) child branch. During
  28  * decoding, the same depth-first traversal is performed, consuming bits and
  29  * hashes as they written during encoding.
  30  *
  31  * The serialization is fixed and provides a hard guarantee about the
  32  * encoded size:
  33  *
  34  *   SIZE <= 10 + ceil(32.25*N)
  35  *
  36  * Where N represents the number of leaf nodes of the partial tree. N itself
  37  * is bounded by:
  38  *
  39  *   N <= total_transactions
  40  *   N <= 1 + matched_transactions*tree_height
  41  *
  42  * The serialization format:
  43  *  - uint32     total_transactions (4 bytes)
  44  *  - varint     number of hashes   (1-3 bytes)
  45  *  - uint256[]  hashes in depth-first order (<= 32*N bytes)
  46  *  - varint     number of bytes of flag bits (1-3 bytes)
  47  *  - byte[]     flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
  48  * The size constraints follow from this.
  49  */
  50 class CPartialMerkleTree
  51 {
  52 protected:
  53     /** the total number of transactions in the block */
  54     unsigned int nTransactions;
  55
  56     /** node-is-parent-of-matched-txid bits */
  57     std::vector<bool> vBits;
  58
  59     /** txids and internal hashes */
  60     std::vector<uint256> vHash;
  61
  62     /** flag set when encountering invalid data */
  63     bool fBad;
  64
  65     /** helper function to efficiently calculate the number of nodes at given height in the merkle tree */
  66     unsigned int CalcTreeWidth(int height) {
  67         return (nTransactions+(1 << height)-1) >> height;
  68     }
  69
  70     /** calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) */
  71     uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
  72
  73     /** recursive function that traverses tree nodes, storing the data as bits and hashes */
  74     void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
  75
  76     /**
  77      * recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild.
  78      * it returns the hash of the respective node and its respective index.
  79      */
  80     uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
  81
  82 public:
  83
  84     /** serialization implementation */
  85     ADD_SERIALIZE_METHODS;
  86
  87     template <typename Stream, typename Operation>
  88     inline void SerializationOp(Stream& s, Operation ser_action) {
  89         READWRITE(nTransactions);
  90         READWRITE(vHash);
  91         std::vector<unsigned char> vBytes;
  92         if (ser_action.ForRead()) {
  93             READWRITE(vBytes);
  94             CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
  95             us.vBits.resize(vBytes.size() * 8);
  96             for (unsigned int p = 0; p < us.vBits.size(); p++)
  97                 us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
  98             us.fBad = false;
  99         } else {
 100             vBytes.resize((vBits.size()+7)/8);
 101             for (unsigned int p = 0; p < vBits.size(); p++)
 102                 vBytes[p / 8] |= vBits[p] << (p % 8);
 103             READWRITE(vBytes);
 104         }
 105     }
 106
 107     /** Construct a partial merkle tree from a list of transaction ids, and a mask that selects a subset of them */
 108     CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
 109
 110     CPartialMerkleTree();
 111
 112     /**
 113      * extract the matching txid's represented by this partial merkle tree
 114      * and their respective indices within the partial tree.
 115      * returns the merkle root, or 0 in case of failure
 116      */
 117     uint256 ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
 118 };
 119
 120
 121 /**
 122  * Used to relay blocks as header + vector<merkle branch>
 123  * to filtered nodes.
 124  */
 125 class CMerkleBlock
 126 {
 127 public:
 128     /** Public only for unit testing */
 129     CBlockHeader header;
 130     CPartialMerkleTree txn;
 131
 132 public:
 133     /** Public only for unit testing and relay testing (not relayed) */
 134     std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
 135
 136     /**
 137      * Create from a CBlock, filtering transactions according to filter
 138      * Note that this will call IsRelevantAndUpdate on the filter for each transaction,
 139      * thus the filter will likely be modified.
 140      */
 141     CMerkleBlock(const CBlock& block, CBloomFilter& filter);
 142
 143     // Create from a CBlock, matching the txids in the set
 144     CMerkleBlock(const CBlock& block, const std::set<uint256>& txids);
 145
 146     CMerkleBlock() {}
 147
 148     ADD_SERIALIZE_METHODS;
 149
 150     template <typename Stream, typename Operation>
 151     inline void SerializationOp(Stream& s, Operation ser_action) {
 152         READWRITE(header);
 153         READWRITE(txn);
 154     }
 155 };
 156
 157 #endif // BITCOIN_MERKLEBLOCK_H