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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
Return-Path: <natanael.l@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id E026BB6C
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 17 Apr 2017 22:35:00 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw0-f181.google.com (mail-yw0-f181.google.com
[209.85.161.181])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CC207180
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 17 Apr 2017 22:34:56 +0000 (UTC)
Received: by mail-yw0-f181.google.com with SMTP id j9so62000947ywj.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 17 Apr 2017 15:34:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=U74r9NzVns6oCxB/9emicI/U6edFoFWvyJz8Bf1I9CE=;
b=Iwi1F4bKrmJPxaz30+/HN0FWz4g/AGFXmWufnCuEusVxQBpU2EOF2o7mOrxDncy+Gd
wwIbjfSz5c62S6W7BMlgCam+6Zhq1L364bS9fKYWlZDfNLDS7IufKx12SS2UQgHylZnn
tm+buJhzkSxzvAxwFk5X45cR4vI1NRCR9kQtWY0b51ngbs+Sr/WQ3cClt24JI1X8iBei
bnj62Vuxl2il2yt2qNYPtGicgny4RKB5E5qwSJ+tYJOMNvwJqTYGv5PDIGSwuDDXrOK6
EOVo08G8Bi+/5sBgdPRTTu/zhU93g9C0ThbZUyhi0Fma0N1FBCBJUZ2KgLFAgqgyI04b
KRVw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=U74r9NzVns6oCxB/9emicI/U6edFoFWvyJz8Bf1I9CE=;
b=hvXvwUG+OFTrsdbOGd+vvDzKeSuMwWrBFYhWffCv1UpM50PC3eZpVs8+uqb8+AwT1b
dSKS8GZ7RrI++lIiEaj+zR6yM1/fwldVVHfjTQq9lsgR3iZ8BU4iFKCbjZbsnVq74Yo+
mNFH0Eh67AtloZUqu+D1dc32R0Sekjz5kTDHbon6bBBusGa9gDWo6FVfwNF8S4G30e1F
Ptv/vE91Rh7NgjDlhzhQtrC/SJrotiMixBmiMSnDs3kAJkZcryHtDLvvyqOTeBvcujLk
r9YUXv7EQmpMXctz5zgHlsQl7loQo4BluzQUZWvVkPd25YUSGJqyICZuTLtYyBQAj7Zp
LrEg==
X-Gm-Message-State: AN3rC/6TzFgnSmnlaR65LThsWvJcfRBT8ouk/Z6l8JknyyC7Xz9MxND3
lOs2wTWgWfoFkH8GMDEqUQ3s9FgRcw==
X-Received: by 10.13.221.208 with SMTP id g199mr16873604ywe.21.1492468496012;
Mon, 17 Apr 2017 15:34:56 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.37.35.88 with HTTP; Mon, 17 Apr 2017 15:34:55 -0700 (PDT)
Received: by 10.37.35.88 with HTTP; Mon, 17 Apr 2017 15:34:55 -0700 (PDT)
In-Reply-To: <CAJowKgK-0rqqeKkQZj0itZf79fT++OOYXJKg1pik-7mFieU=ZA@mail.gmail.com>
References: <BL2PR03MB435F510935FC7E230118AD3EE380@BL2PR03MB435.namprd03.prod.outlook.com>
<CAAy62_K5ePDuvVn8=DtwJX6ek00Z_r4u9LyA0W11vgZmQ=zzDg@mail.gmail.com>
<0690791a46d7a7699fc3427e92a76e9b.squirrel@mail.fairluck.net>
<CAJowKg+dZr-PcHfCY5AO2BO8_-5QfwzvG3PuJA+mTLWw9=a-Og@mail.gmail.com>
<461f7ce7a17c5765daadc461cdd3373c@cock.lu>
<CAJowKg+1vUBmr7cTzUy8gAdjEWTM_+07G9Z96Bo=wd6_htgv1Q@mail.gmail.com>
<CAJowKgJPjWb_S0jb+RJ9-90sucb=ZeU2-qrNqrVN5USTaxDjDw@mail.gmail.com>
<CAJowKgJ+3=sOenU9EQ4eCOw8CDMoSX_L=0pUqfBKj3ZyVBXoTA@mail.gmail.com>
<CAJowKgKqyb7DCs-yrbj4Z8Kzmgg0GCKXh+wwdSvfPHregiwdvA@mail.gmail.com>
<CAJowKgL=UmJvE0KpSsa20AJBF6Ur85ghRymHY+=11VOezmaaxw@mail.gmail.com>
<CAJowKgK-0rqqeKkQZj0itZf79fT++OOYXJKg1pik-7mFieU=ZA@mail.gmail.com>
From: Natanael <natanael.l@gmail.com>
Date: Tue, 18 Apr 2017 00:34:55 +0200
Message-ID: <CAAt2M19iCd4=qyquvhFNw77YqO3++p6ckMWZLHCAa+8xUWGbAg@mail.gmail.com>
To: Erik Aronesty <earonesty@gmail.com>, erik@q32.com
Content-Type: multipart/alternative; boundary=94eb2c06e3fa8b3515054d6466ed
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Malice Reactive Proof of Work Additions (MR
POWA): Protecting Bitcoin from malicious miners
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: Mon, 17 Apr 2017 22:35:01 -0000
--94eb2c06e3fa8b3515054d6466ed
Content-Type: text/plain; charset=UTF-8
Den 17 apr. 2017 16:14 skrev "Erik Aronesty via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:
It's too bad we can't make the POW somehow dynamic so that any specialized
hardware is impossible, and only GPU / FPGA is possible.
Maybe a variant of Keccak where the size of the sponge is increased along
with additional zero bits required. Seems like this would either have to
resist specialized hardware or imply sha3 is compromised such that the size
of the sponge does not incerase the number of possible output bits as
expected.
Technically SHA3 (keccak) already has the SHAKE mode, an extensible output
function (XOF). It's basically a hash with arbitary output length (with
fixed state size, 256 bits is the common choice). A little bit like hooking
a hash straight into a stream cipher.
The other modes should *probably* not allow the same behavior, though. I
can't guarantee that however.
You may be interested in looking at parameterizable ciphers and if any of
them might be applicable to PoW.
IMHO the best option if we change PoW is an algorithm that's moderately
processing heavy (we still need reasonably fast verification) and which
resists partial state reuse (not fast or fully "linear" in processing like
SHA256) just for the sake of invalidating asicboost style attacks, and it
should also have an existing reference implementation for hardware that's
provably close in performance to the theoretical ideal implementation of
the algorithm (in other words, one where we know there's no hidden
optimizations).
Anything relying on memory or other such expensive components is likely to
fall flat eventually as fast memory is made more compact, cheaper and moves
closer to the cores.
That should be approximately what it takes to level out the playing field
in ASIC manufacturing, because then we would know there's no fancy tricks
to deploy that would give one player unfair advantage. The competition
would mostly be about packing similar gate designs closely and energy
efficiency. (Now that I think about it, the proof MAY have to consider
energy use too, as a larger and slower but more efficient chip still is
competitive in mining...)
We should also put a larger nonce in the header if possible, to reduce the
incentive to mess with the entropy elsewhere in blocks.
--94eb2c06e3fa8b3515054d6466ed
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div data-smartmail=3D"gmail_signature" dir=3D"auto"><br>=
</div><div class=3D"gmail_extra" dir=3D"auto"><div class=3D"gmail_quote">De=
n 17 apr. 2017 16:14 skrev "Erik Aronesty via bitcoin-dev" <<a=
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bi=
tcoin-dev@lists.<wbr>linuxfoundation.org</a>>:<br type=3D"attribution"><=
blockquote class=3D"m_8645300429802790440quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto"><div class=
=3D"m_8645300429802790440quoted-text"><div class=3D"gmail_extra" dir=3D"aut=
o"><div class=3D"gmail_quote"><br><blockquote class=3D"m_864530042980279044=
0m_-5360631722375867952quote" style=3D"margin:0 0 0 .8ex;border-left:1px #c=
cc solid;padding-left:1ex"><div dir=3D"auto"><div dir=3D"auto">It's too=
bad we can't make the POW somehow dynamic so that any specialized hard=
ware is impossible, and only GPU / FPGA is possible.</div><div dir=3D"auto"=
><div class=3D"gmail_extra"><div class=3D"gmail_quote"><blockquote class=3D=
"m_8645300429802790440m_-5360631722375867952m_6005315452753799385quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></bloc=
kquote></div><br></div></div></div>
</blockquote></div><br></div></div><div class=3D"gmail_extra" dir=3D"auto">=
Maybe a variant of=C2=A0<span style=3D"background-color:rgb(255,255,255);co=
lor:rgb(34,34,34);font-family:"helvetica neue",helvetica,"ni=
mbus sans l",arial,"liberation sans",sans-serif;font-size:16=
px">Keccak where the size of the sponge is increased along with additional =
zero bits required.=C2=A0 Seems like this would either have to resist speci=
alized hardware or imply sha3 is compromised such that the size of the spon=
ge does not incerase the number of possible output bits as expected.=C2=A0<=
/span></div></div></blockquote></div></div><div dir=3D"auto"><br></div><div=
dir=3D"auto">Technically SHA3 (keccak) already has the SHAKE mode, an exte=
nsible output function (XOF). It's basically a hash with arbitary outpu=
t length (with fixed state size, 256 bits is the common choice). A little b=
it like hooking a hash straight into a stream cipher.=C2=A0</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">The other modes should *probably* not=
allow the same behavior, though. I can't guarantee that however.=C2=A0=
</div><div dir=3D"auto"><br></div><div dir=3D"auto">You may be interested i=
n looking at parameterizable ciphers and if any of them might be applicable=
to PoW.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">IMHO the =
best option if we change PoW is an algorithm that's moderately processi=
ng heavy (we still need reasonably fast verification) and which resists par=
tial state reuse (not fast or fully "linear" in processing like S=
HA256) just for the sake of invalidating asicboost style attacks, and it sh=
ould also have an existing reference implementation for hardware that's=
provably close in performance to the theoretical ideal implementation of t=
he algorithm (in other words, one where we know there's no hidden optim=
izations).=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">Anythin=
g relying on memory or other such expensive components is likely to fall fl=
at eventually as fast memory is made more compact, cheaper and moves closer=
to the cores.=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">Tha=
t should be approximately what it takes to level out the playing field in A=
SIC manufacturing, because then we would know there's no fancy tricks t=
o deploy that would give one player unfair advantage. The competition would=
mostly be about packing similar gate designs closely and energy efficiency=
. (Now that I think about it, the proof MAY have to consider energy use too=
, as a larger and slower but more efficient chip still is competitive in mi=
ning...)=C2=A0</div><div dir=3D"auto"><br></div><div dir=3D"auto">We should=
also put a larger nonce in the header if possible, to reduce the incentive=
to mess with the entropy elsewhere in blocks.=C2=A0</div><div class=3D"gma=
il_extra" dir=3D"auto"></div></div>
--94eb2c06e3fa8b3515054d6466ed--
|
