aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/Makefile.am2
-rw-r--r--src/Makefile.test.include1
-rw-r--r--src/chain.cpp3
-rw-r--r--src/chainparams.cpp3
-rw-r--r--src/consensus/merkle.cpp172
-rw-r--r--src/consensus/merkle.h32
-rw-r--r--src/main.cpp251
-rw-r--r--src/main.h3
-rw-r--r--src/miner.cpp3
-rw-r--r--src/net.h9
-rw-r--r--src/primitives/block.cpp63
-rw-r--r--src/primitives/block.h6
-rw-r--r--src/qt/optionsdialog.cpp75
-rw-r--r--src/qt/optionsdialog.h23
-rw-r--r--src/qt/qvalidatedlineedit.cpp16
-rw-r--r--src/qt/qvalidatedlineedit.h4
-rw-r--r--src/test/main_tests.cpp1
-rw-r--r--src/test/merkle_tests.cpp136
-rw-r--r--src/test/miner_tests.cpp3
-rw-r--r--src/test/pmt_tests.cpp3
-rw-r--r--src/version.h5
21 files changed, 664 insertions, 150 deletions
diff --git a/src/Makefile.am b/src/Makefile.am
index f1e98dabde..40f2e19af0 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -100,6 +100,7 @@ BITCOIN_CORE_H = \
compat/sanity.h \
compressor.h \
consensus/consensus.h \
+ consensus/merkle.h \
consensus/params.h \
consensus/validation.h \
core_io.h \
@@ -268,6 +269,7 @@ libbitcoin_common_a_SOURCES = \
chainparams.cpp \
coins.cpp \
compressor.cpp \
+ consensus/merkle.cpp \
core_read.cpp \
core_write.cpp \
hash.cpp \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index fafc1a2944..c377183ad5 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -57,6 +57,7 @@ BITCOIN_TESTS =\
test/dbwrapper_tests.cpp \
test/main_tests.cpp \
test/mempool_tests.cpp \
+ test/merkle_tests.cpp \
test/miner_tests.cpp \
test/mruset_tests.cpp \
test/multisig_tests.cpp \
diff --git a/src/chain.cpp b/src/chain.cpp
index 5b8ce076c4..3450ed6c3f 100644
--- a/src/chain.cpp
+++ b/src/chain.cpp
@@ -51,6 +51,9 @@ CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
}
const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
+ if (pindex == NULL) {
+ return NULL;
+ }
if (pindex->nHeight > Height())
pindex = pindex->GetAncestor(Height());
while (pindex && !Contains(pindex))
diff --git a/src/chainparams.cpp b/src/chainparams.cpp
index 5d6d1ef9d8..a46866a2be 100644
--- a/src/chainparams.cpp
+++ b/src/chainparams.cpp
@@ -4,6 +4,7 @@
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include "chainparams.h"
+#include "consensus/merkle.h"
#include "tinyformat.h"
#include "util.h"
@@ -32,7 +33,7 @@ static CBlock CreateGenesisBlock(const char* pszTimestamp, const CScript& genesi
genesis.nVersion = nVersion;
genesis.vtx.push_back(txNew);
genesis.hashPrevBlock.SetNull();
- genesis.hashMerkleRoot = genesis.ComputeMerkleRoot();
+ genesis.hashMerkleRoot = BlockMerkleRoot(genesis);
return genesis;
}
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
new file mode 100644
index 0000000000..9a8afa8a33
--- /dev/null
+++ b/src/consensus/merkle.cpp
@@ -0,0 +1,172 @@
+#include "merkle.h"
+#include "hash.h"
+#include "utilstrencodings.h"
+
+/* WARNING! If you're reading this because you're learning about crypto
+ and/or designing a new system that will use merkle trees, keep in mind
+ that the following merkle tree algorithm has a serious flaw related to
+ duplicate txids, resulting in a vulnerability (CVE-2012-2459).
+
+ The reason is that if the number of hashes in the list at a given time
+ is odd, the last one is duplicated before computing the next level (which
+ is unusual in Merkle trees). This results in certain sequences of
+ transactions leading to the same merkle root. For example, these two
+ trees:
+
+ A A
+ / \ / \
+ B C B C
+ / \ | / \ / \
+ D E F D E F F
+ / \ / \ / \ / \ / \ / \ / \
+ 1 2 3 4 5 6 1 2 3 4 5 6 5 6
+
+ for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
+ 6 are repeated) result in the same root hash A (because the hash of both
+ of (F) and (F,F) is C).
+
+ The vulnerability results from being able to send a block with such a
+ transaction list, with the same merkle root, and the same block hash as
+ the original without duplication, resulting in failed validation. If the
+ receiving node proceeds to mark that block as permanently invalid
+ however, it will fail to accept further unmodified (and thus potentially
+ valid) versions of the same block. We defend against this by detecting
+ the case where we would hash two identical hashes at the end of the list
+ together, and treating that identically to the block having an invalid
+ merkle root. Assuming no double-SHA256 collisions, this will detect all
+ known ways of changing the transactions without affecting the merkle
+ root.
+*/
+
+/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
+static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
+ if (pbranch) pbranch->clear();
+ if (leaves.size() == 0) {
+ if (pmutated) *pmutated = false;
+ if (proot) *proot = uint256();
+ return;
+ }
+ bool mutated = false;
+ // count is the number of leaves processed so far.
+ uint32_t count = 0;
+ // inner is an array of eagerly computed subtree hashes, indexed by tree
+ // level (0 being the leaves).
+ // For example, when count is 25 (11001 in binary), inner[4] is the hash of
+ // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
+ // the last leaf. The other inner entries are undefined.
+ uint256 inner[32];
+ // Which position in inner is a hash that depends on the matching leaf.
+ int matchlevel = -1;
+ // First process all leaves into 'inner' values.
+ while (count < leaves.size()) {
+ uint256 h = leaves[count];
+ bool matchh = count == branchpos;
+ count++;
+ int level;
+ // For each of the lower bits in count that are 0, do 1 step. Each
+ // corresponds to an inner value that existed before processing the
+ // current leaf, and each needs a hash to combine it.
+ for (level = 0; !(count & (((uint32_t)1) << level)); level++) {
+ if (pbranch) {
+ if (matchh) {
+ pbranch->push_back(inner[level]);
+ } else if (matchlevel == level) {
+ pbranch->push_back(h);
+ matchh = true;
+ }
+ }
+ mutated |= (inner[level] == h);
+ CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
+ }
+ // Store the resulting hash at inner position level.
+ inner[level] = h;
+ if (matchh) {
+ matchlevel = level;
+ }
+ }
+ // Do a final 'sweep' over the rightmost branch of the tree to process
+ // odd levels, and reduce everything to a single top value.
+ // Level is the level (counted from the bottom) up to which we've sweeped.
+ int level = 0;
+ // As long as bit number level in count is zero, skip it. It means there
+ // is nothing left at this level.
+ while (!(count & (((uint32_t)1) << level))) {
+ level++;
+ }
+ uint256 h = inner[level];
+ bool matchh = matchlevel == level;
+ while (count != (((uint32_t)1) << level)) {
+ // If we reach this point, h is an inner value that is not the top.
+ // We combine it with itself (Bitcoin's special rule for odd levels in
+ // the tree) to produce a higher level one.
+ if (pbranch && matchh) {
+ pbranch->push_back(h);
+ }
+ CHash256().Write(h.begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
+ // Increment count to the value it would have if two entries at this
+ // level had existed.
+ count += (((uint32_t)1) << level);
+ level++;
+ // And propagate the result upwards accordingly.
+ while (!(count & (((uint32_t)1) << level))) {
+ if (pbranch) {
+ if (matchh) {
+ pbranch->push_back(inner[level]);
+ } else if (matchlevel == level) {
+ pbranch->push_back(h);
+ matchh = true;
+ }
+ }
+ CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
+ level++;
+ }
+ }
+ // Return result.
+ if (pmutated) *pmutated = mutated;
+ if (proot) *proot = h;
+}
+
+uint256 ComputeMerkleRoot(const std::vector<uint256>& leaves, bool* mutated) {
+ uint256 hash;
+ MerkleComputation(leaves, &hash, mutated, -1, NULL);
+ return hash;
+}
+
+std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
+ std::vector<uint256> ret;
+ MerkleComputation(leaves, NULL, NULL, position, &ret);
+ return ret;
+}
+
+uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
+ uint256 hash = leaf;
+ for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
+ if (nIndex & 1) {
+ hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash));
+ } else {
+ hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it));
+ }
+ nIndex >>= 1;
+ }
+ return hash;
+}
+
+uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
+{
+ std::vector<uint256> leaves;
+ leaves.resize(block.vtx.size());
+ for (size_t s = 0; s < block.vtx.size(); s++) {
+ leaves[s] = block.vtx[s].GetHash();
+ }
+ return ComputeMerkleRoot(leaves, mutated);
+}
+
+std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
+{
+ std::vector<uint256> leaves;
+ leaves.resize(block.vtx.size());
+ for (size_t s = 0; s < block.vtx.size(); s++) {
+ leaves[s] = block.vtx[s].GetHash();
+ }
+ return ComputeMerkleBranch(leaves, position);
+}
diff --git a/src/consensus/merkle.h b/src/consensus/merkle.h
new file mode 100644
index 0000000000..6ef59745ac
--- /dev/null
+++ b/src/consensus/merkle.h
@@ -0,0 +1,32 @@
+// Copyright (c) 2015 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_MERKLE
+#define BITCOIN_MERKLE
+
+#include <stdint.h>
+#include <vector>
+
+#include "primitives/transaction.h"
+#include "primitives/block.h"
+#include "uint256.h"
+
+uint256 ComputeMerkleRoot(const std::vector<uint256>& leaves, bool* mutated = NULL);
+std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position);
+uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& branch, uint32_t position);
+
+/*
+ * Compute the Merkle root of the transactions in a block.
+ * *mutated is set to true if a duplicated subtree was found.
+ */
+uint256 BlockMerkleRoot(const CBlock& block, bool* mutated = NULL);
+
+/*
+ * Compute the Merkle branch for the tree of transactions in a block, for a
+ * given position.
+ * This can be verified using ComputeMerkleRootFromBranch.
+ */
+std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position);
+
+#endif
diff --git a/src/main.cpp b/src/main.cpp
index 6b6840ce8c..31913956b7 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -12,6 +12,7 @@
#include "checkpoints.h"
#include "checkqueue.h"
#include "consensus/consensus.h"
+#include "consensus/merkle.h"
#include "consensus/validation.h"
#include "hash.h"
#include "init.h"
@@ -246,6 +247,8 @@ struct CNodeState {
uint256 hashLastUnknownBlock;
//! The last full block we both have.
CBlockIndex *pindexLastCommonBlock;
+ //! The best header we have sent our peer.
+ CBlockIndex *pindexBestHeaderSent;
//! Whether we've started headers synchronization with this peer.
bool fSyncStarted;
//! Since when we're stalling block download progress (in microseconds), or 0.
@@ -255,6 +258,8 @@ struct CNodeState {
int nBlocksInFlightValidHeaders;
//! Whether we consider this a preferred download peer.
bool fPreferredDownload;
+ //! Whether this peer wants invs or headers (when possible) for block announcements.
+ bool fPreferHeaders;
CNodeState() {
fCurrentlyConnected = false;
@@ -263,11 +268,13 @@ struct CNodeState {
pindexBestKnownBlock = NULL;
hashLastUnknownBlock.SetNull();
pindexLastCommonBlock = NULL;
+ pindexBestHeaderSent = NULL;
fSyncStarted = false;
nStallingSince = 0;
nBlocksInFlight = 0;
nBlocksInFlightValidHeaders = 0;
fPreferredDownload = false;
+ fPreferHeaders = false;
}
};
@@ -397,6 +404,22 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) {
}
}
+// Requires cs_main
+bool CanDirectFetch(const Consensus::Params &consensusParams)
+{
+ return chainActive.Tip()->GetBlockTime() > GetAdjustedTime() - consensusParams.nPowTargetSpacing * 20;
+}
+
+// Requires cs_main
+bool PeerHasHeader(CNodeState *state, CBlockIndex *pindex)
+{
+ if (state->pindexBestKnownBlock && pindex == state->pindexBestKnownBlock->GetAncestor(pindex->nHeight))
+ return true;
+ if (state->pindexBestHeaderSent && pindex == state->pindexBestHeaderSent->GetAncestor(pindex->nHeight))
+ return true;
+ return false;
+}
+
/** Find the last common ancestor two blocks have.
* Both pa and pb must be non-NULL. */
CBlockIndex* LastCommonAncestor(CBlockIndex* pa, CBlockIndex* pb) {
@@ -2556,16 +2579,17 @@ static bool ActivateBestChainStep(CValidationState& state, const CChainParams& c
* or an activated best chain. pblock is either NULL or a pointer to a block
* that is already loaded (to avoid loading it again from disk).
*/
-bool ActivateBestChain(CValidationState& state, const CChainParams& chainparams, const CBlock* pblock)
-{
- CBlockIndex *pindexNewTip = NULL;
+bool ActivateBestChain(CValidationState &state, const CChainParams& chainparams, const CBlock *pblock) {
CBlockIndex *pindexMostWork = NULL;
do {
boost::this_thread::interruption_point();
+ CBlockIndex *pindexNewTip = NULL;
+ const CBlockIndex *pindexFork;
bool fInitialDownload;
{
LOCK(cs_main);
+ CBlockIndex *pindexOldTip = chainActive.Tip();
pindexMostWork = FindMostWorkChain();
// Whether we have anything to do at all.
@@ -2576,26 +2600,44 @@ bool ActivateBestChain(CValidationState& state, const CChainParams& chainparams,
return false;
pindexNewTip = chainActive.Tip();
+ pindexFork = chainActive.FindFork(pindexOldTip);
fInitialDownload = IsInitialBlockDownload();
}
// When we reach this point, we switched to a new tip (stored in pindexNewTip).
// Notifications/callbacks that can run without cs_main
if (!fInitialDownload) {
- uint256 hashNewTip = pindexNewTip->GetBlockHash();
+ // Find the hashes of all blocks that weren't previously in the best chain.
+ std::vector<uint256> vHashes;
+ CBlockIndex *pindexToAnnounce = pindexNewTip;
+ while (pindexToAnnounce != pindexFork) {
+ vHashes.push_back(pindexToAnnounce->GetBlockHash());
+ pindexToAnnounce = pindexToAnnounce->pprev;
+ if (vHashes.size() == MAX_BLOCKS_TO_ANNOUNCE) {
+ // Limit announcements in case of a huge reorganization.
+ // Rely on the peer's synchronization mechanism in that case.
+ break;
+ }
+ }
// Relay inventory, but don't relay old inventory during initial block download.
int nBlockEstimate = 0;
if (fCheckpointsEnabled)
nBlockEstimate = Checkpoints::GetTotalBlocksEstimate(chainparams.Checkpoints());
{
LOCK(cs_vNodes);
- BOOST_FOREACH(CNode* pnode, vNodes)
- if (chainActive.Height() > (pnode->nStartingHeight != -1 ? pnode->nStartingHeight - 2000 : nBlockEstimate))
- pnode->PushInventory(CInv(MSG_BLOCK, hashNewTip));
+ BOOST_FOREACH(CNode* pnode, vNodes) {
+ if (chainActive.Height() > (pnode->nStartingHeight != -1 ? pnode->nStartingHeight - 2000 : nBlockEstimate)) {
+ BOOST_REVERSE_FOREACH(const uint256& hash, vHashes) {
+ pnode->PushBlockHash(hash);
+ }
+ }
+ }
}
// Notify external listeners about the new tip.
- GetMainSignals().UpdatedBlockTip(pindexNewTip);
- uiInterface.NotifyBlockTip(hashNewTip);
+ if (!vHashes.empty()) {
+ GetMainSignals().UpdatedBlockTip(pindexNewTip);
+ uiInterface.NotifyBlockTip(vHashes.front());
+ }
}
} while(pindexMostWork != chainActive.Tip());
CheckBlockIndex(chainparams.GetConsensus());
@@ -2876,7 +2918,7 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo
// Check the merkle root.
if (fCheckMerkleRoot) {
bool mutated;
- uint256 hashMerkleRoot2 = block.ComputeMerkleRoot(&mutated);
+ uint256 hashMerkleRoot2 = BlockMerkleRoot(block, &mutated);
if (block.hashMerkleRoot != hashMerkleRoot2)
return state.DoS(100, error("CheckBlock(): hashMerkleRoot mismatch"),
REJECT_INVALID, "bad-txnmrklroot", true);
@@ -4332,6 +4374,14 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
LOCK(cs_main);
State(pfrom->GetId())->fCurrentlyConnected = true;
}
+
+ if (pfrom->nVersion >= SENDHEADERS_VERSION) {
+ // Tell our peer we prefer to receive headers rather than inv's
+ // We send this to non-NODE NETWORK peers as well, because even
+ // non-NODE NETWORK peers can announce blocks (such as pruning
+ // nodes)
+ pfrom->PushMessage("sendheaders");
+ }
}
@@ -4401,6 +4451,12 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
pfrom->fDisconnect = true;
}
+ else if (strCommand == "sendheaders")
+ {
+ LOCK(cs_main);
+ State(pfrom->GetId())->fPreferHeaders = true;
+ }
+
else if (strCommand == "inv")
{
@@ -4445,7 +4501,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
// not a direct successor.
pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexBestHeader), inv.hash);
CNodeState *nodestate = State(pfrom->GetId());
- if (chainActive.Tip()->GetBlockTime() > GetAdjustedTime() - chainparams.GetConsensus().nPowTargetSpacing * 20 &&
+ if (CanDirectFetch(chainparams.GetConsensus()) &&
nodestate->nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) {
vToFetch.push_back(inv);
// Mark block as in flight already, even though the actual "getdata" message only goes out
@@ -4553,6 +4609,8 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
LogPrint("net", "Ignoring getheaders from peer=%d because node is in initial block download\n", pfrom->id);
return true;
}
+
+ CNodeState *nodestate = State(pfrom->GetId());
CBlockIndex* pindex = NULL;
if (locator.IsNull())
{
@@ -4580,6 +4638,11 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
if (--nLimit <= 0 || pindex->GetBlockHash() == hashStop)
break;
}
+ // pindex can be NULL either if we sent chainActive.Tip() OR
+ // if our peer has chainActive.Tip() (and thus we are sending an empty
+ // headers message). In both cases it's safe to update
+ // pindexBestHeaderSent to be our tip.
+ nodestate->pindexBestHeaderSent = pindex ? pindex : chainActive.Tip();
pfrom->PushMessage("headers", vHeaders);
}
@@ -4609,11 +4672,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
mapAlreadyAskedFor.erase(inv);
- // Check for recently rejected (and do other quick existence checks)
- if (AlreadyHave(inv))
- return true;
-
- if (AcceptToMemoryPool(mempool, state, tx, true, &fMissingInputs))
+ if (!AlreadyHave(inv) && AcceptToMemoryPool(mempool, state, tx, true, &fMissingInputs))
{
mempool.check(pcoinsTip);
RelayTransaction(tx);
@@ -4693,13 +4752,20 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
if (pfrom->fWhitelisted && GetBoolArg("-whitelistalwaysrelay", DEFAULT_WHITELISTALWAYSRELAY)) {
// Always relay transactions received from whitelisted peers, even
- // if they were rejected from the mempool, allowing the node to
- // function as a gateway for nodes hidden behind it.
+ // if they were already in the mempool or rejected from it due
+ // to policy, allowing the node to function as a gateway for
+ // nodes hidden behind it.
//
- // FIXME: This includes invalid transactions, which means a
- // whitelisted peer could get us banned! We may want to change
- // that.
- RelayTransaction(tx);
+ // Never relay transactions that we would assign a non-zero DoS
+ // score for, as we expect peers to do the same with us in that
+ // case.
+ int nDoS = 0;
+ if (!state.IsInvalid(nDoS) || nDoS == 0) {
+ LogPrintf("Force relaying tx %s from whitelisted peer=%d\n", tx.GetHash().ToString(), pfrom->id);
+ RelayTransaction(tx);
+ } else {
+ LogPrintf("Not relaying invalid transaction %s from whitelisted peer=%d (%s)\n", tx.GetHash().ToString(), pfrom->id, FormatStateMessage(state));
+ }
}
}
int nDoS = 0;
@@ -4768,6 +4834,53 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexLast), uint256());
}
+ bool fCanDirectFetch = CanDirectFetch(chainparams.GetConsensus());
+ CNodeState *nodestate = State(pfrom->GetId());
+ // If this set of headers is valid and ends in a block with at least as
+ // much work as our tip, download as much as possible.
+ if (fCanDirectFetch && pindexLast->IsValid(BLOCK_VALID_TREE) && chainActive.Tip()->nChainWork <= pindexLast->nChainWork) {
+ vector<CBlockIndex *> vToFetch;
+ CBlockIndex *pindexWalk = pindexLast;
+ // Calculate all the blocks we'd need to switch to pindexLast, up to a limit.
+ while (pindexWalk && !chainActive.Contains(pindexWalk) && vToFetch.size() <= MAX_BLOCKS_IN_TRANSIT_PER_PEER) {
+ if (!(pindexWalk->nStatus & BLOCK_HAVE_DATA) &&
+ !mapBlocksInFlight.count(pindexWalk->GetBlockHash())) {
+ // We don't have this block, and it's not yet in flight.
+ vToFetch.push_back(pindexWalk);
+ }
+ pindexWalk = pindexWalk->pprev;
+ }
+ // If pindexWalk still isn't on our main chain, we're looking at a
+ // very large reorg at a time we think we're close to caught up to
+ // the main chain -- this shouldn't really happen. Bail out on the
+ // direct fetch and rely on parallel download instead.
+ if (!chainActive.Contains(pindexWalk)) {
+ LogPrint("net", "Large reorg, won't direct fetch to %s (%d)\n",
+ pindexLast->GetBlockHash().ToString(),
+ pindexLast->nHeight);
+ } else {
+ vector<CInv> vGetData;
+ // Download as much as possible, from earliest to latest.
+ BOOST_REVERSE_FOREACH(CBlockIndex *pindex, vToFetch) {
+ if (nodestate->nBlocksInFlight >= MAX_BLOCKS_IN_TRANSIT_PER_PEER) {
+ // Can't download any more from this peer
+ break;
+ }
+ vGetData.push_back(CInv(MSG_BLOCK, pindex->GetBlockHash()));
+ MarkBlockAsInFlight(pfrom->GetId(), pindex->GetBlockHash(), chainparams.GetConsensus(), pindex);
+ LogPrint("net", "Requesting block %s from peer=%d\n",
+ pindex->GetBlockHash().ToString(), pfrom->id);
+ }
+ if (vGetData.size() > 1) {
+ LogPrint("net", "Downloading blocks toward %s (%d) via headers direct fetch\n",
+ pindexLast->GetBlockHash().ToString(), pindexLast->nHeight);
+ }
+ if (vGetData.size() > 0) {
+ pfrom->PushMessage("getdata", vGetData);
+ }
+ }
+ }
+
CheckBlockIndex(chainparams.GetConsensus());
}
@@ -5294,6 +5407,100 @@ bool SendMessages(CNode* pto, bool fSendTrickle)
}
//
+ // Try sending block announcements via headers
+ //
+ {
+ // If we have less than MAX_BLOCKS_TO_ANNOUNCE in our
+ // list of block hashes we're relaying, and our peer wants
+ // headers announcements, then find the first header
+ // not yet known to our peer but would connect, and send.
+ // If no header would connect, or if we have too many
+ // blocks, or if the peer doesn't want headers, just
+ // add all to the inv queue.
+ LOCK(pto->cs_inventory);
+ vector<CBlock> vHeaders;
+ bool fRevertToInv = (!state.fPreferHeaders || pto->vBlockHashesToAnnounce.size() > MAX_BLOCKS_TO_ANNOUNCE);
+ CBlockIndex *pBestIndex = NULL; // last header queued for delivery
+ ProcessBlockAvailability(pto->id); // ensure pindexBestKnownBlock is up-to-date
+
+ if (!fRevertToInv) {
+ bool fFoundStartingHeader = false;
+ // Try to find first header that our peer doesn't have, and
+ // then send all headers past that one. If we come across any
+ // headers that aren't on chainActive, give up.
+ BOOST_FOREACH(const uint256 &hash, pto->vBlockHashesToAnnounce) {
+ BlockMap::iterator mi = mapBlockIndex.find(hash);
+ assert(mi != mapBlockIndex.end());
+ CBlockIndex *pindex = mi->second;
+ if (chainActive[pindex->nHeight] != pindex) {
+ // Bail out if we reorged away from this block
+ fRevertToInv = true;
+ break;
+ }
+ assert(pBestIndex == NULL || pindex->pprev == pBestIndex);
+ pBestIndex = pindex;
+ if (fFoundStartingHeader) {
+ // add this to the headers message
+ vHeaders.push_back(pindex->GetBlockHeader());
+ } else if (PeerHasHeader(&state, pindex)) {
+ continue; // keep looking for the first new block
+ } else if (pindex->pprev == NULL || PeerHasHeader(&state, pindex->pprev)) {
+ // Peer doesn't have this header but they do have the prior one.
+ // Start sending headers.
+ fFoundStartingHeader = true;
+ vHeaders.push_back(pindex->GetBlockHeader());
+ } else {
+ // Peer doesn't have this header or the prior one -- nothing will
+ // connect, so bail out.
+ fRevertToInv = true;
+ break;
+ }
+ }
+ }
+ if (fRevertToInv) {
+ // If falling back to using an inv, just try to inv the tip.
+ // The last entry in vBlockHashesToAnnounce was our tip at some point
+ // in the past.
+ if (!pto->vBlockHashesToAnnounce.empty()) {
+ const uint256 &hashToAnnounce = pto->vBlockHashesToAnnounce.back();
+ BlockMap::iterator mi = mapBlockIndex.find(hashToAnnounce);
+ assert(mi != mapBlockIndex.end());
+ CBlockIndex *pindex = mi->second;
+
+ // Warn if we're announcing a block that is not on the main chain.
+ // This should be very rare and could be optimized out.
+ // Just log for now.
+ if (chainActive[pindex->nHeight] != pindex) {
+ LogPrint("net", "Announcing block %s not on main chain (tip=%s)\n",
+ hashToAnnounce.ToString(), chainActive.Tip()->GetBlockHash().ToString());
+ }
+
+ // If the peer announced this block to us, don't inv it back.
+ // (Since block announcements may not be via inv's, we can't solely rely on
+ // setInventoryKnown to track this.)
+ if (!PeerHasHeader(&state, pindex)) {
+ pto->PushInventory(CInv(MSG_BLOCK, hashToAnnounce));
+ LogPrint("net", "%s: sending inv peer=%d hash=%s\n", __func__,
+ pto->id, hashToAnnounce.ToString());
+ }
+ }
+ } else if (!vHeaders.empty()) {
+ if (vHeaders.size() > 1) {
+ LogPrint("net", "%s: %u headers, range (%s, %s), to peer=%d\n", __func__,
+ vHeaders.size(),
+ vHeaders.front().GetHash().ToString(),
+ vHeaders.back().GetHash().ToString(), pto->id);
+ } else {
+ LogPrint("net", "%s: sending header %s to peer=%d\n", __func__,
+ vHeaders.front().GetHash().ToString(), pto->id);
+ }
+ pto->PushMessage("headers", vHeaders);
+ state.pindexBestHeaderSent = pBestIndex;
+ }
+ pto->vBlockHashesToAnnounce.clear();
+ }
+
+ //
// Message: inventory
//
vector<CInv> vInv;
diff --git a/src/main.h b/src/main.h
index dfa2fcb537..3dec613fc7 100644
--- a/src/main.h
+++ b/src/main.h
@@ -98,6 +98,9 @@ static const unsigned int DEFAULT_BANSCORE_THRESHOLD = 100;
static const bool DEFAULT_TESTSAFEMODE = false;
+/** Maximum number of headers to announce when relaying blocks with headers message.*/
+static const unsigned int MAX_BLOCKS_TO_ANNOUNCE = 8;
+
struct BlockHasher
{
size_t operator()(const uint256& hash) const { return hash.GetCheapHash(); }
diff --git a/src/miner.cpp b/src/miner.cpp
index 5b711210db..27a1fbcf80 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -10,6 +10,7 @@
#include "chainparams.h"
#include "coins.h"
#include "consensus/consensus.h"
+#include "consensus/merkle.h"
#include "consensus/validation.h"
#include "hash.h"
#include "main.h"
@@ -373,7 +374,7 @@ void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned
assert(txCoinbase.vin[0].scriptSig.size() <= 100);
pblock->vtx[0] = txCoinbase;
- pblock->hashMerkleRoot = pblock->ComputeMerkleRoot();
+ pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
}
//////////////////////////////////////////////////////////////////////////////
diff --git a/src/net.h b/src/net.h
index 3664ce9a70..fb299fb0b4 100644
--- a/src/net.h
+++ b/src/net.h
@@ -390,6 +390,9 @@ public:
std::vector<CInv> vInventoryToSend;
CCriticalSection cs_inventory;
std::multimap<int64_t, CInv> mapAskFor;
+ // Used for headers announcements - unfiltered blocks to relay
+ // Also protected by cs_inventory
+ std::vector<uint256> vBlockHashesToAnnounce;
// Ping time measurement:
// The pong reply we're expecting, or 0 if no pong expected.
@@ -504,6 +507,12 @@ public:
}
}
+ void PushBlockHash(const uint256 &hash)
+ {
+ LOCK(cs_inventory);
+ vBlockHashesToAnnounce.push_back(hash);
+ }
+
void AskFor(const CInv& inv);
// TODO: Document the postcondition of this function. Is cs_vSend locked?
diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp
index 7a58074d24..7280c18f77 100644
--- a/src/primitives/block.cpp
+++ b/src/primitives/block.cpp
@@ -15,69 +15,6 @@ uint256 CBlockHeader::GetHash() const
return SerializeHash(*this);
}
-uint256 CBlock::ComputeMerkleRoot(bool* fMutated) const
-{
- /* WARNING! If you're reading this because you're learning about crypto
- and/or designing a new system that will use merkle trees, keep in mind
- that the following merkle tree algorithm has a serious flaw related to
- duplicate txids, resulting in a vulnerability (CVE-2012-2459).
-
- The reason is that if the number of hashes in the list at a given time
- is odd, the last one is duplicated before computing the next level (which
- is unusual in Merkle trees). This results in certain sequences of
- transactions leading to the same merkle root. For example, these two
- trees:
-
- A A
- / \ / \
- B C B C
- / \ | / \ / \
- D E F D E F F
- / \ / \ / \ / \ / \ / \ / \
- 1 2 3 4 5 6 1 2 3 4 5 6 5 6
-
- for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
- 6 are repeated) result in the same root hash A (because the hash of both
- of (F) and (F,F) is C).
-
- The vulnerability results from being able to send a block with such a
- transaction list, with the same merkle root, and the same block hash as
- the original without duplication, resulting in failed validation. If the
- receiving node proceeds to mark that block as permanently invalid
- however, it will fail to accept further unmodified (and thus potentially
- valid) versions of the same block. We defend against this by detecting
- the case where we would hash two identical hashes at the end of the list
- together, and treating that identically to the block having an invalid
- merkle root. Assuming no double-SHA256 collisions, this will detect all
- known ways of changing the transactions without affecting the merkle
- root.
- */
- std::vector<uint256> vMerkleTree;
- vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
- for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it)
- vMerkleTree.push_back(it->GetHash());
- int j = 0;
- bool mutated = false;
- for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
- {
- for (int i = 0; i < nSize; i += 2)
- {
- int i2 = std::min(i+1, nSize-1);
- if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
- // Two identical hashes at the end of the list at a particular level.
- mutated = true;
- }
- vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]), END(vMerkleTree[j+i]),
- BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
- }
- j += nSize;
- }
- if (fMutated) {
- *fMutated = mutated;
- }
- return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
-}
-
std::string CBlock::ToString() const
{
std::stringstream s;
diff --git a/src/primitives/block.h b/src/primitives/block.h
index 54731ff557..5c017d436f 100644
--- a/src/primitives/block.h
+++ b/src/primitives/block.h
@@ -118,12 +118,6 @@ public:
return block;
}
- // Build the merkle tree for this block and return the merkle root.
- // If non-NULL, *mutated is set to whether mutation was detected in the merkle
- // tree (a duplication of transactions in the block leading to an identical
- // merkle root).
- uint256 ComputeMerkleRoot(bool* mutated = NULL) const;
-
std::string ToString() const;
};
diff --git a/src/qt/optionsdialog.cpp b/src/qt/optionsdialog.cpp
index d0191fa6d8..647c860bdc 100644
--- a/src/qt/optionsdialog.cpp
+++ b/src/qt/optionsdialog.cpp
@@ -34,8 +34,7 @@ OptionsDialog::OptionsDialog(QWidget *parent, bool enableWallet) :
QDialog(parent),
ui(new Ui::OptionsDialog),
model(0),
- mapper(0),
- fProxyIpsValid(true)
+ mapper(0)
{
ui->setupUi(this);
@@ -60,12 +59,11 @@ OptionsDialog::OptionsDialog(QWidget *parent, bool enableWallet) :
connect(ui->connectSocks, SIGNAL(toggled(bool)), ui->proxyIp, SLOT(setEnabled(bool)));
connect(ui->connectSocks, SIGNAL(toggled(bool)), ui->proxyPort, SLOT(setEnabled(bool)));
+ connect(ui->connectSocks, SIGNAL(toggled(bool)), this, SLOT(updateProxyValidationState()));
connect(ui->connectSocksTor, SIGNAL(toggled(bool)), ui->proxyIpTor, SLOT(setEnabled(bool)));
connect(ui->connectSocksTor, SIGNAL(toggled(bool)), ui->proxyPortTor, SLOT(setEnabled(bool)));
-
- ui->proxyIp->installEventFilter(this);
- ui->proxyIpTor->installEventFilter(this);
+ connect(ui->connectSocksTor, SIGNAL(toggled(bool)), this, SLOT(updateProxyValidationState()));
/* Window elements init */
#ifdef Q_OS_MAC
@@ -119,7 +117,12 @@ OptionsDialog::OptionsDialog(QWidget *parent, bool enableWallet) :
mapper->setOrientation(Qt::Vertical);
/* setup/change UI elements when proxy IPs are invalid/valid */
- connect(this, SIGNAL(proxyIpChecks(QValidatedLineEdit *, int)), this, SLOT(doProxyIpChecks(QValidatedLineEdit *, int)));
+ ui->proxyIp->setCheckValidator(new ProxyAddressValidator(parent));
+ ui->proxyIpTor->setCheckValidator(new ProxyAddressValidator(parent));
+ connect(ui->proxyIp, SIGNAL(validationDidChange(QValidatedLineEdit *)), this, SLOT(updateProxyValidationState()));
+ connect(ui->proxyIpTor, SIGNAL(validationDidChange(QValidatedLineEdit *)), this, SLOT(updateProxyValidationState()));
+ connect(ui->proxyPort, SIGNAL(textChanged(const QString&)), this, SLOT(updateProxyValidationState()));
+ connect(ui->proxyPortTor, SIGNAL(textChanged(const QString&)), this, SLOT(updateProxyValidationState()));
}
OptionsDialog::~OptionsDialog()
@@ -200,18 +203,6 @@ void OptionsDialog::setMapper()
mapper->addMapping(ui->thirdPartyTxUrls, OptionsModel::ThirdPartyTxUrls);
}
-void OptionsDialog::enableOkButton()
-{
- /* prevent enabling of the OK button when data modified, if there is an invalid proxy address present */
- if(fProxyIpsValid)
- setOkButtonState(true);
-}
-
-void OptionsDialog::disableOkButton()
-{
- setOkButtonState(false);
-}
-
void OptionsDialog::setOkButtonState(bool fState)
{
ui->okButton->setEnabled(fState);
@@ -269,24 +260,20 @@ void OptionsDialog::clearStatusLabel()
ui->statusLabel->clear();
}
-void OptionsDialog::doProxyIpChecks(QValidatedLineEdit *pUiProxyIp, int nProxyPort)
+void OptionsDialog::updateProxyValidationState()
{
- Q_UNUSED(nProxyPort);
-
- CService addrProxy;
-
- /* Check for a valid IPv4 / IPv6 address */
- if (!(fProxyIpsValid = LookupNumeric(pUiProxyIp->text().toStdString().c_str(), addrProxy)))
+ QValidatedLineEdit *pUiProxyIp = ui->proxyIp;
+ QValidatedLineEdit *otherProxyWidget = (pUiProxyIp == ui->proxyIpTor) ? ui->proxyIp : ui->proxyIpTor;
+ if (pUiProxyIp->isValid() && (!ui->proxyPort->isEnabled() || ui->proxyPort->text().toInt() > 0) && (!ui->proxyPortTor->isEnabled() || ui->proxyPortTor->text().toInt() > 0))
{
- disableOkButton();
- pUiProxyIp->setValid(false);
- ui->statusLabel->setStyleSheet("QLabel { color: red; }");
- ui->statusLabel->setText(tr("The supplied proxy address is invalid."));
+ setOkButtonState(otherProxyWidget->isValid()); //only enable ok button if both proxys are valid
+ ui->statusLabel->clear();
}
else
{
- enableOkButton();
- ui->statusLabel->clear();
+ setOkButtonState(false);
+ ui->statusLabel->setStyleSheet("QLabel { color: red; }");
+ ui->statusLabel->setText(tr("The supplied proxy address is invalid."));
}
}
@@ -312,18 +299,18 @@ void OptionsDialog::updateDefaultProxyNets()
(strProxy == strDefaultProxyGUI.toStdString()) ? ui->proxyReachTor->setChecked(true) : ui->proxyReachTor->setChecked(false);
}
-bool OptionsDialog::eventFilter(QObject *object, QEvent *event)
+ProxyAddressValidator::ProxyAddressValidator(QObject *parent) :
+QValidator(parent)
{
- if(event->type() == QEvent::FocusOut)
- {
- if(object == ui->proxyIp)
- {
- Q_EMIT proxyIpChecks(ui->proxyIp, ui->proxyPort->text().toInt());
- }
- else if(object == ui->proxyIpTor)
- {
- Q_EMIT proxyIpChecks(ui->proxyIpTor, ui->proxyPortTor->text().toInt());
- }
- }
- return QDialog::eventFilter(object, event);
+}
+
+QValidator::State ProxyAddressValidator::validate(QString &input, int &pos) const
+{
+ Q_UNUSED(pos);
+ // Validate the proxy
+ proxyType addrProxy = proxyType(CService(input.toStdString(), 9050), true);
+ if (addrProxy.IsValid())
+ return QValidator::Acceptable;
+
+ return QValidator::Invalid;
}
diff --git a/src/qt/optionsdialog.h b/src/qt/optionsdialog.h
index 348489c599..489e35da49 100644
--- a/src/qt/optionsdialog.h
+++ b/src/qt/optionsdialog.h
@@ -6,6 +6,7 @@
#define BITCOIN_QT_OPTIONSDIALOG_H
#include <QDialog>
+#include <QValidator>
class OptionsModel;
class QValidatedLineEdit;
@@ -18,6 +19,18 @@ namespace Ui {
class OptionsDialog;
}
+/** Proxy address widget validator, checks for a valid proxy address.
+ */
+class ProxyAddressValidator : public QValidator
+{
+ Q_OBJECT
+
+public:
+ explicit ProxyAddressValidator(QObject *parent);
+
+ State validate(QString &input, int &pos) const;
+};
+
/** Preferences dialog. */
class OptionsDialog : public QDialog
{
@@ -30,14 +43,7 @@ public:
void setModel(OptionsModel *model);
void setMapper();
-protected:
- bool eventFilter(QObject *object, QEvent *event);
-
private Q_SLOTS:
- /* enable OK button */
- void enableOkButton();
- /* disable OK button */
- void disableOkButton();
/* set OK button state (enabled / disabled) */
void setOkButtonState(bool fState);
void on_resetButton_clicked();
@@ -46,7 +52,7 @@ private Q_SLOTS:
void showRestartWarning(bool fPersistent = false);
void clearStatusLabel();
- void doProxyIpChecks(QValidatedLineEdit *pUiProxyIp, int nProxyPort);
+ void updateProxyValidationState();
/* query the networks, for which the default proxy is used */
void updateDefaultProxyNets();
@@ -57,7 +63,6 @@ private:
Ui::OptionsDialog *ui;
OptionsModel *model;
QDataWidgetMapper *mapper;
- bool fProxyIpsValid;
};
#endif // BITCOIN_QT_OPTIONSDIALOG_H
diff --git a/src/qt/qvalidatedlineedit.cpp b/src/qt/qvalidatedlineedit.cpp
index 346369392c..5658a0bdcf 100644
--- a/src/qt/qvalidatedlineedit.cpp
+++ b/src/qt/qvalidatedlineedit.cpp
@@ -99,9 +99,25 @@ void QValidatedLineEdit::checkValidity()
}
else
setValid(false);
+
+ Q_EMIT validationDidChange(this);
}
void QValidatedLineEdit::setCheckValidator(const QValidator *v)
{
checkValidator = v;
}
+
+bool QValidatedLineEdit::isValid()
+{
+ // use checkValidator in case the QValidatedLineEdit is disabled
+ if (checkValidator)
+ {
+ QString address = text();
+ int pos = 0;
+ if (checkValidator->validate(address, pos) == QValidator::Acceptable)
+ return true;
+ }
+
+ return valid;
+}
diff --git a/src/qt/qvalidatedlineedit.h b/src/qt/qvalidatedlineedit.h
index 8665acda5e..8cb6a425fa 100644
--- a/src/qt/qvalidatedlineedit.h
+++ b/src/qt/qvalidatedlineedit.h
@@ -18,6 +18,7 @@ public:
explicit QValidatedLineEdit(QWidget *parent);
void clear();
void setCheckValidator(const QValidator *v);
+ bool isValid();
protected:
void focusInEvent(QFocusEvent *evt);
@@ -31,6 +32,9 @@ public Q_SLOTS:
void setValid(bool valid);
void setEnabled(bool enabled);
+Q_SIGNALS:
+ void validationDidChange(QValidatedLineEdit *validatedLineEdit);
+
private Q_SLOTS:
void markValid();
void checkValidity();
diff --git a/src/test/main_tests.cpp b/src/test/main_tests.cpp
index 21ae46d6e9..2b92d239e9 100644
--- a/src/test/main_tests.cpp
+++ b/src/test/main_tests.cpp
@@ -72,5 +72,4 @@ BOOST_AUTO_TEST_CASE(test_combiner_all)
Test.disconnect(&ReturnTrue);
BOOST_CHECK(Test());
}
-
BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp
new file mode 100644
index 0000000000..1e31f2e679
--- /dev/null
+++ b/src/test/merkle_tests.cpp
@@ -0,0 +1,136 @@
+// Copyright (c) 2015 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "consensus/merkle.h"
+#include "test/test_bitcoin.h"
+#include "random.h"
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup)
+
+// Older version of the merkle root computation code, for comparison.
+static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
+{
+ vMerkleTree.clear();
+ vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
+ for (std::vector<CTransaction>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
+ vMerkleTree.push_back(it->GetHash());
+ int j = 0;
+ bool mutated = false;
+ for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
+ {
+ for (int i = 0; i < nSize; i += 2)
+ {
+ int i2 = std::min(i+1, nSize-1);
+ if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
+ // Two identical hashes at the end of the list at a particular level.
+ mutated = true;
+ }
+ vMerkleTree.push_back(Hash(vMerkleTree[j+i].begin(), vMerkleTree[j+i].end(),
+ vMerkleTree[j+i2].begin(), vMerkleTree[j+i2].end()));
+ }
+ j += nSize;
+ }
+ if (fMutated) {
+ *fMutated = mutated;
+ }
+ return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
+}
+
+// Older version of the merkle branch computation code, for comparison.
+static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
+{
+ std::vector<uint256> vMerkleBranch;
+ int j = 0;
+ for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
+ {
+ int i = std::min(nIndex^1, nSize-1);
+ vMerkleBranch.push_back(vMerkleTree[j+i]);
+ nIndex >>= 1;
+ j += nSize;
+ }
+ return vMerkleBranch;
+}
+
+static inline int ctz(uint32_t i) {
+ if (i == 0) return 0;
+ int j = 0;
+ while (!(i & 1)) {
+ j++;
+ i >>= 1;
+ }
+ return j;
+}
+
+BOOST_AUTO_TEST_CASE(merkle_test)
+{
+ for (int i = 0; i < 32; i++) {
+ // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
+ int ntx = (i <= 16) ? i : 17 + (insecure_rand() % 4000);
+ // Try up to 3 mutations.
+ for (int mutate = 0; mutate <= 3; mutate++) {
+ int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
+ if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
+ int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
+ int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
+ if (duplicate2 >= ntx1) break;
+ int ntx2 = ntx1 + duplicate2;
+ int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the the third mutation.
+ if (duplicate3 >= ntx2) break;
+ int ntx3 = ntx2 + duplicate3;
+ // Build a block with ntx different transactions.
+ CBlock block;
+ block.vtx.resize(ntx);
+ for (int j = 0; j < ntx; j++) {
+ CMutableTransaction mtx;
+ mtx.nLockTime = j;
+ block.vtx[j] = mtx;
+ }
+ // Compute the root of the block before mutating it.
+ bool unmutatedMutated = false;
+ uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
+ BOOST_CHECK(unmutatedMutated == false);
+ // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
+ block.vtx.resize(ntx3);
+ for (int j = 0; j < duplicate1; j++) {
+ block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
+ }
+ for (int j = 0; j < duplicate2; j++) {
+ block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
+ }
+ for (int j = 0; j < duplicate3; j++) {
+ block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
+ }
+ // Compute the merkle root and merkle tree using the old mechanism.
+ bool oldMutated = false;
+ std::vector<uint256> merkleTree;
+ uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
+ // Compute the merkle root using the new mechanism.
+ bool newMutated = false;
+ uint256 newRoot = BlockMerkleRoot(block, &newMutated);
+ BOOST_CHECK(oldRoot == newRoot);
+ BOOST_CHECK(newRoot == unmutatedRoot);
+ BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
+ BOOST_CHECK(oldMutated == newMutated);
+ BOOST_CHECK(newMutated == !!mutate);
+ // If no mutation was done (once for every ntx value), try up to 16 branches.
+ if (mutate == 0) {
+ for (int loop = 0; loop < std::min(ntx, 16); loop++) {
+ // If ntx <= 16, try all branches. Otherise, try 16 random ones.
+ int mtx = loop;
+ if (ntx > 16) {
+ mtx = insecure_rand() % ntx;
+ }
+ std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
+ std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
+ BOOST_CHECK(oldBranch == newBranch);
+ BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx].GetHash(), newBranch, mtx) == oldRoot);
+ }
+ }
+ }
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index dc20e34634..1d7c9f65c0 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -5,6 +5,7 @@
#include "chainparams.h"
#include "coins.h"
#include "consensus/consensus.h"
+#include "consensus/merkle.h"
#include "consensus/validation.h"
#include "main.h"
#include "miner.h"
@@ -93,7 +94,7 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
pblock->vtx[0] = CTransaction(txCoinbase);
if (txFirst.size() < 2)
txFirst.push_back(new CTransaction(pblock->vtx[0]));
- pblock->hashMerkleRoot = pblock->ComputeMerkleRoot();
+ pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
pblock->nNonce = blockinfo[i].nonce;
CValidationState state;
BOOST_CHECK(ProcessNewBlock(state, chainparams, NULL, pblock, true, NULL));
diff --git a/src/test/pmt_tests.cpp b/src/test/pmt_tests.cpp
index d9f3c3e467..0d7fb2bc35 100644
--- a/src/test/pmt_tests.cpp
+++ b/src/test/pmt_tests.cpp
@@ -2,6 +2,7 @@
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include "consensus/merkle.h"
#include "merkleblock.h"
#include "serialize.h"
#include "streams.h"
@@ -48,7 +49,7 @@ BOOST_AUTO_TEST_CASE(pmt_test1)
}
// calculate actual merkle root and height
- uint256 merkleRoot1 = block.ComputeMerkleRoot();
+ uint256 merkleRoot1 = BlockMerkleRoot(block);
std::vector<uint256> vTxid(nTx, uint256());
for (unsigned int j=0; j<nTx; j++)
vTxid[j] = block.vtx[j].GetHash();
diff --git a/src/version.h b/src/version.h
index 6cdddf9255..f7cf18d0b6 100644
--- a/src/version.h
+++ b/src/version.h
@@ -9,7 +9,7 @@
* network protocol versioning
*/
-static const int PROTOCOL_VERSION = 70011;
+static const int PROTOCOL_VERSION = 70012;
//! initial proto version, to be increased after version/verack negotiation
static const int INIT_PROTO_VERSION = 209;
@@ -37,4 +37,7 @@ static const int MEMPOOL_GD_VERSION = 60002;
//! "filter*" commands are disabled without NODE_BLOOM after and including this version
static const int NO_BLOOM_VERSION = 70011;
+//! "sendheaders" command and announcing blocks with headers starts with this version
+static const int SENDHEADERS_VERSION = 70012;
+
#endif // BITCOIN_VERSION_H
generated by cgit v1.2.3 (git 2.26.2) at 2024-10-10 01:18:21 +0000