Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 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 3850 : 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 0 : unsigned int CalcTreeWidth(int height) {
67 291436 : 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.
79 : */
80 : uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch);
81 :
82 : public:
83 :
84 : /** serialization implementation */
85 351 : ADD_SERIALIZE_METHODS;
86 :
87 : template <typename Stream, typename Operation>
88 351 : inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
89 351 : READWRITE(nTransactions);
90 351 : READWRITE(vHash);
91 : std::vector<unsigned char> vBytes;
92 351 : if (ser_action.ForRead()) {
93 175 : READWRITE(vBytes);
94 175 : CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
95 350 : us.vBits.resize(vBytes.size() * 8);
96 155775 : for (unsigned int p = 0; p < us.vBits.size(); p++)
97 233400 : us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
98 175 : us.fBad = false;
99 : } else {
100 352 : vBytes.resize((vBits.size()+7)/8);
101 154374 : for (unsigned int p = 0; p < vBits.size(); p++)
102 308396 : vBytes[p / 8] |= vBits[p] << (p % 8);
103 176 : READWRITE(vBytes);
104 : }
105 351 : }
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 : * returns the merkle root, or 0 in case of failure
115 : */
116 : uint256 ExtractMatches(std::vector<uint256> &vMatch);
117 : };
118 :
119 :
120 : /**
121 : * Used to relay blocks as header + vector<merkle branch>
122 : * to filtered nodes.
123 : */
124 54 : class CMerkleBlock
125 : {
126 : public:
127 : /** Public only for unit testing */
128 : CBlockHeader header;
129 : CPartialMerkleTree txn;
130 :
131 : public:
132 : /** Public only for unit testing and relay testing (not relayed) */
133 : std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
134 :
135 : /**
136 : * Create from a CBlock, filtering transactions according to filter
137 : * Note that this will call IsRelevantAndUpdate on the filter for each transaction,
138 : * thus the filter will likely be modified.
139 : */
140 : CMerkleBlock(const CBlock& block, CBloomFilter& filter);
141 :
142 : // Create from a CBlock, matching the txids in the set
143 : CMerkleBlock(const CBlock& block, const std::set<uint256>& txids);
144 :
145 14 : CMerkleBlock() {}
146 :
147 15 : ADD_SERIALIZE_METHODS;
148 :
149 : template <typename Stream, typename Operation>
150 15 : inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
151 15 : READWRITE(header);
152 15 : READWRITE(txn);
153 15 : }
154 : };
155 :
156 : #endif // BITCOIN_MERKLEBLOCK_H
|
