From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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: From: Gregory Maxwell To: Andy Parkins 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 Subject: Re: [Bitcoin-development] ASIC-proof mining X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 Jul 2014 11:37:34 -0000 On Fri, Jul 4, 2014 at 3: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. 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.