From 391dff16fe9ace90fc0f3308a5c63c453370e713 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 11 Aug 2015 21:03:31 +0200 Subject: Do not store Merkle branches in the wallet. Assume that when a wallet transaction has a valid block hash and transaction position in it, the transaction is actually there. We're already trusting wallet data in a much more fundamental way anyway. To prevent backward compatibility issues, a new record is used for storing the block locator in the wallet. Old wallets will see a wallet file synchronized up to the genesis block, and rescan automatically. --- src/primitives/block.cpp | 39 ++------------------------------------- 1 file changed, 2 insertions(+), 37 deletions(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 5b9c13d87..7a58074d2 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -15,7 +15,7 @@ uint256 CBlockHeader::GetHash() const return SerializeHash(*this); } -uint256 CBlock::BuildMerkleTree(bool* fMutated) const +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 @@ -52,7 +52,7 @@ uint256 CBlock::BuildMerkleTree(bool* fMutated) const known ways of changing the transactions without affecting the merkle root. */ - vMerkleTree.clear(); + std::vector vMerkleTree; 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()); @@ -78,37 +78,6 @@ uint256 CBlock::BuildMerkleTree(bool* fMutated) const return (vMerkleTree.empty() ? uint256() : 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 uint256(); - 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; @@ -123,9 +92,5 @@ std::string CBlock::ToString() const { 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(); } -- cgit v1.2.3 From eece63fa72566068cb2a1bf85c95a72a5ba59bc9 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 17 Nov 2015 17:35:44 +0100 Subject: Switch blocks to a constant-space Merkle root/branch algorithm. This switches the Merkle tree logic for blocks to one that runs in constant (small) space. The old code is moved to tests, and a new test is added that for various combinations of block sizes, transaction positions to compute a branch for, and mutations: * Verifies that the old code and new code agree for the Merkle root. * Verifies that the old code and new code agree for the Merkle branch. * Verifies that the computed Merkle branch is valid. * Verifies that mutations don't change the Merkle root. * Verifies that mutations are correctly detected. --- src/primitives/block.cpp | 63 ------------------------------------------------ 1 file changed, 63 deletions(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 7a58074d2..7280c18f7 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 vMerkleTree; - 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() ? uint256() : vMerkleTree.back()); -} - std::string CBlock::ToString() const { std::stringstream s; -- cgit v1.2.3 From fa24439ff3d8ab5b9efaf66ef4dae6713b88cb35 Mon Sep 17 00:00:00 2001 From: MarcoFalke Date: Sun, 13 Dec 2015 17:58:29 +0100 Subject: Bump copyright headers to 2015 --- src/primitives/block.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 7280c18f7..59e949d71 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2014 The Bitcoin Core developers +// Copyright (c) 2009-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. -- cgit v1.2.3 From eff736e55e84441f9509285e83a1a6ee9a0c6e69 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 29 Mar 2016 16:46:20 +0200 Subject: Reformat version in UpdateTip and other messages Also remove the hardly-readable nBits from UpdateTip's log message. --- src/primitives/block.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 59e949d71..6fb33230a 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -18,7 +18,7 @@ uint256 CBlockHeader::GetHash() const 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", + s << strprintf("CBlock(hash=%s, ver=0x%08x, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%u)\n", GetHash().ToString(), nVersion, hashPrevBlock.ToString(), -- cgit v1.2.3 From 2b1f6f9ccf36f1e0a2c9d99154e1642f796d7c2b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sun, 3 Jan 2016 18:54:50 +0100 Subject: BIP141: Other consensus critical limits, and BIP145 Includes changes by Suhas Daftuar, Luke-jr, and mruddy. --- src/primitives/block.cpp | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 6fb33230a..df900388f 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -31,3 +31,12 @@ std::string CBlock::ToString() const } return s.str(); } + +int64_t GetBlockCost(const CBlock& block) +{ + // This implements the cost = (stripped_size * 4) + witness_size formula, + // using only serialization with and without witness data. As witness_size + // is equal to total_size - stripped_size, this formula is identical to: + // cost = (stripped_size * 3) + total_size. + return ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION); +} -- cgit v1.2.3 From 2c06bae39edfaa9c0855d83377ad8fda09e4fa08 Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Mon, 18 Jul 2016 13:28:26 -0400 Subject: Rename "block cost" to "block weight" --- src/primitives/block.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index df900388f..0e6ab4dd7 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -32,11 +32,11 @@ std::string CBlock::ToString() const return s.str(); } -int64_t GetBlockCost(const CBlock& block) +int64_t GetBlockWeight(const CBlock& block) { - // This implements the cost = (stripped_size * 4) + witness_size formula, + // This implements the weight = (stripped_size * 4) + witness_size formula, // using only serialization with and without witness data. As witness_size // is equal to total_size - stripped_size, this formula is identical to: - // cost = (stripped_size * 3) + total_size. + // weight = (stripped_size * 3) + total_size. return ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION); } -- cgit v1.2.3 From 1662b437b33b7ec5a1723f6ae6187d3bdd06f593 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 10 Nov 2016 17:26:00 -0800 Subject: Make CBlock::vtx a vector of shared_ptr --- src/primitives/block.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 0e6ab4dd7..95bd2211f 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -27,7 +27,7 @@ std::string CBlock::ToString() const vtx.size()); for (unsigned int i = 0; i < vtx.size(); i++) { - s << " " << vtx[i].ToString() << "\n"; + s << " " << vtx[i]->ToString() << "\n"; } return s.str(); } -- cgit v1.2.3 From 27765b6403cece54320374b37afb01a0cfe571c3 Mon Sep 17 00:00:00 2001 From: isle2983 Date: Sat, 31 Dec 2016 11:01:21 -0700 Subject: Increment MIT Licence copyright header year on files modified in 2016 Edited via: $ contrib/devtools/copyright_header.py update . --- src/primitives/block.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 95bd2211f..9a979094c 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2015 The Bitcoin Core developers +// Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -- cgit v1.2.3 From b506efbe747ba31ee1f41be14cdbc0c30dfcf67f Mon Sep 17 00:00:00 2001 From: Warren Togami Date: Wed, 21 May 2014 20:24:15 +0100 Subject: Litecoin: Scrypt n=1024 Pow hash based upon Colin Percival's Tarnsnap (2009) Modified by Artforz, coblee, pooler, wtogami, Nikolay Belikov, Adrian Gallagher --- src/primitives/block.cpp | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 9a979094c..4cfc576f0 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -6,6 +6,7 @@ #include "primitives/block.h" #include "hash.h" +#include "crypto/scrypt.h" #include "tinyformat.h" #include "utilstrencodings.h" #include "crypto/common.h" @@ -15,6 +16,13 @@ uint256 CBlockHeader::GetHash() const return SerializeHash(*this); } +uint256 CBlockHeader::GetPoWHash() const +{ + uint256 thash; + scrypt_1024_1_1_256(BEGIN(nVersion), BEGIN(thash)); + return thash; +} + std::string CBlock::ToString() const { std::stringstream s; -- cgit v1.2.3 From bc8cca48968dfa3f60b5eae6a2b92bdd2870eee3 Mon Sep 17 00:00:00 2001 From: Ross Nicoll Date: Sun, 13 Aug 2017 13:31:12 +0100 Subject: Merge AuxPoW support from Namecore Changes are as below: Wrap CBlockHeader::nVersion into a new class (CBlockVersion). This allows to take care of interpreting the field into a base version, auxpow flag and the chain ID. Update getauxblock.py for new 'generate' RPC call. Add 'auxpow' to block JSON. Accept auxpow as PoW verification. Add unit tests for auxpow verification. Add check for memory-layout of CBlockVersion. Weaken auxpow chain ID checks for the testnet. Allow Params() to overrule when to check the auxpow chain ID and for legacy blocks. Use this to disable the checks on testnet. Introduce CPureBlockHeader. Split the block header part that is used by auxpow and the "real" block header (that uses auxpow) to resolve the cyclic dependency between the two. Differentiate between uint256 and arith_uint256. This change was done upstream, modify the auxpow code. Add missing lock in auxpow_tests. Fix REST header check for auxpow headers. Those can be longer, thus take that into account. Also perform the check actually on an auxpow header. Correctly set the coinbase for getauxblock results. Call IncrementExtraNonce in getauxblock so that the coinbase is actually initialised with the stuff it should be. (BIP30 block height and COINBASE_FLAGS.) Implement getauxblock plus regression test. Turn auxpow test into FIXTURE test. This allows using of the Params() calls. Move CMerkleTx code to auxpow.cpp. Otherwise we get linker errors when building without wallet. Fix rebase with BIP66. Update the code to handle BIP66's nVersion=3. Enforce that auxpow parent blocks have no auxpow block version. This is for compatibility with namecoind. See also https://github.com/namecoin/namecoin/pull/199. Move auxpow-related parameters to Consensus::Params. --- src/primitives/block.cpp | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'src/primitives/block.cpp') diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp index 4cfc576f0..1df912d35 100644 --- a/src/primitives/block.cpp +++ b/src/primitives/block.cpp @@ -6,21 +6,21 @@ #include "primitives/block.h" #include "hash.h" -#include "crypto/scrypt.h" #include "tinyformat.h" #include "utilstrencodings.h" #include "crypto/common.h" -uint256 CBlockHeader::GetHash() const +void CBlockHeader::SetAuxpow (CAuxPow* apow) { - return SerializeHash(*this); -} - -uint256 CBlockHeader::GetPoWHash() const -{ - uint256 thash; - scrypt_1024_1_1_256(BEGIN(nVersion), BEGIN(thash)); - return thash; + if (apow) + { + auxpow.reset(apow); + SetAuxpowFlag(true); + } else + { + auxpow.reset(); + SetAuxpowFlag(false); + } } std::string CBlock::ToString() const -- cgit v1.2.3