From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 0438A6C for ; Thu, 6 Apr 2017 02:22:07 +0000 (UTC) X-Greylist: delayed 00:11:36 by SQLgrey-1.7.6 Received: from c.mail.sonic.net (c.mail.sonic.net [64.142.111.80]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6CAA3196 for ; Thu, 6 Apr 2017 02:22:06 +0000 (UTC) Received: from [192.168.1.190] (63.135.62.197.nwinternet.com [63.135.62.197] (may be forged)) (authenticated bits=0) by c.mail.sonic.net (8.15.1/8.15.1) with ESMTPSA id v362ASqS020415 (version=TLSv1 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT); Wed, 5 Apr 2017 19:10:29 -0700 Content-Type: multipart/signed; boundary="Apple-Mail=_662F3FAA-5706-4839-A2A7-E9A08D6F4682"; protocol="application/pgp-signature"; micalg=pgp-sha512 Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\)) X-Pgp-Agent: GPGMail From: Jonathan Toomim In-Reply-To: Date: Wed, 5 Apr 2017 19:10:27 -0700 Message-Id: References: To: Gregory Maxwell , Bitcoin Protocol Discussion X-Mailer: Apple Mail (2.3112) X-Sonic-CAuth: UmFuZG9tSVbpcIb5o9lUqTCS+i+qlIDtUjnSpk9CK5VQaBaKtNCWb1x/usgkW5MkIXTwI1cC69MM+OE6m/TvMx7AvxhqhRcQ X-Sonic-ID: C;qGdUNG4a5xGSmdRbNyX4rQ== M;anamNG4a5xGSmdRbNyX4rQ== X-Sonic-Spam-Details: 0.0/5.0 by cerberusd X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Thu, 06 Apr 2017 02:25:46 +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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 06 Apr 2017 02:22:07 -0000 --Apple-Mail=_662F3FAA-5706-4839-A2A7-E9A08D6F4682 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii 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 = wrote: >=20 > 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. >=20 > 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. >=20 > 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. --Apple-Mail=_662F3FAA-5706-4839-A2A7-E9A08D6F4682 Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP using GPGMail -----BEGIN PGP SIGNATURE----- Comment: GPGTools - https://gpgtools.org iQEcBAEBCgAGBQJY5aOUAAoJEIEuMk4MG0P108MIAJJMKYbk4updO6dS1tvnSFQJ 4AN9VdOrJjk2iBxl+cDhCTgsE4DrIARGLCta9F1QmOMvcFVhpEPaJno5vp6XJXdq gZwaIQpHtutLpRJ3EH/Z9qvn6lYdluEowC3MhEJ9Bwa64jsBqrldXfP9T0VSljxE eQP0RtG5bfckVw7k0fco9rHtLx7MQmtD51FnIEGhu+m14iZOjvJNJ/mrwoI1IRl0 gUlzu7hG4XPOLiwgmipT/OvTpnVPRtbwOO+hVYoxWubQsDThrk31n0JkRe2BlH4+ FmPztkKRYR6b52z7P88quePthi81LB+GHJn2YMl4esWge20l7V3bWLD0OYd6LFQ= =UisG -----END PGP SIGNATURE----- --Apple-Mail=_662F3FAA-5706-4839-A2A7-E9A08D6F4682--