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
|
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 1F428C2A
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 25 Sep 2019 11:28:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com
[209.85.221.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4F9E18A8
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 25 Sep 2019 11:28:11 +0000 (UTC)
Received: by mail-wr1-f41.google.com with SMTP id h7so6403545wrw.8
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 25 Sep 2019 04:28:11 -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=Zeb8rO4fAyXCiWwMMTxe5ymBYUwtBTalreOQiSO4Q7o=;
b=DOqOdqjPvKQAPBfcQubYopF5HouOsAQdNnmmVBJEPrbnyojd9TNZdD56oU+Tne3Wxe
rCwDyqzXRNb6jSZ/9rHzK/pLu/X95RhcjCt7kMdAW8DHXwTDYNVgqeDjP5kk5ZCvRvwO
Qb9IW27Xk3SAgRV/K7RtUfZgEEesbPDmn2Kgg10CJxkFdDbZLpmAcNnOvGJj+o6WgPNn
KtZH5GbXeZ4ZVMYwMjxUBclW79wwCbK0AStBNksv76kylDwVNTYaXfcoZ0TZTBSqe4yt
SbNR2eX4+t2VWTij3pfk9qmKaj6AMfPDcYauFAlTbBPhDiDiw1HbHawBY56cyxIxezTN
jYCg==
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=Zeb8rO4fAyXCiWwMMTxe5ymBYUwtBTalreOQiSO4Q7o=;
b=AZPm0XqTPsIor9g2gVwjsC5wm9A04xQ3gM9KRveGZfefY2yYU/3W2lRPTMRU4PZunc
ygdOxR2f5SyW7cKOLr59Mk0O3OdY1OhWe15yhfOmOyUD3gqzT/Pl3LIIUyGkEefZjvz3
CfQ9ok/5jQB7e+Q9JlF8DOaQDLHk2cWCTXw8Q8p4/F6XVT3no9J1ytcsmZvccBygMwLR
/wHb6OWKxVhtAKnKuHsqRneKp/6sp+QAehO0W+TIZ27zVFO/pQx1aMzQLYzOqDXEs71S
rHxsXMHEsBLFFSUf1JMq8CQyjPsQbNyjm9nhQw10Lizy8lCQB86YKc9m2vaI2HovQ30v
kWBQ==
X-Gm-Message-State: APjAAAUGhqkDg2NzCjZzSgzPKwSS09R01vSmp0yr2zsTHeXwjla572WN
61sARKpj/z7ZCSy2GLcBMurFeZhx1fnYsw==
X-Google-Smtp-Source: APXvYqzpzFMVxBFmx7q8yYwEjGtfR4aEJAPI0qCC+jLNwnnnMIt71/6+twrteL7WTknyOlQL3U3ZuA==
X-Received: by 2002:a05:6000:12c9:: with SMTP id
l9mr8715653wrx.163.1569410889193;
Wed, 25 Sep 2019 04:28:09 -0700 (PDT)
Received: from [172.22.0.30] ([82.117.251.135])
by smtp.gmail.com with ESMTPSA id c6sm5369038wrb.60.2019.09.25.04.28.07
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Wed, 25 Sep 2019 04:28:08 -0700 (PDT)
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>
X-Readdle-Message-ID: 8914e269-e922-43f4-8846-9fb21a8044f3@Spark
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="5d8b4f45_3a95f874_4055"
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: Wed, 25 Sep 2019 11:37:09 +0000
Subject: [bitcoin-dev] New BIP for p2p messages/state enabling
reconciliation-based protocols (Erlay)
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: Wed, 25 Sep 2019 11:28:20 -0000
--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 >1s to reconcile would cause=
transmitting duplicate transactions (extra bandwidth), and we cannot ass=
ume <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--
|
