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 1Wcykf-0001pU-HS for bitcoin-development@lists.sourceforge.net; Wed, 23 Apr 2014 15:06:21 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.148.106 as permitted sender) client-ip=62.13.148.106; envelope-from=pete@petertodd.org; helo=outmail148106.authsmtp.co.uk; Received: from outmail148106.authsmtp.co.uk ([62.13.148.106]) by sog-mx-2.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1Wcykd-00006q-Mc for bitcoin-development@lists.sourceforge.net; Wed, 23 Apr 2014 15:06:21 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt18.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s3NF64Sx088453; Wed, 23 Apr 2014 16:06:04 +0100 (BST) Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s3NF5vTQ053827 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Wed, 23 Apr 2014 16:05:59 +0100 (BST) Date: Wed, 23 Apr 2014 11:05:55 -0400 From: Peter Todd To: Jonathan Levin Message-ID: <20140423150555.GE19430@savin> References: <52CDA01B-13BF-4BB8-AC9A-5FBBB324FD15@sant.ox.ac.uk> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="mR8QP4gmHujQHb1c" Content-Disposition: inline In-Reply-To: <52CDA01B-13BF-4BB8-AC9A-5FBBB324FD15@sant.ox.ac.uk> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: c7c792a7-caf8-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aQdMdAEUGUUGAgsB AmIbWlJeUFt7WWM7 bAxPbAVDY01GQQRq WVdMSlVNFUsrAmJ3 A1h6Mxl3dA1EfzB0 Z0BqXj4IWxd9fEQs RVMHRDsOeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4mFTk6 QBUDFi5nGkNNRiM9 KAYjI0IdG0BZKl81 KVIuUE4ZNBl6 X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/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 X-Headers-End: 1Wcykd-00006q-Mc Cc: bitcoin-research@lists.cs.princeton.edu, "bitcoin-development@lists.sourceforge.net" Subject: Re: [Bitcoin-development] Economics of information propagation 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: Wed, 23 Apr 2014 15:06:21 -0000 --mR8QP4gmHujQHb1c Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Mon, Apr 21, 2014 at 01:30:28AM +0000, Jonathan Levin wrote: CC'ing bitcoin-research - may be more appropriate to move the discussion there as this discussion is delving into future scenarios. > Hi all, >=20 > I am a post-graduate economist writing a paper on the incentives of minin= g. Even though this issue has been debated in the forums, I think it is imp= ortant to get a sense of the magnitude of the incentives at play and determ= ine what implications this has for the transaction fee market. >=20 > As it has been pointed out before the marginal cost for miners does not s= tem from the private cost of the miner validating the signature and includi= ng it in the list of transactions in the block but rather the increased pro= bability that the block will be orphaned as a result of slower propagation.= Gavin did some back of the envelope worst case calculations but these over= stated the effect of propagation delay. The reason being the 80ms additiona= l time to reach 50% of the network is spread throughout the time that it ta= kes to reach 50% of the network. During this time miners are notified about= the block and treat it as the longest chain and hence are no longer mining= with the aim to produce a competing block.=20 >=20 > I am looking to calculate the change in the curvature of the probability = mass function that a block hears about my block in any given second as a fu= nction of the block size. Although there is likely to be significant noise = here, there seems to be some stable linear relationships with the time that= it takes to reach different quartiles. Has anyone done this? I have used s= ome empirical data that I am happy to share but ideally I would like analyt= ical solutions. >=20 > Following Peter Todd, I also find the concerning result that propagation = delays results in increasing returns to higher shares of the hashing power.= Indeed it may well be in the interest of large pools to publish large bloc= ks to increase propagation delays on the network which would increase orpha= n rates particularly for small miners and miners that have not invested in = sufficient bandwidth / connectivity. If a small miner hears about a block a= fter 4.5 seconds on average there is a 0.7% chance that there is already a = block in circulation. Large miners can increase the time that it takes for= small miners to hear about blocks by increasing the size of their blocks. = For example if the time that it takes for a small miner to hear about the b= lock goes to 12 seconds there is a 2 percent chance there is already a bloc= k in circulation for the small miner. There is also a 1.2% chance that ther= e will be a competing block published after a small miner propagates in the= time that it gets to full propagation. Am I getting this right that the pr= obability of a miner=E2=80=99s block being orphaned is comprised of the pro= bability that the miner was not the first to find a valid block and the pro= bability that given they are first, someone else in the absence of hearing = about it finds a competing valid block.=20 >=20 > One question is: Are orphans probabilistic and only resolved after hearin= g about a new block that lengthens the chain or is there a way to know in a= dvance? They're probabilistic; mining is progress free so per unit hashing power every miner has an equal chance of finding a block. As for resolution, well, currently nodes (and miners) mine on the block they saw first; if they learn about another block at the same height they stick to the block they are already mining on. First seen at same height is probably generally economically rational as the first block you see probably propagated to the most nodes, although tweaks to that are probably possible. > Is it frowned upon to mine on top of a block that you have just found eve= n though it is very likely going to end up an orphan? Not at all, in fact mining on top of the block is the best thing to do because it *prevents* your block from ending up as an orphan. Basically imagine I find block b1a, and you find conflicting block b1b. What I need to do is find block b2a, which is on top of b1a, before you find block b1b to avoid my block being orphaned. The best way to do that is mining on top of my block - that's what's most rational for me. > Would be happy to share the draft form of the paper and receive any feedb= ack. Sure thing. > Finally, at coinometrics we are working on a modified client to capture i= nformation on network propagation and would invite any suggestions of any o= ther useful statistics that would be useful in the development of software.= =20 So looking at the replies your post got in the past few days it looks like there's some misinformation going around. First of all is the question of how harmful it is if miners mine on top of blocks that they haven't actually validated, and yes, that's extremely harmful. For instance if I were an attacker I could mine an invalid block that makes coins out of thin air and use it to defraud SPV-wallet-using clients; everyone who is mining without validating is helping me succesfully pull off that attack by increasing the chance I'll get enough confirms to trick my target into thinking the coins are real. (remember I could have stolen the hashing power by hacking into a pool) Mark Friedenbach suggested headers first where the block header and block contents are propagated around the network separately. What that results in has a few different scenarios: 1) Fee's don't matter and miners aren't forced to validate This is the scenario we're in right now. The block reward comprises the supermajority of mining income, and it is possible to mine a block without first validating the contents of the previous block. When a miner receives a block header that extends the longest known blockchain they can immediately switch to it and start mining. Whether or not doing so is rational is just a matter of what's the probability that the previous block was invalid? If it was, the miner mining it just wasted 25BTC, $12.5k, so you can be almost sure it is valid and you don't need to wait. Of course, if you then find a block, you can pull the same trick all over again and the next guy might be mining on top of two blocks they haven't validated, and so on. Obviously this presents a very nasty failure mode if the majority of miners follow this behavior and a block is invalid, or even just gets lost. Similarly in the majority scenario there's no direct incentive to actually propagate your blocks - they'll still get accepted to the main chain anyway. That said, small and large miners make roughly the same amount as the block reward dominates and blocks of any size will get confirmations fairly quickly. 2) Fee's do matter and miners aren't forced to validate Now transaction fees represent a non-trivial portion of a miner's income. Centralization incentives would depend on to what extent fees do matter. Again, there's some nasty failure modes possible. That large, slow-to-propagate blocks still get confirmed, yet small miners can't mine transaction fees is likely a major centralization incentive. 3) Miners are forced to validate Or at least, we can force miners to actually have the previous block. Andrew Miller's Permacoin is one approach; some varients of UTXO commitments have this as a side-effect too. On the one hand this solves the really nasty failure modes that headers-first has; on the other hand you're back to the centralization incentives we have right now. What's important however to remember is that any attempt at saying things like "[A]s soon as [Miners] receive and process the contents of block A, they switch to that." - as Mark suggested(2) - doesn't belong in an economic analysis as such rules are unenforcable. For instance that'd suggest that in the forced-validation headers-first scenario a large miner who received a block header, then found block themselves, would switch to mining the block they *didn't* find simply because they "got the header first". Obviously this is not economically rational for them to do so they won't, leading to the same centralization incentives as always. As for why that's economically irrational: so the large miner finds that second block and broadcasts it around the network. Do you the small miner keep mining on the shorter chain just because the large miner broke the gentlemans agreement to respect header times? Of course not, time is relative and you have no idea whether or not anyone else is doing so. If you mine on the shorter chain you're side is going to need to find two blocks to catch up - not likely. Secondly you risk forking the network due to a consensus failure, say by a divergent times the headers were received. 1) http://cs.umd.edu/%7Eamiller/permacoin.pdf --=20 'peter'[:-1]@petertodd.org 0000000000000000278031f86c71265f6eaf1fe9ce6cc831dc4f956676a7a7f7 --mR8QP4gmHujQHb1c Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) iQGrBAEBCACVBQJTV9bPXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDAyNzgwMzFmODZjNzEyNjVmNmVhZjFmZTljZTZjYzgzMWRj NGY5NTY2NzZhN2E3ZjcvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfsjEwf+NIHSyYo2cTjbcapbUl6b0cvS lOR+3grkLnitgCPRvSeaLjZRz4Wd3ZG0asOE4UKzk6ib7stia+PPq2KfxZbeYUAK UkJbB+HlTYaJzT0Bi8f08hLE8BxubpbYOj8zWs1APPApnlaWKKOYdr+m9X4Q773j 9zpOSH8tAV0OEu7qZYssqrmnmWMwjz1IfkXua78SrwCvc+QJ2RgTm4MdH6mEKcgT Xcc/SBi2bM/0cklS+IDNNpQo9gNWrqo4cvPDmllROg7ierskv6sW6IApc+uJzoer noMHGW+mkASbcVdmY7Y1Jop2Twc2TqZT4jnaouvaTRGhknnV0MGcjiz5LhRTqA== =x/OP -----END PGP SIGNATURE----- --mR8QP4gmHujQHb1c--