From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1VdRKj-0004PT-3T for bitcoin-development@lists.sourceforge.net; Mon, 04 Nov 2013 21:05:13 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.77 as permitted sender) client-ip=62.13.149.77; envelope-from=pete@petertodd.org; helo=outmail149077.authsmtp.com; Received: from outmail149077.authsmtp.com ([62.13.149.77]) by sog-mx-2.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1VdRKg-0006Yr-Tj for bitcoin-development@lists.sourceforge.net; Mon, 04 Nov 2013 21:05:13 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt15.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rA4L4wJ6050111; Mon, 4 Nov 2013 21:04:58 GMT Received: from petertodd.org (petertodd.org [174.129.28.249]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rA4L4pCd060493 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Mon, 4 Nov 2013 21:04:54 GMT Date: Mon, 4 Nov 2013 16:04:51 -0500 From: Peter Todd To: Ittay Message-ID: <20131104210451.GA4443@petertodd.org> References: <20131104142621.GA2190@petertodd.org> <20131104150406.GA2566@petertodd.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="/04w6evG8XlLl3ft" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: c12ecbb6-4594-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR bgdMdgYUFloCAgsB AmUbWVVeUFl7XGc7 ag1VcwRfa1RMVxto VEFWR1pVCwQmQ20F ehpeIU1ycQVCcX0+ YURrWHUVD0V4IBUv EEhJEWgPYXphaTUc TRJQdwFJcANIexZF O1F6ACIKLwdSbGoL NQ4vNDcwO3BTJTpY RgYVKF8UXXNDNyMg QFUNEDMiB0QZSil7 Kh0gJ0RUFk8aMU81 N1ZJ X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 174.129.28.249/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) 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 SPF_PASS SPF: sender matches SPF record 0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [URIs: petertodd.org] X-Headers-End: 1VdRKg-0006Yr-Tj Cc: Bitcoin Dev , Emin =?iso-8859-1?B?R/xu?= Sirer Subject: Re: [Bitcoin-development] Auto-generated miner backbone 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: Mon, 04 Nov 2013 21:05:13 -0000 --/04w6evG8XlLl3ft Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote: > On Mon, Nov 4, 2013 at 10:25 AM, Ittay wrote: >=20 > > As for the rational motivation of the individual miners - that's a good > > point! > > Here is a solution we did not put in the paper due to space constraints > > that should alleviate your concern: > > Instead of locally choosing a block at random, have a deterministic > > pseudo-random mechanism for choosing between competing chains. E.g., ta= ke > > the one whose last block hash is smaller. This way all miners choose the > > same chain, and the guarantees of our solution hold. > > >=20 > I take that back. Speaking of, I'm going to take back my solution as well; I misunderstood your paper. So here's your argument in a ELI5 nutshell: Alice is a miner with some amount of hashing power. She has the ability to detect new blocks on the network extremely effectively for whatever reason; in short she has unusually good knowledge of the state of the network. She is also very good at publishing her blocks and getting them to the majority of hashing power in very little time; she has unusually good connectivity to all miners. (low-latency and high bandwidth) She's so good at this that when she finds a new block, she keeps it a secret! She can get away with this because she knows that the moment Bob finds a block, she can immediately broadcast it to the rest of the network before the other block propagates. Instead of building on Bob's blocks, almost everyone builds on Alice's block, depriving Bob of the revenue. Gradually Alice gets more and more miners because Bob, and other pools, don't pay out as much. You propose a rule where essentially miners extend Bob's block 50% of the time, and show in your paper how that leads to a scenario where Alice needs to have at leastr 1/4 of the total hashing power to succesfully pull this attack off anyway. What I did succesfully show is that for a short-term rational miner they're still better off mining to extend the block they hear about first rather than using your pick-one-at-random rule, because when you hear about a block is important information about whether or not the majority is mining on it. This is true even if others are using the pick-one-at-random rule. (they're better defecting than doing what's right for the whole network) Even worse is that miners have a rational incentive to broadcast such near-target headers to try to encourage other miners to work on the same fork that they are working on. The near-target idea came about for a totally different reason, so it's something that might wind up being implemented anyway. Mike Hearn's idea of making it easy to identify nodes associated with hashing power is still wrong. Although again, it's something that miners themselves have rational incentives to do. (you always want to encourage others to send you their blocks, and you also want to be able to send your blocks to the majority of hashing power as quickly as possible) Where the idea goes wrong is it makes it easier for Alice to identify hashing power, specifically where she needs to send her blocks to distribute them to the majority as quickly as possible. The second problem occurs if those nodes also distribute blocks to connecting peers: this makes it easy for Alice to be sure she'll hear about a new block as soon as possible by connecting to every one of those peers with a high-speed, low-latency connection. Bizzarely the idea does work if the advertised nodes only accept blocks, and never send blocks - instead miners would *only* send their blocks to other miners who have proven their hashing power, and do so essentially largest miner to smallest. Now unless Alice already is a large miner, her strategy can't work. Of course this will strongly encourage further centralization of pools. But it is in the interests of rational miners sadly. That blocks take a finite amount of time to propagate makes the problem worse: for Alice to learn that another block has been mined only requires her to receive the small 80 byte header from a peer; she doesn't need the whole block. She thus can know the block exists well before it has a chance to propagate fully. Even if every miner were directly peered to every other as some suggest, Alice could simply make smaller blocks, faster propagating than everyone else and use especially low-latency connections to win the race. On the other hand, the Bitcoin protocol is currently designed such that a miner can mine a block without knowing the previous block in full. Given the large block reward and/or a supply of transactions they knew no other miner had a rational miner would start trying to extend the longest chain they know about prior to actually receiving and validating the full block. Again, when miners start doing this - perhaps out of desperation due to low revenue - as long as Alice has the lowest latency network she'll win. (she doesn't even need to have the highest bandwidth in this case) We can change the protocol to force miners to fully validate blocks prior to mining extensions, but that only forces Alice to get more bandwidth - she still wins. Speaking of low-latency, latency not only centralizes control in a single pool, it centralizes pools and even mining hardware itself in a single physical location. Anyone at the edges of the propagation network will get comparatively less revenue than those in the center, gradually tightening the network, even without selfish mining. Alice's strategy of course should be to position her nodes in the geographical center. It's worth noting how if Alice is the one with the lowest average latency, she will win against any other miner trying to persue the same selfish miner strategy that she is using. Finally nLockTime makes the selfish miner strategy even more profitable. You may not be aware, but it's possible to make a transaction that can't be mined until some time in the future, measured by either block height or block timestamp. I've proposed to use this mechanism in announce/commit sacrifices: you create a transaction that can't be mined until some point in the future that sacrifices a large amount to mining fees, and then prior to that point you include it in the blockchain as data, proving the whole world knew about your transaction. The idea was that which miner managed to include the transaction, and collect the reward, would be random. However whenever Alice is able to maintain a lead over other miners she's able to reliably mine significantly more of those valuable transactions, further increasing her revenue over other miners. I must say, you've really opened a can of worms... --=20 'peter'[:-1]@petertodd.org 000000000000000379e2a349ccee65efc29d43e2c742f8e4a9247d68025ace84 --/04w6evG8XlLl3ft Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJSeAvzAAoJEBmcgzuo5/CFoEAIAICqo4+Pn2IqB9w98oYtDEbm 8xi7S5X96/Ow4fpa/cPvZivYqsRlR0B+4o82cxT8WC6Omv57ZyXvHbNDrZJjVhN7 7Wf8saRmR/PswMv8IG1oAli4ejfdBugRSw+MXyk7anXrCNHospnaOs+jFe2pM4i9 095YrZfDrFEWP08ypVj6hLRP2dRsLqLoGmkiCZj9JXc/lrSV1rWb78FvYYFMIxjV +taSdokA0vm/eQuUUimDxpbXSxDLKAREMEX4pYgZ6x2AQ9rjRjuFP6uk1M1Y3BOk h8oJ45OC8rOlkhVLwUEZdkSncOgIyL0jdx3tRqVwohtoVqH+NE/VSXc3h3P78es= =VxC/ -----END PGP SIGNATURE----- --/04w6evG8XlLl3ft--