Fix overly eager BIP30 bypass #12204

morcos · 2018-01-16T18:57:40Z

In #6931 we introduced a possible consensus breaking change by misunderstanding how completely BIP 34 obviated the need for BIP 30. Unfixed, this could break consensus after block height about 1.9M. Explained in code comment.

h/t @sdaftuar

instagibbs · 2018-01-16T19:37:21Z

src/validation.cpp

Maybe put "block" in front of blocks being named by number. (and everywhere else)

I was reading it as the the height in coinbase aka the number 176,684 in the block's coinbase at height 490,897.

ryanofsky · 2018-01-16T20:20:29Z

src/validation.cpp

Is the significance of 1,938,702 just that it is the third lowest height found encoded in the old coinbases? The sentence doesn't say where 1,938,702 comes from, and this is written like it should be obvious what the number means.

If it is just the third lowest height found in the search, I think it would be clearer to say something like "An exhaustive search of all blocks before the BIP34 height found that the lowest height values indicated in coinbase scriptSigs were: 209,921, 490,897, and 1,983,702."

jnewbery

concept ACK 9ab7fe0b3f50b2cc3514975b26eb7c63134bdd40.

I'm currently running my own analysis of pre-BIP34 blocks to make sure that it agrees with what you found. It would be good to have a gist showing those results with code so other people can easily validate for themselves.

In general, I'm not sure whether code comments are appropriate for such a long and nuanced description. It certainly breaks up the flow of the ConnectBlock(). However, more verbose is generally better than less, and I don't have a better suggestion of where to put this level of comment that would stay maintained with the code.

jnewbery · 2018-01-16T21:07:27Z

src/validation.cpp

Rather than start your new comment explaining where the previous comment is incorrect, I think it makes sense to remove/reword the paragraph above.

I also think it would make the whole comment clearer if you explicitly introduced terminology at the top of the comment. Something like:

- block height: the height of the block in the blockchain - coinbase height: the height indicated in the coinbase transaction's scriptSig under BIP34 rules. All blocks with block height >= 227,931 must have coinbase height equal to block height. This is a consensus rule.

rather than sprinkling the rest of the comment with multiple terms for the same concept: a scriptSig with a valid-looking BIP34 height..., scriptSig indicating..., indicated block height, coinbase with indicated height.

I think it is useful to understand the basic logic that BIP 34 implies BIP 30 is met and doesn't need to be checked. But then understand why it's not quite that simple. It also matches the historical evolution of the code. So I left this comment as correction to the previous one.

jimpo · 2018-01-17T01:26:13Z

src/validation.cpp

typo: optimization

gmaxwell · 2018-01-17T11:32:58Z

Concept ACK.

TheBlueMatt

code-level utACK, modulo comment comments.

maflcko · 2018-01-18T23:49:55Z

Concept ACK. Though, I have never checked if any of the heights or hashes make sense. Wouldn't it help review if #6931 or this pull actually included the code that was used to determine those magic numbers?

jnewbery · 2018-01-19T22:25:08Z

My analysis matches yours exactly. The pre-BIP34 blocks with coinbase height > block height are (in ascending order):

block_height | coinbase_height
209920 | 209921
176684 | 490897
164384 | 1983702
169895 | 3708179 <---- I expect to be dead before this height
....

so you're right that the only heights that we should care about are 209921, 490897 and 1983702.

jnewbery · 2018-01-19T22:44:32Z

If anyone wants to re-run the analysis, the gist with my code is here: https://gist.github.com/jnewbery/df0a98f3d2fea52e487001bf2b9ef1fd

(this is quite slow since it's hitting the RPC interface 3 times for each block. It'd be faster to deserialize block files directly, patch bitcoind to print this data itself, or use BlockSci or a similar block analysis tool)

achow101 · 2018-01-20T06:06:28Z

code utACK, haven't actually read through the whole comment.

I agree with the above analysis that block 1983702 is the lowest block height that we need to worry about. We could soft fork in something prior to that block to guarantee that the txids will be different, e.g. block height in the nLockTime field.

morcos · 2018-01-25T16:28:05Z

Comment updated to hopefully be clearer. Code unchanged.

For reference here is how I double checked the possible violations. I patched bitcoind with this snippet and then ran with -reindex-chainstate.

@@ -1724,6 +1724,16 @@ static bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockInd
                 }
             }
         }
+        if (block.vtx[0]->vin[0].scriptSig.size() >= 4 && block.vtx[0]->vin[0].scriptSig[0] == 3) {
+            std::vector<unsigned char> vch;
+            for (int i=1;i<4;i++)
+                vch.push_back( block.vtx[0]->vin[0].scriptSig[i]);
+            CScriptNum height(vch,false);
+            int height_indicated = height.getint();
+            if (height_indicated > pindex->nHeight) {
+                fprintf(stdout,"Potential future duplicate: block %d has indicated height %d\n",pindex->nHeight,height_indicated);
+            }
+        }
     }
 
     // Start enforcing BIP68 (sequence locks) and BIP112 (CHECKSEQUENCEVERIFY) using versionbits logic.

jnewbery · 2018-01-26T19:16:23Z

Tested ACK 3f3b991

laanwj · 2018-02-08T15:48:02Z

Looks sensible to me. Although I think we should definitely make this a chain parameter, or at least define a constant, instead of hardcoding this magic number:

Optional TODO: Have BIP30 checking activate at a per chain block height.

I don't think we're in enough of a hurry here to skip that.

morcos · 2018-02-15T15:04:35Z

@laanwj I'm happy to define it as a constant locally, but it seems like adding it as a chain parameter just adds unnecessary cruft to the code. This is such an obscure (and irrelevant for decades) element of the consensus that it seems better to keep it entirely contained to one spot in the code base, so it doesn't occupy mental energy in other places. That said, will defer to your judgement...

EDIT: Or if we think testnet3 will get longer than 1.9 million blocks, then I suppose that's an argument for per chain so we don't do unnecessary calculations on testnet3.

laanwj · 2018-02-15T18:01:02Z

Nono I'm OK with that, but if we actively argue against making it a chain parameter we should remove the TODO as well, otherwise it's inviting someone else to make that change. My only point is that there is no hurry to merge this, so no reason to leave unfinished TODOs in the code.

morcos · 2018-02-15T18:35:42Z

updated to a constant and removed optional TODO, I believe its better to keep this mess contained to one section of the code

laanwj · 2018-02-15T18:44:14Z

utACK 5b8b387

jnewbery · 2018-02-16T14:49:22Z

utACK 5b8b387

Difference is that there is now a constexpr int BIP34_IMPLIES_BIP30_LIMIT and the comment has been updated.

Travis failed because of a timeout. I'll kick it.

sdaftuar · 2018-03-07T14:11:15Z

ACK

@sdaftuar

5b8b387 Fix overly eager BIP30 bypass (Alex Morcos) Pull request description: In #6931 we introduced a possible consensus breaking change by misunderstanding how completely BIP 34 obviated the need for BIP 30. Unfixed, this could break consensus after block height about 1.9M. Explained in code comment. h/t @sdaftuar Tree-SHA512: 8f798c3f203432fd4ae1c1c08bd6967b4a5ec2064ed5f6a7dcf3bff34ea830952838dd4ff70d70b5080cf4644f601e5526b60456c08f43789e4aae05621d9d6b

c894e8f [Core] Remove BIP30 check (random-zebra) Pull request description: A bit of history ---- Two transactions can have the same txid if their parents are identical, since the txids of the parents are included in a transaction. Coinbases have no parents, so it used to be possible for two of them to be identical. Further, by building on duplicate coinbases, duplicate normal transactions were possible as well (http://r6.ca/blog/20120206T005236Z.html). In order to remove the possibility of having duplicate transaction ids, Bitcoin introduced, with BIP30, the following consensus rule: - Blocks are not allowed to contain a transaction whose identifier matches that of an earlier, not-fully-spent transaction in the same chain. [[1](https://github.com/bitcoin/bips/blob/master/bip-0030.mediawiki)] This rule was enforced by verifying (in `ConnectBlock`) that none of the transactions in the block was overwriting an already existent non-pruned CCoins entry. BIP34 was later added in Bitcoin to enforce better transaction uniqueness, with the update of block version to 2, which introduced the following consensus rule: - the first serialized element in the scriptSig of coinbase transactions must be the height of the chain. [[2](https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki)] After the complete activation of BIP34, there seemed to be no longer need for the check in `ConnectBlock`, added for BIP30, as duplicated coinbases were rendered impossible with BIP34 (bitcoin#6931). This assumption was later revisited, when several blocks were found on Bitcoin's main chain (before BIP34 activation), having coinbase scripts with an height higher than the current chain height (and higher than the BIP34 activation height). Thus, coinbases for blocks at these "future" heights would have given the opportunity for BIP30 to be violated even with BIP34 enforced (bitcoin#12204). Motivation for this PR ---- PIVX has BIP30 and BIP34 consensus rules already implemented since the chain start. The first block after the genesis (height=1) has version 3. The "block.nVersion=2 rule" is enforced in `ContextualCheckBlock` https://github.com/PIVX-Project/PIVX/blob/af3dd41f86684a5e4a18cfb85d471a199cc980da/src/main.cpp#L3605-L3612 However the code still has the (somewhat expensive) BIP30 check in `ConnectBlock`, which wasn't needed at all, given the full enforcement of BIP34 since the start of the chain. This PR removes it. *Side Note*: Even without BIP34, with Proof-of-Stake, coinbase transactions have empty scriptPubKey (thus unspendable outputs), therefore there would have been no need for BIP30 checks in any case (at least after PoS activation height). ACKs for top commit: furszy: Great find! ACK c894e8f. Fuzzbawls: ACK c894e8f Tree-SHA512: bc0dec1ef68c05db35ee0a132d0817c851667ce47ba5ec7eae31d29f1a44266f987db4462dc16d2320684bf76a6088c3fdbe77e08a9312ab6a1b7a58b6632661

A bit of history ---- Two transactions can have the same txid if their parents are identical, since the txids of the parents are included in a transaction. Coinbases have no parents, so it used to be possible for two of them to be identical. Further, by building on duplicate coinbases, duplicate normal transactions were possible as well (http://r6.ca/blog/20120206T005236Z.html). In order to remove the possibility of having duplicate transaction ids, Bitcoin introduced, with BIP30, the following consensus rule: - Blocks are not allowed to contain a transaction whose identifier matches that of an earlier, not-fully-spent transaction in the same chain. [[1](https://github.com/bitcoin/bips/blob/master/bip-0030.mediawiki)] This rule was enforced by verifying (in `ConnectBlock`) that none of the transactions in the block was overwriting an already existent non-pruned CCoins entry. BIP34 was later added in Bitcoin to enforce better transaction uniqueness, with the update of block version to 2, which introduced the following consensus rule: - the first serialized element in the scriptSig of coinbase transactions must be the height of the chain. [[2](https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki)] After the complete activation of BIP34, there seemed to be no longer need for the check in `ConnectBlock`, added for BIP30, as duplicated coinbases were rendered impossible with BIP34 (bitcoin/bitcoin#6931). This assumption was later revisited, when several blocks were found on Bitcoin's main chain (before BIP34 activation), having coinbase scripts with an height higher than the current chain height (and higher than the BIP34 activation height). Thus, coinbases for blocks at these "future" heights would have given the opportunity for BIP30 to be violated even with BIP34 enforced (bitcoin/bitcoin#12204). Squorum has BIP30 and BIP34 consensus rules already implemented since the chain start. The first block after the genesis (height=1) has version 4. However the code still has the (somewhat expensive) BIP30 check in `ConnectBlock`, which wasn't needed at all, given the full enforcement of BIP34 since the start of the chain. This commit removes it. *Side Note*: Even without BIP34, with Proof-of-Stake, coinbase transactions have empty scriptPubKey (thus unspendable outputs), therefore there would have been no need for BIP30 checks in any case (at least after PoS activation height).

@sdaftuar

Summary: 5b8b387 Fix overly eager BIP30 bypass (Alex Morcos) Pull request description: In #6931 we introduced a possible consensus breaking change by misunderstanding how completely BIP 34 obviated the need for BIP 30. Unfixed, this could break consensus after block height about 1.9M. Explained in code comment. h/t @sdaftuar --- Backport of Core [[bitcoin/bitcoin#12204 | PR12204]] Test Plan: ninja all check check-functional Reviewers: #bitcoin_abc, PiRK Reviewed By: PiRK Differential Revision: https://reviews.bitcoinabc.org/D8209

instagibbs reviewed Jan 16, 2018

View reviewed changes

ryanofsky reviewed Jan 16, 2018

View reviewed changes

jnewbery reviewed Jan 16, 2018

View reviewed changes

jimpo reviewed Jan 17, 2018

View reviewed changes

src/validation.cpp Outdated

Copy link

Contributor

jimpo Jan 17, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

typo: optimization

TheBlueMatt reviewed Jan 17, 2018

View reviewed changes

fanquake added the Consensus label Jan 22, 2018

morcos force-pushed the bip30bypassfix branch from 9ab7fe0 to 3f3b991 Compare January 25, 2018 16:25

Fix overly eager BIP30 bypass

5b8b387

morcos force-pushed the bip30bypassfix branch from 3f3b991 to 5b8b387 Compare February 15, 2018 18:34

laanwj merged commit 5b8b387 into bitcoin:master Mar 7, 2018

random-zebra mentioned this pull request Jul 31, 2020

[Core] Remove BIP30 check PIVX-Project/PIVX#1775

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Fix overly eager BIP30 bypass #12204

Fix overly eager BIP30 bypass #12204

Uh oh!

Conversation

morcos commented Jan 16, 2018

Uh oh!

instagibbs Jan 16, 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!

ryanofsky Jan 16, 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!

jnewbery left a comment

Choose a reason for hiding this comment

Uh oh!

jnewbery Jan 16, 2018

Choose a reason for hiding this comment

Uh oh!

morcos Jan 25, 2018

Choose a reason for hiding this comment

Uh oh!

jimpo Jan 17, 2018

Choose a reason for hiding this comment

Uh oh!

gmaxwell commented Jan 17, 2018

Uh oh!

TheBlueMatt left a comment • 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!

maflcko commented Jan 18, 2018

Uh oh!

jnewbery commented Jan 19, 2018

Uh oh!

jnewbery commented Jan 19, 2018

Uh oh!

achow101 commented Jan 20, 2018

Uh oh!

morcos commented Jan 25, 2018

Uh oh!

jnewbery commented Jan 26, 2018

Uh oh!

laanwj commented Feb 8, 2018

Uh oh!

morcos commented Feb 15, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

laanwj commented Feb 15, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

morcos commented Feb 15, 2018

Uh oh!

laanwj commented Feb 15, 2018

Uh oh!

jnewbery commented Feb 16, 2018

Uh oh!

sdaftuar commented Mar 7, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

12 participants

instagibbs Jan 16, 2018 •

edited

Loading

ryanofsky Jan 16, 2018 •

edited

Loading

TheBlueMatt left a comment •

edited

Loading

morcos commented Feb 15, 2018 •

edited

Loading

laanwj commented Feb 15, 2018 •

edited

Loading