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\))
From: Jonathan Toomim <j@toom.im>
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: <B186E7A6-0FD4-4C82-B42F-7EE61D420A7E@toom.im>
	<CAAS2fgTTUjVUx0GQYed-tWnH4RmS0tpv2yrpCOGJSeW8kJkYiw@mail.gmail.com>
	<05C32A45-2EE8-4808-A0C6-18B1C30A8E1C@toom.im>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] INV overhead and batched INVs to reduce full node
	traffic
Precedence: list


--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--