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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <etotheipi@gmail.com>) id 1X317t-0000py-5H
for bitcoin-development@lists.sourceforge.net;
Fri, 04 Jul 2014 10:53:57 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 74.125.82.169 as permitted sender)
client-ip=74.125.82.169; envelope-from=etotheipi@gmail.com;
helo=mail-we0-f169.google.com;
Received: from mail-we0-f169.google.com ([74.125.82.169])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1X317r-00016o-BS
for bitcoin-development@lists.sourceforge.net;
Fri, 04 Jul 2014 10:53:57 +0000
Received: by mail-we0-f169.google.com with SMTP id t60so1505402wes.14
for <bitcoin-development@lists.sourceforge.net>;
Fri, 04 Jul 2014 03:53:49 -0700 (PDT)
X-Received: by 10.180.105.170 with SMTP id gn10mr17402356wib.31.1404471228999;
Fri, 04 Jul 2014 03:53:48 -0700 (PDT)
Received: from [172.11.13.74] ([31.216.236.194])
by mx.google.com with ESMTPSA id
do5sm77872464wib.16.2014.07.04.03.53.47
for <bitcoin-development@lists.sourceforge.net>
(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Fri, 04 Jul 2014 03:53:48 -0700 (PDT)
Message-ID: <53B687BB.9010103@gmail.com>
Date: Fri, 04 Jul 2014 06:53:47 -0400
From: Alan Reiner <etotheipi@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:24.0) Gecko/20100101 Thunderbird/24.5.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <10566815.3CllqoMfON@momentum>
In-Reply-To: <10566815.3CllqoMfON@momentum>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
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
(etotheipi[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: 1X317r-00016o-BS
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 10:53:57 -0000
Just a thought on this -- I'm not saying this is a good idea or a bad
idea, because I have spent about zero time thinking about it, but
something did come to mind as I read this. Reading 20 GB of data for
every hash might be a bit excessive. And as the blockchain grows, it
will become infeasible to continue. However, what comes to mind is the
ROMix algorithm defined by Colin Percival, which was the pre-cursor to
scrypt. Which is actually what Armory uses for key stretching because
it's far simpler than scrypt itself while maintaining the memory-hard
properties (the downside is that it's much less flexible in allowing the
user to trade-off compute time vs memory usage).
ROMix works by taking N sequential hashes and storing the results into a
single N*32 byte lookup table. So if N is 1,000,000, you are going to
compute 1,000,000 and store the results into 32,000,000 sequential bytes
of RAM. Then you are going to do 1,000,000 lookup operations on that
table, using the hash of the previous lookup result, to determine the
location of next lookup (within that 32,000,000 bytes). Assuming a
strong hash function, this means its impossible to know in advance what
needs to be available in RAM to lookup, and it's easiest if you simply
hold all 32,000,000 bytes in RAM.
Something similar could be applied to your idea. We use the hash of a
prevBlockHash||nonce as the starting point for 1,000,000 lookup
operations. The output of the previous lookup is used to determine
which block and tx (perhaps which chunk of 32 bytes within that tx) is
used for the next lookup operation. This means that in order to do the
hashing, you need the entire blockchain available to you, even though
you'll only be using a small fraction of it for each "hash". This might
achieve what you're describing without actually requiring the full 20 GB
of reading on ever hash.
-Alan
On 07/04/2014 06:27 AM, Andy Parkins 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.
>
> It strikes me that he's right that it's impossible for any algorithm to exist
> that can't be implemented in an ASIC. However, that's only because it's
> trying to pick an algorithm that is CPU bound. You could protect against ASCI
> mining (or rather, make it irrelevant that it was being used) by making the
> algorithm IO-bound rather than CPU-bound.
>
> For example, what if the proof-of-work hash for a block were no longer just
> "hash of block", which contains the hash of the parent block, but instead were
> hash of
>
> [NEW_BLOCK] [ALL_PREVIOUS_BLOCKS] [NEW_BLOCK]
>
> [ALL_PREVIOUS_BLOCKS] is now 20GB (from memory) and growing. By prefixing and
> suffixing the new block, you have to feed every byte of the blockchain through
> the hashing engine (the prefix prevents you caching the intermediate result).
> Whatever bus you're using to feed your high speed hashing engine, it will
> always be faster than the bus -- hence you're now IO-bound, not CPU-bound, and
> any hashing engine will, effectively, be the same.
>
> I'm making the assumption that SHA-256 is not cacheable from the middle
> outwards, so the whole block-chain _has_ to be transferred for every hash.
>
> Apologies in advance if this is a stupid idea.
>
>
>
> Andy
|
