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-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V1vbE-0000fl-Jv for bitcoin-development@lists.sourceforge.net; Wed, 24 Jul 2013 09:43:12 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.75 as permitted sender) client-ip=62.13.149.75; envelope-from=pete@petertodd.org; helo=outmail149075.authsmtp.net; Received: from outmail149075.authsmtp.net ([62.13.149.75]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1V1vbA-0006u2-V9 for bitcoin-development@lists.sourceforge.net; Wed, 24 Jul 2013 09:43:12 +0000 Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) by punt14.authsmtp.com (8.14.2/8.14.2/) with ESMTP id r6O9h0lc082715; Wed, 24 Jul 2013 09:43:00 GMT 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 r6O9gtWS055498 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Wed, 24 Jul 2013 10:42:58 +0100 (BST) Date: Wed, 24 Jul 2013 05:42:55 -0400 From: Peter Todd To: Tier Nolan Message-ID: <20130724094255.GB12568@savin> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="RASg3xLB4tUQ4RcS" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 6ca2e85d-f445-11e2-b10b-0025903375e2 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAYUEkAYAgsB AmUbWlReVF97XGs7 bAxPbAVDY01GQQRq WVdMSlVNFUsqB2MI UVp5MRl3cgFPcDBx YUVrWj5dDxV4IE54 FlMCEWkDeGZhPWIC AkFYJR5UcAFPdx9G aVd6AXFDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4nHyUg XREIACkuG0JNQyIs ZyQBFRYcEU8dP18p WQAA X-Authentic-SMTP: 61633532353630.1019: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: 1V1vbA-0006u2-V9 Cc: bitcoin-development@lists.sourceforge.net Subject: Re: [Bitcoin-development] Distributing low POW headers 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, 24 Jul 2013 09:43:12 -0000 --RASg3xLB4tUQ4RcS Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Jul 23, 2013 at 12:27:03PM +0100, Tier Nolan wrote: > I was thinking about a change to the rules for distinguishing between for= ks > and maybe a BIP.. Please provide equations and data justifying the 'magic constants' in this proposal. Currently we do not relay blocks to peers if they conflict with blocks in the best known chain. What changes exactly are you proposing to that behavior? > *Summary* >=20 > - Low POW headers should be broadcast by the network >=20 > If a header has more than 1/64 of the POW of a block, it should be > broadcast. This provides information on which fork is getting most of the > hashing power. >=20 > - Miners should use the header information to decide on longest chain >=20 > The fork selection rule for miners should be biased towards staying on the > fork that has the most hashing power. >=20 > This means that they might keep hashing on a fork that is 1-2 blocks > shorter. >=20 > If most miners follow the rule, then it is the best strategy for other > miners to also follow this rule. >=20 > - Advantages >=20 > This lowers the probability of natural and malicious reversals. >=20 > *Distributing low POW headers* >=20 > First block header messages that have more than 1/64 of the standard POW > requirements would be forwarded. >=20 > This means the client needs to maintain a short term view of the entire > header tree. >=20 > if (header extends header tree) { > if (header meets full POW) { > add to header tree; > forward to peers; > check if any blocks in storage now extend the header tree > } else { > if (header meets POW / 64) { > forward to peers; > } > } else { > if (header meets POW) { > add to orphan header storage > } > } >=20 > The storage could be limited and headers could be discarded after a while. >=20 > This has the extra advantage that it informs clients of forks that are > receiving hashing power. >=20 > This could be linked to a protocol version to prevent disconnects due to > invalid header messages. >=20 > *Determining the longest chain* >=20 > Each link would get extra credit for headers received. >=20 > Assume there are 2 forks starting at block A as the fork point. >=20 > A(63) <- B(72) <- C(37) <- D(58) >=20 > and >=20 > A(63) <- B'(6) <- C'(9) <- D'(4) <- E(7) <- F(6) >=20 > The numbers in brackets are the number of low POW headers received that > have those blocks as parent. >=20 > The new rule is that the POW for a block is equal to >=20 > POW * (1 + (headers / 16)) >=20 > Only headers within of the end of the (shorter) chain > count. However, in most cases, that doesn't matter since the fork point > will act as the start point. As long as miners keep headers for 30-40 > blocks, they will likely have all headers back to any reasonable fork poi= nt. >=20 > This means that the top fork is considered longer, since it has much more > headers, even though it has 2 less blocks. >=20 > If 75% of the miners follow this rule, then the top fork will eventually > catch up and win, so it is in the interests of the other 25% to follow the > rule too. >=20 > Even if there isn't complete agreement on headers received, the fork that > is getting the most hashing will naturally gain most of the headers, so > ties will be broken quickly. --=20 'peter'[:-1]@petertodd.org 000000000000001e1c3393788031c4e427b67cfd1b5e90a3b0de4fff094b2894 --RASg3xLB4tUQ4RcS Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJR76GeAAoJECSBQD2l8JH7hAIH/icO10VXLr8y0Z8xczfA/vFB /OkM7/c5DuowwNHjAdPHAS5eyIsWuOaeP4UQ6u++x2GPZr8Z5rQSsQSTelMWzo/W ec5n2gIQ5EJuBMMY57Txcuy8H7aL5iJruWWXVfqfVDkILRP9HZdJsK7IzKiy94Af 6PBAQ3cMMt7EPVJMvztS90vZKLPRd+HvNMCpxByr+oFA5FrguOwk6VTPOOHUjjk2 dED5GOueHVhV8TpJoEacJOXeGT/T1zFvVZw6ZMi3QGIF8sHOq5wnGv6m3/lbOhWY YzRpYB8QxeMG6tXXg5M+4ZX8fHI1VT0Z/7MWgjo9bMNJwBc6dqyhPzSxIj/0QDY= =J0Cf -----END PGP SIGNATURE----- --RASg3xLB4tUQ4RcS--