Remove duplicatable duplicate-input check from CheckTransaction

TheBlueMatt commented at 6:52 pm on October 31, 2016: member

Benchmark results indicate this saves about 0.5-0.7ms during CheckBlock.

gmaxwell commented at 6:01 am on November 1, 2016: contributor

I believe that with this change if a whitelisted peer gives us a transaction with internally duplicated inputs, we will relay it (CheckTransaction will pass, conflict with the mempool will not set DoS.) and then our peers running without this change will ban us (Their CheckTransaction will fail). Less critically, this change results in txn with internal doublespends getting a misleading log entry of mempool-conflict.

Edit: I suggest creating a CheckTransactionHarder that ATMP uses which will check for transaction internal duplication and still nDoS. This way block processing can still avoid the redundant test.

TheBlueMatt force-pushed on Nov 1, 2016

TheBlueMatt commented at 5:35 pm on November 1, 2016: member

Simplified diff and fixed.

in src/main.cpp: in 1019c03ad3 outdated

1095-    for (const auto& txin : tx.vin)
1096-    {
1097-        if (vInOutPoints.count(txin.prevout))
1098-            return state.DoS(100, false, REJECT_INVALID, "bad-txns-inputs-duplicate");
1099-        vInOutPoints.insert(txin.prevout);
1100+    // Check for duplicate inputs - note that this check is slow so we skip it in CheckBlock

gmaxwell commented at 4:20 am on November 2, 2016:

point out that it’s also redundant there please!

dexX7 commented at 6:21 am on September 19, 2018:

How is it redundant? Can you point to the case where it’s checked a second time?

gmaxwell commented at 4:21 am on November 2, 2016: contributor

utACK +/- comment nit.

in src/bench/checkblock.cpp: in 1019c03ad3 outdated

0@@ -0,0 +1,53 @@
1+// Copyright (c) 2016 Matt Corallo
2+// Unlike the rest of Bitcoin Core, this file is
3+// distributed under the Affero General Public License (AGPL v3)

laanwj commented at 9:29 am on November 2, 2016:

Code under this license cannot be accepted, sorry

gmaxwell commented at 7:52 pm on November 3, 2016:

lol. I didn’t notice that.

laanwj changes_requested

laanwj added the label Tests on Nov 2, 2016

TheBlueMatt commented at 11:32 am on November 2, 2016: member

Eek, license change was a mistake, sorry.

On November 2, 2016 5:29:28 AM EDT, “Wladimir J. van der Laan” notifications@github.com wrote:

laanwj requested changes on this pull request.

@@ -0,0 +1,53 @@ +// Copyright (c) 2016 Matt Corallo +// Unlike the rest of Bitcoin Core, this file is +// distributed under the Affero General Public License (AGPL v3)

Code under this license cannot be accepted, sorry

You are receiving this because you authored the thread. Reply to this email directly or view it on GitHub: #9049#pullrequestreview-6775188

TheBlueMatt force-pushed on Nov 2, 2016

TheBlueMatt commented at 2:06 pm on November 2, 2016: member

Fixed the broken license header.

sipa commented at 7:25 am on November 3, 2016: member

A very interesting duplication of the word “duplicate” in the PR title.

MarcoFalke renamed this:
~~Remove duplicatble duplicate-input check from CheckTransaction~~
Remove duplicatable duplicate-input check from CheckTransaction
on Nov 3, 2016

MarcoFalke added the label Resource usage on Nov 7, 2016

MarcoFalke removed the label Tests on Nov 7, 2016

MarcoFalke added the label Tests on Nov 7, 2016

sipa commented at 10:27 pm on November 7, 2016: member

@laanwj I believe you need to dismiss the requested changes (as they’re addressed).

laanwj approved

laanwj commented at 9:08 am on November 8, 2016: member

Approved the requested change. BTW: block413567.hex.h is a 6MB file - I’d prefer generating this on the fly as we do with the other .X.h files. Edit: working on build system change for this…

laanwj commented at 9:29 am on November 8, 2016: member

Can you please squash the top commit of https://github.com/laanwj/bitcoin/tree/2016_11_generate_bench_file into the benchmark commit?

This has the necessary build system change to generate the block.hex file on the fly from the raw data, like with the tests. @theuni can you have take a look too perhaps?

theuni commented at 8:22 pm on November 8, 2016: member

@laanwj looks good to me. Only slight criticism is that we may want to generate .h/.cpp pairs for blocks to ensure that they end up in separate compilation units, but we can always address that later if it becomes an issue.

in src/main.cpp: in 2ced91bf1a outdated

1100+    // Check for duplicate inputs - note that this check is slow so we skip it in CheckBlock
1101+    if (fCheckDuplicateInputs) {
1102+        set<COutPoint> vInOutPoints;
1103+        for (const auto& txin : tx.vin)
1104+        {
1105+            if (vInOutPoints.count(txin.prevout))

theuni commented at 9:58 pm on November 8, 2016:

Also worth noting (though not really related here), I measure a ~20%-25% time reduction by avoiding doing 2 lookups:

0std::set<COutPoint> vInOutPoints;
1for (const auto& txin : tx.vin)
2{
3    if (!vInOutPoints.insert(txin.prevout).second)
4        return state.DoS(100, false, REJECT_INVALID, "bad-txns-inputs-duplicate");
5}

laanwj commented at 6:36 am on November 9, 2016: member

@laanwj looks good to me. Only slight criticism is that we may want to generate .h/.cpp pairs for blocks to ensure that they end up in separate compilation units, but we can always address that later if it becomes an issue.

Fully agree. On the long run, I’d like to forego the conversion to hex and subsequent compilation entirely on build chains that supports this, by embedding the binary directly as mentioned in a comment here #6658 (comment). The current way wastes a lot of time and memory while compiling.

Add deserialize + CheckBlock benchmarks, and a full block hex b2e178a2d2

Remove redundant duplicate-input check from CheckTransaction eecffe50ef

Optimize vInOutPoints insertion a bit e2b3fb349e

TheBlueMatt force-pushed on Nov 9, 2016

TheBlueMatt commented at 7:30 pm on November 9, 2016: member

Picked up (and squashed) @laanwj’s changes and went ahead and remove the duplicate-lookup for ATMP uses.

laanwj merged this on Nov 10, 2016

laanwj closed this on Nov 10, 2016

laanwj referenced this in commit 71bc39eb74 on Nov 10, 2016

paveljanik referenced this in commit 6544457d5f on Nov 10, 2016

codablock referenced this in commit a9aa477daf on Jan 15, 2018

TheBlueMatt referenced this in commit b8f801964f on Sep 17, 2018

TheBlueMatt referenced this in commit 833180f538 on Sep 17, 2018

TheBlueMatt referenced this in commit d1dee20547 on Sep 17, 2018

laanwj referenced this in commit 52965fbaef on Sep 18, 2018

laanwj referenced this in commit 4b8a3f5d23 on Sep 18, 2018

UdjinM6 referenced this in commit f7e8e72468 on Sep 18, 2018

UdjinM6 referenced this in commit eaae127cf4 on Sep 18, 2018

cryptapus referenced this in commit d018a9b73e on Sep 18, 2018

UdjinM6 referenced this in commit d3b30e9b2f on Sep 18, 2018

UdjinM6 referenced this in commit 3cc4ac1376 on Sep 19, 2018

EvgenijM86 referenced this in commit 16dd486411 on Sep 19, 2018

CryptoDJ referenced this in commit a18e7bfd9c on Sep 22, 2018

CryptoDJ referenced this in commit 157d20b27b on Sep 22, 2018

CryptoDJ referenced this in commit b2caaf2135 on Sep 22, 2018

CryptoDJ referenced this in commit 52d0d61cde on Sep 22, 2018

CryptoDJ referenced this in commit d755a209c3 on Sep 22, 2018

ripper234 commented at 5:32 am on September 22, 2018: none

So, if I understand correctly, this caused CVE-2018-17144.

Can we do a root cause analysis / 5 whys explaining how this was introduced?

thijstriemstra commented at 4:00 pm on September 22, 2018: none

It’s scary to see how this code was merged with so much confidence. The fact there wasn’t a unit test covering this piece of code makes me feel little better though, a bad unit test would be even worse. I hope btc core will never accept contributions without tests again.

dfoderick commented at 8:14 pm on September 22, 2018: none

Can we do a root cause analysis / 5 whys explaining how this was introduced?

Short version. This pull request added a boolean parameter to CheckTransaction method
bool CheckTransaction(const CTransaction& tx, CValidationState &state, bool fCheckDuplicateInputs)

Then in CheckBlock method the flag was passed in as false bypassing the check for duplicate inputs. Assumption was that transaction would already be validated by other code so there was no need to validate a second time.
if (!CheckTransaction(tx, state, false))

Why there was no unit test? Why there are so many assumptions in code? Why did programmer not put the flag on transaction class instead?

ripper234 commented at 5:13 am on September 23, 2018: none

Why this passed code review? (How many people reviewed it?)

adlai commented at 10:22 am on September 23, 2018: none

@ripper234 commented 5 hours ago

Why this passed code review? (How many people reviewed it?) [sic]

I’m sure Microsoft is the right corporate person to ask.

ripper234 commented at 6:41 pm on September 23, 2018: none

?

scravy commented at 10:31 am on September 24, 2018: contributor

@dfoderick I question that these questions are in the spirit of a 5 whys root-cause analysis. You are supposed to go deeper, not wider as you do.

Anyhow, the PR merged here was a refactoring and performance improvement, and there already was no test that could have been broken by this; which I believe to be the real culprit.

dfoderick commented at 3:36 pm on September 24, 2018: none

Anyhow, the PR merged here was a refactoring and performance improvement, and there already was no test that could have been broken by this; which I believe to be the real culprit.

Correct. The test for this bug did not exist at the time and was only recently added. https://github.com/bitcoin/bitcoin/commit/9b4a36effcf642f3844c6696b757266686ece11a

There was a bench test to prove the performance gain but no test for correctness. The bug allows a block with an invalid tx to pass block validation.

willyko referenced this in commit a2f2b78754 on Sep 24, 2018

adlai commented at 9:46 am on September 25, 2018: none

@ripper234 commented 2 days ago

?

I’m gonna assume your eloquence was directed at me; if you’re not the antecedent of that pronoun, or my assumption was asinine, please ignore this message! @ripper234, if you truly care about “why this passed code review” (See how here the grammar is correct, and there’s no need for editorialization? Amazing, this whole language business!), then you should be able to assign a lower bound to “How many people reviewed it” with confidence equal to your mnemonic fidelity. If this message is unclear, please go back to code review, and leave the Github issue brigading to the professional trolls (or perhaps, take your concerns to the mailing list).

jnewbery commented at 4:13 pm on September 25, 2018: member

I suggest we lock this PR. For all the drive-by commenters two years after the fact: if you’re serious about wanting to improve security and code quality in Bitcoin Core, you can start by:

testing release candidates
reviewing open PRs
contributing code

MarcoFalke locked this on Sep 25, 2018

Remove duplicatable duplicate-input check from CheckTransaction #9049