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; 
MIME-Version: 1.0
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
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] ASIC-proof mining
Precedence: list

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.