From: Jonathan Toomim <j@toom.im>
Content-Type: multipart/signed;
	boundary="Apple-Mail=_9AF4F793-F5F2-48EB-9981-8B07B9B69FB3";
	protocol="application/pgp-signature"; micalg=pgp-sha512
Date: Thu, 25 Feb 2016 21:35:14 -0800
Message-Id: <B186E7A6-0FD4-4C82-B42F-7EE61D420A7E@toom.im>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\))
Subject: [bitcoin-dev] INV overhead and batched INVs to reduce full node
	traffic
Precedence: list


--Apple-Mail=_9AF4F793-F5F2-48EB-9981-8B07B9B69FB3
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_66A93333-4E04-49C8-BC47-ADDA071CABD1"


--Apple-Mail=_66A93333-4E04-49C8-BC47-ADDA071CABD1
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

The INV scheme used by Bitcoin is not very efficient at all. Once you =
take into account Bitcoin, TCP (including ACKs), IP, and ethernet =
overheads, each INV takes 193 bytes, according to wireshark. That's 127 =
bytes for the INV message and 66 bytes for the ACK. All of this is for =
32 bytes of payload, for an "efficiency" of 16.5% (i.e. 83.5% overhead). =
For a 400 byte transaction with 20 peers, this can result in 3860 bytes =
sent in INVs for only 400 bytes of actual data.

An improvement that I've been thinking about implementing (after =
Blocktorrent) is an option for batched INVs. Including the hashes for =
two txes per IP packet instead of one would increase the INV size to 229 =
bytes for 64 bytes of payload -- that is, you add 36 bytes to the packet =
for every 32 bytes of actual payload. This is a marginal efficiency of =
88.8% for each hash after the first. This is *much* better.

Waiting a short period of time to accumulate several hashes together and =
send them as a batched INV could easily reduce the traffic of running =
bitcoin nodes by a factor of 2, and possibly even more than that. =
However, if too many people used it, such a technique would slow down =
the propagation of transactions across the bitcoin network slightly, =
which might make some people unhappy. The ill effects could likely be =
mitigated by choosing a different batch size for each peer based on each =
peer's preferences. Each node could choose one or two peers to which =
they send INVs in batches of one or two, four more peers in which they =
send batches of two to four, and the rest in batches of four to eight, =
for example.

(This is a continuation of a conversation started on =
https://bitcointalk.org/index.php?topic=3D1377345 =
<https://bitcointalk.org/index.php?topic=3D1377345.new#new>.)

Jonathan

--Apple-Mail=_66A93333-4E04-49C8-BC47-ADDA071CABD1
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=us-ascii

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" =
class=3D""><div class=3D"">The INV scheme used by Bitcoin is not very =
efficient at all. Once you take into account Bitcoin, TCP (including =
ACKs), IP, and ethernet overheads, each INV takes 193 bytes, according =
to wireshark. That's 127 bytes for the INV message and 66 bytes for the =
ACK. All of this is for 32 bytes of payload, for an "efficiency" of =
16.5% (i.e. 83.5% overhead). For a 400 byte transaction with 20 peers, =
this can result in 3860 bytes sent in INVs for only 400 bytes of actual =
data.</div><div class=3D""><br class=3D""></div><div class=3D"">An =
improvement that I've been thinking about implementing (after =
Blocktorrent) is an option for batched INVs. Including the hashes for =
two txes per IP packet instead of one would increase the INV size to 229 =
bytes for 64 bytes of payload -- that is, you add 36 bytes to the packet =
for every 32 bytes of actual payload. This is a marginal efficiency of =
88.8% for each hash after the first. This is *much* better.</div><div =
class=3D""><br class=3D""></div><div class=3D"">Waiting a short period =
of time to accumulate several hashes together and send them as a batched =
INV could easily reduce the traffic of running bitcoin nodes by a factor =
of 2, and possibly even more than that. However, if too many people used =
it, such a technique would slow down the propagation of transactions =
across the bitcoin network slightly, which might make some people =
unhappy. The ill effects could likely be mitigated by choosing a =
different batch size for each peer based on each peer's preferences. =
Each node could choose one or two peers to which they send INVs in =
batches of one or two, four more peers in which they send batches of two =
to four, and the rest in batches of four to eight, for =
example.</div><div class=3D""><br class=3D""></div><div class=3D"">(This =
is a continuation of a conversation started on&nbsp;<a =
href=3D"https://bitcointalk.org/index.php?topic=3D1377345.new#new" =
class=3D"">https://bitcointalk.org/index.php?topic=3D1377345</a>.)</div><d=
iv class=3D""><br class=3D""></div><div =
class=3D"">Jonathan</div></body></html>=

--Apple-Mail=_66A93333-4E04-49C8-BC47-ADDA071CABD1--

--Apple-Mail=_9AF4F793-F5F2-48EB-9981-8B07B9B69FB3
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

iQEcBAEBCgAGBQJWz+QTAAoJEIEuMk4MG0P1Ai0H+QF4WQlpUe4j9qPfkSdCfxis
d7H2sm038ISefa0nNSztK07jczCu+uA5xB7tdotDIJ3ukFTZ1QhxZMxhcs5I0rq7
Wjc0Id/nsg0FJO5VBfI9Jg7ZrEEnwnJBud7I7oqk8bFTfEXt4xFXiIOOge7wkoeT
zOoQuzIUfSa6WKbSr7XdV1R2BvjQrfyjhdB13wrw7qie4Xt6kh5oXViTVsrIZZXS
HHSTuK0db1KbyHIsgUNHcLhbFJfzbknH7gqM7K7MJDrOkuTwXe0UYYRliJFKtyEY
+y1AZJlVNjplIrcxOTeW3hcpDv43bQuhE7pD8ZO6FrztBQBsAjG5wtN5j6IL8/g=
=Osn2
-----END PGP SIGNATURE-----

--Apple-Mail=_9AF4F793-F5F2-48EB-9981-8B07B9B69FB3--