1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
Return-Path: <j@toom.im>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9B3E2CDB
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <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>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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--
|
