rpc: have verifytxoutproof check the number of txns in proof structure #13452

instagibbs · 2018-06-12T21:16:32Z

Recent publication of a weakness in Bitcoin's merkle tree construction demonstrates many SPV applications vulnerable to an expensive to pull off yet still plausible attack: https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/

This change would at least allow verifytxoutproof to properly validate that the proof matches a known block, with known number of transactions any time after the full block is processed. This should neuter the attack entirely.

The negative is that a header-only processed block/future syncing mode would cause this to fail until the node has imported the data required.

related: #13451

importprunedfunds needs this check as well. Can expand it to cover this if people like the idea.

maflcko · 2018-06-12T22:20:22Z

utACK 614fd8db3259b01e47d7b551ac389bd3137c8c5a. Looks like a nice belt-and-suspenders with no strings attached: I think it is reasonable for a node to fail here, in case it hasn't downloaded the transactions (and thus doesn't know the number of transactions).

luke-jr · 2018-06-12T22:46:14Z

utACK

achow101 · 2018-06-12T23:15:21Z

utACK 614fd8db3259b01e47d7b551ac389bd3137c8c5a

sipa · 2018-06-13T18:34:13Z

src/rpc/rawtransaction.cpp

Is it right to throw an RPC error here? This is more similar to being given an invalid proof (as opposed to an incorrectly formatted/unusable one), in which case Null is returned currently.

deja vu: #11120 (comment)

(I can also just have it clear the return list)

Yes, I feel there is a big difference between not having the block (which means being unable to validate) and being given an intentionally fraudulent proof.

Requiring software to deal and match RPC errors instead of being covered by dealing with the existing "invalid proof" case sounds much nicer.

I also think you need to check for nTx = 0 by the way (as it may mean a block for which we only have headers etc), and treat that as not having the block.

@sipa Is it well-defined that a headers-only blockindex will have nTx==0? The comments say nTx simply is unreliable in that case...

instagibbs · 2018-06-14T13:55:58Z

took @sipa suggestions

luke-jr · 2018-06-16T04:22:04Z

I think this actually breaks in pruned mode, since nTx gets set to 0. :/

( Actually, I can't find where pruning resets nTx... just asserts and comments implying it must. :| )

sipa · 2018-06-16T04:26:30Z

@luke-jr Really? That would be unfortunate. I assumed that nTX == 0 was only the case if we never accepted the full block.

luke-jr · 2018-06-16T04:32:51Z

I'm not sure on the actual behaviour right now, since I can't find where it's zeroed. It may be that the asserts are an unrelated bug (but I'd expect we'd have noticed if that were the case).

sipa · 2018-06-16T04:40:10Z

Can you point to the asserts?

luke-jr · 2018-06-16T16:15:04Z

Nevermind, looks like there's only one left in master, and it's wrapped under a !fHavePruned check.

instagibbs · 2018-06-18T13:51:16Z

I think this actually breaks in pruned mode, since nTx gets set to 0. :/

This is hopefully not the case, because I have a merged PR with tests that pass #13451

sipa · 2018-06-22T02:19:11Z

utACK ed82f17

sdaftuar

ACK apart from the nits I left.

I also wrote up a test that exercises the logic, if you feel like including that with this patch: sdaftuar@e6db405

sdaftuar · 2018-06-21T20:28:29Z

src/rpc/rawtransaction.cpp


    const CBlockIndex* pindex = LookupBlockIndex(merkleBlock.header.GetHash());
-    if (!pindex || !chainActive.Contains(pindex)) {
+    if (!pindex || !chainActive.Contains(pindex) || pindex->nTx == 0) {


pindex->nTx == 0 implies !chainActive.Contains(pindex), so I think we can eliminate that condition. You can't be in chainactive if you never received the transactions for a block. Alternatively, we could add a comment for future readers that explains that this is redundant.

sdaftuar · 2018-06-21T20:30:29Z

src/rpc/rawtransaction.cpp

-    for (const uint256& hash : vMatch)
-        res.push_back(hash.GetHex());
+    // Check if proof is valid, only add results if so
+    if (pindex->nTx == merkleBlock.txn.GetNumTransactions()) {


nit: I think if the proof lies about the number of transactions, we should throw an error, rather than just return an empty list, but I don't feel strongly about the API if you like it this way.

sdaftuar · 2018-06-21T20:32:24Z

src/rpc/rawtransaction.cpp

            "1. \"proof\"    (string, required) The hex-encoded proof generated by gettxoutproof\n"
            "\nResult:\n"
-            "[\"txid\"]      (array, strings) The txid(s) which the proof commits to, or empty array if the proof is invalid\n"
+            "[\"txid\"]      (array, strings) The txid(s) which the proof commits to, or empty array if the proof can not be validated.\n"


I think we should leave the language here unchanged? If we can't validate the proof because the number of transactions differs from what we stored in our blockindex, then the proof is invalid!

instagibbs · 2018-06-22T14:42:44Z

cherry-picked @sdaftuar test, thanks!

DrahtBot · 2018-06-26T11:24:58Z

Note to reviewers: This pull request conflicts with the following ones:

tests: Enable automatic detection of undefined names in Python tests scripts. Remove wildcard imports. #13054 (tests: Enable automatic detection of undefined names in Python tests scripts. Remove wildcard imports. by practicalswift)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

laanwj · 2018-07-09T18:25:43Z

utACK d280617

…proof structure d280617 [qa] Add a test for merkle proof malleation (Suhas Daftuar) ed82f17 have verifytxoutproof check the number of txns in proof structure (Gregory Sanders) Pull request description: Recent publication of a weakness in Bitcoin's merkle tree construction demonstrates many SPV applications vulnerable to an expensive to pull off yet still plausible attack: https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/ This change would at least allow `verifytxoutproof` to properly validate that the proof matches a known block, with known number of transactions any time after the full block is processed. This should neuter the attack entirely. The negative is that a header-only processed block/future syncing mode would cause this to fail until the node has imported the data required. related: #13451 `importprunedfunds` needs this check as well. Can expand it to cover this if people like the idea. Tree-SHA512: 0682ec2b622a38b29f3f635323e0a8b6fc071e8a6fd134c954579926ee7b516e642966bafa667016744ce49c16e19b24dbc8801f982a36ad0a6a4aff6d93f82b

Github-Pull: bitcoin#13452 Rebased-From: ed82f17

Github-Pull: bitcoin#13452 Rebased-From: d280617

fanquake · 2018-07-13T23:57:35Z

Should be backported in #13644.

Github-Pull: bitcoin#13452 Rebased-From: ed82f17

Github-Pull: bitcoin#13452 Rebased-From: d280617

Github-Pull: bitcoin#13452 Rebased-From: ed82f17

…xns in proof structure d280617 [qa] Add a test for merkle proof malleation (Suhas Daftuar) ed82f17 have verifytxoutproof check the number of txns in proof structure (Gregory Sanders) Pull request description: Recent publication of a weakness in Bitcoin's merkle tree construction demonstrates many SPV applications vulnerable to an expensive to pull off yet still plausible attack: https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/ This change would at least allow `verifytxoutproof` to properly validate that the proof matches a known block, with known number of transactions any time after the full block is processed. This should neuter the attack entirely. The negative is that a header-only processed block/future syncing mode would cause this to fail until the node has imported the data required. related: bitcoin#13451 `importprunedfunds` needs this check as well. Can expand it to cover this if people like the idea. Tree-SHA512: 0682ec2b622a38b29f3f635323e0a8b6fc071e8a6fd134c954579926ee7b516e642966bafa667016744ce49c16e19b24dbc8801f982a36ad0a6a4aff6d93f82b

maflcko added the RPC/REST/ZMQ label Jun 12, 2018

maflcko changed the title ~~have verifytxoutproof check the number of txns in proof structure~~ rpc: have verifytxoutproof check the number of txns in proof structure Jun 12, 2018

maflcko added this to the 0.16.2 milestone Jun 13, 2018

maflcko added the Needs backport label Jun 13, 2018

sipa reviewed Jun 13, 2018

View reviewed changes

have verifytxoutproof check the number of txns in proof structure

ed82f17

instagibbs force-pushed the actuallyverifytxoutproof branch from 614fd8d to ed82f17 Compare June 14, 2018 13:55

bitcoin deleted a comment from DrahtBot Jun 15, 2018

sdaftuar approved these changes Jun 22, 2018

View reviewed changes

[qa] Add a test for merkle proof malleation

d280617

laanwj merged commit d280617 into bitcoin:master Jul 9, 2018

fanquake mentioned this pull request Jul 12, 2018

0.16: Remaining backports for 0.16.2 #13644

Merged

Bushstar mentioned this pull request Jul 13, 2018

commits from bitcoin/master FeatherCoin/Feathercoin#354

Merged

maflcko pushed a commit to maflcko/bitcoin-core that referenced this pull request Jul 13, 2018

have verifytxoutproof check the number of txns in proof structure

6b9dc8c

Github-Pull: bitcoin#13452 Rebased-From: ed82f17

maflcko pushed a commit to maflcko/bitcoin-core that referenced this pull request Jul 13, 2018

[qa] Add a test for merkle proof malleation

b72c0bd

Github-Pull: bitcoin#13452 Rebased-From: d280617

fanquake removed the Needs backport label Jul 13, 2018

luke-jr pushed a commit to bitcoinknots/bitcoin that referenced this pull request Jul 18, 2018

have verifytxoutproof check the number of txns in proof structure

c3f8bdc

Github-Pull: bitcoin#13452 Rebased-From: ed82f17

luke-jr pushed a commit to bitcoinknots/bitcoin that referenced this pull request Jul 18, 2018

[qa] Add a test for merkle proof malleation

2e2fd7e

Github-Pull: bitcoin#13452 Rebased-From: d280617

sipa added the Needs release note label Aug 14, 2018

HashUnlimited pushed a commit to chaincoin/chaincoin that referenced this pull request Jan 11, 2019

have verifytxoutproof check the number of txns in proof structure

f8924ba

Github-Pull: bitcoin#13452 Rebased-From: ed82f17

fanquake removed the Needs release note label Mar 20, 2019

harding mentioned this pull request Apr 2, 2021

chain: request pruned blocks from backend peers btcsuite/btcwallet#737

Merged

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

rpc: have verifytxoutproof check the number of txns in proof structure #13452

rpc: have verifytxoutproof check the number of txns in proof structure #13452

Uh oh!

Conversation

instagibbs commented Jun 12, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Jun 12, 2018

Uh oh!

luke-jr commented Jun 12, 2018

Uh oh!

achow101 commented Jun 12, 2018

Uh oh!

sipa Jun 13, 2018

Choose a reason for hiding this comment

Uh oh!

instagibbs Jun 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa Jun 13, 2018

Choose a reason for hiding this comment

Uh oh!

luke-jr Jun 16, 2018

Choose a reason for hiding this comment

Uh oh!

instagibbs commented Jun 14, 2018

Uh oh!

luke-jr commented Jun 16, 2018

Uh oh!

sipa commented Jun 16, 2018

Uh oh!

luke-jr commented Jun 16, 2018

Uh oh!

sipa commented Jun 16, 2018

Uh oh!

luke-jr commented Jun 16, 2018

Uh oh!

instagibbs commented Jun 18, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sipa commented Jun 22, 2018

Uh oh!

sdaftuar left a comment

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jun 21, 2018

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jun 21, 2018

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jun 21, 2018

Choose a reason for hiding this comment

Uh oh!

instagibbs commented Jun 22, 2018

Uh oh!

DrahtBot commented Jun 26, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

laanwj commented Jul 9, 2018

Uh oh!

fanquake commented Jul 13, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

instagibbs commented Jun 12, 2018 •

edited

Loading

instagibbs Jun 13, 2018 •

edited

Loading

instagibbs commented Jun 18, 2018 •

edited

Loading

DrahtBot commented Jun 26, 2018 •

edited

Loading