Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1VO6HY-0005Uu-OE for bitcoin-development@lists.sourceforge.net; Mon, 23 Sep 2013 13:34:32 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.113 as permitted sender) client-ip=62.13.149.113; envelope-from=pete@petertodd.org; helo=outmail149113.authsmtp.com; Received: from outmail149113.authsmtp.com ([62.13.149.113]) by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1VO6HX-0006Dj-4O for bitcoin-development@lists.sourceforge.net; Mon, 23 Sep 2013 13:34:32 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt5.authsmtp.com (8.14.2/8.14.2) with ESMTP id r8NDYPbG082766 for ; Mon, 23 Sep 2013 14:34:25 +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 r8NDYJRw074459 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO) for ; Mon, 23 Sep 2013 14:34:22 +0100 (BST) Date: Mon, 23 Sep 2013 09:34:19 -0400 From: Peter Todd To: bitcoin-development@lists.sourceforge.net Message-ID: <20130923133419.GB4400@savin> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="kXdP64Ggrk/fb43R" Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: db70ab1a-2454-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hXKl1LNVAaWXld WiVPGEoXDxgzCjYj NEgGOBsDNw4AXQZ1 Mx0JXVBSFQZ4ABgL BRoUUBs8cANYeX5u ZEFqQHFbVVt/fUFi QwAWHRNyDB0CL2AY VERdfk1VdwpOdlER OFd/BSEMMHgFYn9k WlZqMmt0N2UHcmEN GltQfAobGBsHF2Eq YR0LB3AlGUoORG05 NRsvJlUVB1oKeks1 KxM5Q1UfPVcVBEVC DwlVGihBLlYIWyss C2sA 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: 1VO6HX-0006Dj-4O Subject: [Bitcoin-development] Near-block broadcasts for proof of tx 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: Mon, 23 Sep 2013 13:34:33 -0000 --kXdP64Ggrk/fb43R Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Currently there is no way for a node, SPV or otherwise, to know if a transaction has been broadcast succesfully to any amount of hashing power. This makes it difficult to determine if a transaction failed to either propagate across the network, or failed to pay sufficient fees to be worthy of inclusion in a block. Broadcasting blocks that almost, but not quite, met the difficulty target provides clients with fast and honest proof about the hashing power mining their transaction. This proof is inherently honest because making a "near-block" is an expensive operation; additionally given at least one honest peer a node can detect near-block censorship by any other peer statistically. Limitations of fee estimation =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D Mempool-based fee estimation is limited by the ability of peers to lie, particularly to SPV peers. Miners wishing to increase fees can conduct sybil attacks where they lie to peers about the average fees required to get transactions into blocks. This problem is particularly dangerous given the lack of incentives to run full-nodes in the first place; the number of full nodes has continued to drop over time as users switch to SPV clients and web-wallets; it would be unfortunate if users started switching to web-wallets because they could offer better fee estimation. In any case creating monetary incentives to sybil the network is very undesirable. Out-of-band fee payment has the opposite effect of making fees in blocks appear lower than actually required to get them mined; transactions will get stuck unless an initial bad estimate can be replaced with a higher paying one. The payment protocol makes out-of-band fee payment attractive in the case where you want to accept a payment from a customer and pay the fee for them; child-pays-for-parent wastes money paying for additional blockchain space. Replacement-based schemes allow for recovery from stuck too-low transactions, but they are still succeptable to sybil attacks. (don't relay the transaction to other pools) Miner incentives to create near blocks =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Why would a miner want to go to the trouble of broadcasting a near block anyway? Wouldn't it be better if users didn't get feedback about fees and over-paid instead? If you are a large miner as a % of total profit efforts such as sybiling the network have a greater rate of return; if you are a small miner the greater income you receive from deception is outweighed by the cost. Thus you have an incentive to provide mechanisms to force larger miners to behave honestly. Secondly near-blocks could help "pre-propagate" transactions that will be mined in the near future, thus reducing block propagation times and hence orphan rates. (the pre-propagation can use the proof-of-work to rate-limit transactions that nodes would otherwise not forward, also allowing non-full nodes to safely participate in relaying) Again, this is something that most interests smaller miners with less peak bandwidth rather than large pools. In the event of a fork near blocks can be used to more quickly determine which side of the fork has the majority of hashing power, allowing the minority side to switch sooner. Again the reduction in orphan rates benefits smaller miners more than larger ones. (though note how only near-block headers are required for this application) Contents of a near block =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =46rom the miner incentives we see that near blocks should contain two types of information: 1) Transactions known to the miner, but not included in the current block. This information allows nodes to determine if a transaction they have broadcast was succesfully propagated to the majority of hashing power regardless of whether or not it is being mined, allowing nodes to avoid sybil attacks attempting to censor the transactions they make. This information needs to be committed separately in the coinbase tx. The incentive for miners here is to ensure that no-one can gain an unfair advantage with a sybil attack. 2) Transactions the miner is attempting to mine, proved by the merkle root. The incentives here are allowing non-full nodes to safely propagate transactions, improving block propagation, as well as further preventing deception by larger miners. Transaction mutability complicates both #1 and #2. In the case of #1 nodes can exploit mutability while relaying transactions, although at least relaying mutability is increasingly difficult; the incentives are such that the miners themselves have no reason to lie about the txids they know of. For #2 the incentives are all harmed by mutating transactions, so again we can expect miners to either leave transactions as they are, or simply not publish near blocks at all. Bandwidth usage is reasonable: the average transaction from the last 10,000 blocks is 450 bytes. Both data sets can be delta compressed against previously sent txids. Even a naive implementation that sends full txids would result in near blocks that are about 1/10th of the size of full blocks. (32-byte txids, and 1/4 of that amount in the "seen but not mined" list) The machinery for near blocks can also be easily re-used to implement improved full-block relaying with transactions in blocks being referenced to by txid. Replacement with near blocks =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D An node making a transaction can do the following: 1. Broadcast the transaction with an initial estimated fee. (the txid is added to the bloom filter here) The estimate can safely be be on the low side. 2. Wait 3. If transaction still hasn't appeared in either a block or near block, rebroadcast with a higher fee, either by replace-by-fee method, or zero-conf safe method of adding an additional txin+txout. Peers practicing censorship of either transactions or near blocks can be detected statisticly by preferring to connect to peers that provide more near blocks. Note how a short 80-byte near block header is sufficient information to detect a peer withholding near blocks, and that header can be relayed by SPV peers safely. If the transaction fails to get into the "seen-but-not-mined" list, a node can use that failure as an indication to find other peers to relay too. Currently SPV clients are vulnerable to their peers withholding valid bloom filter matches; future UTXO commitments can be designed to make this impossible, and spot-check auditing can detect it now. Out-of-band fee payment with near blocks =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D A purchaser of out-of-band fee payment services can use near-blocks to check that their fee offer has been accepted and miners are mining their transaction. This would be particularly useful for a decentralized system where offers backed by fidelity bonds are made; it would be good to encourage such systems over arrangements between purchasers and large pools. Security =3D=3D=3D=3D=3D=3D=3D=3D There is a serious problem however with proof-of-propagation and proof-of-mining: they let miners cheat. The proof that a given transaction is being mined can be used to mine the transaction yourself, without having to maintain a copy of the UTXO set or indeed do any validation at all. Having said that this risk already exists due to P2Pool, which forwards transactions along with shares already. In any case, it's yet another argument that we need miners to prove they possess the UTXO set. --=20 'peter'[:-1]@petertodd.org --kXdP64Ggrk/fb43R Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQEcBAEBCAAGBQJSQENaAAoJECSBQD2l8JH7YeYH/1QyC06BNzYUmLzhB2zsLDvE zgPh7csB1mEA0x4TZaZF18LwD5vb0dTOwNA5hT2ONPcFNq1IAWx+9uAfx8yVdSy8 8PtU07LBuswiD45MaZPIfe+WaGRBC8s1U2fSnkUQNSKOhwMH1fg6JmFHyg7ZZkM6 oXNUj2GCpb7jG6jtIYju8YWzFD+xXrr3BuYXjYAFS0ISGP55XFx+q0qnB0CfTAUD u6QVHWWDnRYlHIf7vYX88ZuCXM6x4HOW6/ehoyL+nzRKvvtYSxpWxjKQdEp4A4SN d3yiasplR49iG8mOID9J/L7PtSfpWIzK0NUR/r/PhnQJi8rkZ43W8V4mfLxOa+4= =KARG -----END PGP SIGNATURE----- --kXdP64Ggrk/fb43R--