Date: Wed, 25 Sep 2019 14:28:00 +0300
From: Gleb Naumenko <naumenko.gs@gmail.com>
To: Bitcoin-Dev <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <8914e269-e922-43f4-8846-9fb21a8044f3@Spark>
In-Reply-To: <c06eeb3e-4611-4196-8d2f-f3c3470aeea3@Spark>
References: <c06eeb3e-4611-4196-8d2f-f3c3470aeea3@Spark>
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="5d8b4f45_3a95f874_4055"
Subject: [bitcoin-dev] New BIP for p2p messages/state enabling
 reconciliation-based protocols (Erlay)
Precedence: list

--5d8b4f45_3a95f874_4055
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

We are opening for review a draft of the new BIP, which describes low-lev=
el specifications for the reconciliation-based transaction announcement p=
rotocol.
https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawi=
ki

Agreeing on this spec would enable integration of more bandwidth-efficien=
t relay protocols, like Erlay (https://arxiv.org/abs/1905.10518).

The draft has all the background necessary to understand the work, so ple=
ase read and review.
It introduces salted short transaction IDs (required to do reconciliation=
 efficiently) and demonstrates how to compute sketches based on these IDs=
 (including simple python scripts).
It also introduces wtxid-based truncated transaction IDs (to trivially sa=
ve significant fraction of the bandwidth).
=46inally, it specifies all the messages to be used by an efficient recon=
ciliation-based protocol, and new state variables required for the protoc=
ol.

Please note that, comparing to the Erlay paper, we decided to add extra r=
ound, where 2 parties explicitly map 32-bit short IDs to 128-bit truncate=
d IDs, because otherwise peers which take >1s to reconcile would cause tr=
ansmitting duplicate transactions (extra bandwidth), and we cannot assume=
 <1s latency in Bitcoin, especially over Tor.
According to my estimates, the bandwidth overhead due to the measure from=
 the BIP (extra communication round) is only extra 10% comparing to the o=
riginal Erlay estimates.

It is possible that we missed some of the state variables required to han=
dle corner cases of the protocol, because the spec is based on my prototy=
pe code, and it might evolve when we will be building an actual productio=
n-ready implementation.

Overall, I believe that this spec is ready for review.

Even though this work does not require a fork, the change is quite signif=
icant, and peer-review is critical for the system, so please take a look.=
 =46eel free to reach out for questions and comments here or directly ove=
r email.

=E2=80=93 gleb

--5d8b4f45_3a95f874_4055
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>
<div dir=3D=22auto=22>We are opening for review a draft of the new BIP, w=
hich describes low-level specifications for the reconciliation-based tran=
saction announcement protocol.
<div dir=3D=22auto=22><a href=3D=22https://github.com/naumenkogs/bips/blo=
b/master/bip-reconcil.mediawiki=22>https://github.com/naumenkogs/bips/blo=
b/bip-reconcil/bip-reconcil.mediawiki</a><br />
<br />
Agreeing on this spec would enable integration of more bandwidth-efficien=
t relay protocols, like Erlay (<a href=3D=22https://arxiv.org/abs/1905.10=
518=22>https://arxiv.org/abs/1905.10518</a>).<br />
<br />
The draft has all the background necessary to understand the work, so ple=
ase read and review.<br />
It introduces salted short transaction IDs (required to do reconciliation=
 efficiently) and demonstrates how to compute sketches based on these IDs=
 (including simple python scripts).<br />
It also introduces wtxid-based truncated transaction IDs (to trivially sa=
ve significant fraction of the bandwidth).<br />
=46inally, it specifies all the messages to be used by an efficient recon=
ciliation-based protocol, and new state variables required for the protoc=
ol.<br />
<br />
Please note that, comparing to the Erlay paper, we decided to add extra r=
ound, where 2 parties explicitly map 32-bit short IDs to 128-bit truncate=
d IDs, because otherwise peers which take &gt;1s to reconcile would cause=
 transmitting duplicate transactions (extra bandwidth), and we cannot ass=
ume &lt;1s latency in Bitcoin, especially over Tor.<br />
According to my estimates, the bandwidth overhead due to the measure from=
 the BIP (extra communication round) is only extra 10% comparing to the o=
riginal Erlay estimates.<br />
<br />
It is possible that we missed some of the state variables required to han=
dle corner cases of the protocol, because the spec is based on my prototy=
pe code, and it might evolve when we will be building an actual productio=
n-ready implementation.<br />
<br />
Overall, I believe that this spec is ready for review.<br />
<br />
Even though this work does not require a fork, the change is quite signif=
icant, and peer-review is critical for the system, so please take a look.=
 =46eel free to reach out for questions and comments here or directly ove=
r email.<br />
<div dir=3D=22auto=22><br /></div>
<div dir=3D=22auto=22>=E2=80=93 gleb</div>
</div>
</div>
</div>
</body>
</html>

--5d8b4f45_3a95f874_4055--