Fork of invalid blocks due to BIP66 violations
17 messages, 4 to 5 Jul 2015. Started by Raystonn ..
Raystonn . (4), Tier Nolan (4), Peter Todd (3), Justus Ranvier (3), Odinn Cyberguerrilla (2), Greg Maxwell
We need some analysis on why this has happened. It appears the larger hashrate is violating BIP66. Thus it appears the network is rejecting this BIP, though potentially accidentally. If this is an accident, how is such a large portion of hashrate forking, and what can we do to avoid this in the future?
Raystonn
On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail•com> wrote:
Quoted text (1 line)
> We need some analysis on why this has happened. It appears the larger hashrate is violating BIP66. Thus it appears the network is rejecting this BIP, though potentially accidentally. If this is an accident, how is such a large portion of hashrate forking, and what can we do to avoid this in the future?
A near majority of the hashrate on the network appears to be SPV mining.
Btcnuggets was a non-upgraded miner that produced an invalid block after the lock in and f2pool and antpool have been extending it. Fortunately their extension contains no transactions (an artifact of SPV mining). Obviously a complete understanding is going to take some time; though I would note that this general failure mode was one we were aware of and is part of the reason the treshold is so high.
On Sat, Jul 04, 2015 at 03:17:17AM +0000, Gregory Maxwell wrote:
Quoted text (4 lines)
> On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail•com> wrote: > > We need some analysis on why this has happened. It appears the larger hashrate is violating BIP66. Thus it appears the network is rejecting this BIP, though potentially accidentally. If this is an accident, how is such a large portion of hashrate forking, and what can we do to avoid this in the future? > > A near majority of the hashrate on the network appears to be SPV mining.
As for what "SPV mining" is:
While blocks are propagating throughout the network, frequently it's possible for miners to get the header of the block before they get and fully validate the block itself. This is just a few seconds to tens of seconds, but that's a big deal for profitability. So miners have been running custom patches that mine on top of the longest chain they know about, even if they haven't actually verified the blocks in it due to propagation delays.
Unfortunately the Bitcoin protocol lets you do that, and the extra % of revenue makes a big difference when you take into account the low profit margins of mining these days. BIP66 happened to trigger this issue this time, but actually *any* miner creating an invalid block for *any* reason would have done so with the software miners are running right now.
"The Wall Street of Bitcoin"
On 07/03/2015 08:30 PM, Peter Todd wrote:
Quoted text (35 lines)
> On Sat, Jul 04, 2015 at 03:17:17AM +0000, Gregory Maxwell wrote: >> On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail•com> >> wrote: >>> We need some analysis on why this has happened. It appears the >>> larger hashrate is violating BIP66. Thus it appears the >>> network is rejecting this BIP, though potentially accidentally. >>> If this is an accident, how is such a large portion of hashrate >>> forking, and what can we do to avoid this in the future? >> >> A near majority of the hashrate on the network appears to be SPV >> mining. > > As for what "SPV mining" is: > > While blocks are propagating throughout the network, frequently > it's possible for miners to get the header of the block before they > get and fully validate the block itself. This is just a few seconds > to tens of seconds, but that's a big deal for profitability. So > miners have been running custom patches that mine on top of the > longest chain they know about, even if they haven't actually > verified the blocks in it due to propagation delays. > > Unfortunately the Bitcoin protocol lets you do that, and the extra > % of revenue makes a big difference when you take into account the > low profit margins of mining these days. BIP66 happened to trigger > this issue this time, but actually *any* miner creating an invalid > block for *any* reason would have done so with the software miners > are running right now. > > > > _______________________________________________ bitcoin-dev mailing > list bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
- -- http://abis.io ~ "a protocol concept to enable decentralization and expansion of a giving economy, and a new social good" https://keybase.io/odinn
SPV clients are at risk in scenarios like this. We should encourage them to check node versions against the minimum required for safety. This check should be upgraded when new BIPs go into effect. It won't help against malicious nodes. But it will help in cases such as today's.
On 3 Jul 2015 8:17 pm, Gregory Maxwell <gmaxwell@gmail•com> wrote:
On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail•com> wrote:
Quoted text (1 line)
> We need some analysis on why this has happened. It appears the larger hashrate is violating BIP66. Thus it appears the network is rejecting this BIP, though potentially accidentally. If this is an accident, how is such a large portion of hashrate forking, and what can we do to avoid this in the future?
A near majority of the hashrate on the network appears to be SPV mining.
Btcnuggets was a non-upgraded miner that produced an invalid block
after the lock in and f2pool and antpool have been extending it.
Fortunately their extension contains no transactions (an artifact of
SPV mining). Obviously a complete understanding is going to take some
time; though I would note that this general failure mode was one we
were aware of and is part of the reason the treshold is so high.
On Fri, Jul 03, 2015 at 10:17:38PM -0700, Raystonn wrote:
Yeah, I was really surprised when I found out today that bitcoinj doesn't implement any of the soft-fork code. There's no excuse for not doing that frankly. :(
Quoted text (26 lines)
> <p dir="ltr">SPV clients are at risk in scenarios like this. We should encourage them to check node versions against the minimum required for safety. This check should be upgraded when new BIPs go into effect. It won't help against malicious nodes. But it will help in cases such as today's.<br> > </p> > <div class="gmail_quote">On 3 Jul 2015 8:17 pm, Gregory Maxwell <gmaxwell@gmail•com> wrote:<br type='attribution'><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> > > > > <div> > <div>On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail.com> wrote:<br /> > > We need some analysis on why this has happened. It appears the larger hashrate is violating BIP66. Thus it appears the network is rejecting this BIP, though potentially accidentally. If this is an accident, how is such a large portion of hashrate forking, and what can we do to avoid this in the future?<br /> > <br /> > A near majority of the hashrate on the network appears to be SPV mining.<br /> > <br /> > Btcnuggets was a non-upgraded miner that produced an invalid block<br /> > after the lock in and f2pool and antpool have been extending it.<br /> > Fortunately their extension contains no transactions (an artifact of<br /> > SPV mining). Obviously a complete understanding is going to take some<br /> > time; though I would note that this general failure mode was one we<br /> > were aware of and is part of the reason the treshold is so high.<br /> > </div> > </div> > > </blockquote></div> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Raystonn,
How would an average SPV wallet user know anything about this at all? They might not know it is even happening, or if they have some idea that something is wrong, then they wouldn't know what to do.
Say you use Electrum, some older version like 1.9. Electrum's current version is 2.3.3. Or say you use a slightly older version like 2.2. In any event, how is an end user possibly going to know which of Electrum's (or any other SPV wallet's) versions are "the minimum required for safety?" (so as to know they would need to upgrade because problems)? Is this just something where it's really down to community announcements on websites and reddits and the like?
On 07/03/2015 10:17 PM, Raystonn wrote:
Quoted text (33 lines)
> SPV clients are at risk in scenarios like this. We should encourage > them to check node versions against the minimum required for > safety. This check should be upgraded when new BIPs go into effect. > It won't help against malicious nodes. But it will help in cases > such as today's. > > On 3 Jul 2015 8:17 pm, Gregory Maxwell <gmaxwell@gmail•com> wrote: > > On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail•com> > wrote: >> We need some analysis on why this has happened. It appears the > larger hashrate is violating BIP66. Thus it appears the network > is rejecting this BIP, though potentially accidentally. If this is > an accident, how is such a large portion of hashrate forking, and > what can we do to avoid this in the future? > > A near majority of the hashrate on the network appears to be SPV > mining. > > Btcnuggets was a non-upgraded miner that produced an invalid block > after the lock in and f2pool and antpool have been extending it. > Fortunately their extension contains no transactions (an artifact > of SPV mining). Obviously a complete understanding is going to > take some time; though I would note that this general failure mode > was one we were aware of and is part of the reason the treshold is > so high. > > > > _______________________________________________ bitcoin-dev mailing > list bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
- -- http://abis.io ~ "a protocol concept to enable decentralization and expansion of a giving economy, and a new social good" https://keybase.io/odinn
The SPV clients should be checking node versions. This is for wallet authors to implement. End-users should just stay current with their chosen wallet software.
On 3 Jul 2015 10:40 pm, odinn <odinn.cyberguerrilla@riseup•net> wrote:
Raystonn,
How would an average SPV wallet user know anything about this at all?
They might not know it is even happening, or if they have some idea
that something is wrong, then they wouldn't know what to do.
Say you use Electrum, some older version like 1.9. Electrum's current
version is 2.3.3. Or say you use a slightly older version like 2.2.
In any event, how is an end user possibly going to know which of
Electrum's (or any other SPV wallet's) versions are "the minimum
required for safety?" (so as to know they would need to upgrade
because problems)? Is this just something where it's really down to
community announcements on websites and reddits and the like?
On 07/03/2015 10:17 PM, Raystonn wrote:
Quoted text (33 lines)
> SPV clients are at risk in scenarios like this. We should encourage > them to check node versions against the minimum required for > safety. This check should be upgraded when new BIPs go into effect. > It won't help against malicious nodes. But it will help in cases > such as today's. > > On 3 Jul 2015 8:17 pm, Gregory Maxwell <gmaxwell@gmail•com> wrote: > > On Sat, Jul 4, 2015 at 3:11 AM, Raystonn <raystonn@hotmail•com> > wrote: >> We need some analysis on why this has happened. It appears the > larger hashrate is violating BIP66. Thus it appears the network > is rejecting this BIP, though potentially accidentally. If this is > an accident, how is such a large portion of hashrate forking, and > what can we do to avoid this in the future? > > A near majority of the hashrate on the network appears to be SPV > mining. > > Btcnuggets was a non-upgraded miner that produced an invalid block > after the lock in and f2pool and antpool have been extending it. > Fortunately their extension contains no transactions (an artifact > of SPV mining). Obviously a complete understanding is going to > take some time; though I would note that this general failure mode > was one we were aware of and is part of the reason the treshold is > so high. > > > > _______________________________________________ bitcoin-dev mailing > list bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
- --
"a protocol concept to enable decentralization
and expansion of a giving economy, and a new social good"
On Fri, Jul 03, 2015 at 10:43:14PM -0700, Raystonn wrote:
Quoted text (1 line)
> <p dir="ltr">The SPV clients should be checking node versions. This is for wallet authors to implement. End-users should just stay current with their chosen wallet software.<br>
Nodes can and do lie about what version they are all the time.
Fact is, SPV means you're trusting other people to check the rules for you. In this particular case bitcoinj could have - and should have - checked the BIP66 soft-fork rules, but in general there's no easy solution to this problem.
As I said, this doesn't help against malicious nodes. But it helps on a case such as today's.
On 3 Jul 2015 10:45 pm, Peter Todd <pete@petertodd•org> wrote:
On Fri, Jul 03, 2015 at 10:43:14PM -0700, Raystonn wrote:
Quoted text (1 line)
> <p dir="ltr">The SPV clients should be checking node versions. This is for wallet authors to implement. End-users should just stay current with their chosen wallet software.<br>
Nodes can and do lie about what version they are all the time.
Fact is, SPV means you're trusting other people to check the rules for
you. In this particular case bitcoinj could have - and should have -
checked the BIP66 soft-fork rules, but in general there's no easy
solution to this problem.
On Sat, Jul 4, 2015 at 4:30 AM, Peter Todd <pete@petertodd•org> wrote:
Quoted text (10 lines)
> As for what "SPV mining" is: > > While blocks are propagating throughout the network, frequently it's > possible for miners to get the header of the block before they get and > fully validate the block itself. This is just a few seconds to tens of > seconds, but that's a big deal for profitability. So miners have been > running custom patches that mine on top of the longest chain they know > about, even if they haven't actually verified the blocks in it due to > propagation delays. >
Is the invalid fork pretty much all empty blocks then?
SPV mining isn't inherently dangerous, if it is only for a short period of time. It can boost the total work for the block chain.
Inherently, invalid blocks are rare, so assuming a header is valid is the correct assumption.
For safety (for the miner), SPV miners should switch back to full mining after 20-30 seconds without fully validating the chain that they are on.
- header received - header verified (they skipped this step) - build on header with empty block - receive full block -- mark header as invalid if this step times out - verify full block -- mark header as invalid if verification fails - build on full block with non-empty block
An easier rule is that you only build on a header if the header's parent (or even grandparent) has been fully verified. That rule would prevent the illegal fork from growing past 1-2 blocks. It would mean that SPV miners would start wasting hashing power once the invalid fork hit 2 blocks. They wouldn't even build on their own block.
I guess miners never added code of that kind? That is pretty shocking that a majority would SPV mine without that safeguard against the main vulnerability of SPV mining.
Even waiting a few minutes before switch back would protect against this.
Worse, in this case, is that it wasn't just an invalid block, it was an invalid header chain. They could have done the check with headers only.
On 07/04/2015 12:44 AM, Peter Todd wrote:
Quoted text (4 lines)
> Fact is, SPV means you're trusting other people to check the rules for > you. In this particular case bitcoinj could have - and should have - > checked the BIP66 soft-fork rules, but in general there's no easy > solution to this problem.
In general, the situation can be improved if there existed proofs which validating full nodes could broadcast which would tell SPV nodes why the branch it sees with the most proof of work is actually invalid.
As far as I can tell, producing such proofs is reasonably straightforward for all cases except the case where a block is invalid because it contains a transaction which references a non-existent output.
The shortest proof that a particular transaction does not exist in the blockchain is the entire blockchain.
If each transaction input identified the block containing the referenced outpoint, then the proof of non-existence is either the block in question, or the list of block headers (to show that the block doesn't exist). That's a significant improvement in proof size over the entire blockchain.
Proving the non-existence of a particular transaction in a specific block could be made easier for future blocks by requiring transactions to be ordered in the merkle tree by their hashes. Then it would just require a few nodes in the tree to show that the transaction isn't in the place where it should be.
On Sat, Jul 4, 2015 at 4:18 PM, Justus Ranvier < justus@openbitcoinprivacyproject•org> wrote:
Quoted text (4 lines)
> In general, the situation can be improved if there existed proofs which > validating full nodes could broadcast which would tell SPV nodes why the > branch it sees with the most proof of work is actually invalid. >
Yeah, fraud proofs have been suggested lots of times in the past.
In this case, they weren't even needed. Fully updated SPV clients should also have rejected the invalid fork. All the information required to reject it was in the header chain.
The problem wasn't SPV miners, it was SPV-miners where the SPV part wasn't upgraded to handle v3 blocks.
Quoted text (4 lines)
> As far as I can tell, producing such proofs is reasonably > straightforward for all cases except the case where a block is invalid > because it contains a transaction which references a non-existent output. >
Even that can be handled with UTXO set commitments. If the UTXO tree is sorted you can prove that an entry doesn't exist.
What cannot be handled is proving that a block is invalid if the transaction data for the block is withheld.
Quoted text (6 lines)
> If each transaction input identified the block containing the referenced > outpoint, then the proof of non-existence is either the block in > question, or the list of block headers (to show that the block doesn't > exist). That's a significant improvement in proof size over the entire > blockchain. >
That is reasonable. Unconfirmed transactions can't include that info though.
It could be committed in as an extra commitment.
One issue is that you need to prove of of these commitments too.
A transaction which points to the wrong block would also be provable in the same way.
Quoted text (6 lines)
> Proving the non-existence of a particular transaction in a specific > block could be made easier for future blocks by requiring transactions > to be ordered in the merkle tree by their hashes. Then it would just > require a few nodes in the tree to show that the transaction isn't in > the place where it should be. >
You could just have an extra merkle tree.
You would only need to include the block hashes for all transactions to show that the two trees don't match. That is 32 bytes per transaction rather than the full 200-500 bytes per transaction.
On 07/04/2015 10:35 AM, Tier Nolan wrote:
Quoted text (2 lines)
> Even that can be handled with UTXO set commitments. If the UTXO tree is > sorted you can prove that an entry doesn't exist.
How do we know if a committed UTXO set is valid? If a majority of the hashing power is willing to extend an invalid branch, it's reasonable to assume they'd be willing to commit an invalid UTXO set as well.
In order for the committed UTXO set to be reliable at a minimum it will need to contain at a source block reference for each item in the set. That would enable fraud proof to show that the committed UTXO set contains invalid entries.
Quoted text (11 lines)
>> If each transaction input identified the block containing the referenced >> outpoint, then the proof of non-existence is either the block in >> question, or the list of block headers (to show that the block doesn't >> exist). That's a significant improvement in proof size over the entire >> blockchain. >> > > That is reasonable. Unconfirmed transactions can't include that info > though. > > It could be committed in as an extra commitment.
I agree the information should be an extra commitment produced by the miner, rather than changing the format of the transaction, since the author of a transaction can't always know the required information ahead of time.
Quoted text (1 line)
> One issue is that you need to prove of of these commitments too.
If items in the the proof tree are required to be sorted, then it's easy to proof that an item is missing.
On Sat, Jul 4, 2015 at 5:01 PM, Justus Ranvier < justus@openbitcoinprivacyproject•org> wrote:
Quoted text (4 lines)
> How do we know if a committed UTXO set is valid? If a majority of the > hashing power is willing to extend an invalid branch, it's reasonable to > assume they'd be willing to commit an invalid UTXO set as well. >
You can prove that it wasn't updated correctly.
For each transaction, the UTXO tree root before and after is committed.
You show the root before, and the root after and show that the after root is wrong. You also need to include some merkle paths to prove the transform.
Quoted text (3 lines)
> If items in the the proof tree are required to be sorted, then it's easy > to proof that an item is missing. >
Yes, you can mostly get short proofs for each step, but you have to make sure your proofs are also provable.
It means going through everything that needs to be proved for a block to be valid.
On 07/04/2015 12:58 PM, Tier Nolan wrote:
Quoted text (5 lines)
> Yes, you can mostly get short proofs for each step, but you have to make > sure your proofs are also provable. > > It means going through everything that needs to be proved for a block to be > valid.
I think the problem is tractable if some reasonable assumptions are made about the ability of SPV clients to perform validity checks that don't involve any state outside a single transaction (or block):
On Sun, Jul 5, 2015 at 12:33 AM, Justus Ranvier < justus@openbitcoinprivacyproject•org> wrote:
Quoted text (7 lines)
> I think the problem is tractable if some reasonable assumptions are made > about the ability of SPV clients to perform validity checks that don't > involve any state outside a single transaction (or block): > > https://gist.github.com/justusranvier/451616fa4697b5f25f60 > >
I agree, it is definitely tractable.
If Bitcoin was being designed from scratch, it could be made even easier.
As things stand, the extra commitment information needs to be added to extra trees, which themselves need to be checked.
The "prover", in your example, should ideally store additional meta-data along with each block.
If P2SH was made mandatory, then much of the transaction validation could be performed on the transaction alone.
Both the signature and the public key would be included in the spending transaction.