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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <gmaxwell@gmail.com>) id 1X31o6-0005B1-2B
for bitcoin-development@lists.sourceforge.net;
Fri, 04 Jul 2014 11:37:34 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.128.174 as permitted sender)
client-ip=209.85.128.174; envelope-from=gmaxwell@gmail.com;
helo=mail-ve0-f174.google.com;
Received: from mail-ve0-f174.google.com ([209.85.128.174])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1X31o3-0002ZN-Qw
for bitcoin-development@lists.sourceforge.net;
Fri, 04 Jul 2014 11:37:34 +0000
Received: by mail-ve0-f174.google.com with SMTP id jx11so1530625veb.5
for <bitcoin-development@lists.sourceforge.net>;
Fri, 04 Jul 2014 04:37:26 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.52.27.133 with SMTP id t5mr7912630vdg.9.1404473846231; Fri,
04 Jul 2014 04:37:26 -0700 (PDT)
Received: by 10.52.75.165 with HTTP; Fri, 4 Jul 2014 04:37:26 -0700 (PDT)
In-Reply-To: <10566815.3CllqoMfON@momentum>
References: <10566815.3CllqoMfON@momentum>
Date: Fri, 4 Jul 2014 04:37:26 -0700
Message-ID: <CAAS2fgRrAOgEv7Hq4BofS5UoDPsJy3hEt34od54pY6vtEq0Agw@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Andy Parkins <andyparkins@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: -1.6 (-)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(gmaxwell[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1X31o3-0002ZN-Qw
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] ASIC-proof mining
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Fri, 04 Jul 2014 11:37:34 -0000
On Fri, Jul 4, 2014 at 3:27 AM, Andy Parkins <andyparkins@gmail.com> wrote:
> Hello,
>
> I had a thought after reading Mike Hearn's blog about it being impossible=
to
> have an ASIC-proof proof of work algorithm.
>
> Perhaps I'm being dim, but I thought I'd mention my thought anyway.
Thanks for sharing. Ideas similar to what you're describing have come
up a number of times before.
I believe the particular formulation you're suggesting is not workable
for a number of reasons.
If I understand what you're proposing correctly, it that it has very
high (nearly symmetrical) verification costs, all the verifiers have
to also hash all of that information to check the result. It is
imperative for the system that the proof of work be cheap to verify,
since every system needs to verify it and have no incentive to skip
verifying it, needs to use it to block DOS attacks, etc.
I believe this design would also completely preclude lite nodes (SPV
nodes, section 8 of https://bitcoin.org/bitcoin.pdf), which are the
most popular Bitcoin wallets. SPV wallets do not need to store the
blockchain, in fact they technically need no storage at all=E2=80=94 and ar=
e
secure, given some assumptions about the decentralization and honesty
of mining. It would make Bitcoin more or less infeasible to use on
mobile devices and force many people using wallets onto centralized
services providers which they'd have to trust to process their
transactions.
Another longer term side effect of making verification costly is that
it makes it much less reasonable to provide zero knoweldge proofs for
data in Bitcoin=E2=80=94 closing off a whole set of useful tools like stron=
gly
private proofs of solvency, and strongly private bitcoin-backed
pseudonymous identities.
I also believe this would also break pruning (section 7 of
bitcoin.pdf): Right now a fully validating node can be created that
uses only on the order of 1GB of disk space, without pruning the
number is 25 GB and the gap is just going to grow over time. The
elimiating of pruning would be a major scalability hit.
A smaller, but potentially still important issue is that the proposed
proof of work function would be expensive to run even once. This may
result in it not being effectively progress free=E2=80=94 if a miner would
typically only make a small number of tries before success then it
would make mining like a race where faster miners would have a
super-linear advantage over others instead of statistically rewarding
miners fairly.
There are ways to make what I think you're trying to accomplish work
with fewer tradeoffs that have been suggested before (see
https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas "POW which involves
queries against the UTXO set")... the general idea there is that the
candidate block header is used to randomly select one or a few random
entries in the set of spendable coins (UTXO set), which are then
included in the hashing. If the UTXO set is also committed in every
block via a hash tree when the miner finds a solution he can also
extract a compact membership proof that shows the UTXO he included in
his hashing were the right ones. This way the work can still be
verified by systems that don't have the blockchain (though they may
use 10x more bandwidth=E2=80=94 unfortunate on its own and perhaps enough t=
o
still make zero knoweldge proofs less practical), and because the
queries are against the UTXO set instead of the whole blockchain it's
not incompatible with pruning.
Though even with those fixes, I am far from sure that this would be
helpful: It would not preclude specialized high efficiency hardware
for mining (see https://download.wpsoftware.net/bitcoin/asic-faq.pdf
for set of general arguments in this space), and the hardware that
existed may not be actually useful for validation in much the same way
that you cannot use existing mining hardware as a general sha256
accelerator.
This specialized hardware might look more like an massively parallel
flash or dram array with integrated computation (e.g.
http://www.eecg.toronto.edu/~dunc/cram/ )=E2=80=94 and these differences ma=
y
not all be good: by shifting costs from operating energy to gate-count
it moves the total costs into hardware which is one-time and amortized
over use (generally for modern process, compute bound equipment costs
more in energy than the marginal costs in fabrication after a month or
two of operation), potentially creating an advantage for
earlier/larger participants. Plus a CRAM like design might also have
massive throughput advantages compared to commodity hardware operating
in a bus limited mode its hard to say until millions have been sunk in
trying to optimize it, but even if it does not=E2=80=94 one of the argument=
s
made in asic-faq.pdf is because mining should be, in theory, nearly
perfect competition even the small advantage in costs from eliminating
unneeded peripherals can basically drive everyone without that
advantage out.
As an aside, there is an altcoin "boolberry" that implements something
where 2MB of data is extracted from the blockchain and then mined one.
But because the extraction is not in the inner-loop mining pools just
send it out to miners... and of course it could be uploaded to a
dedicated mining coprocessor (or FPGA, or GPU) if anyone ever got
around to doing the optimizations... it also has most of the other
issues I raised above relative to your proposal. It's still too new to
see what failure modes it suffers the most from first, and the
altcoins that it is mostly competing with suffer from their own ill
advised (_very slow_) POW.
> Apologies in advance if this is a stupid idea.
No need to be sorry=E2=80=94 talking about these things is how people learn=
.
While I don't think this idea is good, and I'm even skeptical about
fixed versions=E2=80=94 I promise you many other people were thinking simil=
ar
or even less useful things and will find the discussion interesting.
|
