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>
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="5cec7ccb_66ef438d_14b"
Subject: [bitcoin-dev] Bandwidth-Efficient Transaction Relay for Bitcoin
Precedence: list

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