public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function
@ 2017-04-05 21:37 Gregory Maxwell
  2017-04-05 23:05 ` theymos
                   ` (9 more replies)
  0 siblings, 10 replies; 49+ messages in thread
From: Gregory Maxwell @ 2017-04-05 21:37 UTC (permalink / raw)
  To: Bitcoin Dev

A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which
is exploited by ASICBOOST and the various steps which could be used to
block it in the network if it became a problem.

While most discussion of ASICBOOST has focused on the overt method
of implementing it, there also exists a covert method for using it.

As I explained one of the approaches to inhibit covert ASICBOOST I
realized that my words were pretty much also describing the SegWit
commitment structure.

The authors of the SegWit proposal made a specific effort to not be
incompatible with any mining system and, in particular, changed the
design at one point to accommodate mining chips with forced payout
addresses.

Had there been awareness of exploitation of this attack an effort
would have been made to avoid incompatibility-- simply to separate
concerns.  But the best methods of implementing the covert attack
are significantly incompatible with virtually any method of
extending Bitcoin's transaction capabilities; with the notable
exception of extension blocks (which have their own problems).

An incompatibility would go a long way to explain some of the
more inexplicable behavior from some parties in the mining
ecosystem so I began looking for supporting evidence.

Reverse engineering of a particular mining chip has demonstrated
conclusively that ASICBOOST has been implemented
in hardware.

On that basis, I offer the following BIP draft for discussion.
This proposal does not prevent the attack in general, but only
inhibits covert forms of it which are incompatible with
improvements to the Bitcoin protocol.

I hope that even those of us who would strongly prefer that
ASICBOOST be blocked completely can come together to support
a protective measure that separates concerns by inhibiting
the covert use of it that potentially blocks protocol improvements.

The specific activation height is something I currently don't have
a strong opinion, so I've left it unspecified for the moment.

<pre>
  BIP: TBD
  Layer: Consensus
  Title: Inhibiting a covert attack on the Bitcoin POW function
  Author: Greg Maxwell <greg@xiph.org>
  Status: Draft
  Type: Standards Track
  Created: 2016-04-05
  License: PD
</pre>

==Abstract==

This proposal inhibits the covert exploitation of a known
vulnerability in Bitcoin Proof of Work function.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.

==Motivation==

Due to a design oversight the Bitcoin proof of work function has a potential
attack which can allow an attacking miner to save up-to 30% of their energy
costs (though closer to 20% is more likely due to implementation overheads).

Timo Hanke and Sergio Demian Lerner claim to hold a patent on this attack,
which they have so far not licensed for free and open use by the public.
They have been marketing their patent licenses under the trade-name
ASICBOOST.  The document takes no position on the validity or enforceability
of the patent.

There are two major ways of exploiting the underlying vulnerability: One
obvious way which is highly detectable and is not in use on the network
today and a covert way which has significant interaction and potential
interference with the Bitcoin protocol.  The covert mechanism is not
easily detected except through its interference with the protocol.

In particular, the protocol interactions of the covert method can block the
implementation of virtuous improvements such as segregated witness.

Exploitation of this vulnerability could result in payoff of as much as
$100 million USD per year at the time this was written (Assuming at
50% hash-power miner was gaining a 30% power advantage and that mining
was otherwise at profit equilibrium).  This could have a phenomenal
centralizing effect by pushing mining out of profitability for all
other participants, and the income from secretly using this
optimization could be abused to significantly distort the Bitcoin
ecosystem in order to preserve the advantage.

Reverse engineering of a mining ASIC from a major manufacture has
revealed that it contains an undocumented, undisclosed ability
to make use of this attack. (The parties claiming to hold a
patent on this technique were completely unaware of this use.)

On the above basis the potential for covert exploitation of this
vulnerability and the resulting inequality in the mining process
and interference with useful improvements presents a clear and
present danger to the Bitcoin system which requires a response.

==Background==

The general idea of this attack is that SHA2-256 is a merkle damgard hash
function which consumes 64 bytes of data at a time.

The Bitcoin mining process repeatedly hashes an 80-byte 'block header' while
incriminating a 32-bit nonce which is at the end of this header data. This
means that the processing of the header involves two runs of the compression
function run-- one that consumes the first 64 bytes of the header and a
second which processes the remaining 16 bytes and padding.

The initial 'message expansion' operations in each step of the SHA2-256
function operate exclusively on that step's 64-bytes of input with no
influence from prior data that entered the hash.

Because of this if a miner is able to prepare a block header with
multiple distinct first 64-byte chunks but identical 16-byte
second chunks they can reuse the computation of the initial
expansion for multiple trials. This reduces power consumption.

There are two broad ways of making use of this attack. The obvious
way is to try candidates with different version numbers.  Beyond
upsetting the soft-fork detection logic in Bitcoin nodes this has
little negative effect but it is highly conspicuous and easily
blocked.

The other method is based on the fact that the merkle root
committing to the transactions is contained in the first 64-bytes
except for the last 4 bytes of it.  If the miner finds multiple
candidate root values which have the same final 32-bit then they
can use the attack.

To find multiple roots with the same trailing 32-bits the miner can
use efficient collision finding mechanism which will find a match
with as little as 2^16 candidate roots expected, 2^24 operations to
find a 4-way hit, though low memory approaches require more
computation.

An obvious way to generate different candidates is to grind the
coinbase extra-nonce but for non-empty blocks each attempt will
require 13 or so additional sha2 runs which is very inefficient.

This inefficiency can be avoided by computing a sqrt number of
candidates of the left side of the hash tree (e.g. using extra
nonce grinding) then an additional sqrt number of candidates of
the right  side of the tree using transaction permutation or
substitution of a small number of transactions.  All combinations
of the left and right side are then combined with only a single
hashing operation virtually eliminating all tree related
overhead.

With this final optimization finding a 4-way collision with a
moderate amount of memory requires ~2^24 hashing operations
instead of the >2^28 operations that would be require for
extra-nonce  grinding which would substantially erode the
benefit of the attack.

It is this final optimization which this proposal blocks.

==New consensus rule==

Beginning block X and until block Y the coinbase transaction of
each block MUST either contain a BIP-141 segwit commitment or a
correct WTXID commitment with ID 0xaa21a9ef.

(See BIP-141 "Commitment structure" for details)

Existing segwit using miners are automatically compatible with
this proposal. Non-segwit miners can become compatible by simply
including an additional output matching a default commitment
value returned as part of getblocktemplate.

Miners SHOULD NOT automatically discontinue the commitment
at the expiration height.

==Discussion==

The commitment in the left side of the tree to all transactions
in the right side completely prevents the final sqrt speedup.

A stronger inhibition of the covert attack in the form of
requiring the least significant bits of the block timestamp
to be equal to a hash of the first 64-bytes of the header. This
would increase the collision space from 32 to 40 or more bits.
The root value could be required to meet a specific hash prefix
requirement in order to increase the computational work required
to try candidate roots. These change would be more disruptive and
there is no reason to believe that it is currently necessary.

The proposed rule automatically sunsets. If it is no longer needed
due to the introduction of stronger rules or the acceptance of the
version-grinding form then there would be no reason to continue
with this requirement.  If it is still useful at the expiration
time the rule can simply be extended with a new softfork that
sets longer date ranges.

This sun-setting avoids the accumulation of technical debt due
to retaining enforcement of this rule when it is no longer needed
without requiring a hard fork to remove it.

== Overt attack ==

The non-covert form can be trivially blocked by requiring that
the header version match the coinbase transaction version.

This proposal does not include this block because this method
may become generally available without restriction in the future,
does not generally interfere with improvements in the protocol,
and because it is so easily detected that it could be blocked if
it becomes an issue in the future.

==Backward compatibility==


==Implementation==


==Acknowledgments==


==Copyright==

This document is placed in the public domain.


^ permalink raw reply	[flat|nested] 49+ messages in thread
* Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function
@ 2017-04-06  4:47 Oliver Petruzel
  0 siblings, 0 replies; 49+ messages in thread
From: Oliver Petruzel @ 2017-04-06  4:47 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

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

> > One of the things going for us here is that Bitmain has been keeping
ASICBOOST
> > from their own customers - as far as we know they haven't been sharing
it, and
> > thus they're the only ones you can actually use it.
> >
> > So while we're pissing off Bitmain in disabling it, we wouldn't be
affecting
> > anyone else.
> >
> > Equally, mining is a zero-sum game: if no-one can use ASICBOOST, miners
are in
> > the same position as before. ASICBOOST is only relevant to miners like
Bitmain
> > who have access to it while other miners don't.

Peter -
Do we know that for a fact, though? What evidence or intelligence do we
have to indicate Bitmain itself is the only entity using the covert boost?

A few possibilities:
1. They could have already shared it with a limited number of strategic
partners;
2. They could have offered to share it with various parties in exchange for
something (money, support for BU, etc); or
3. They could provide the custom firmware/software to select parties as a
direct response to this disclosure -- which would enhance their defenses
against a soft fork.
4. They could share the firmware/software with EVERY owner of their
equipment in a last-ditch defense against a soft fork. (after all, some
advantage over other equipment manufacturers is still better than no
advantage, right?)

Assumptions could lead to failure, so these are just some things to keep in
mind.

Respectfully,
Oliver

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

^ permalink raw reply	[flat|nested] 49+ messages in thread
* Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function
@ 2017-04-06  4:49 Raystonn .
  2017-04-06  7:47 ` praxeology_guy
  0 siblings, 1 reply; 49+ messages in thread
From: Raystonn . @ 2017-04-06  4:49 UTC (permalink / raw)
  To: Gregory Maxwell, bitcoin-dev

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

Great catch, and a good proposal for a fix.  Pushing the activation height out to allow existing hardware to enter obsolescence prior to activation may help reduce miner resistance.  It may also avoid legal threats from those currently abusing.  If miners still resist, the threat of an earlier activation height is a good negotiating tool.

Raystonn

On 5 Apr 2017 2:39 p.m., Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which
is exploited by ASICBOOST and the various steps which could be used to
block it in the network if it became a problem.

While most discussion of ASICBOOST has focused on the overt method
of implementing it, there also exists a covert method for using it.

As I explained one of the approaches to inhibit covert ASICBOOST I
realized that my words were pretty much also describing the SegWit
commitment structure.

The authors of the SegWit proposal made a specific effort to not be
incompatible with any mining system and, in particular, changed the
design at one point to accommodate mining chips with forced payout
addresses.

Had there been awareness of exploitation of this attack an effort
would have been made to avoid incompatibility-- simply to separate
concerns.  But the best methods of implementing the covert attack
are significantly incompatible with virtually any method of
extending Bitcoin's transaction capabilities; with the notable
exception of extension blocks (which have their own problems).

An incompatibility would go a long way to explain some of the
more inexplicable behavior from some parties in the mining
ecosystem so I began looking for supporting evidence.

Reverse engineering of a particular mining chip has demonstrated
conclusively that ASICBOOST has been implemented
in hardware.

On that basis, I offer the following BIP draft for discussion.
This proposal does not prevent the attack in general, but only
inhibits covert forms of it which are incompatible with
improvements to the Bitcoin protocol.

I hope that even those of us who would strongly prefer that
ASICBOOST be blocked completely can come together to support
a protective measure that separates concerns by inhibiting
the covert use of it that potentially blocks protocol improvements.

The specific activation height is something I currently don't have
a strong opinion, so I've left it unspecified for the moment.

<pre>
  BIP: TBD
  Layer: Consensus
  Title: Inhibiting a covert attack on the Bitcoin POW function
  Author: Greg Maxwell <greg@xiph.org>
  Status: Draft
  Type: Standards Track
  Created: 2016-04-05
  License: PD
</pre>

==Abstract==

This proposal inhibits the covert exploitation of a known
vulnerability in Bitcoin Proof of Work function.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.

==Motivation==

Due to a design oversight the Bitcoin proof of work function has a potential
attack which can allow an attacking miner to save up-to 30% of their energy
costs (though closer to 20% is more likely due to implementation overheads).

Timo Hanke and Sergio Demian Lerner claim to hold a patent on this attack,
which they have so far not licensed for free and open use by the public.
They have been marketing their patent licenses under the trade-name
ASICBOOST.  The document takes no position on the validity or enforceability
of the patent.

There are two major ways of exploiting the underlying vulnerability: One
obvious way which is highly detectable and is not in use on the network
today and a covert way which has significant interaction and potential
interference with the Bitcoin protocol.  The covert mechanism is not
easily detected except through its interference with the protocol.

In particular, the protocol interactions of the covert method can block the
implementation of virtuous improvements such as segregated witness.

Exploitation of this vulnerability could result in payoff of as much as
$100 million USD per year at the time this was written (Assuming at
50% hash-power miner was gaining a 30% power advantage and that mining
was otherwise at profit equilibrium).  This could have a phenomenal
centralizing effect by pushing mining out of profitability for all
other participants, and the income from secretly using this
optimization could be abused to significantly distort the Bitcoin
ecosystem in order to preserve the advantage.

Reverse engineering of a mining ASIC from a major manufacture has
revealed that it contains an undocumented, undisclosed ability
to make use of this attack. (The parties claiming to hold a
patent on this technique were completely unaware of this use.)

On the above basis the potential for covert exploitation of this
vulnerability and the resulting inequality in the mining process
and interference with useful improvements presents a clear and
present danger to the Bitcoin system which requires a response.

==Background==

The general idea of this attack is that SHA2-256 is a merkle damgard hash
function which consumes 64 bytes of data at a time.

The Bitcoin mining process repeatedly hashes an 80-byte 'block header' while
incriminating a 32-bit nonce which is at the end of this header data. This
means that the processing of the header involves two runs of the compression
function run-- one that consumes the first 64 bytes of the header and a
second which processes the remaining 16 bytes and padding.

The initial 'message expansion' operations in each step of the SHA2-256
function operate exclusively on that step's 64-bytes of input with no
influence from prior data that entered the hash.

Because of this if a miner is able to prepare a block header with
multiple distinct first 64-byte chunks but identical 16-byte
second chunks they can reuse the computation of the initial
expansion for multiple trials. This reduces power consumption.

There are two broad ways of making use of this attack. The obvious
way is to try candidates with different version numbers.  Beyond
upsetting the soft-fork detection logic in Bitcoin nodes this has
little negative effect but it is highly conspicuous and easily
blocked.

The other method is based on the fact that the merkle root
committing to the transactions is contained in the first 64-bytes
except for the last 4 bytes of it.  If the miner finds multiple
candidate root values which have the same final 32-bit then they
can use the attack.

To find multiple roots with the same trailing 32-bits the miner can
use efficient collision finding mechanism which will find a match
with as little as 2^16 candidate roots expected, 2^24 operations to
find a 4-way hit, though low memory approaches require more
computation.

An obvious way to generate different candidates is to grind the
coinbase extra-nonce but for non-empty blocks each attempt will
require 13 or so additional sha2 runs which is very inefficient.

This inefficiency can be avoided by computing a sqrt number of
candidates of the left side of the hash tree (e.g. using extra
nonce grinding) then an additional sqrt number of candidates of
the right  side of the tree using transaction permutation or
substitution of a small number of transactions.  All combinations
of the left and right side are then combined with only a single
hashing operation virtually eliminating all tree related
overhead.

With this final optimization finding a 4-way collision with a
moderate amount of memory requires ~2^24 hashing operations
instead of the >2^28 operations that would be require for
extra-nonce  grinding which would substantially erode the
benefit of the attack.

It is this final optimization which this proposal blocks.

==New consensus rule==

Beginning block X and until block Y the coinbase transaction of
each block MUST either contain a BIP-141 segwit commitment or a
correct WTXID commitment with ID 0xaa21a9ef.

(See BIP-141 "Commitment structure" for details)

Existing segwit using miners are automatically compatible with
this proposal. Non-segwit miners can become compatible by simply
including an additional output matching a default commitment
value returned as part of getblocktemplate.

Miners SHOULD NOT automatically discontinue the commitment
at the expiration height.

==Discussion==

The commitment in the left side of the tree to all transactions
in the right side completely prevents the final sqrt speedup.

A stronger inhibition of the covert attack in the form of
requiring the least significant bits of the block timestamp
to be equal to a hash of the first 64-bytes of the header. This
would increase the collision space from 32 to 40 or more bits.
The root value could be required to meet a specific hash prefix
requirement in order to increase the computational work required
to try candidate roots. These change would be more disruptive and
there is no reason to believe that it is currently necessary.

The proposed rule automatically sunsets. If it is no longer needed
due to the introduction of stronger rules or the acceptance of the
version-grinding form then there would be no reason to continue
with this requirement.  If it is still useful at the expiration
time the rule can simply be extended with a new softfork that
sets longer date ranges.

This sun-setting avoids the accumulation of technical debt due
to retaining enforcement of this rule when it is no longer needed
without requiring a hard fork to remove it.

== Overt attack ==

The non-covert form can be trivially blocked by requiring that
the header version match the coinbase transaction version.

This proposal does not include this block because this method
may become generally available without restriction in the future,
does not generally interfere with improvements in the protocol,
and because it is so easily detected that it could be blocked if
it becomes an issue in the future.

==Backward compatibility==


==Implementation==


==Acknowledgments==


==Copyright==

This document is placed in the public domain.
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


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

^ permalink raw reply	[flat|nested] 49+ messages in thread
* Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function
@ 2017-04-07  1:34 Daniele Pinna
  2017-04-07  6:46 ` Emilian Ursu
                   ` (2 more replies)
  0 siblings, 3 replies; 49+ messages in thread
From: Daniele Pinna @ 2017-04-07  1:34 UTC (permalink / raw)
  To: Gregory Maxwell, Bitcoin Dev

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

Can you please not forget to supply us more details on the claims made
regarding the reverse engineering of the Asic chip?

It is absolutely crucial that we get these independently verified ASAP.

Daniele

Message: 2
> Date: Thu, 6 Apr 2017 21:38:31 +0000
> From: Gregory Maxwell <greg@xiph.org>
> To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
> Subject: Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on
>         the     Bitcoin POW function
> Message-ID:
>         <CAAS2fgSTrMjKZVpL4wRidnzTCC9O3OEF=oCnROf1pggz2cDgJA@mail.
> gmail.com>
> Content-Type: text/plain; charset=UTF-8
> On Wed, Apr 5, 2017 at 9:37 PM, Gregory Maxwell <greg@xiph.org> wrote:
> > each block MUST either contain a BIP-141 segwit commitment or a
> > correct WTXID commitment with ID 0xaa21a9ef.
> It was just pointed out to me that the proposed ID (which I just
> selected to be above the segwit one) collides with one chosen in
> another non-BIP proposal.  This wasn't intentional, and I'll happily
> change the value when I update the document.

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

^ permalink raw reply	[flat|nested] 49+ messages in thread

end of thread, other threads:[~2017-04-07 13:28 UTC | newest]

Thread overview: 49+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-04-05 21:37 [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function Gregory Maxwell
2017-04-05 23:05 ` theymos
2017-04-06  0:17   ` Gregory Maxwell
2017-04-06  0:39     ` Joseph Poon
2017-04-06  0:40       ` Joseph Poon
2017-04-06  1:32       ` Gregory Maxwell
2017-04-06  2:09         ` Joseph Poon
2017-04-05 23:25 ` Anthony Towns
2017-04-05 23:42 ` Joseph Poon
2017-04-06  2:10 ` Jonathan Toomim
2017-04-06 20:21   ` Jared Lee Richardson
2017-04-06  2:31 ` Peter Todd
2017-04-06  2:39   ` Bram Cohen
2017-04-06  2:49     ` Peter Todd
2017-04-06  3:11       ` Erik Aronesty
2017-04-06  3:23         ` Peter Todd
2017-04-06  3:23       ` David Vorick
2017-04-06  3:42         ` Peter Todd
2017-04-06  5:46         ` Thomas Daede
2017-04-06  6:24         ` Jonathan Toomim
2017-04-06 12:04           ` David Vorick
     [not found]           ` <CAMZUoK=oDAD9nhFAHkgncWtYxjBNh3qXbUffOH57QMnqjhmN6g@mail.gmail.com>
     [not found]             ` <CAMZUoKn8tr3LGbks0TnaCx9NTP6MZUzQ8PE6jDq1xiqpYyYwow@mail.gmail.com>
2017-04-06 13:55               ` Russell O'Connor
2017-04-06 16:49           ` Marco
2017-04-06 17:04           ` Alex Mizrahi
2017-04-06 17:13           ` Alex Mizrahi
2017-04-07 12:59             ` Jannes Faber
2017-04-07 13:28               ` Erik Aronesty
2017-04-06 17:31           ` Jared Lee Richardson
2017-04-06 17:26         ` Jared Lee Richardson
2017-04-06 15:36       ` Alex Mizrahi
2017-04-06 17:51     ` Jorge Timón
2017-04-06  7:24 ` bfd
2017-04-06  9:17 ` Luke Dashjr
2017-04-06 12:02 ` Luv Khemani
2017-04-06 12:11   ` Bryan Bishop
2017-04-06 17:43     ` Timo Hanke
2017-04-06 12:30   ` Luv Khemani
2017-04-06 15:15     ` Jorge Timón
2017-04-06 15:41       ` Daniel Robinson
2017-04-06 16:13 ` Andreas Schildbach
2017-04-06 21:38 ` Gregory Maxwell
2017-04-06  4:47 Oliver Petruzel
2017-04-06  4:49 Raystonn .
2017-04-06  7:47 ` praxeology_guy
2017-04-06 12:13   ` David Vorick
2017-04-07  1:34 Daniele Pinna
2017-04-07  6:46 ` Emilian Ursu
2017-04-07  7:44 ` Alex Mizrahi
2017-04-07  8:08 ` praxeology_guy

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox