From: "Jan Čapek" <jan.capek@braiins•cz>
To: Sergio Demian Lerner via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP Proposal: Inhibiting a covert optimization on the Bitcoin POW function
Date: Sat, 8 Apr 2017 00:48:11 +0200 [thread overview]
Message-ID: <20170408004811.2a0c2b9e@glum> (raw)
In-Reply-To: <CAKzdR-rzb6oBq01DQM530pdgNUjzc79yjtYp_HAyF5GZpBPnFw@mail.gmail.com>
Hi,
1 comment below
On Fri, 7 Apr 2017 17:52:17 -0300
Sergio Demian Lerner via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> <pre>
> BIP: TBD
> Layer: Consensus
> Title: Inhibiting a covert optimization on the Bitcoin POW function
> Author: Sergio Demian Lerner <sergio.d.lerner@gmail•com>
> Status: Draft
> Type: Standards Track
> Created: 2016-04-07
> License: PD
> </pre>
>
> ==Abstract==
>
> This proposal inhibits the covert use of a known optimization 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 optimization which can allow a rational 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 applied for a patent on this
> optimization. The company "Sunrise Tech Group, Llc" has offered to
> license it to any interested party in the past. Sunrise Tech Group
> has 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 taking advantage of this optimization, as
> described
> by the patent:
> One 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.
>
> The use of this optimization could result in a big payoff, but the
> actual sum depends on the degree of research, investment and effort
> put into designing
> the improved cores.
>
> On the above basis the potential for covert use of this optimization
> in the covert form and interference with useful improvements presents
> a danger to the Bitcoin system.
>
> ==Background==
>
> The general idea of this optimization 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 optimization. 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 optimization.
>
> 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 optimization.
>
> 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 optimization 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.
Root value pow - Does this mean that every miner would be penalized in
this way regardless of the actual number of transactions in the block?
> 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 optimization ==
>
> A BIP for avoiding erroneous warning messages when miners use the
> overt version
> of the optimization was proposed several years ago, in order to deter
> the covert
> use of the optimization. But that BIP was rejected.
> However, in light of the current discoveries, that BIP could be
> reconsidered.
>
> The over optimization does not generally interfere with improvements
> in the protocol.
>
> ==Backward compatibility==
>
>
> ==Implementation==
>
>
> ==Acknowledgments==
>
> Greg Maxwell <greg@xiph•org> for the original report, which contained
> several errors that were corrected in the present proposal.
>
> ==Copyright==
>
> This document is placed in the public domain.
--
CEO Braiins Systems | Slushpool.com
tel: +420 604 566 382
email: jan.capek@braiins•cz
http://braiins.cz
http://slushpool.com
prev parent reply other threads:[~2017-04-07 22:48 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-07 20:52 Sergio Demian Lerner
2017-04-07 22:48 ` Jan Čapek [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170408004811.2a0c2b9e@glum \
--to=jan.capek@braiins$(echo .)cz \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox