Do txid duplicates check inside BuildMerkleRoot

sipa commented at 10:32 pm on September 15, 2014: member

Move the txid duplicates check into BuildMerkleTree (where it can be done without building a full txid set), and rename the method to CalculateMerkleTree.

sipa force-pushed on Sep 15, 2014

sipa force-pushed on Sep 20, 2014

sipa commented at 2:54 am on September 20, 2014: member

Removed the dependency on #4925, as that seems more controversial.

gmaxwell commented at 7:17 pm on September 22, 2014: contributor

The English in this patch is a bit confusing. What this is checking for is not the generalized case of a duplicate TXID but only the second pre-image tree-grafting attack.

sipa force-pushed on Sep 22, 2014

sipa commented at 7:53 pm on September 22, 2014: member

@gmaxwell Agree, fixed. I added some extra comments too.

sipa force-pushed on Sep 22, 2014

sipa commented at 9:35 pm on September 22, 2014: member

Added a comment.

gmaxwell commented at 9:39 pm on September 22, 2014: contributor

The claim that an interior collision implies a duplicate is only computationally sound. I think this is fine, and might even be protective against some kinds of crazy attacks in the face of an actual collision… though since it is a consensus rule change we should note it (though not worry, since it’s only a change in cases where we’re completely broken).

I can’t ACK yet because even though it looks good, commenting out the mutated=true; assignment is not enough to make test_bitcoin fail… so we are inadequately testing this condition (or the patch is broken).

sipa force-pushed on Sep 22, 2014

sipa commented at 10:35 pm on September 22, 2014: member

So, it seems pulltester doesn’t actually test the merkle root txid duplication issue… ping @TheBlueMatt

TheBlueMatt commented at 10:38 pm on September 22, 2014: member

Willfix in upcoming test updates.

sipa commented at 11:01 pm on September 22, 2014: member

Seems it did trigger failure - let’s run again to be sure.

sipa commented at 0:03 am on September 23, 2014: member

Good, it failed, and for the right reason. I’m removing the ‘bug’ commit again.

sipa force-pushed on Sep 23, 2014

gmaxwell commented at 0:47 am on September 23, 2014: contributor

ACK. (okay, glad pulltester did catch it, poor timing on that first pass result. :) )

sipa commented at 0:50 am on September 23, 2014: member

s/pulltester/comparison tool/. Travis caught it as well.

petertodd commented at 7:20 am on September 23, 2014: contributor

ACK

Tested with mainnet block 99960, duplicated the last tx, and submitted on testnet with unexciting results.

sipa force-pushed on Sep 23, 2014

sipa commented at 5:48 pm on September 23, 2014: member

I significantly expanded the comments and commit message.

sipa force-pushed on Sep 23, 2014

petertodd commented at 6:33 pm on September 23, 2014: contributor

@sipa Nice!

1 beer @changetip

changetip commented at 8:29 pm on September 23, 2014: none

Hi sipa, petertodd sent you a Bitcoin tip worth 1 beer (8.084 mBTC/$3.50), and I’m here to deliver it ➔ collect your tip at ChangeTip.com.

Is this real?

theuni commented at 10:30 pm on September 23, 2014: member

@sipa The new comments make this worlds easier to review. Thanks for that. Looks sane to me.

sipa commented at 1:41 am on September 24, 2014: member

@petertodd Thanks!

in src/core.cpp: in c6ec0c4466 outdated

274     for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
275     {
276         for (int i = 0; i < nSize; i += 2)
277         {
278             int i2 = std::min(i+1, nSize-1);
279+            if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[i] == vMerkleTree[i2]) {

laanwj commented at 7:03 am on September 24, 2014:

Shouldn’t this be vMerkleTree[j+i] == vMerkleTree[j+i2] as below in the hashing?

sipa commented at 10:07 am on September 24, 2014:

Good catch, yes. Seems like it only worked for the bottom level (j=0), and the only case tested by comparison tool was in that level…

laanwj commented at 8:56 am on September 24, 2014: member

I created a silly python script to visualize the Satoshi Merkle tree, marking the nodes where a mutation check happens according to the logic in this pull in red: https://gist.github.com/laanwj/28326a4ba4f3ce1d89f1

Do merkle root and txid duplicates check simultaneously

Move the txid duplicates check into BuildMerkleTree, where it can be done
much more efficiently (without needing to build a full txid set to detect
duplicates).

The previous version (using the std::set<uint256> to detect duplicates) was
also slightly too weak. A block mined with actual duplicate transactions
(which is invalid, due to the inputs of the duplicated transactions being
seen as double spends) would trigger the duplicates logic, resulting in the
block not being stored on disk, and rerequested. This change fixes that by
only triggering in the case of duplicated transactions that can actually
result in an identical merkle root.

584a358997

sipa force-pushed on Sep 24, 2014

BitcoinPullTester commented at 5:33 pm on September 24, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/p4926_584a358997e52a87e8c5402269c7fb3784ed2065/ for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

sipa commented at 7:32 pm on September 24, 2014: member

@laanwj Fixed the offsets.

laanwj commented at 6:29 am on September 25, 2014: member

Looks good to me now. ACK.

sipa commented at 6:44 pm on September 26, 2014: member

@gmaxwell @jgarzik Is this acceptable, or do we wait until comparisontool does non-bottom-level merkle malleability tests?

sipa commented at 2:25 am on October 2, 2014: member

@gmaxwell Comparison tool now performs merkle malleability tests at non-bottom level.

gmaxwell commented at 3:17 am on October 2, 2014: contributor

re-ACK.

sipa merged this on Oct 2, 2014

sipa closed this on Oct 2, 2014

sipa referenced this in commit 76c171033c on Oct 2, 2014

MarcoFalke locked this on Sep 8, 2021

Do txid duplicates check inside BuildMerkleRoot #4926