Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Raystonn]

[-- Attachment #1: Type: text/html, Size: 4163 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 647 bytes --]

On Fri, Jul 03, 2015 at 10:43:14PM -0700, Raystonn wrote:
> <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.

-- 
'peter'[:-1]@petertodd.org
00000000000000000a43884e675843f56df90feffeabf56c4e7350f96b623f00

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Justus Ranvier]

[-- Attachment #1.1: Type: text/plain, Size: 1621 bytes --]

On 07/04/2015 12:44 AM, Peter Todd wrote:
> 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.

-- 
Justus Ranvier
Open Bitcoin Privacy Project
http://www.openbitcoinprivacyproject.org/
justus@openbitcoinprivacyproject.org
E7AD 8215 8497 3673 6D9E 61C4 2A5F DA70 EAD9 E623

[-- Attachment #1.2: 0xEAD9E623.asc --]
[-- Type: application/pgp-keys, Size: 18667 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 2262 bytes --]

On Sat, Jul 4, 2015 at 4:18 PM, Justus Ranvier <
justus@openbitcoinprivacyproject.org> wrote:

> 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.


> 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.


> 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.


> 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.

[-- Attachment #2: Type: text/html, Size: 3291 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Justus Ranvier]

[-- Attachment #1.1: Type: text/plain, Size: 1683 bytes --]

On 07/04/2015 10:35 AM, Tier Nolan wrote:
> 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.

>> 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.

> 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.



-- 
Justus Ranvier
Open Bitcoin Privacy Project
http://www.openbitcoinprivacyproject.org/
justus@openbitcoinprivacyproject.org
E7AD 8215 8497 3673 6D9E 61C4 2A5F DA70 EAD9 E623

[-- Attachment #1.2: 0xEAD9E623.asc --]
[-- Type: application/pgp-keys, Size: 18667 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 894 bytes --]

On Sat, Jul 4, 2015 at 5:01 PM, Justus Ranvier <
justus@openbitcoinprivacyproject.org> wrote:

> 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.


> 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.

[-- Attachment #2: Type: text/html, Size: 1515 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Justus Ranvier]

[-- Attachment #1.1: Type: text/plain, Size: 708 bytes --]

On 07/04/2015 12:58 PM, Tier Nolan wrote:
> 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):

https://gist.github.com/justusranvier/451616fa4697b5f25f60


-- 
Justus Ranvier
Open Bitcoin Privacy Project
http://www.openbitcoinprivacyproject.org/
justus@openbitcoinprivacyproject.org
E7AD 8215 8497 3673 6D9E 61C4 2A5F DA70 EAD9 E623

[-- Attachment #1.2: 0xEAD9E623.asc --]
[-- Type: application/pgp-keys, Size: 18667 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 903 bytes --]

On Sun, Jul 5, 2015 at 12:33 AM, Justus Ranvier <
justus@openbitcoinprivacyproject.org> wrote:

> 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.

[-- Attachment #2: Type: text/html, Size: 1540 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 2004 bytes --]

On Sat, Jul 4, 2015 at 4:30 AM, Peter Todd <pete@petertodd.org> wrote:

> 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.

[-- Attachment #2: Type: text/html, Size: 2668 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Raystonn]

[-- Attachment #1: Type: text/html, Size: 1160 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[odinn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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:
> 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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJVl3HCAAoJEGxwq/inSG8CXXIH/0s8o09UwRld+upM2pdAovMu
1SBCg/JeK3jXvqJDjyAbYe22WbnW8ykrZdujo1MFGuoZWbgrrSXo581lpyCy3O6c
SZYfAJee4eILzBl4MOwiAImcJBE3zOBCKT/DDaD1Qc8XvX6ReWJFYZgHsp/5F/BL
VlwVV9505V3X2G+y+3XOPwLggCu6m0MkRgeUjNTwdn+j6Yg6/NjJbS+YDDgjZ9dM
y3+uGA9Ek0bCLwjceUh8xAEwb+QUJrJgrNIo1vjuy+NRl18s1rUSx1YGTRkAD8eV
spdGTmXClx/phNnsR072hsqYRSj0CzhV8cQnEAh3ZmB4/RMhcxeNDmGw4rFNwD4=
=71aR
-----END PGP SIGNATURE-----

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2092 bytes --]

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. :(

> <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 &lt;gmaxwell@gmail.com&gt; 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 &lt;raystonn&#64;hotmail.com&gt; wrote:<br />
> &gt; 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


-- 
'peter'[:-1]@petertodd.org
000000000000000014870ea5d966efbae21588be363949de7cb3838f42b00e2f

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 646 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Raystonn]

[-- Attachment #1: Type: text/html, Size: 1534 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[odinn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

"The Wall Street of Bitcoin"

On 07/03/2015 08:30 PM, Peter Todd wrote:
> 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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJVl1PeAAoJEGxwq/inSG8C2LAIAK9FbCODbTu2t2yktusv37Sd
zf5/ApqciZ01X4oiQHHKXIgzhYgNenv2dnRsBsrGtn53L1AopXOiSIcz8ECCYsjp
lwiKitebU7VukDlCu07ZQpff62Hm34lsqo2oXZHSC/lKYXD5llixgCmNrs2CTYrF
bWxCr2pngr+azDFX9hUSr6c48MO8Id8hdiWIcYwofNOcUACloqgJ/SaZZqT5OSXj
gk3Iq0ltTQdc71z7g8G1cqHfL/Nu47X0XnwVt8UAOn0b8bo3Hbz3QegPXoj1tik2
j8lJUqm3lwKdIky2i50OWxL/agaXou3jJy19jhziW5sRh3tkZfC4BbI+wazfRyk=
=dW9O
-----END PGP SIGNATURE-----

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1482 bytes --]

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.

-- 
'peter'[:-1]@petertodd.org
00000000000000001242e0216eb113f1c50e4c18ecfbc8b9c0224ec82ec391d6

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Fork of invalid blocks due to BIP66 violations

[Gregory Maxwell]

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] Fork of invalid blocks due to BIP66 violations

[Raystonn]

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