From: Jonathan Toomim <j@toom•im>
To: Gregory Maxwell <greg@xiph•org>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack on the Bitcoin POW function
Date: Wed, 5 Apr 2017 19:10:27 -0700 [thread overview]
Message-ID: <A0F870EB-AAFF-4730-9B88-6C2600981EAB@toom.im> (raw)
In-Reply-To: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2017-04-06 2:22 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-05 21:37 Gregory Maxwell
2017-04-05 23:05 ` theymos
2017-04-06 0:17 ` Gregory Maxwell
2017-04-06 0:39 ` Joseph Poon
2017-04-06 0:40 ` Joseph Poon
2017-04-06 1:32 ` Gregory Maxwell
2017-04-06 2:09 ` Joseph Poon
2017-04-05 23:25 ` Anthony Towns
2017-04-05 23:42 ` Joseph Poon
2017-04-06 2:10 ` Jonathan Toomim [this message]
2017-04-06 20:21 ` Jared Lee Richardson
2017-04-06 2:31 ` Peter Todd
2017-04-06 2:39 ` Bram Cohen
2017-04-06 2:49 ` Peter Todd
2017-04-06 3:11 ` Erik Aronesty
2017-04-06 3:23 ` Peter Todd
2017-04-06 3:23 ` David Vorick
2017-04-06 3:42 ` Peter Todd
2017-04-06 5:46 ` Thomas Daede
2017-04-06 6:24 ` Jonathan Toomim
2017-04-06 12:04 ` David Vorick
[not found] ` <CAMZUoK=oDAD9nhFAHkgncWtYxjBNh3qXbUffOH57QMnqjhmN6g@mail.gmail.com>
[not found] ` <CAMZUoKn8tr3LGbks0TnaCx9NTP6MZUzQ8PE6jDq1xiqpYyYwow@mail.gmail.com>
2017-04-06 13:55 ` Russell O'Connor
2017-04-06 16:49 ` Marco
2017-04-06 17:04 ` Alex Mizrahi
2017-04-06 17:13 ` Alex Mizrahi
2017-04-07 12:59 ` Jannes Faber
2017-04-07 13:28 ` Erik Aronesty
2017-04-06 17:31 ` Jared Lee Richardson
2017-04-06 17:26 ` Jared Lee Richardson
2017-04-06 15:36 ` Alex Mizrahi
2017-04-06 17:51 ` Jorge Timón
2017-04-06 7:24 ` bfd
2017-04-06 9:17 ` Luke Dashjr
2017-04-06 12:02 ` Luv Khemani
2017-04-06 12:11 ` Bryan Bishop
2017-04-06 17:43 ` Timo Hanke
2017-04-06 12:30 ` Luv Khemani
2017-04-06 15:15 ` Jorge Timón
2017-04-06 15:41 ` Daniel Robinson
2017-04-06 16:13 ` Andreas Schildbach
2017-04-06 21:38 ` Gregory Maxwell
2017-04-06 4:47 Oliver Petruzel
2017-04-06 4:49 Raystonn .
2017-04-06 7:47 ` praxeology_guy
2017-04-06 12:13 ` David Vorick
2017-04-07 1:34 Daniele Pinna
2017-04-07 6:46 ` Emilian Ursu
2017-04-07 7:44 ` Alex Mizrahi
2017-04-07 8:08 ` praxeology_guy
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=A0F870EB-AAFF-4730-9B88-6C2600981EAB@toom.im \
--to=j@toom$(echo .)im \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=greg@xiph$(echo .)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