From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9B3E2CDB for ; Sat, 27 Feb 2016 09:08:27 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from d.mail.sonic.net (d.mail.sonic.net [64.142.111.50]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3A1DBAB for ; Sat, 27 Feb 2016 09:08:27 +0000 (UTC) Received: from [192.168.1.190] (63.135.62.197.nwinternet.com [63.135.62.197] (may be forged)) (authenticated bits=0) by d.mail.sonic.net (8.15.1/8.15.1) with ESMTPSA id u1R98NiD024768 (version=TLSv1 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT) for ; Sat, 27 Feb 2016 01:08:24 -0800 Content-Type: multipart/signed; boundary="Apple-Mail=_51FF7605-FCED-4B2E-A8F7-8399187DB976"; protocol="application/pgp-signature"; micalg=pgp-sha512 Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\)) X-Pgp-Agent: GPGMail 2.6b2 From: Jonathan Toomim In-Reply-To: <05C32A45-2EE8-4808-A0C6-18B1C30A8E1C@toom.im> Date: Sat, 27 Feb 2016 01:08:22 -0800 Message-Id: <52B8920A-1482-4662-BC90-1A2A9BF8F924@toom.im> References: <05C32A45-2EE8-4808-A0C6-18B1C30A8E1C@toom.im> To: Bitcoin Dev X-Mailer: Apple Mail (2.3112) X-Sonic-CAuth: UmFuZG9tSVZMs2dKxj7d7kmIAzg4p7KXRCVY12B+tjtT3zLr42hykfpYsNCrsC7vMmOjtagTG+pDcz74QVaxDCaDJHoFJsXs X-Sonic-ID: C;ZihgpzHd5RGvW00iDwNmVA== M;VGbopzHd5RGvW00iDwNmVA== X-Sonic-Spam-Details: 0.0/5.0 by cerberusd X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] INV overhead and batched INVs to reduce full node traffic X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 27 Feb 2016 09:08:27 -0000 --Apple-Mail=_51FF7605-FCED-4B2E-A8F7-8399187DB976 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii Well, here's another idea: we could shorten the tx hashes to about 4 to = 6 bytes instead of 32. Let's say we have a 1 GB mempool with 2M transactions in it. A 4 byte = shorthash would have a 0.046% chance of resulting in a collision with = another transaction in our mempool, assuming a random distribution of = hash values. Of course, an attacker might construct transactions specifically for = collisions. To protect against that, we set up a different salt value = for each connection, and for the INV message, we use a 4 to 6 byte = salted hash instead of the full thing. In case a peer does have a = collision with one salt value, there are still 7 other peers with = different salt values. The probability that they all fail is about = 2.2e-27 with a 4-byte hash for a single peer. If we have 500,000 full = nodes and 1M transactions per 10 minutes, the chance is 1.1e-15 that = even one peer misses even one transaction. This strategy would come with about 12 bytes of additional memory = overhead per peer per tx, or maybe a little more. In exchange for that = 12 bytes per peer*tx, we would save up to 28 bytes per peer*tx of = network bandwidth. In typical conditions (e.g. 100-ish MB mempool, 16 = peers, 2 MB blocks, 500 B serialized tx size), that could result in = 1.792 MB net traffic saved per block (7.7 GB/month) at the expense of 12 = MB of RAM. Overall, this technique might have the ability to reduce INV = traffic by 5-8x in the asymptotic case, or maybe 2-3x for a realistic = case. I know short hashes like this have been proposed many times before for = block propagation (e.g. by Gavin in his O(1) scaling gist, or in XTB). = Has anyone else thought of using them like this in INV messages? Can = anyone think of any major problems with the idea? --Apple-Mail=_51FF7605-FCED-4B2E-A8F7-8399187DB976 Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP using GPGMail -----BEGIN PGP SIGNATURE----- Comment: GPGTools - https://gpgtools.org iQEcBAEBCgAGBQJW0WeHAAoJEIEuMk4MG0P1IH4IANBcsFWiwUFi+l1mndnjx52i nkiyWAhdGsvqdZVv6VbKCzhRskdQM8f5SnIsQ5YSMLIPyeyLBVheVwhAyvC4bsch 2ZNyOpFUZMtujjbErchpXwxYWxiVZ7w81tlpnThtqs+xv/tpFsnjU360luONKWfU HTVYQVdY3fZFkGYMVM2Axbbt7wsfT7BmBvOsKrI7WmU0B20HlIaAw42GEluySoGl Dmn3TGO0kLNKXyL589ZwkmTSvsO7zvUuztIe5L7z0J/MJZw8mmPnvcI8etaJGqAk nAqzrZr4BUe1xSBeu7Ae67a2LO6Mda6WnLWkoH3VKVb04nxCw8DDpuo8H5jDLH0= =8i0+ -----END PGP SIGNATURE----- --Apple-Mail=_51FF7605-FCED-4B2E-A8F7-8399187DB976--