mirror of
https://github.com/dashpay/dash.git
synced 2024-12-25 12:02:48 +01:00
4aa197dbdb
fa4632c41714dfaa699bacc6a947d72668a4deef test: Move boost/stdlib includes last (MarcoFalke) fa488f131fd4f5bab0d01376c5a5013306f1abcd scripted-diff: Bump copyright headers (MarcoFalke) fac5c373006a9e4bcbb56843bb85f1aca4d87599 scripted-diff: Sort test includes (MarcoFalke) Pull request description: When writing tests, often includes need to be added or removed. Currently the list of includes is not sorted, so developers that write tests and have `clang-format` installed will either have an unrelated change (sorting) included in their commit or they will have to manually undo the sort. This pull preempts both issues by just sorting all includes in one commit. Please be aware that this is **NOT** a change to policy to enforce clang-format or any other developer guideline or process. Developers are free to use whatever tool they want, see also #18651. Edit: Also includes a commit to bump the copyright headers, so that the touched files don't need to be touched again for that. ACKs for top commit: practicalswift: ACK fa4632c41714dfaa699bacc6a947d72668a4deef jonatack: ACK fa4632c41714dfaa, light review and sanity checks with gcc build and clang fuzz build Tree-SHA512: 130a8d073a379ba556b1e64104d37c46b671425c0aef0ed725fd60156a95e8dc83fb6f0b5330b2f8152cf5daaf3983b4aca5e75812598f2626c39fd12b88b180
75 lines
3.0 KiB
C++
75 lines
3.0 KiB
C++
// Copyright (c) 2015-2020 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 <hash.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 level
|
|
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.
|
|
*/
|
|
|
|
|
|
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
|
|
bool mutation = false;
|
|
while (hashes.size() > 1) {
|
|
if (mutated) {
|
|
for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
|
|
if (hashes[pos] == hashes[pos + 1]) mutation = true;
|
|
}
|
|
}
|
|
if (hashes.size() & 1) {
|
|
hashes.push_back(hashes.back());
|
|
}
|
|
SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
|
|
hashes.resize(hashes.size() / 2);
|
|
}
|
|
if (mutated) *mutated = mutation;
|
|
if (hashes.size() == 0) return uint256();
|
|
return hashes[0];
|
|
}
|
|
|
|
|
|
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(std::move(leaves), mutated);
|
|
}
|
|
|