Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Daniele Pinna]

[-- 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 --]

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Emilian Ursu]

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



The fact that this is possible should be enough for us to implement 
meassures against it.

On Fri, 7 Apr 2017, Daniele Pinna via bitcoin-dev wrote:

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Alex Mizrahi]

[-- Attachment #1: Type: text/plain, Size: 600 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.
>

Bitmain confirmed that their chips support ASICBOOST and it can be used for
mining:

https://blog.bitmain.com/en/regarding-recent-allegations-smear-campaigns/

They claim that they don't use it on mainnet, but that claim cannot be
verified. it is possible to do covert ASICBOOST in a 100% covert manner.
(It can be done without "transaction reordering" so it's not worth
analyzing blocks etc.)

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[praxeology_guy]

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

Daniele Pinna,

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

gmaxwell told me that back even in S7 chips its possible to set the SHA256 midstate/IV instead of just resetting it to the standard SHA256 IV. This essentially allows you to re-use midstates, which is one of the key necessary features for the ASICBOOST optimization to work. From the chip's perspective there is not much difference between the covert and overt optimization methods, particularly given that the whole IV/midstate vector can be set.

The covert method just requires more work than the overt method:. overt you just permutate the version bits, vs the covert one requires you find partial hash collisions of the tx merkle root. The extra work to find the partial tx merkle root hash collisions could be done at different stages in the mining system... some speculate that it could be done in the miner's FPGA.

Not sure how exactly gmaxwell (or his friend) did it. I don't currently own any mining hardware nor the time to do it myself.

Cheers,
Praxeology Guy

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Erik Aronesty]

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

It is *not proof of stake.* when:

a) burn happens regardless of whether you successfully mine.
b) miner cannot know which tx are burns
c) the majority of burns cannot be used for mining and are simply lost
(poisson discovery distribution)
d) burn involves real risk: *every bit as much at stake *

(It's the difference between a computer secured by not being connected to
the internet, and a computer secured by re-imaging from a computer that
was, in the past, not connected to the internet.)

It is possible to craft a burn-network such that the only way for a miner
to prevent a burn is to prevent all transactions other than his own.

This is still a weakness, and I can't see a way around it though.


On Fri, Apr 7, 2017 at 8:59 AM, Jannes Faber via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> On 6 April 2017 at 19:13, Alex Mizrahi via bitcoin-dev <bitcoin-dev@lists.
> linuxfoundation.org> wrote:
>
>>
>> Ethically, this situation has some similarities to the DAO fork.
>>
>>
>> Much better analogy:
>>
>> 1. An ISV make software which makes use of an undocumented OS feature.
>> 2. That feature is no longer present in the next OS release.
>> 3. ISV suffers losses because its software cannot work under new OS, and
>> thus people stop buying it.
>>
>> I think 99% of programmers would agree that this loss was inflicted by a
>> bad decision of ISV, and not by OS vendor changing OS internals. Relying on
>> undocumented features is something you do on your own risk.
>>
>
> Right. And in this case, code still is law: if the code specifies a
> version number field and some miner finds an optimization that only works
> when the version number == 1 then it's his own problem once the network
> upgrades to version 2. In no way is there anything ethical about blocking
> the upgrade.
>
> History is not an indicator of the possible values any field can hold in
> the future. Limiting your operation to some arbitrary subset is at your own
> risk.
>
> Regarding the comparison: I haven't heard anyone even suggest rolling back
> the last year of the blockchain to undo the damage already done, any
> comparison can end there. If Jonathan wants to persist with this comparison
> it would be more like people deciding to stop further funding of the hacked
> contract. Yeah, that evil.
>
> --
> Jannes Faber
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jannes Faber]

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

On 6 April 2017 at 19:13, Alex Mizrahi via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> Ethically, this situation has some similarities to the DAO fork.
>
>
> Much better analogy:
>
> 1. An ISV make software which makes use of an undocumented OS feature.
> 2. That feature is no longer present in the next OS release.
> 3. ISV suffers losses because its software cannot work under new OS, and
> thus people stop buying it.
>
> I think 99% of programmers would agree that this loss was inflicted by a
> bad decision of ISV, and not by OS vendor changing OS internals. Relying on
> undocumented features is something you do on your own risk.
>

Right. And in this case, code still is law: if the code specifies a version
number field and some miner finds an optimization that only works when the
version number == 1 then it's his own problem once the network upgrades to
version 2. In no way is there anything ethical about blocking the upgrade.

History is not an indicator of the possible values any field can hold in
the future. Limiting your operation to some arbitrary subset is at your own
risk.

Regarding the comparison: I haven't heard anyone even suggest rolling back
the last year of the blockchain to undo the damage already done, any
comparison can end there. If Jonathan wants to persist with this comparison
it would be more like people deciding to stop further funding of the hacked
contract. Yeah, that evil.

--
Jannes Faber

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Gregory Maxwell]

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.

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jared Lee Richardson]

> Just checking to see if I understand this optimization correctly. In order to find merkle roots in which the rightmost 32 bits are identical (i.e. partial hash collisions), we want to compute as many merkle root hashes as quickly as possible. The fastest way to do this is to take the top level of the Merkle tree, and to collect a set of left branches and right branches which can be independently manipulated. While the left branch can easily be manipulated by changing the extranonce in the coinbase transaction, the right branch would need to be modified by changing one of the transactions in the right branch or by changing the number of transactions in the right branch. Correct so far?

Envisioning it in my head and trying to read the white paper, it
sounds like the process for a non-stratum mining farm would be this:

On primary server with sufficient memory, calculate ~4k-6k valid
left-side merkle tree roots and ~4k-6k right-side merkle tree roots.
Then try hashing every left-side option with every right-side option.
I'm not sure if modern asic chips are sufficiently generic that they
can also sha256-double-hash those combinations, but it seems logical
to assume that the permutations of those hashes could be computed on
an asic, perhaps via additional hardware installed on the server.
Hashing these is easier if there are fewer steps, i.e., fewer
transactions.

Out of this will come N(2-16 at most, higher not needed) colliding
merkle roots where the last 4 bytes are identical.  Those N different
merkle combinations are what can be used on the actual mining devices,
and those are all that needs to be sent for the optimization to work.

On the actual mining device, what is done is to take the identical
(collision) right 4 bytes of the merkle root and hash it with one
nonce value.  Since you have N(assume 8) inputs that all work with the
same value, calculating this single hash of once nonce is equivalent
to calculating 8 nonce hashes during the normal process, and this step
is 1/4th of the normal hashing process.  This hash(or mid-value?) is
then sent to 8 different cores which complete the remaining 3 hash
steps with each given collision value.  Then you increment the nonce
once and start over.

This works out to a savings of (assuming compressor and expander steps
of SHA2 require computationally the same amount of time) 25% * (7 / 8)
where N=8.

Greg, or someone else, can you confirm that this is the right
understanding of the approach?

> I have not seen or heard of any hardware available that can run more efficiently using getblocktemplate.

As above, it doesn't require such a massive change.  They just need to
retrieve N different sets of work from the central server instead of 1
set of work.  The central server itself might need substantial
bandwidth if it farmed out the merkle-root hashing computational space
to miners.  Greg, is that what you're assuming they are doing?  Now
that I think about it, even that situation could be improved.  Suppose
you have N miners who can do either a merkle-tree combinatoric
double-sha or a block-nonce double-sha.  The central server calculates
the left and right merkle treeset to be combined and also assigns each
miner each a unique workspace within those combinatorics.  The miners
compute each hash in their workspace and shard the results within
themselves according to the last 16 bits.  Each miner then needs only
the memory for 1/Nth of the workspace, and can report back to the
central server only the highest number of collisions it has found
until the central server is satisfied and returns the miners to normal
(collided) mining.

Seems quite workable in a large mining farm to me, and would allow the
collisions to be found very, very quickly.

That said, it strikes me that there may be some statistical method by
which we can isolate which pools seem to have used this approach
against the background noise of other pools.  Hmm...

Jared



On Wed, Apr 5, 2017 at 7:10 PM, Jonathan Toomim via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Just checking to see if I understand this optimization correctly. In order to find merkle roots in which the rightmost 32 bits are identical (i.e. partial hash collisions), we want to compute as many merkle root hashes as quickly as possible. The fastest way to do this is to take the top level of the Merkle tree, and to collect a set of left branches and right branches which can be independently manipulated. While the left branch can easily be manipulated by changing the extranonce in the coinbase transaction, the right branch would need to be modified by changing one of the transactions in the right branch or by changing the number of transactions in the right branch. Correct so far?
>
> With the stratum mining protocol, the server (the pool) includes enough information for the coinbase transaction to be modified by stratum client (the miner), but it does not include any information about the right side of the merkle tree except for the top-level hash. Stratum also does not allow the client to supply any modifications to the merkle tree (including the right side) back to the stratum server. This means that any implementation of this final optimization would need to be using a protocol other than stratum, like getblocktemplate, correct?
>
> I think it would be helpful for the discussion to know if this optimization were currently being used or not, and if so, how widely.
>
> All of the consumer-grade hardware that I have seen defaults to stratum-only operation, and I have not seen or heard of any hardware available that can run more efficiently using getblocktemplate. As the current pool infrastructure uses stratum exclusively, this optimization would require significant retooling among pools, and probably a redesign of their core algorithms to help discover and share these partial collisions more frequently. It's possible that some large private farms have deployed a special system for solo mining that uses this optimization, of course, but it's also possible that there's a teapot in space somewhere between the orbit of Earth and Mars.
>
> Do you know of any ways to perform this optimization via stratum? If not, do you have any evidence that this optimization is actually being used by private solo mining farms? Or is this discussion purely about preventing this optimization from being used in the future?
>
> -jtoomim
>
>> On Apr 5, 2017, at 2:37 PM, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>> 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.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jorge Timón]

On Thu, Apr 6, 2017 at 4:39 AM, Bram Cohen via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Asicboost also has the problem that it isn't treating the hashing as a black
> box, and thus has impacts on what gets mined. In particular it creates an
> incentive to make blocks smaller. That's a very unwanted effect, and
> anything like it should be engineered out on principle.

This is an interesting point.

If you have a precise description why it makes an incentive to make
blocks smaller I would love to read it.
Somebody asked and I didn't have an answer.
I imagine you try several reorderings sometimes excluding certain
branches of the merkle tree, permuting the branches you exclude or
something similar, but I really don't know the algorithm in detail and
I didn't want to say something inaccurate.

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Timo Hanke]

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

Bryan,

Interesting argument, but I think it is not an accurate comparison. People
usually mean that, for example, say 2^80 of the original operations are
needed rather than the intended 2^128 to find a collision. This could be
the case in a broken algorithms such as a toy SHA variant with too small
states and too few rounds. These kind of attacks usually refer to that
something is learned from prior evaluations that be should't be possible to
be learned. For example, if someone could somehow construct a pre-image in
256 evaluations, getting one additional bit right at a time. Similar to a
cheap combination lock where you can figure out the correct 4 digits in a
worst case of 4*10 attempts by "feeling" it, rather than having to do the
intended 10,000 attempts. That's the kind of thing that would be called an
"attack".

Here, however, we are talking about making the individual operations
cheaper by a constant of ~20%, not changing the number of operations. That
doesn't qualify as an attack in the sense that you mean.

Best,
Timo




On Thu, Apr 6, 2017 at 5:11 AM, Bryan Bishop via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Thu, Apr 6, 2017 at 7:02 AM, Luv Khemani via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Could you elaborate on why you consider ASICBOOST to be an attack? Attack
>> here implies ill-intent by the practitioner towards the network as a
>> primary motivating factor.
>>
>>
> See https://www.reddit.com/r/Bitcoin/comments/63otrp/
> gregory_maxwell_major_asic_manufacturer_is/dfwcki3/
>
> """
> I think that it is an attack is a completely unambiguous technical
> description of what it is. If a signature is supposed to resist forgery
> against 2^128 operations, but you find a way to do it with 2^80 instead,
> this is an attack. It is, perhaps, not a very concerning attack and you may
> or may not change your signature scheme to avoid it or may just instead say
> the scheme has 2^80 security. But there is no doubt that it would be called
> an attack, especially if it was not described in the original proposal.
>
> In Bitcoin's Proof of Work, you are attempting to prove a certain amount
> of work has been done. This shortcut significantly reduces the amount of
> work. It's an attack. Normally it wouldn't be a serious attack-- it would
> just get appended to the defacto definition of what the Bitcoin Proof of
> work is-- similar to the signature system just getting restarted as having
> 2^80 security-- but in it's covert form it cannot just be adopted because
> it blocks many further improvements (not just segwit, but the vast majority
> of other proposals), and additional the licensing restrictions inhibit
> adoption.
>
> The proposal I posted does not prevent the technique, only the covert
> form: That is, it doesn't even attempt to solve the patented tech
> eventually will centralize the system problem. It is narrowly targeted at
> the interference with upgrades.
>
> Taking a step back-- even ignoring my geeking out about the technical
> definition of 'attack' in crypographic contexts, we have a set of issues
> here that left addressed will seriously harm the system going forward for
> the the significant monetary benefit of an exploiting party. I think that
> also satisfies a lay definition of the term: Something someone does, that
> none one expected, that makes them money at everyone elses expense.
> """
>
> - Bryan
> http://heybryan.org/
> 1 512 203 0507 <(512)%20203-0507>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jared Lee Richardson]

To me, all of these miss the main objection.  If a miner found an
optimization and kept it for themselves, that's their prerogative.
But if that optimization also happens to directly discourage the
growth and improvement of the protocol in many unforseen ways, and it
also encourages the miner to include fewer transactions per block,
that directly hurts Bitcoin and its future.  Something should clearly
be done about it when the latter is at issue.  I agree with you that
the former is a relative nonissue.

On Wed, Apr 5, 2017 at 11:24 PM, Jonathan Toomim via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Ethically, this situation has some similarities to the DAO fork. We have an entity who closely examined the code, found an unintended characteristic of that code, and made use of that characteristic in order to gain tens of millions of dollars. Now that developers are aware of it, they want to modify the code in order to negate as much of the gains as possible.
>
> There are differences, too, of course: the DAO attacker was explicitly malicious and stole Ether from others, whereas Bitmain is just optimizing their hardware better than anyone else and better than some of us think they should be allowed to.
>
> In both cases, developers are proposing that the developers and a majority of users collude to reduce the wealth of a single entity by altering the blockchain rules.
>
> In the case of the DAO fork, users were stealing back stolen funds, but that justification doesn't apply in this case. On the other hand, in this case we're talking about causing someone a loss by reducing the value of hardware investments rather than forcibly taking back their coins, which is less direct and maybe more justifiable.
>
> While I don't like patented mining algorithms, I also don't like the idea of playing Calvin Ball on the blockchain. Rule changes should not be employed as a means of disempowering and empoverishing particular entities without very good reason. Whether patenting a mining optimization qualifies as good reason is questionable.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jared Lee Richardson]

> We are not going to invalidate covert asicboost without a fight. And we are working with a system that actively (and is demonstrably very effective at doing it) resists changes which are contentious. This is definitely a contentious change, because an important part of the community (the miners) is going to be actively resisting it.

I'd just like to point out, invalidating asicboost has only a very
limited number of potential detractors.  Only a mining farm that
self-mined and used custom software would be able to exploit this.
Every other mining farm on the planet, plus any users wishing for more
transactions to be included in blocks would be in favor of this,
assuming the theory that it favors fewer transactions is correct.
That makes it less contentious than many other alternatives.  It might
even force the mining operation(s) in question to flip and support SW
in order to avoid losing face and/or appearing guilty.

As an additional plus, nearly all of the BU crowd and most BU
supporting miners would have little reason to object to Asicboost -
Based on philosophy alone, but not based on any practical
considerations.

Jared

On Wed, Apr 5, 2017 at 8:23 PM, David Vorick via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> I have a practical concern related to the amount of activation energy
> required to get something like this through. We are talking about
> implementing something that would remove tens to hundreds of millions of
> dollars of mining revenue for miners who have already gambled that this
> income would be available to them.
>
> That's not something they are going to let go of without a fight, and we've
> already seen this with the segwit resistance. Further, my understanding is
> that this makes a UASF a lot more difficult. Mining hardware that has unique
> optimizations on one chain only can resist a UASF beyond a simple economic
> majority, because they can do more hashes on the same amount of revenue.
> Threshold for success is no longer 51%, especially if you are expecting the
> miners to struggle (and this is a case where they have a very good reason to
> struggle). Any resistance from the hashrate during the early days of a UASF
> will inevitably cause large reorgs for older nodes, and is not much better
> than a hardfork.
>
> I don't know what the right answer is. But I know that we are not going to
> get segwit without a fight. We are not going to invalidate covert asicboost
> without a fight. And we are working with a system that actively (and is
> demonstrably very effective at doing it) resists changes which are
> contentious. This is definitely a contentious change, because an important
> part of the community (the miners) is going to be actively resisting it.
>
> I urge everybody to realize how difficult something like this is going to be
> to pull off. We are literally talking about invalidating hardware (or at
> least the optimized bits). It's only going to succeed if everybody is
> conclusively on board. As you consider proposals, realize that anything
> which is not the simplest and least contentious is already dead.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Alex Mizrahi]

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

> Ethically, this situation has some similarities to the DAO fork.


Much better analogy:

1. An ISV make software which makes use of an undocumented OS feature.
2. That feature is no longer present in the next OS release.
3. ISV suffers losses because its software cannot work under new OS, and
thus people stop buying it.

I think 99% of programmers would agree that this loss was inflicted by a
bad decision of ISV, and not by OS vendor changing OS internals. Relying on
undocumented features is something you do on your own risk.

I think it is ethically unambiguous to everyone who isn't on Bitmain's
payroll.

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Alex Mizrahi]

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

> Ethically, this situation has some similarities to the DAO fork.


There are no similarities.

The DAO fork was against the principles of cryptocurrencies: a change of
the ledger done in violation of pre-agreed rules. The whole point of
cryptocurrency is to avoid shit like that. (E.g. a central banker changing
ledger as he wants.)

Greg's proposal is in line with the principles of cryptocurrencies:
PoW-based cryptocurrency can work only if there is a competition between
miners, which requires all miners to have equal access to the technology.

The notion that Bitmain is entitled to future profits is completely
ridiculous. Every investment has a risk, and doing unusual stuff which
boosts your profits is associated with increased risk. Developers just need
to make sure all miners are on equal grounds, as that's the whole point of
the protocol. If Bitmain loses their profits because of that it's really
just Bitmain's problem.

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Marco]

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

On 04/06/2017 03:24 AM, Jonathan Toomim via bitcoin-dev wrote:
> Ethically, this situation has some similarities to the DAO fork. We have an entity who closely examined the code, found an unintended characteristic of that code, and made use of that characteristic in order to gain tens of millions of dollars. Now that developers are aware of it, they want to modify the code in order to negate as much of the gains as possible.
>
> There are differences, too, of course: the DAO attacker was explicitly malicious and stole Ether from others, whereas Bitmain is just optimizing their hardware better than anyone else and better than some of us think they should be allowed to.
>
> In both cases, developers are proposing that the developers and a majority of users collude to reduce the wealth of a single entity by altering the blockchain rules.
>
> In the case of the DAO fork, users were stealing back stolen funds, but that justification doesn't apply in this case. On the other hand, in this case we're talking about causing someone a loss by reducing the value of hardware investments rather than forcibly taking back their coins, which is less direct and maybe more justifiable.
>
> While I don't like patented mining algorithms, I also don't like the idea of playing Calvin Ball on the blockchain. Rule changes should not be employed as a means of disempowering and empoverishing particular entities without very good reason. Whether patenting a mining optimization qualifies as good reason is questionable.
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Quite different in that the DAO fork was about an application level bug
and this current proposal is about a possibly dangerous incentive at
protocol level.
In the first, a protocol change was called to recover funds lost for an
application level bug. In the latter, a protocol change is being called
to address a perceived incentive problem in the protocol.

A good comparison would be if a protocol level change was being proposed
for a case like mt gox. But it's not.

Plus... This proposal only addresses one covert asicboost and not other
overt forms.
Even though we may, as well, have good reasons to block other overt forms.

Marco Agner
https://www.agner.io


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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Andreas Schildbach]

On 04/05/2017 11:37 PM, Gregory Maxwell via bitcoin-dev wrote:

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

Do you plan to release details about this, or is it already documented
somewhere?

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Daniel Robinson]

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

I think you're misreading Luv. He's defending the idea of blocking covert
ASICBOOST, not defending ASICBOOST.

On Thu, Apr 6, 2017 at 11:16 AM Jorge Timón via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Thu, Apr 6, 2017 at 2:30 PM, Luv Khemani via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > Just to add on to the ethical issue of blocking this.
> >
> >
> > If blocking the covert form of ASICBOOST is seen as unethical, then the
> same can be said about libsecp256k1, various client optimisations,
> Compactblocks.
>
> This is simply a non sequitur. These optimizations benefit users. On
> the other hand, asicboost doesn't benefit users in any way, it only
> benefits some miners if and only if not all miners use it. It
> obviously harms the miners that aren't using it by making them less
> profitable (maybe to the point that they lose money).
> If all miners use it or if no one of them uses it is equivalent from
> the point of view of the user. In fact, the very fact of allowing it
> makes the network less secure unless every single honest miner uses
> it, for an attacker could use it against the network.
>
> Even if asicboost was good for users in any way (which as explained
> isn't), this proposal doesn't disable it, only the covert form that
> cannot be proven to be used.
>
> Therefore there's no rational arguments to oppose this proposal unless
> you are (or are invested in):
>
> A) A Miner currently using the covert form of asicboost.
>
> B) A Miner planning to use the covert form of asicboost soon.
>
> C) An attacker using or planning to use the covert form of asicboost.
>
> > All of which seek to reduce the efficacy of large miners and selfish
> mining.
>
> Asicboost doesn't seek this and doesn't help with this in any way.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Alex Mizrahi]

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

> Agreed! There's no benefit to Bitcoin for having it - one way or the other
> miners are going to destroy ~12BTC/block worth of energy. Meanwhile it
> appears
> to have lead to something like a year of stupid political bullshit based
> on a
> secret advantage - there's no reason to invite a repeat of this episode.


But is it even possible to completely remove ASICBOOST optimization
possibility?

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jorge Timón]

On Thu, Apr 6, 2017 at 2:30 PM, Luv Khemani via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Just to add on to the ethical issue of blocking this.
>
>
> If blocking the covert form of ASICBOOST is seen as unethical, then the same can be said about libsecp256k1, various client optimisations, Compactblocks.

This is simply a non sequitur. These optimizations benefit users. On
the other hand, asicboost doesn't benefit users in any way, it only
benefits some miners if and only if not all miners use it. It
obviously harms the miners that aren't using it by making them less
profitable (maybe to the point that they lose money).
If all miners use it or if no one of them uses it is equivalent from
the point of view of the user. In fact, the very fact of allowing it
makes the network less secure unless every single honest miner uses
it, for an attacker could use it against the network.

Even if asicboost was good for users in any way (which as explained
isn't), this proposal doesn't disable it, only the covert form that
cannot be proven to be used.

Therefore there's no rational arguments to oppose this proposal unless
you are (or are invested in):

A) A Miner currently using the covert form of asicboost.

B) A Miner planning to use the covert form of asicboost soon.

C) An attacker using or planning to use the covert form of asicboost.

> All of which seek to reduce the efficacy of large miners and selfish mining.

Asicboost doesn't seek this and doesn't help with this in any way.

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Russell O'Connor]

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

Hi Jonathan,

The proposal raised here does not deny miners the ability to use ASICBOOST.
Miners can still use overt ASICBOOST by version bit fiddling and get the
same power savings.  In fact, overt ASICBOOST is much easier to implement
than covert ASICBOOST, so I don't really understand what the objection is.


On Apr 6, 2017 13:44, "Jonathan Toomim via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

Ethically, this situation has some similarities to the DAO fork. We have an
entity who closely examined the code, found an unintended characteristic of
that code, and made use of that characteristic in order to gain tens of
millions of dollars. Now that developers are aware of it, they want to
modify the code in order to negate as much of the gains as possible.

There are differences, too, of course: the DAO attacker was explicitly
malicious and stole Ether from others, whereas Bitmain is just optimizing
their hardware better than anyone else and better than some of us think
they should be allowed to.

In both cases, developers are proposing that the developers and a majority
of users collude to reduce the wealth of a single entity by altering the
blockchain rules.

In the case of the DAO fork, users were stealing back stolen funds, but
that justification doesn't apply in this case. On the other hand, in this
case we're talking about causing someone a loss by reducing the value of
hardware investments rather than forcibly taking back their coins, which is
less direct and maybe more justifiable.

While I don't like patented mining algorithms, I also don't like the idea
of playing Calvin Ball on the blockchain. Rule changes should not be
employed as a means of disempowering and empoverishing particular entities
without very good reason. Whether patenting a mining optimization qualifies
as good reason is questionable.

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Luv Khemani]

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

Just to add on to the ethical issue of blocking this.


If blocking the covert form of ASICBOOST is seen as unethical, then the same can be said about libsecp256k1, various client optimisations, Compactblocks.

All of which seek to reduce the efficacy of large miners and selfish mining.


I also find it very ironic that the author of the Selfish Mining paper who rang alarm bells about miner centralisation in 2013 is now opposing attempts to reduce miner centralisation.


________________________________
From: bitcoin-dev-bounces@lists.linuxfoundation.org <bitcoin-dev-bounces@lists.linuxfoundation.org> on behalf of Luv Khemani via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Sent: Thursday, April 6, 2017 8:02 PM
To: Gregory Maxwell; Bitcoin Protocol Discussion
Subject: Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function


Hi Greg


Great work in discovering this!


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


Could you elaborate on why you consider ASICBOOST to be an attack? Attack here implies ill-intent by the practitioner towards the network as a primary motivating factor.

Personally, i see this as a miner acting in his self-interest and had i been a miner and knew about the covert method, i would use it too.

So while i'm no fan of Bitmain/Jihan, i do not condone the vilification he has received over the use of ASICBOOST to gain an edge.

I know i'm griping over semantics, but in the current political climate, they can be amplified by some to cause more drama than is healthy.


Other thoughts:


Several people have commented that blocking the use of this covert technique is unethical or "wrong".
To quote Emin:

>Taking action to block this is similar to the government taking measures to block Elon Musk's more efficient electric cars. Specifically prosecuting a chosen miner, in the current political climate, would send a terrible message of absolute centralization in the hands of one particular developer group, and it would severely damage Bitcoin mining and the coin's security.

This is a poor analogy and extremely misleading as the the basis for blocking has nothing to do with efficiency and more to do with the following:

1) Blocking upgrades to the protocol that are deemed by the vast majority of the technical community/Bitcoin Businesses as being the best way forward

2) An advantage by a miner/group, especially one with majority hashrate is a threat to decentralisation and security of the network and it is entirely justifiable for devs to nullify such an advantage.
You can see it as an arms race where miners are always finding ways to gain an edge and devs trying to discover such edges and nullify them to level the playing field.
This is how the game works and it should not be viewed in a political angle or taken personally by either party. Miners are acting in their self-interest and Devs are trying to secure the network and increase decentralisation.
Both are doing their job.

Just by revealing the info, you have effectively ensured the nullification of any edge enjoyed by miners using the covert technique in the medium to long term.
Either miners not using the technique will all start signalling for SegWit to nullify their competitors edge or they will procure hardware which has the edge.

Given the threat to decentralisation, i also believe UASF will gain more momentum as users seek to protect the network from further miner centralisation.


________________________________
From: bitcoin-dev-bounces@lists.linuxfoundation.org <bitcoin-dev-bounces@lists.linuxfoundation.org> on behalf of Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Sent: Thursday, April 6, 2017 5:37 AM
To: Bitcoin Dev
Subject: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

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
bitcoin-dev -- Bitcoin Protocol Discussion - Linux Foundation<https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
lists.linuxfoundation.org
Bitcoin development and protocol discussion. This list is lightly moderated. - No offensive posts, no personal attacks. - Posts must concern development of bitcoin ...




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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[David Vorick]

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

>
> Another thing that could be done is increase the number of times SHA256 is
> performed... but now we are really talking about altering the PoW
> algorithm.  Correct me if I'm wrong: The more number of times its
> performed, the less any patent-able pre or post calculation
> skipping/caching have an effect on efficiency.
>

The more complex that the PoW algorithm is, the more likely it is that
someone finds a unique and special method for optimizing it that they are
able to patent. And the more difficult it is to create specialized hardware
to run that algorithm, meaning that there will be fewer players who are
able to do so profitably (higher fixed costs).

If you want to talk about changing the PoW algorithm, you really want to be
looking to simplify it so that it's more obvious (not that you can ever be
completely sure) that there are no hidden or unexpected optimizations that
someone could patent.

We can even do a lot better than SHA. Cryptographic hash functions need to
be collision resistant, and collision resistance is the property that
usually breaks. Preimage resistance and partial preimage resistance (and
second preimage resistance) is generally easier to protect - to the best of
our knowledge, md5 would actually still be a secure PoW function today.

It's bitterly ironic to me that so much research and effort has been put
into making asic-resistant PoW algorithms when in the long run
asic-resistance only leads to problems like these - single parties who have
found significant optimizations and not shared them, completely destroying
any chance of a level playing field and giving themselves a centralized
monopoly - a result that is supremely unhealthy for the rest of the
community.

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Bryan Bishop]

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

On Thu, Apr 6, 2017 at 7:02 AM, Luv Khemani via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Could you elaborate on why you consider ASICBOOST to be an attack? Attack
> here implies ill-intent by the practitioner towards the network as a
> primary motivating factor.
>
>
See
https://www.reddit.com/r/Bitcoin/comments/63otrp/gregory_maxwell_major_asic_manufacturer_is/dfwcki3/

"""
I think that it is an attack is a completely unambiguous technical
description of what it is. If a signature is supposed to resist forgery
against 2^128 operations, but you find a way to do it with 2^80 instead,
this is an attack. It is, perhaps, not a very concerning attack and you may
or may not change your signature scheme to avoid it or may just instead say
the scheme has 2^80 security. But there is no doubt that it would be called
an attack, especially if it was not described in the original proposal.

In Bitcoin's Proof of Work, you are attempting to prove a certain amount of
work has been done. This shortcut significantly reduces the amount of work.
It's an attack. Normally it wouldn't be a serious attack-- it would just
get appended to the defacto definition of what the Bitcoin Proof of work
is-- similar to the signature system just getting restarted as having 2^80
security-- but in it's covert form it cannot just be adopted because it
blocks many further improvements (not just segwit, but the vast majority of
other proposals), and additional the licensing restrictions inhibit
adoption.

The proposal I posted does not prevent the technique, only the covert form:
That is, it doesn't even attempt to solve the patented tech eventually will
centralize the system problem. It is narrowly targeted at the interference
with upgrades.

Taking a step back-- even ignoring my geeking out about the technical
definition of 'attack' in crypographic contexts, we have a set of issues
here that left addressed will seriously harm the system going forward for
the the significant monetary benefit of an exploiting party. I think that
also satisfies a lay definition of the term: Something someone does, that
none one expected, that makes them money at everyone elses expense.
"""

- Bryan
http://heybryan.org/
1 512 203 0507

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[David Vorick]

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

On Thu, Apr 6, 2017 at 2:24 AM, Jonathan Toomim via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Ethically, this situation has some similarities to the DAO fork. We have
> an entity who closely examined the code, found an unintended characteristic
> of that code, and made use of that characteristic in order to gain tens of
> millions of dollars. Now that developers are aware of it, they want to
> modify the code in order to negate as much of the gains as possible.
>
> There are differences, too, of course: the DAO attacker was explicitly
> malicious and stole Ether from others, whereas Bitmain is just optimizing
> their hardware better than anyone else and better than some of us think
> they should be allowed to.
>
> In both cases, developers are proposing that the developers and a majority
> of users collude to reduce the wealth of a single entity by altering the
> blockchain rules.
>
> In the case of the DAO fork, users were stealing back stolen funds, but
> that justification doesn't apply in this case. On the other hand, in this
> case we're talking about causing someone a loss by reducing the value of
> hardware investments rather than forcibly taking back their coins, which is
> less direct and maybe more justifiable.
>
> While I don't like patented mining algorithms, I also don't like the idea
> of playing Calvin Ball on the blockchain. Rule changes should not be
> employed as a means of disempowering and empoverishing particular entities
> without very good reason. Whether patenting a mining optimization qualifies
> as good reason is questionable.
>

Bitmain is blocking protocol upgrades to preserve their mining advantage.
This is quite distinct from someone taking advantage of a visibly broken
and highly toxic smart contract to net themselves tens of millions of
dollars. Further, Bitmain is performing a patented hardware optimization.
The patents mean that other miners are unable to capitalize on these
optimizations. These optimizations are to the tune of 30%. If you give one
player in the mining industry a permanent 30% cost advantage they will
eventually own everything. It's an industry where margins tend towards zero.

The asicboost patent is a direct threat to the health of the Bitcoin
ecosystem, and now we have visible proof. The war against segwit and the
strife with Bitcoin Unlimited was very damaging to the ecosystem, damaging
to the price, and holding back significant improvements and upgrades to the
Bitcoin protocol. I interpret this as a direct attack on the Bitcoin
ecosystem.

I don't know if changing the rules to nullify asicboost is the right move.
I'm sure this won't be the last patent that causes damage to the ecosystem.
But you need to recognize that the issue is not that Bitmain ran a hardware
optimization. It's that hardware optimizations exist which directly inhibit
upgrading the protocol. And it's that hardware optimizations exist
encumbered by patents enough to give one party a decisive advantage in
mining, decisive enough for them to build a single, centralized monopoly.

Each problem is separate, and each problem is significant, and each problem
is fundamental. The DAO attack was a one-time bout of stupidity that
threatened a fixed amount of money. asicboost is an ongoing status that
directly damages Bitcoin's ability to upgrade, and directly damage
Bitcoin's ability to retain any modicum of decentralization in the
hashrate. The DAO issue did neither of these things for ethereum.

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Luv Khemani]

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

Hi Greg


Great work in discovering this!


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


Could you elaborate on why you consider ASICBOOST to be an attack? Attack here implies ill-intent by the practitioner towards the network as a primary motivating factor.

Personally, i see this as a miner acting in his self-interest and had i been a miner and knew about the covert method, i would use it too.

So while i'm no fan of Bitmain/Jihan, i do not condone the vilification he has received over the use of ASICBOOST to gain an edge.

I know i'm griping over semantics, but in the current political climate, they can be amplified by some to cause more drama than is healthy.


Other thoughts:


Several people have commented that blocking the use of this covert technique is unethical or "wrong".
To quote Emin:

>Taking action to block this is similar to the government taking measures to block Elon Musk's more efficient electric cars. Specifically prosecuting a chosen miner, in the current political climate, would send a terrible message of absolute centralization in the hands of one particular developer group, and it would severely damage Bitcoin mining and the coin's security.

This is a poor analogy and extremely misleading as the the basis for blocking has nothing to do with efficiency and more to do with the following:

1) Blocking upgrades to the protocol that are deemed by the vast majority of the technical community/Bitcoin Businesses as being the best way forward

2) An advantage by a miner/group, especially one with majority hashrate is a threat to decentralisation and security of the network and it is entirely justifiable for devs to nullify such an advantage.
You can see it as an arms race where miners are always finding ways to gain an edge and devs trying to discover such edges and nullify them to level the playing field.
This is how the game works and it should not be viewed in a political angle or taken personally by either party. Miners are acting in their self-interest and Devs are trying to secure the network and increase decentralisation.
Both are doing their job.

Just by revealing the info, you have effectively ensured the nullification of any edge enjoyed by miners using the covert technique in the medium to long term.
Either miners not using the technique will all start signalling for SegWit to nullify their competitors edge or they will procure hardware which has the edge.

Given the threat to decentralisation, i also believe UASF will gain more momentum as users seek to protect the network from further miner centralisation.


________________________________
From: bitcoin-dev-bounces@lists.linuxfoundation.org <bitcoin-dev-bounces@lists.linuxfoundation.org> on behalf of Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Sent: Thursday, April 6, 2017 5:37 AM
To: Bitcoin Dev
Subject: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

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
bitcoin-dev -- Bitcoin Protocol Discussion - Linux Foundation<https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
lists.linuxfoundation.org
Bitcoin development and protocol discussion. This list is lightly moderated. - No offensive posts, no personal attacks. - Posts must concern development of bitcoin ...




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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Luke Dashjr]

On Wednesday, April 05, 2017 9:37:45 PM Gregory Maxwell via bitcoin-dev wrote:
> 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.

Why not simply require the BIP-141 commitment?

> Existing segwit using miners are automatically compatible with
> this proposal.

Not entirely. The commitment is not required until segwit activates.
But this should be trivial to implement at least.

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

How does it not interfere with BIP 9? I suppose the versionbits could be moved 
to the generation transaction version, but this would hide them from light 
clients.

> This document is placed in the public domain.

Could you please use one of these?

    https://github.com/bitcoin/bips/blob/master/bip-0002.mediawiki#Recommended_licenses

Luke

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[praxeology_guy]

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

If this is the underlying reason why SegWit is being delayed... that is pretty deplorable.

Probably too late now for bitcoin, but maybe it would be good to pre-mix the block header bits around before it even enters the SHA256 hash. Not sure if best to use a hardcoded map, or to make the map with the tx merkle root as a seed. Depends on how hard it is to find good nonce (etc) bit location collisions.

Maybe gmaxwell's solution is good enough for this particular problem... but the above recommendation might help improve bitcoin's available remaining puzzle difficulty.

Another thing that could be done is increase the number of times SHA256 is performed... but now we are really talking about altering the PoW algorithm. Correct me if I'm wrong: The more number of times its performed, the less any patent-able pre or post calculation skipping/caching have an effect on efficiency.

Cheers,
Praxeology Guy

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[bfd]

Miners blocking SegWit due to ASICBOOST requirements also means they 
would block future deployment of committed bloom filters.

On 2017-04-06 00:37, Gregory Maxwell via bitcoin-dev 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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jonathan Toomim]

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

Ethically, this situation has some similarities to the DAO fork. We have an entity who closely examined the code, found an unintended characteristic of that code, and made use of that characteristic in order to gain tens of millions of dollars. Now that developers are aware of it, they want to modify the code in order to negate as much of the gains as possible.

There are differences, too, of course: the DAO attacker was explicitly malicious and stole Ether from others, whereas Bitmain is just optimizing their hardware better than anyone else and better than some of us think they should be allowed to.

In both cases, developers are proposing that the developers and a majority of users collude to reduce the wealth of a single entity by altering the blockchain rules.

In the case of the DAO fork, users were stealing back stolen funds, but that justification doesn't apply in this case. On the other hand, in this case we're talking about causing someone a loss by reducing the value of hardware investments rather than forcibly taking back their coins, which is less direct and maybe more justifiable.

While I don't like patented mining algorithms, I also don't like the idea of playing Calvin Ball on the blockchain. Rule changes should not be employed as a means of disempowering and empoverishing particular entities without very good reason. Whether patenting a mining optimization qualifies as good reason is questionable.

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 496 bytes --]

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Thomas Daede]

On 04/05/2017 08:23 PM, David Vorick via bitcoin-dev wrote:
> I have a practical concern related to the amount of activation energy
> required to get something like this through. We are talking about
> implementing something that would remove tens to hundreds of millions of
> dollars of mining revenue for miners who have already gambled that this
> income would be available to them.

The proposed BIP only removes covert ASICBOOST. As long as the ASICs can
also do the non-covert ASICBOOST, it shouldn't have any impact on miner
revenue.

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Raystonn .]

[-- 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 --]

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Oliver Petruzel]

[-- 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 --]

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Peter Todd]

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

On Wed, Apr 05, 2017 at 11:23:22PM -0400, David Vorick wrote:
> I urge everybody to realize how difficult something like this is going to
> be to pull off. We are literally talking about invalidating hardware (or at
> least the optimized bits). It's only going to succeed if everybody is
> conclusively on board. As you consider proposals, realize that anything
> which is not the simplest and least contentious is already dead.

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.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Peter Todd]

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

On Wed, Apr 05, 2017 at 11:11:53PM -0400, Erik Aronesty wrote:
> If the primary purpose of pow is to destroy value, then a masked proof of
> burn to an expanded address that assigns the private key holder the right

You're talking about proof-of-stake here.

At best it's very difficult for such a "proof-of-burn" to _actually_ be a
proof, as the burn only happens if the consensus mechanism ultimately includes
that burn. Contrast that to proof-of-work's incredibly simple proof: you _know_
energy was destroyed to find a PoW solution, regardless of what consensus is
ultimately reached.

It's the difference between a computer secured from hackers with an anti-virus
scanner, and a computer secured by the fact that it's not connected to the
internet at all.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[David Vorick]

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

I have a practical concern related to the amount of activation energy
required to get something like this through. We are talking about
implementing something that would remove tens to hundreds of millions of
dollars of mining revenue for miners who have already gambled that this
income would be available to them.

That's not something they are going to let go of without a fight, and we've
already seen this with the segwit resistance. Further, my understanding is
that this makes a UASF a lot more difficult. Mining hardware that has
unique optimizations on one chain only can resist a UASF beyond a simple
economic majority, because they can do more hashes on the same amount of
revenue. Threshold for success is no longer 51%, especially if you are
expecting the miners to struggle (and this is a case where they have a very
good reason to struggle). Any resistance from the hashrate during the early
days of a UASF will inevitably cause large reorgs for older nodes, and is
not much better than a hardfork.

I don't know what the right answer is. But I know that we are not going to
get segwit without a fight. We are not going to invalidate covert asicboost
without a fight. And we are working with a system that actively (and is
demonstrably very effective at doing it) resists changes which are
contentious. This is definitely a contentious change, because an important
part of the community (the miners) is going to be actively resisting it.

I urge everybody to realize how difficult something like this is going to
be to pull off. We are literally talking about invalidating hardware (or at
least the optimized bits). It's only going to succeed if everybody is
conclusively on board. As you consider proposals, realize that anything
which is not the simplest and least contentious is already dead.

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Erik Aronesty]

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

If the primary purpose of pow is to destroy value, then a masked proof of
burn to an expanded address that assigns the private key holder the right
to mine only in the next Nth block would be sufficient.  Expanding the
address space so that addresses can only be proven invalid only with the
private key.  Miners can then not trivially game the system by excluding
tx...without killing the entire system.  ( Like POW ... miners lose many
burns since only one valid proof is deterministically selected. Difficult
adjusted upward based on the number of valid proofs per block.)

The other part of "real POW" is that miners take *time* to mine.  Proof of
destroyed value us not sufficient.  Proof of time spent is critical....
something even a masked burn cannot provide.

On Apr 5, 2017 10:49 PM, "Peter Todd via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Wed, Apr 05, 2017 at 07:39:08PM -0700, Bram Cohen wrote:
> > On Wed, Apr 5, 2017 at 7:31 PM, Peter Todd via bitcoin-dev <
> > > While I'm in favour of blocking covert usage of ASICBOOST, there's
> every
> > > reason
> > > to block non-covert usage of it as well. In a low margin business like
> > > mining,
> > > the advatange it gives is enormous - quite possibly 10x your profit
> margin
> > > -
> > > and given that barrier free access to being able to purchase ASICs is
> > > already
> > > an archilles heal for Bitcoin there is every reason to eliminate this
> legal
> > > vulnerability. Additionally, it's a technical vulnerability as well: we
> > > want
> > > getting into the ASIC manufacturing and design business to have as low
> > > barriers
> > > to entry as is feasible, and the ASICBOOST exploit significantly
> increases
> > > the
> > > minimum capital requirements to do so.
> > >
> >
> > Asicboost also has the problem that it isn't treating the hashing as a
> > black box, and thus has impacts on what gets mined. In particular it
> > creates an incentive to make blocks smaller. That's a very unwanted
> effect,
> > and anything like it should be engineered out on principle.
>
> Agreed! There's no benefit to Bitcoin for having it - one way or the other
> miners are going to destroy ~12BTC/block worth of energy. Meanwhile it
> appears
> to have lead to something like a year of stupid political bullshit based
> on a
> secret advantage - there's no reason to invite a repeat of this episode.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Peter Todd]

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

On Wed, Apr 05, 2017 at 07:39:08PM -0700, Bram Cohen wrote:
> On Wed, Apr 5, 2017 at 7:31 PM, Peter Todd via bitcoin-dev <
> > While I'm in favour of blocking covert usage of ASICBOOST, there's every
> > reason
> > to block non-covert usage of it as well. In a low margin business like
> > mining,
> > the advatange it gives is enormous - quite possibly 10x your profit margin
> > -
> > and given that barrier free access to being able to purchase ASICs is
> > already
> > an archilles heal for Bitcoin there is every reason to eliminate this legal
> > vulnerability. Additionally, it's a technical vulnerability as well: we
> > want
> > getting into the ASIC manufacturing and design business to have as low
> > barriers
> > to entry as is feasible, and the ASICBOOST exploit significantly increases
> > the
> > minimum capital requirements to do so.
> >
> 
> Asicboost also has the problem that it isn't treating the hashing as a
> black box, and thus has impacts on what gets mined. In particular it
> creates an incentive to make blocks smaller. That's a very unwanted effect,
> and anything like it should be engineered out on principle.

Agreed! There's no benefit to Bitcoin for having it - one way or the other
miners are going to destroy ~12BTC/block worth of energy. Meanwhile it appears
to have lead to something like a year of stupid political bullshit based on a
secret advantage - there's no reason to invite a repeat of this episode.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Bram Cohen]

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

On Wed, Apr 5, 2017 at 7:31 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> While I'm in favour of blocking covert usage of ASICBOOST, there's every
> reason
> to block non-covert usage of it as well. In a low margin business like
> mining,
> the advatange it gives is enormous - quite possibly 10x your profit margin
> -
> and given that barrier free access to being able to purchase ASICs is
> already
> an archilles heal for Bitcoin there is every reason to eliminate this legal
> vulnerability. Additionally, it's a technical vulnerability as well: we
> want
> getting into the ASIC manufacturing and design business to have as low
> barriers
> to entry as is feasible, and the ASICBOOST exploit significantly increases
> the
> minimum capital requirements to do so.
>

Asicboost also has the problem that it isn't treating the hashing as a
black box, and thus has impacts on what gets mined. In particular it
creates an incentive to make blocks smaller. That's a very unwanted effect,
and anything like it should be engineered out on principle.

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Peter Todd]

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

On Wed, Apr 05, 2017 at 09:37:45PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> 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.

While I'm in favour of blocking covert usage of ASICBOOST, there's every reason
to block non-covert usage of it as well. In a low margin business like mining,
the advatange it gives is enormous - quite possibly 10x your profit margin -
and given that barrier free access to being able to purchase ASICs is already
an archilles heal for Bitcoin there is every reason to eliminate this legal
vulnerability. Additionally, it's a technical vulnerability as well: we want
getting into the ASIC manufacturing and design business to have as low barriers
to entry as is feasible, and the ASICBOOST exploit significantly increases the
minimum capital requirements to do so.

Remember that the whole purpose of PoW is to destroy value on a level playing
field. Anything that inhibits a level playing field is an exploit. While this
isn't standard crypto - we can't fix every exploit completely - since we're
going to do a technical change to partially mitigate the ASCIBOOST exploit
there is every reason to fully mitigate it.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

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

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Jonathan Toomim]

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

Just checking to see if I understand this optimization correctly. In order to find merkle roots in which the rightmost 32 bits are identical (i.e. partial hash collisions), we want to compute as many merkle root hashes as quickly as possible. The fastest way to do this is to take the top level of the Merkle tree, and to collect a set of left branches and right branches which can be independently manipulated. While the left branch can easily be manipulated by changing the extranonce in the coinbase transaction, the right branch would need to be modified by changing one of the transactions in the right branch or by changing the number of transactions in the right branch. Correct so far?

With the stratum mining protocol, the server (the pool) includes enough information for the coinbase transaction to be modified by stratum client (the miner), but it does not include any information about the right side of the merkle tree except for the top-level hash. Stratum also does not allow the client to supply any modifications to the merkle tree (including the right side) back to the stratum server. This means that any implementation of this final optimization would need to be using a protocol other than stratum, like getblocktemplate, correct?

I think it would be helpful for the discussion to know if this optimization were currently being used or not, and if so, how widely.

All of the consumer-grade hardware that I have seen defaults to stratum-only operation, and I have not seen or heard of any hardware available that can run more efficiently using getblocktemplate. As the current pool infrastructure uses stratum exclusively, this optimization would require significant retooling among pools, and probably a redesign of their core algorithms to help discover and share these partial collisions more frequently. It's possible that some large private farms have deployed a special system for solo mining that uses this optimization, of course, but it's also possible that there's a teapot in space somewhere between the orbit of Earth and Mars.

Do you know of any ways to perform this optimization via stratum? If not, do you have any evidence that this optimization is actually being used by private solo mining farms? Or is this discussion purely about preventing this optimization from being used in the future?

-jtoomim

> On Apr 5, 2017, at 2:37 PM, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> 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.


[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 496 bytes --]

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Joseph Poon]

On Thu, Apr 06, 2017 at 01:32:03AM +0000, Gregory Maxwell wrote:
> On Thu, Apr 6, 2017 at 12:39 AM, Joseph Poon <joseph@lightning.network> wrote:
> > #bitcoin@freenode:
> >  00:04    gmaxwell| lol poon pretending that he isn't complicit in all this stuff.
> >
> > Are you *fucking* serious? Is this how you resolve all problems? I'm
> > taking you seriously and having second thoughts and want to make public
> > commitments to do the right thing without any evidence and you come out
> > and say *this*?

Apologies to the list.

> I apologize for the glib talk on chat and I hope you understand that
> the tone in such venues is significantly informal; and that my remark
> was a causal one among friends which was not intended in a spirit as
> seriously as you've taken it.

You're still presuming ill-will. I'm seriously offended. I'm not upset
with the glib talk, I'm upset that you think I have ill will.

> That said, two days ago you participated in a highly unusual
> announcement of a protocol change that-- rather than being sent for
> community review in any plausible venue for that purpose-- was
> announced as a done deal in embargoed media announcements.  This
> proposed protocol change seemed custom tailored to preserve covert
> boosting, and incorporated direct support for lightning -- and the
> leading competing theory was that a large miner opposed segwit
> specifically because they wanted to block lightning. Moreover, I have
> heard reports I consider reliable that this work was funded by the
> miner in question.

We specifically told you guys privately and publicly when asked that it
was simply to be able to do it in 2 weeks. Check out the code, it was
much faster to do it that way. The spec wasn't complete and I have
personal biases against doing it on the main-chain since it would
benefit things if there was smart contract proections on the main chain
as well, which I figured would be more controversial. I never said
anything about public commitments to transactions. In fact, I'm pretty
good at figuring things out and tend to cargo-cult things (since culture
is the genetic memory is civlizations), if I saw BIP141/SegWit required
a commitment instead of it being optional, I would've probably thought
about it. Why wasn't this required as part of SegWit? BIP141 is still
vulnerable. Why did you pull this out just now? I'm totally blindsided
here, hence my earlier reply of wanting to resolve it in the Extension
Block proposal.

> In the time since, when people asked for revisions to the proposal to
> not block segwit they received responses from the Bcoin account on
> twitter that "there would be no amendments", and I was sent leaked
> chatlogs of you making considerably hostile statements, claiming that
> if your extension block proposal is "a litmus test for corruption",
> and claimed (before AFAIK anyone had had a chance to comment on it)
> that the Bitcoin project contributors opposed it for "nonsense
> reasons".

I never participated in that, and the specific announcement here
indicates that changes will be happening. The intention was to get it
out as a draft and *working* demo code.

https://medium.com/purse-essays/ready-for-liftoff-a5533f4de0b6

That was specifically after Core developers accused me of publicly
acting in poor form without any understanding of the situation. I was
especially annoyed because all of you are acting with similar secrecy,
even worse, there is specific organization by Core which the public is
not aware of. Think about it from my perspective, you all blocked me out
intentionally for months and then accuse me of going to journalists for
a couple hours before? I'm seriously hurt.

> It is with this in mind that when you tried to pull me into an off the
> record conversation that I responded stating:
> 
> "[...] I am disinclined to communicate with you except in email where I can
> get third party transferable proof of our communication.  I'm
> concerned that you may now be involved in a conspiracy which I do not
> want to be implicated in myself.
> 
> It is my estimation that, for that above reason, it would be in my
> best interest to not communicate with you at all.  But in all your
> prior interactions you appeared to have integrity and sense, so out of
> respect for that history I'm willing to communicate with you, but only
> in public or in email where my end is on gmail."

Nice you cut out the beginning which explains on *why* I didn't reply:

"with an embargoed press release in Forbes.

That's how you roll now, right? :-/"

Why didn't you include your entire message?

That was in reply to my initial message reaching out to you and Adam
Back:
"Hi, would you like a phone call tomorrow?

I am in Thailand right now, I understand if what I did is upsetting, my
goal was not to upset you.

I deeply respect you both technically, but I do believe what I am doing
is right. If you could find a way, I would be extremely grateful if we
could chat sometime."

Replying with a beginning like that with that kind of hostility means I
sort of don't know how to reply! Further, you didn't express any real
concerns to me. I just figured you were mad and wanted to give you time
to cool off. Calling someone up is a way to explain over a higher
bandwidth medium gives material reiteration of a real honest heartfelt
apology in misunderstanding.

> This was two days ago and you did not respond further.
> 
> With that in mind I hope you do not find some casual crap-talking on
> chat to be especially surprising.
> 
> I understand that you didn't intend for the initial message to be
> posted in public, so I'm sorry for continuing the thread here-- but I
> thought it was useful for people to understand the context behind that
> glib remark: Including the point that I do not know for a fact that
> you are complicit in anything, but I consider your recent actions to
> be highly concerning.

I'm only including more details in the email because you had deceptive
framing. I normally would *never* include contents in a private email
message and believe this is already the gray area. I already feel
uncomfortable publishing my message to you without permission, but I
feel it's necessary context, but I will not continue. Would you like to
have a public call instead? I really want to talk to you to express that
I really mean what's best for bitcoin. I've had a sleepless night
thinking about these things, this type of drama is *NOT* good for
bitcoin.

I came here with good intent, even with Core and Blockstream being
outright hostile and controlling with many personal problems over the
years which I have never aired previously. I can tell when I'm not
welcome. I'm going to take a break from all of this.

-- 
Joseph Poon

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Gregory Maxwell]

On Thu, Apr 6, 2017 at 12:39 AM, Joseph Poon <joseph@lightning.network> wrote:
> #bitcoin@freenode:
>  00:04    gmaxwell| lol poon pretending that he isn't complicit in all this stuff.
>
> Are you *fucking* serious? Is this how you resolve all problems? I'm
> taking you seriously and having second thoughts and want to make public
> commitments to do the right thing without any evidence and you come out
> and say *this*?

I apologize for the glib talk on chat and I hope you understand that
the tone in such venues is significantly informal; and that my remark
was a causal one among friends which was not intended in a spirit as
seriously as you've taken it.

That said, two days ago you participated in a highly unusual
announcement of a protocol change that-- rather than being sent for
community review in any plausible venue for that purpose-- was
announced as a done deal in embargoed media announcements.  This
proposed protocol change seemed custom tailored to preserve covert
boosting, and incorporated direct support for lightning -- and the
leading competing theory was that a large miner opposed segwit
specifically because they wanted to block lightning. Moreover, I have
heard reports I consider reliable that this work was funded by the
miner in question.

In the time since, when people asked for revisions to the proposal to
not block segwit they received responses from the Bcoin account on
twitter that "there would be no amendments", and I was sent leaked
chatlogs of you making considerably hostile statements, claiming that
if your extension block proposal is "a litmus test for corruption",
and claimed (before AFAIK anyone had had a chance to comment on it)
that the Bitcoin project contributors opposed it for "nonsense
reasons".

It is with this in mind that when you tried to pull me into an off the
record conversation that I responded stating:

"[...] I am disinclined to communicate with you except in email where I can
get third party transferable proof of our communication.  I'm
concerned that you may now be involved in a conspiracy which I do not
want to be implicated in myself.

It is my estimation that, for that above reason, it would be in my
best interest to not communicate with you at all.  But in all your
prior interactions you appeared to have integrity and sense, so out of
respect for that history I'm willing to communicate with you, but only
in public or in email where my end is on gmail."

This was two days ago and you did not respond further.

With that in mind I hope you do not find some casual crap-talking on
chat to be especially surprising.

I understand that you didn't intend for the initial message to be
posted in public, so I'm sorry for continuing the thread here-- but I
thought it was useful for people to understand the context behind that
glib remark: Including the point that I do not know for a fact that
you are complicit in anything, but I consider your recent actions to
be highly concerning.

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Joseph Poon]

Ahh, sorry all for this public message. :(

On Wed, Apr 05, 2017 at 05:39:00PM -0700, Joseph Poon wrote:
> #bitcoin@freenode:
>  00:04    gmaxwell| lol poon pretending that he isn't complicit in all this stuff.
> 
> Are you *fucking* serious? Is this how you resolve all problems? I'm
> taking you seriously and having second thoughts and want to make public
> commitments to do the right thing without any evidence and you come out
> and say *this*?

-- 
Joseph Poon

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Joseph Poon]

#bitcoin@freenode:
 00:04    gmaxwell| lol poon pretending that he isn't complicit in all this stuff.

Are you *fucking* serious? Is this how you resolve all problems? I'm
taking you seriously and having second thoughts and want to make public
commitments to do the right thing without any evidence and you come out
and say *this*?

On Thu, Apr 06, 2017 at 12:17:17AM +0000, Gregory Maxwell via bitcoin-dev wrote:
> On Wed, Apr 5, 2017 at 11:05 PM, theymos via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > This seems to be a serious security problem.  Would it be possible to have
> > a flag-day softfork included in Bitcoin Core as soon as 0.14.1? I think that a trigger
> > 3-6 months from release should be sufficient for enough of the economy to upgrade,
> > given the severity of the issue.
> 
> Not 0.14.1 because that is in RC already and will hopefully be out in a week.
> 
> I think the speed of adoption depends a lot of the level of support
> from the community. I don't believe there are any technical hurdles to
> implementing this relatively quickly (and I specifically propose using
> the users choice of the segwit commitment or a modified form in order
> to lower the technical complexity and risk).
> 
> > BIP 141 says that the the commitment is optional if there are no SegWit transactions in
> > the block,  so will today's SegWit-ready miners always produce it even when optional
> > according to BIP 141, as required by this softfork?
> 
> This is the default behavior as of 0.13.2, but I haven't gone out to
> measure this which is why the backwards compatibility section of the
> BIP isn't written yet.
> 
> 
> While I'm posting, I've had a dozen off-list emails that presented me
> with some FAQ:
> 
> Many people asked what other protocol upgrades beyond segwit could run
> into the same incompatibility.
> 
> Many proposed improvements to Bitcoin require additional
> transaction-dependent commitment data.
> 
> Examples include:
> 
> (1) Segwit.
> (2) UTXO commitments. (non-delayed, at least)
> (3) Committed Bloom filters
> (4) Committed address indexes
> (5) STXO commitments (non-delayed).
> (6) Weak blocks
> (7) Most kinds of fraud proofs
> -- to state a few.
> 
> Unfortunately, putting *any* commitment to data dependent on the right
> hand side of the hash tree in the left hand side (e.g. coinbase) means
> a massive increase in the computation required for covert boosting,
> because it means you can't use the left+right side combinations to
> eliminate most of the hashing.
> 
> It's plausible, in fact, that this extra computation could completely
> nullify the ASICBOOST advantage-- though this depends a lot on the
> fine details of the implementation.
> 
> This proposal does not itself propose nullifying ASICBOOST entirely,
> it proposes severely handicapping the covert form of it, and
> eliminating the differential advantage for boosting miners related to
> the use of transaction-dependent commitments.
> 
> Basically there are two completely separate concerns: that boosting
> can produce a monopoly advantage which could be severely harmful to
> the ecosystem, and that the efficient implementation of _covert_
> boosting can severely harm many useful protocol improvements.   My
> proposal only addresses the second concern, by (I believe) completely
> leveling the playing field so that opposing commitments will not break
> boosting any worse, and by making covert boosting less appealing in
> general.
> 
> Use of the segwit-style commitment even in non-segwit blocks is sufficient
> because the segwit commitment commits to all  transactions  (except
> the coinbase) and not just segwit ones.
> (It was designed this way so that lite clients that needed witness
> data could work with just one tree).
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

-- 
Joseph Poon

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Gregory Maxwell]

On Wed, Apr 5, 2017 at 11:05 PM, theymos via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> This seems to be a serious security problem.  Would it be possible to have
> a flag-day softfork included in Bitcoin Core as soon as 0.14.1? I think that a trigger
> 3-6 months from release should be sufficient for enough of the economy to upgrade,
> given the severity of the issue.

Not 0.14.1 because that is in RC already and will hopefully be out in a week.

I think the speed of adoption depends a lot of the level of support
from the community. I don't believe there are any technical hurdles to
implementing this relatively quickly (and I specifically propose using
the users choice of the segwit commitment or a modified form in order
to lower the technical complexity and risk).

> BIP 141 says that the the commitment is optional if there are no SegWit transactions in
> the block,  so will today's SegWit-ready miners always produce it even when optional
> according to BIP 141, as required by this softfork?

This is the default behavior as of 0.13.2, but I haven't gone out to
measure this which is why the backwards compatibility section of the
BIP isn't written yet.


While I'm posting, I've had a dozen off-list emails that presented me
with some FAQ:

Many people asked what other protocol upgrades beyond segwit could run
into the same incompatibility.

Many proposed improvements to Bitcoin require additional
transaction-dependent commitment data.

Examples include:

(1) Segwit.
(2) UTXO commitments. (non-delayed, at least)
(3) Committed Bloom filters
(4) Committed address indexes
(5) STXO commitments (non-delayed).
(6) Weak blocks
(7) Most kinds of fraud proofs
-- to state a few.

Unfortunately, putting *any* commitment to data dependent on the right
hand side of the hash tree in the left hand side (e.g. coinbase) means
a massive increase in the computation required for covert boosting,
because it means you can't use the left+right side combinations to
eliminate most of the hashing.

It's plausible, in fact, that this extra computation could completely
nullify the ASICBOOST advantage-- though this depends a lot on the
fine details of the implementation.

This proposal does not itself propose nullifying ASICBOOST entirely,
it proposes severely handicapping the covert form of it, and
eliminating the differential advantage for boosting miners related to
the use of transaction-dependent commitments.

Basically there are two completely separate concerns: that boosting
can produce a monopoly advantage which could be severely harmful to
the ecosystem, and that the efficient implementation of _covert_
boosting can severely harm many useful protocol improvements.   My
proposal only addresses the second concern, by (I believe) completely
leveling the playing field so that opposing commitments will not break
boosting any worse, and by making covert boosting less appealing in
general.

Use of the segwit-style commitment even in non-segwit blocks is sufficient
because the segwit commitment commits to all  transactions  (except
the coinbase) and not just segwit ones.
(It was designed this way so that lite clients that needed witness
data could work with just one tree).

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Joseph Poon]

Hi Greg,

On Wed, Apr 05, 2017 at 09:37:45PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> 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.
> 
> [...]
> 
> ==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.

Decentralized systems without patent encumbrance is an important topic
for me. We'd be very interested in adding this into extension blocks.

Claims like these merit serious attention. If you can provide any kind
of proof or documentation of this (doesn't need to be conclusive, just
something), I will provide my word and promise publicly here and now
that I will personally see to it that a commitment which solves this
(albeit possibly using a slightly different format to make it
compatible) is added into the Extension Blocks spec. If there is
evidence, my support and authorship of the Extension Block specification
is contingent upon resolving this issue.

We have added an issue here:
https://github.com/tothemoon-org/extension-blocks/issues/6

I'm interested in a more detailed explanation on how the Merle tree
structure works so we can add it to the spec, I didn't follow exactly
the new consensus rule and its mechanism in those several lines.

We will begin making a pull request adding it into our specification,
but more clarity on how to do it on its own would be helpful. We will
also consider the code exposure change to adding in SegWit on the
Canonical/1MB chain if it is more elegant to implement.

Packaging this into our proposal would not only be important, but
helpful to the end goals of this proposal as it becomes a standard
soft-fork consensus rule which has greater guarantees around
enforcibility than user-actication.

Further, can you provide clarity and confirmation into why this
commitment wasn't required as part of SegWit? 

-- 
Joseph Poon

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Anthony Towns]

On Wed, Apr 05, 2017 at 09:37:45PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> The Bitcoin mining process repeatedly hashes an 80-byte 'block header' while
> incriminating a 32-bit nonce 

That should probably be "incrementing"...

Cheers,
aj

Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[theymos]

This seems to be a serious security problem.  Would it be possible to have
a flag-day softfork included in Bitcoin Core as soon as 0.14.1? I think that a trigger
3-6 months from release should be sufficient for enough of the economy to upgrade,
given the severity of the issue.

BIP 141 says that the the commitment is optional if there are no SegWit transactions in
the block,  so will today's SegWit-ready miners always produce it even when optional
according to BIP 141, as required by this softfork?

On Wed, Apr 5, 2017, at 04:37 PM, Gregory Maxwell via bitcoin-dev 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

[bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function

[Gregory Maxwell]

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.