Add tests for malformed partial merkle trees, including the transaction count limit at its 16666 boundary, and for GetBitsProof returning zero for zero, negative and overflowing targets.
These were discovered by finding gaps in an alternate implementation (bitcoin-s)
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline and AI policy for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | instagibbs |
| Stale ACK | darosior |
If your review is incorrectly listed, please copy-paste <code><!--meta-tag:bot-skip--></code> into the comment that the bot should ignore.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
Concept ACK
cc @instagibbs
125 | @@ -125,4 +126,36 @@ BOOST_AUTO_TEST_CASE(pmt_malleability) 126 | BOOST_CHECK(tree.ExtractMatches(vTxid, vIndex).IsNull()); 127 | } 128 | 129 | +BOOST_AUTO_TEST_CASE(pmt_malformed)
suggestion
diff --git a/src/test/pmt_tests.cpp b/src/test/pmt_tests.cpp
--- a/src/test/pmt_tests.cpp
+++ b/src/test/pmt_tests.cpp
@@ -8,4 +8,5 @@
#include <serialize.h>
#include <streams.h>
+#include <test/util/common.h>
#include <test/util/random.h>
#include <test/util/setup_common.h>
@@ -143,17 +144,18 @@ BOOST_AUTO_TEST_CASE(pmt_malformed)
// The transaction count is limited to MAX_BLOCK_WEIGHT /
MIN_TRANSACTION_WEIGHT.
- static_assert(MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT == 16666);
- BOOST_CHECK(extract(16666, 1, {0x00}) == uint256{1});
- BOOST_CHECK(extract(16667, 1, {0x00}).IsNull());
- // An empty tree is invalid.
+ constexpr uint32_t max_tx_count{MAX_BLOCK_WEIGHT /
MIN_TRANSACTION_WEIGHT};
+ static_assert(max_tx_count == 16666);
+ BOOST_CHECK_EQUAL(extract(max_tx_count, 1, {0x00}), uint256{1});
+ BOOST_CHECK(extract(max_tx_count + 1, 1, {0x00}).IsNull());
+ // An empty tree, more hashes than transactions, and fewer bits than
hashes are
+ // rejected before traversal. Traversal would reject each of them anyway,
so these
+ // check the result, not the early returns.
BOOST_CHECK(extract(0, 0, {0x00}).IsNull());
- // There cannot be more hashes than transactions.
BOOST_CHECK(extract(1, 2, {0x00}).IsNull());
- // There cannot be fewer bits than hashes.
BOOST_CHECK(extract(9, 9, {0xff}).IsNull());
// Traversal runs out of hashes: the root is a parent of a match, so both
of its
// leaves need a hash, but only one is provided.
BOOST_CHECK(extract(2, 1, {0x01}).IsNull());
- // Traversal runs out of bits: eight bits do not cover the path to the
third leaf.
+ // Traversal runs out of bits: eight bits reach the third leaf but not
the fourth.
BOOST_CHECK(extract(16, 8, {0xff}).IsNull());
}
added thanks
134 | @@ -135,6 +135,19 @@ BOOST_AUTO_TEST_CASE(CheckProofOfWork_test_zero_target) 135 | BOOST_CHECK(!CheckProofOfWork(hash, nBits, consensus)); 136 | } 137 | 138 | +BOOST_AUTO_TEST_CASE(GetBitsProof_test)
suggestion
diff --git a/src/test/pow_tests.cpp b/src/test/pow_tests.cpp
--- a/src/test/pow_tests.cpp
+++ b/src/test/pow_tests.cpp
@@ -139,12 +139,16 @@ BOOST_AUTO_TEST_CASE(GetBitsProof_test)
{
// Targets that are zero, negative or overflow encode no work.
- BOOST_CHECK(GetBitsProof(0x00000000) == 0);
- BOOST_CHECK(GetBitsProof(0x01003456) == 0);
- BOOST_CHECK(GetBitsProof(0x04923456) == 0);
- BOOST_CHECK(GetBitsProof(0xff123456) == 0);
+ BOOST_CHECK_EQUAL(GetBitsProof(0x00000000), arith_uint256{0});
+ BOOST_CHECK_EQUAL(GetBitsProof(0x01003456), arith_uint256{0});
+ BOOST_CHECK_EQUAL(GetBitsProof(0x04923456), arith_uint256{0});
+ BOOST_CHECK_EQUAL(GetBitsProof(0xff123456), arith_uint256{0});
// The exponent byte is unsigned, so this is a large exponent that
overflows.
- BOOST_CHECK(GetBitsProof(0x80010203) == 0);
+ BOOST_CHECK_EQUAL(GetBitsProof(0x80010203), arith_uint256{0});
+ // The two overflows above shift every mantissa bit out of 256 bits, so
they would
+ // also give zero work without the overflow check. This one keeps the low
bits of
+ // its mantissa when truncated.
+ BOOST_CHECK_EQUAL(GetBitsProof(0x21012345), arith_uint256{0});
// The genesis block target.
- BOOST_CHECK(GetBitsProof(0x1d00ffff) == 0x100010001);
+ BOOST_CHECK_EQUAL(GetBitsProof(0x1d00ffff), arith_uint256{0x100010001});
}
added thanks
ACK 0a74fe80cd1319ecbd07e0f081f7b49eac59872c
With a couple non-blocking suggestions with a couple additional mutant kills via bot:
With the GetBitsProof guard reduced to fNegative || bnTarget == 0, or to just fNegative, the test now fails on the 0x21012345 line. Before this change, both mutations passed.
With the nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT check deleted, the test fails on the max_tx_count + 1 line.
ACK 0a74fe80cd
Bot says that tiny additional diff would get src/merkleblock.cpp to 100% coverage:
--- a/src/test/pmt_tests.cpp
+++ b/src/test/pmt_tests.cpp
@@ -156,6 +156,11 @@ BOOST_AUTO_TEST_CASE(pmt_malformed)
BOOST_CHECK(extract(2, 1, {0x01}).IsNull());
// Traversal runs out of bits: eight bits do not cover the path to the third leaf.
BOOST_CHECK(extract(16, 8, {0xff}).IsNull());
+ // Not all bits are consumed: a second byte of bits is more than padding.
+ BOOST_CHECK(extract(1, 1, {0x00, 0x00}).IsNull());
+ // Not all hashes are consumed: the root is not a parent of a match, so only its
+ // own hash is used.
+ BOOST_CHECK(extract(2, 2, {0x00}).IsNull());
}
Non-blocking, whats here is already an improvement.
I would prefer merging this with the suggestions applied.
Add tests for malformed partial merkle trees, including the
transaction count limit at its 16666 boundary, and for GetBitsProof
returning zero for zero, negative and overflowing targets.
added @darosior and @instagibbs suggestions
reACK https://github.com/bitcoin/bitcoin/pull/36457/commits/0c0e6ba0167e9397e521ba3cbc7a4779ad7518b7
suggested changes taken verbatim