1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2011 Vince Durham
3 // Copyright (c) 2009-2014 The Bitcoin developers
4 // Copyright (c) 2014-2019 Daniel Kraft
5 // Distributed under the MIT/X11 software license, see the accompanying
6 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
7
8 #include <auxpow.h>
9
10 #include <consensus/consensus.h>
11 #include <consensus/merkle.h>
12 #include <hash.h>
13 #include <primitives/block.h>
14 #include <script/script.h>
15 #include <util/strencodings.h>
16 #include <util/system.h>
17
18 #include <algorithm>
19
20 namespace
21 {
22
23 /**
24 * Decodes a 32-bit little endian integer from raw bytes.
25 */
26 uint32_t
DecodeLE32(const unsigned char * bytes)27 DecodeLE32 (const unsigned char* bytes)
28 {
29 uint32_t res = 0;
30 for (int i = 0; i < 4; ++i)
31 {
32 res <<= 8;
33 res |= bytes[3 - i];
34 }
35 return res;
36 }
37
38 } // anonymous namespace
39
40 bool
check(const uint256 & hashAuxBlock,int nChainId,const Consensus::Params & params) const41 CAuxPow::check (const uint256& hashAuxBlock, int nChainId,
42 const Consensus::Params& params) const
43 {
44 if (params.fStrictChainId && parentBlock.GetChainId () == nChainId)
45 return error("Aux POW parent has our chain ID");
46
47 if (vChainMerkleBranch.size() > 30)
48 return error("Aux POW chain merkle branch too long");
49
50 // Check that the chain merkle root is in the coinbase
51 const uint256 nRootHash
52 = CheckMerkleBranch (hashAuxBlock, vChainMerkleBranch, nChainIndex);
53 valtype vchRootHash(nRootHash.begin (), nRootHash.end ());
54 std::reverse (vchRootHash.begin (), vchRootHash.end ()); // correct endian
55
56 // Check that we are in the parent block merkle tree
57 if (CheckMerkleBranch(coinbaseTx->GetHash(), vMerkleBranch, 0)
58 != parentBlock.hashMerkleRoot)
59 return error("Aux POW merkle root incorrect");
60
61 // Check that there is at least one input.
62 if (coinbaseTx->vin.empty())
63 return error("Aux POW coinbase has no inputs");
64
65 const CScript script = coinbaseTx->vin[0].scriptSig;
66
67 // Check that the same work is not submitted twice to our chain.
68 //
69
70 const unsigned char* const mmHeaderBegin = pchMergedMiningHeader;
71 const unsigned char* const mmHeaderEnd
72 = mmHeaderBegin + sizeof (pchMergedMiningHeader);
73 CScript::const_iterator pcHead =
74 std::search(script.begin(), script.end(), mmHeaderBegin, mmHeaderEnd);
75
76 CScript::const_iterator pc =
77 std::search(script.begin(), script.end(), vchRootHash.begin(), vchRootHash.end());
78
79 if (pc == script.end())
80 return error("Aux POW missing chain merkle root in parent coinbase");
81
82 if (pcHead != script.end())
83 {
84 // Enforce only one chain merkle root by checking that a single instance of the merged
85 // mining header exists just before.
86 if (script.end() != std::search(pcHead + 1, script.end(),
87 mmHeaderBegin, mmHeaderEnd))
88 return error("Multiple merged mining headers in coinbase");
89 if (pcHead + sizeof(pchMergedMiningHeader) != pc)
90 return error("Merged mining header is not just before chain merkle root");
91 }
92 else
93 {
94 // For backward compatibility.
95 // Enforce only one chain merkle root by checking that it starts early in the coinbase.
96 // 8-12 bytes are enough to encode extraNonce and nBits.
97 if (pc - script.begin() > 20)
98 return error("Aux POW chain merkle root must start in the first 20 bytes of the parent coinbase");
99 }
100
101
102 // Ensure we are at a deterministic point in the merkle leaves by hashing
103 // a nonce and our chain ID and comparing to the index.
104 pc += vchRootHash.size();
105 if (script.end() - pc < 8)
106 return error("Aux POW missing chain merkle tree size and nonce in parent coinbase");
107
108 const uint32_t nSize = DecodeLE32 (&pc[0]);
109 const unsigned merkleHeight = vChainMerkleBranch.size ();
110 if (nSize != (1u << merkleHeight))
111 return error("Aux POW merkle branch size does not match parent coinbase");
112
113 const uint32_t nNonce = DecodeLE32 (&pc[4]);
114 if (nChainIndex != getExpectedIndex (nNonce, nChainId, merkleHeight))
115 return error("Aux POW wrong index");
116
117 return true;
118 }
119
120 int
getExpectedIndex(uint32_t nNonce,int nChainId,unsigned h)121 CAuxPow::getExpectedIndex (uint32_t nNonce, int nChainId, unsigned h)
122 {
123 // Choose a pseudo-random slot in the chain merkle tree
124 // but have it be fixed for a size/nonce/chain combination.
125 //
126 // This prevents the same work from being used twice for the
127 // same chain while reducing the chance that two chains clash
128 // for the same slot.
129
130 /* This computation can overflow the uint32 used. This is not an issue,
131 though, since we take the mod against a power-of-two in the end anyway.
132 This also ensures that the computation is, actually, consistent
133 even if done in 64 bits as it was in the past on some systems.
134
135 Note that h is always <= 30 (enforced by the maximum allowed chain
136 merkle branch length), so that 32 bits are enough for the computation. */
137
138 uint32_t rand = nNonce;
139 rand = rand * 1103515245 + 12345;
140 rand += nChainId;
141 rand = rand * 1103515245 + 12345;
142
143 return rand % (1u << h);
144 }
145
146 uint256
CheckMerkleBranch(uint256 hash,const std::vector<uint256> & vMerkleBranch,int nIndex)147 CAuxPow::CheckMerkleBranch (uint256 hash,
148 const std::vector<uint256>& vMerkleBranch,
149 int nIndex)
150 {
151 if (nIndex == -1)
152 return uint256 ();
153 for (std::vector<uint256>::const_iterator it(vMerkleBranch.begin ());
154 it != vMerkleBranch.end (); ++it)
155 {
156 if (nIndex & 1)
157 hash = Hash (*it, hash);
158 else
159 hash = Hash (hash, *it);
160 nIndex >>= 1;
161 }
162 return hash;
163 }
164
165 std::unique_ptr<CAuxPow>
createAuxPow(const CPureBlockHeader & header)166 CAuxPow::createAuxPow (const CPureBlockHeader& header)
167 {
168 assert (header.IsAuxpow ());
169
170 /* Build a minimal coinbase script input for merge-mining. */
171 const uint256 blockHash = header.GetHash ();
172 valtype inputData(blockHash.begin (), blockHash.end ());
173 std::reverse (inputData.begin (), inputData.end ());
174 inputData.push_back (1);
175 inputData.insert (inputData.end (), 7, 0);
176
177 /* Fake a parent-block coinbase with just the required input
178 script and no outputs. */
179 CMutableTransaction coinbase;
180 coinbase.vin.resize (1);
181 coinbase.vin[0].prevout.SetNull ();
182 coinbase.vin[0].scriptSig = (CScript () << inputData);
183 assert (coinbase.vout.empty ());
184 CTransactionRef coinbaseRef = MakeTransactionRef (coinbase);
185
186 /* Build a fake parent block with the coinbase. */
187 CBlock parent;
188 parent.nVersion = 1;
189 parent.vtx.resize (1);
190 parent.vtx[0] = coinbaseRef;
191 parent.hashMerkleRoot = BlockMerkleRoot (parent);
192
193 /* Construct the auxpow object. */
194 std::unique_ptr<CAuxPow> auxpow(new CAuxPow (std::move (coinbaseRef)));
195 assert (auxpow->vMerkleBranch.empty ());
196 assert (auxpow->vChainMerkleBranch.empty ());
197 auxpow->nChainIndex = 0;
198 auxpow->parentBlock = parent;
199
200 return auxpow;
201 }
202
203 CPureBlockHeader&
initAuxPow(CBlockHeader & header)204 CAuxPow::initAuxPow (CBlockHeader& header)
205 {
206 /* Set auxpow flag right now, since we take the block hash below when creating
207 the minimal auxpow for header. */
208 header.SetAuxpowVersion(true);
209
210 std::unique_ptr<CAuxPow> apow = createAuxPow (header);
211 CPureBlockHeader& result = apow->parentBlock;
212 header.SetAuxpow (std::move (apow));
213
214 return result;
215 }
216