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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
Return-Path: <naumenko.gs@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 6A64F1B02
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 May 2019 00:11:59 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com
[209.85.210.171])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 48F3EA9
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 May 2019 00:11:58 +0000 (UTC)
Received: by mail-pf1-f171.google.com with SMTP id u17so10312678pfn.7
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 27 May 2019 17:11:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=date:from:to:message-id:in-reply-to:references:subject:mime-version;
bh=97mAbHkDzW+C9AAzia9XEB94AyCzewioQYQT2a8S554=;
b=JdICXyyjbio00vQYioyPVbYlwb0Cj+b4h83T0LxUe8da+C8LWim+8GYu4ZKscu2GUb
X50ggfAO02l5FkHMvIUECtsolQtE1FrG4f8aK8xtDEFVchTtDTwGcHXw5o7c8eA4qZCb
yasQ59X7BBvPRFH1J2vl2ZvXbie20Jja7UdL8fqvjglURaB+bFeB77A6GF7SAMXzp6ef
QSFENZ192GVJfoT9gkPRSl1ULbrCBDyw/mHcTQaeolYhA545V5d3zuCPeZTg9UInvYxJ
BY69vVTn7ZPRP2UT2+VDf3MwcNBpSal3nkhrkY0mdwf0bM398PGyuvq2B1DVFeiaAO5L
IBuw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:date:from:to:message-id:in-reply-to:references
:subject:mime-version;
bh=97mAbHkDzW+C9AAzia9XEB94AyCzewioQYQT2a8S554=;
b=tqB22MQ0/GW6wO+hr5+Wo7mXiMaX2Gzbvd8VDULgB2GRkOdmNH6RCJ4xIxE18wjuvI
wNn4n7UUSChvgotByZ6UWBCzW/kPzCy7zn4iQDr8gVJlHSvuhgixrokH5n6AyX6sGTTK
clM7v5nbNsP5cd1wmu2k9hQQ80YqDcGAHynUcTSATGiO8kNU/H8knh1yKGGLzzdeVduk
1pNoqcckCgD8vuwtHBFKI/qnr+79fLSYXBe77vuxAJrBiZWadoq+rlCCYMFbkXQv7zj+
b/OGlGdS1aFd7cmtUrXbe+YHFZv65vZSLy9BBDpx37zH4zgpdsrAvmiQmFHjLLXo/zsk
BvLQ==
X-Gm-Message-State: APjAAAVIsg29ca5x53Kij1a2uRUi4XHPQyhD8mmkimnXRoORrbcUTRBZ
wtfboHPo4c4dKN67V1evHer7mdybEhM=
X-Google-Smtp-Source: APXvYqzMdvYSIU7WAOMlB8OLgKMGwrs2ShAzcCLJBbtRed0a1adoZcVIF+kYz00pAwZESC2yQCsdpg==
X-Received: by 2002:a63:454e:: with SMTP id u14mr235061pgk.377.1559002317250;
Mon, 27 May 2019 17:11:57 -0700 (PDT)
Received: from [10.0.19.154] (s206-116-45-202.bc.hsia.telus.net.
[206.116.45.202])
by smtp.gmail.com with ESMTPSA id x1sm6123855pgq.13.2019.05.27.17.11.55
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Mon, 27 May 2019 17:11:56 -0700 (PDT)
Date: Mon, 27 May 2019 17:11:50 -0700
From: Gleb Naumenko <naumenko.gs@gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <d9eda8a2-4c96-4dec-a34a-cd184eb8aeda@Spark>
In-Reply-To: <dc505296-d415-443b-be76-90b254853eea@Spark>
References: <dc505296-d415-443b-be76-90b254853eea@Spark>
X-Readdle-Message-ID: d9eda8a2-4c96-4dec-a34a-cd184eb8aeda@Spark
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="5cec7ccb_66ef438d_14b"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Tue, 28 May 2019 02:52:29 +0000
Subject: [bitcoin-dev] Bandwidth-Efficient Transaction Relay for Bitcoin
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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: Tue, 28 May 2019 00:11:59 -0000
--5cec7ccb_66ef438d_14b
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Hi all,
We are making public our latest work on Erlay, an efficient transaction r=
elay protocol for Bitcoin.
It is available here:=C2=A0https://arxiv.org/abs/1905.10518
The main idea is that instead of announcing every transaction to every pe=
er, announcements are only sent directly over a small number of connectio=
ns (only 8 outgoing ones). =46urther relay is achieved by periodically ru=
nning a set reconciliation protocol over every connection between the set=
s of withheld announcements in both directions.
The set reconciliation protocol uses error correcting codes to communicat=
e a set of transactions to a peer with an unknown but similar set using b=
andwidth only equal to the size of the difference and not the size of the=
sets themselves.
Results: we save half of the bandwidth a node consumes, allow increasing =
connectivity almost for free, and, as a side effect, better withstand tim=
ing attacks.
If outbound peer count were increased to 32, Erlay saves around 75% overa=
ll bandwidth compared to the current protocol.
This work uses Minisketch, an efficient library for set reconciliation, w=
hich we made public before:=C2=A0github.com/sipa/minisketch.
Some of you may already know about it from discussions with me, Scaling B=
itcoin 18, or CoreDev in Tokyo. Our proposal has become more precise sinc=
e then.
The next step here is to receive more feedback, have a broader discussion=
, and then write a BIP along with improving reference implementation. We =
are looking forward to hearing your suggestions or concerns regarding thi=
s work.
This protocol is a result of work by myself, Gregory Maxwell, Pieter Wuil=
le, and my supervisors at UBC: Ivan Beschastnikh and Sasha =46edorova.
I would like to thank Tim Ruffing and Ben Woosley for contributions to th=
e write-up, and Blockstream for supporting my work on this protocol.
=E2=80=93 gleb
--5cec7ccb_66ef438d_14b
Content-Type: text/html; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
<html xmlns=3D=22http://www.w3.org/1999/xhtml=22>
<head>
<title></title>
</head>
<body>
<div name=3D=22messageBodySection=22 style=3D=22font-size: 14px; font-fam=
ily: -apple-system, BlinkMacSystem=46ont, sans-serif;=22>
<div dir=3D=22auto=22>Hi all,<br />
<br />
We are making public our latest work on Erlay, an efficient transaction r=
elay protocol for Bitcoin.
<div dir=3D=22auto=22>It is available here:&=23160;<a href=3D=22https://a=
rxiv.org/abs/1905.10518=22>https://arxiv.org/abs/1905.10518</a><br />
<br />
The main idea is that instead of announcing every transaction to every pe=
er, announcements are only sent directly over a small number of connectio=
ns (only 8 outgoing ones). =46urther relay is achieved by periodically ru=
nning a set reconciliation protocol over every connection between the set=
s of withheld announcements in both directions.<br />
<br />
The set reconciliation protocol uses error correcting codes to communicat=
e a set of transactions to a peer with an unknown but similar set using b=
andwidth only equal to the size of the difference and not the size of the=
sets themselves.<br />
<br />
Results: we save half of the bandwidth a node consumes, allow increasing =
connectivity almost for free, and, as a side effect, better withstand tim=
ing attacks.<br />
If outbound peer count were increased to 32, Erlay saves around 75% overa=
ll bandwidth compared to the current protocol.<br />
<br />
This work uses Minisketch, an efficient library for set reconciliation, w=
hich we made public before:&=23160;<a href=3D=22http://github.com/sipa/mi=
nisketch=22>github.com/sipa/minisketch</a>.<br />
<br />
Some of you may already know about it from discussions with me, Scaling B=
itcoin 18, or CoreDev in Tokyo. Our proposal has become more precise sinc=
e then.<br />
<br />
The next step here is to receive more feedback, have a broader discussion=
, and then write a BIP along with improving reference implementation. We =
are looking forward to hearing your suggestions or concerns regarding thi=
s work.<br />
<br />
This protocol is a result of work by myself, Gregory Maxwell, Pieter Wuil=
le, and my supervisors at UBC: Ivan Beschastnikh and Sasha =46edorova.<br=
/>
I would like to thank Tim Ruffing and Ben Woosley for contributions to th=
e write-up, and Blockstream for supporting my work on this protocol.<br /=
></div>
</div>
</div>
<div name=3D=22messageSignatureSection=22 style=3D=22font-size: 14px; fon=
t-family: -apple-system, BlinkMacSystem=46ont, sans-serif;=22><br />
<div dir=3D=22auto=22>=E2=80=93 gleb</div>
</div>
</body>
</html>
--5cec7ccb_66ef438d_14b--
|
