From 99f41b9cf7b8e039cea75500a905498a1f6969f3 Mon Sep 17 00:00:00 2001 From: jtimon Date: Tue, 21 Oct 2014 00:13:47 +0200 Subject: MOVEONLY: core.o -> core/block.o --- src/Makefile.am | 4 +- src/chain.h | 2 +- src/chainparams.h | 2 +- src/core.cpp | 130 ----------------------------------------- src/core.h | 168 ----------------------------------------------------- src/core/block.cpp | 130 +++++++++++++++++++++++++++++++++++++++++ src/core/block.h | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.h | 2 +- src/miner.cpp | 2 +- src/pow.cpp | 2 +- src/wallet.h | 2 +- 11 files changed, 306 insertions(+), 306 deletions(-) delete mode 100644 src/core.cpp delete mode 100644 src/core.h create mode 100644 src/core/block.cpp create mode 100644 src/core/block.h (limited to 'src') diff --git a/src/Makefile.am b/src/Makefile.am index 0385ad9025..4ca75d6a77 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -81,7 +81,7 @@ BITCOIN_CORE_H = \ coins.h \ compat.h \ compressor.h \ - core.h \ + core/block.h \ core/transaction.h \ core_io.h \ crypter.h \ @@ -215,7 +215,7 @@ libbitcoin_common_a_SOURCES = \ chainparams.cpp \ coins.cpp \ compressor.cpp \ - core.cpp \ + core/block.cpp \ core/transaction.cpp \ core_read.cpp \ core_write.cpp \ diff --git a/src/chain.h b/src/chain.h index 290150476e..2a55771622 100644 --- a/src/chain.h +++ b/src/chain.h @@ -6,7 +6,7 @@ #ifndef H_BITCOIN_CHAIN #define H_BITCOIN_CHAIN -#include "core.h" +#include "core/block.h" #include "pow.h" #include "tinyformat.h" #include "uint256.h" diff --git a/src/chainparams.h b/src/chainparams.h index f157419bb2..e27728dbd5 100644 --- a/src/chainparams.h +++ b/src/chainparams.h @@ -6,9 +6,9 @@ #ifndef BITCOIN_CHAIN_PARAMS_H #define BITCOIN_CHAIN_PARAMS_H -#include "core.h" #include "chainparamsbase.h" #include "checkpoints.h" +#include "core/block.h" #include "protocol.h" #include "uint256.h" diff --git a/src/core.cpp b/src/core.cpp deleted file mode 100644 index 08139d5424..0000000000 --- a/src/core.cpp +++ /dev/null @@ -1,130 +0,0 @@ -// Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2014 The Bitcoin developers -// Distributed under the MIT/X11 software license, see the accompanying -// file COPYING or http://www.opensource.org/licenses/mit-license.php. - -#include "core.h" - -#include "hash.h" -#include "tinyformat.h" -#include "utilstrencodings.h" - -uint256 CBlockHeader::GetHash() const -{ - return Hash(BEGIN(nVersion), END(nNonce)); -} - -uint256 CBlock::BuildMerkleTree(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. - */ - vMerkleTree.clear(); - vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. - for (std::vector::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() ? 0 : vMerkleTree.back()); -} - -std::vector CBlock::GetMerkleBranch(int nIndex) const -{ - if (vMerkleTree.empty()) - BuildMerkleTree(); - std::vector vMerkleBranch; - int j = 0; - for (int nSize = 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; -} - -uint256 CBlock::CheckMerkleBranch(uint256 hash, const std::vector& vMerkleBranch, int nIndex) -{ - if (nIndex == -1) - return 0; - for (std::vector::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; -} - -std::string CBlock::ToString() const -{ - std::stringstream s; - s << strprintf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%u)\n", - GetHash().ToString(), - nVersion, - hashPrevBlock.ToString(), - hashMerkleRoot.ToString(), - nTime, nBits, nNonce, - vtx.size()); - for (unsigned int i = 0; i < vtx.size(); i++) - { - s << " " << vtx[i].ToString() << "\n"; - } - s << " vMerkleTree: "; - for (unsigned int i = 0; i < vMerkleTree.size(); i++) - s << " " << vMerkleTree[i].ToString(); - s << "\n"; - return s.str(); -} diff --git a/src/core.h b/src/core.h deleted file mode 100644 index b2288e24ca..0000000000 --- a/src/core.h +++ /dev/null @@ -1,168 +0,0 @@ -// Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2013 The Bitcoin developers -// Distributed under the MIT/X11 software license, see the accompanying -// file COPYING or http://www.opensource.org/licenses/mit-license.php. - -#ifndef BITCOIN_CORE_H -#define BITCOIN_CORE_H - -#include "core/transaction.h" -#include "serialize.h" -#include "uint256.h" - -/** Nodes collect new transactions into a block, hash them into a hash tree, - * and scan through nonce values to make the block's hash satisfy proof-of-work - * requirements. When they solve the proof-of-work, they broadcast the block - * to everyone and the block is added to the block chain. The first transaction - * in the block is a special one that creates a new coin owned by the creator - * of the block. - */ -class CBlockHeader -{ -public: - // header - static const int32_t CURRENT_VERSION=2; - int32_t nVersion; - uint256 hashPrevBlock; - uint256 hashMerkleRoot; - uint32_t nTime; - uint32_t nBits; - uint32_t nNonce; - - CBlockHeader() - { - SetNull(); - } - - ADD_SERIALIZE_METHODS; - - template - inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { - READWRITE(this->nVersion); - nVersion = this->nVersion; - READWRITE(hashPrevBlock); - READWRITE(hashMerkleRoot); - READWRITE(nTime); - READWRITE(nBits); - READWRITE(nNonce); - } - - void SetNull() - { - nVersion = CBlockHeader::CURRENT_VERSION; - hashPrevBlock = 0; - hashMerkleRoot = 0; - nTime = 0; - nBits = 0; - nNonce = 0; - } - - bool IsNull() const - { - return (nBits == 0); - } - - uint256 GetHash() const; - - int64_t GetBlockTime() const - { - return (int64_t)nTime; - } -}; - - -class CBlock : public CBlockHeader -{ -public: - // network and disk - std::vector vtx; - - // memory only - mutable std::vector vMerkleTree; - - CBlock() - { - SetNull(); - } - - CBlock(const CBlockHeader &header) - { - SetNull(); - *((CBlockHeader*)this) = header; - } - - ADD_SERIALIZE_METHODS; - - template - inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { - READWRITE(*(CBlockHeader*)this); - READWRITE(vtx); - } - - void SetNull() - { - CBlockHeader::SetNull(); - vtx.clear(); - vMerkleTree.clear(); - } - - CBlockHeader GetBlockHeader() const - { - CBlockHeader block; - block.nVersion = nVersion; - block.hashPrevBlock = hashPrevBlock; - block.hashMerkleRoot = hashMerkleRoot; - block.nTime = nTime; - block.nBits = nBits; - block.nNonce = nNonce; - return block; - } - - // Build the in-memory 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 BuildMerkleTree(bool* mutated = NULL) const; - - std::vector GetMerkleBranch(int nIndex) const; - static uint256 CheckMerkleBranch(uint256 hash, const std::vector& vMerkleBranch, int nIndex); - std::string ToString() const; -}; - - -/** Describes a place in the block chain to another node such that if the - * other node doesn't have the same branch, it can find a recent common trunk. - * The further back it is, the further before the fork it may be. - */ -struct CBlockLocator -{ - std::vector vHave; - - CBlockLocator() {} - - CBlockLocator(const std::vector& vHaveIn) - { - vHave = vHaveIn; - } - - ADD_SERIALIZE_METHODS; - - template - inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { - if (!(nType & SER_GETHASH)) - READWRITE(nVersion); - READWRITE(vHave); - } - - void SetNull() - { - vHave.clear(); - } - - bool IsNull() - { - return vHave.empty(); - } -}; - -#endif // BITCOIN_CORE_H diff --git a/src/core/block.cpp b/src/core/block.cpp new file mode 100644 index 0000000000..2010d44dac --- /dev/null +++ b/src/core/block.cpp @@ -0,0 +1,130 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2014 The Bitcoin developers +// Distributed under the MIT/X11 software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "core/block.h" + +#include "hash.h" +#include "tinyformat.h" +#include "utilstrencodings.h" + +uint256 CBlockHeader::GetHash() const +{ + return Hash(BEGIN(nVersion), END(nNonce)); +} + +uint256 CBlock::BuildMerkleTree(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. + */ + vMerkleTree.clear(); + vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. + for (std::vector::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() ? 0 : vMerkleTree.back()); +} + +std::vector CBlock::GetMerkleBranch(int nIndex) const +{ + if (vMerkleTree.empty()) + BuildMerkleTree(); + std::vector vMerkleBranch; + int j = 0; + for (int nSize = 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; +} + +uint256 CBlock::CheckMerkleBranch(uint256 hash, const std::vector& vMerkleBranch, int nIndex) +{ + if (nIndex == -1) + return 0; + for (std::vector::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; +} + +std::string CBlock::ToString() const +{ + std::stringstream s; + s << strprintf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%u)\n", + GetHash().ToString(), + nVersion, + hashPrevBlock.ToString(), + hashMerkleRoot.ToString(), + nTime, nBits, nNonce, + vtx.size()); + for (unsigned int i = 0; i < vtx.size(); i++) + { + s << " " << vtx[i].ToString() << "\n"; + } + s << " vMerkleTree: "; + for (unsigned int i = 0; i < vMerkleTree.size(); i++) + s << " " << vMerkleTree[i].ToString(); + s << "\n"; + return s.str(); +} diff --git a/src/core/block.h b/src/core/block.h new file mode 100644 index 0000000000..f1eb7a844f --- /dev/null +++ b/src/core/block.h @@ -0,0 +1,168 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2013 The Bitcoin developers +// Distributed under the MIT/X11 software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef H_BITCOIN_CORE_BLOCK +#define H_BITCOIN_CORE_BLOCK + +#include "core/transaction.h" +#include "serialize.h" +#include "uint256.h" + +/** Nodes collect new transactions into a block, hash them into a hash tree, + * and scan through nonce values to make the block's hash satisfy proof-of-work + * requirements. When they solve the proof-of-work, they broadcast the block + * to everyone and the block is added to the block chain. The first transaction + * in the block is a special one that creates a new coin owned by the creator + * of the block. + */ +class CBlockHeader +{ +public: + // header + static const int32_t CURRENT_VERSION=2; + int32_t nVersion; + uint256 hashPrevBlock; + uint256 hashMerkleRoot; + uint32_t nTime; + uint32_t nBits; + uint32_t nNonce; + + CBlockHeader() + { + SetNull(); + } + + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { + READWRITE(this->nVersion); + nVersion = this->nVersion; + READWRITE(hashPrevBlock); + READWRITE(hashMerkleRoot); + READWRITE(nTime); + READWRITE(nBits); + READWRITE(nNonce); + } + + void SetNull() + { + nVersion = CBlockHeader::CURRENT_VERSION; + hashPrevBlock = 0; + hashMerkleRoot = 0; + nTime = 0; + nBits = 0; + nNonce = 0; + } + + bool IsNull() const + { + return (nBits == 0); + } + + uint256 GetHash() const; + + int64_t GetBlockTime() const + { + return (int64_t)nTime; + } +}; + + +class CBlock : public CBlockHeader +{ +public: + // network and disk + std::vector vtx; + + // memory only + mutable std::vector vMerkleTree; + + CBlock() + { + SetNull(); + } + + CBlock(const CBlockHeader &header) + { + SetNull(); + *((CBlockHeader*)this) = header; + } + + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { + READWRITE(*(CBlockHeader*)this); + READWRITE(vtx); + } + + void SetNull() + { + CBlockHeader::SetNull(); + vtx.clear(); + vMerkleTree.clear(); + } + + CBlockHeader GetBlockHeader() const + { + CBlockHeader block; + block.nVersion = nVersion; + block.hashPrevBlock = hashPrevBlock; + block.hashMerkleRoot = hashMerkleRoot; + block.nTime = nTime; + block.nBits = nBits; + block.nNonce = nNonce; + return block; + } + + // Build the in-memory 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 BuildMerkleTree(bool* mutated = NULL) const; + + std::vector GetMerkleBranch(int nIndex) const; + static uint256 CheckMerkleBranch(uint256 hash, const std::vector& vMerkleBranch, int nIndex); + std::string ToString() const; +}; + + +/** Describes a place in the block chain to another node such that if the + * other node doesn't have the same branch, it can find a recent common trunk. + * The further back it is, the further before the fork it may be. + */ +struct CBlockLocator +{ + std::vector vHave; + + CBlockLocator() {} + + CBlockLocator(const std::vector& vHaveIn) + { + vHave = vHaveIn; + } + + ADD_SERIALIZE_METHODS; + + template + inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { + if (!(nType & SER_GETHASH)) + READWRITE(nVersion); + READWRITE(vHave); + } + + void SetNull() + { + vHave.clear(); + } + + bool IsNull() + { + return vHave.empty(); + } +}; + +#endif // H_BITCOIN_CORE_BLOCK diff --git a/src/main.h b/src/main.h index 09f22471d6..1941ca7059 100644 --- a/src/main.h +++ b/src/main.h @@ -14,7 +14,7 @@ #include "chain.h" #include "chainparams.h" #include "coins.h" -#include "core.h" +#include "core/block.h" #include "core/transaction.h" #include "net.h" #include "pow.h" diff --git a/src/miner.cpp b/src/miner.cpp index cf47b65a5c..0235de3ab3 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -6,7 +6,7 @@ #include "miner.h" #include "amount.h" -#include "core.h" +#include "core/block.h" #include "core/transaction.h" #include "hash.h" #include "main.h" diff --git a/src/pow.cpp b/src/pow.cpp index 75fbfc6a6d..af7fc488ef 100644 --- a/src/pow.cpp +++ b/src/pow.cpp @@ -6,7 +6,7 @@ #include "pow.h" #include "chainparams.h" -#include "core.h" +#include "core/block.h" #include "main.h" #include "timedata.h" #include "uint256.h" diff --git a/src/wallet.h b/src/wallet.h index 4c559cb7b1..acb30970c6 100644 --- a/src/wallet.h +++ b/src/wallet.h @@ -7,7 +7,7 @@ #define BITCOIN_WALLET_H #include "amount.h" -#include "core.h" +#include "core/block.h" #include "core/transaction.h" #include "crypter.h" #include "key.h" -- cgit v1.2.3