1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
Return-Path: <j@toom.im>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 0438A6C
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <j@toom.im>
In-Reply-To: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com>
Date: Wed, 5 Apr 2017 19:10:27 -0700
Message-Id: <A0F870EB-AAFF-4730-9B88-6C2600981EAB@toom.im>
References: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <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 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 =
<bitcoin-dev@lists.linuxfoundation.org> 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--
|
