diff options
| author | bfd <bfd@cock.lu> | 2017-04-06 10:24:03 +0300 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2017-04-06 07:24:11 +0000 |
| commit | 321368a3e94b8da458a0ca8208a7bf430429e962 (patch) | |
| tree | 63c8adc68d38cb9706df533e8c3b30c4c33320fe | |
| parent | 1ce708e3e2dbf0ac8e63655cef920d283351070f (diff) | |
| download | pi-bitcoindev-321368a3e94b8da458a0ca8208a7bf430429e962.tar.gz pi-bitcoindev-321368a3e94b8da458a0ca8208a7bf430429e962.zip | |
Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function
| -rw-r--r-- | f9/828bc9a0ed38d3d6967e10442d56f9b7277f2c | 304 |
1 files changed, 304 insertions, 0 deletions
diff --git a/f9/828bc9a0ed38d3d6967e10442d56f9b7277f2c b/f9/828bc9a0ed38d3d6967e10442d56f9b7277f2c new file mode 100644 index 000000000..be2aebbb5 --- /dev/null +++ b/f9/828bc9a0ed38d3d6967e10442d56f9b7277f2c @@ -0,0 +1,304 @@ +Return-Path: <bfd@cock.lu> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id DB1EE87A + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 6 Apr 2017 07:24:11 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 +Received: from cock.li (cock.li [185.100.85.212]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 923AE90 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 6 Apr 2017 07:24:07 +0000 (UTC) +X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on + smtp1.linux-foundation.org +X-Spam-Level: +X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, + DKIM_VALID,DKIM_VALID_AU,LOTS_OF_MONEY,T_MONEY_PERCENT autolearn=ham + version=3.3.1 +MIME-Version: 1.0 +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cock.lu; s=mail; + t=1491463443; bh=fXzdwvFortnp5S3R04V/ClOChw8IC25jvH+2+ucAIiI=; + h=Date:From:To:Subject:In-Reply-To:References:From; + b=t8Tnjc58DhHd9OSsF7xVFf2jge++RVT4qy2QPo3Eq3kcCyMq5G+QLPqUcEjl4b3P7 + i5hhrMljOoCCxKgYOQ7o6W8nzm75iAohcleHxCTBVswwdQTeOBDj8a4HlnnNOG1NcX + VKIr9vaIC4kSk7ybxd3y3ic+7vgB+7p5tNGhh4zArOgW6ajzh43UPmrOQrMzqezbtQ + 41u9vReHILMxz3WqIYL9Y5mEnSf+atrp/i5mxTrwVlUuAR024nf48CWzJBgdyZkTP0 + ibFHld3P3pQMHaxnYynf+U3ZEa+t94jWWGfa7q+qU0EpO6u03B1v+h+EXUoS5oyVqm + 3lumkWNIOltEA== +Content-Type: text/plain; charset=US-ASCII; + format=flowed +Content-Transfer-Encoding: 7bit +Date: Thu, 06 Apr 2017 10:24:03 +0300 +From: bfd@cock.lu +To: Gregory Maxwell <greg@xiph.org>, Bitcoin Protocol Discussion + <bitcoin-dev@lists.linuxfoundation.org> +In-Reply-To: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com> +References: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com> +Message-ID: <97627075ba7d739931f66eb51650f28a@cock.lu> +X-Sender: bfd@cock.lu +User-Agent: Roundcube Webmail/1.2.3 +X-Mailman-Approved-At: Thu, 06 Apr 2017 11:42:53 +0000 +Subject: Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the + Bitcoin POW function +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.12 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Thu, 06 Apr 2017 07:24:12 -0000 + +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 + |