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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <el33th4x0r@gmail.com>) id 1X8IvB-0003ZN-7o
for bitcoin-development@lists.sourceforge.net;
Sat, 19 Jul 2014 00:54:41 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.219.42 as permitted sender)
client-ip=209.85.219.42; envelope-from=el33th4x0r@gmail.com;
helo=mail-oa0-f42.google.com;
Received: from mail-oa0-f42.google.com ([209.85.219.42])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1X8Iv9-0007BV-I9
for bitcoin-development@lists.sourceforge.net;
Sat, 19 Jul 2014 00:54:41 +0000
Received: by mail-oa0-f42.google.com with SMTP id n16so4509147oag.29
for <bitcoin-development@lists.sourceforge.net>;
Fri, 18 Jul 2014 17:54:34 -0700 (PDT)
X-Received: by 10.182.114.131 with SMTP id jg3mr12222931obb.9.1405731274094;
Fri, 18 Jul 2014 17:54:34 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.76.23.193 with HTTP; Fri, 18 Jul 2014 17:54:14 -0700 (PDT)
In-Reply-To: <CAJHLa0MSdafZiXNH_L8qqH63n3wP5hb0R=EX3SJtsD40Fq_VOA@mail.gmail.com>
References: <CA+iPb=EaX=bvOjNtZ+LnYTMRLQQ9nFcrefAkBdv8eActoX_b8A@mail.gmail.com>
<CABsx9T0ag_o_mu=5Q7Ju7s2hO3jz-o5g9FihE9h4B6+ednd2Pg@mail.gmail.com>
<CAJHLa0NZRF+1QjSwtwjaTE07NWJ_U-O-DE24=P5eSAutMqTupg@mail.gmail.com>
<CABsx9T2BDBNqvinVNk3FmBRWU7R8jf6Vm6NaH74te0FRCh1O-w@mail.gmail.com>
<CAJHLa0O=eCoyvV19dWgTnYd9Di0wLLZtWmCPidc-dWqPNQv_oQ@mail.gmail.com>
<CA+iPb=H2fkjCxS7-hYqHjFzfMh6onk5RqZMxa8zsXeTn6pQMpA@mail.gmail.com>
<CAJHLa0NRUdAPuKXgKDBmXOs9to7gMpHv9ECCz_hTfZpg7SVVJA@mail.gmail.com>
<CA+iPb=HhGkiuaAxQMvpDpUdeU0uA5unPa_0uHGkS3LrmJzEnyQ@mail.gmail.com>
<CA+iPb=FZS9FxP9uYWHTzLpSVJ2uaOwr4dTQSvYuJjhVYCcJOew@mail.gmail.com>
<CAJHLa0MSdafZiXNH_L8qqH63n3wP5hb0R=EX3SJtsD40Fq_VOA@mail.gmail.com>
From: =?UTF-8?Q?Emin_G=C3=BCn_Sirer?= <el33th4x0r@gmail.com>
Date: Fri, 18 Jul 2014 17:54:14 -0700
Message-ID: <CAPkFh0uuo=vOiLVTvozPiO7L26A4DpJ9nrKGeQZ+DC6HbO27TQ@mail.gmail.com>
To: Jeff Garzik <jgarzik@bitpay.com>
Content-Type: multipart/alternative; boundary=001a11c2e3963dff4404fe815190
X-Spam-Score: -0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(el33th4x0r[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1X8Iv9-0007BV-I9
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Squashing redundant tx data in blocks on
the wire
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sat, 19 Jul 2014 00:54:41 -0000
--001a11c2e3963dff4404fe815190
Content-Type: text/plain; charset=UTF-8
I thought I'd chime in and point out some research results that might help.
Even if they don't, there is a cool underlying technique that some of you
might find interesting.
The problem being tackled here is very similar to "set reconciliation,"
where
peer A thinks that the set of transactions that should be in the block is
S_A,
and peer B has actually included set S_B, and S_A and S_B are expected
to not differ much. Ideally, one would like the communication complexity
between A and B to be O(delta), not O(S_B) as it is right now. And ideally,
one would like B to send a single message to A, and for A to figure out the
difference between the two sets, without any lengthy back and forth
communication. In essence, I would like to give you some magical packet
that is pretty small and communicates just the delta between what you and
I know.
This paper from Cornell describes a scheme for achieving this:
Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set reconciliation with
nearly optimal communication complexity. IEEE Transactions on Information
Theory 49(9): 2213-2218 (2003)
http://ipsit.bu.edu/documents/ieee-it3-web.pdf
Those of you looking for a TL;DR should read the intro and then skip to
page 8 for the example. The underlying trick is very cool, comes from the
peer-to-peer/gossip literature, and it is underused. It'd be really cool if
it
could be applied to this problem to reduce the size of the packets.
This approach has three benefits over the Bloom filter approach (if I
understand the Bloom filter idea correctly):
(1) Bloom filters require packets that are still O(S_A),
(2) Bloom filters are probabilistic, so require extra complications
when there is a hash collision. In the worst case, A might get confused
about which transaction B actually included, which would lead to a
fork. (I am not sure if I followed the Bloom filter idea fully -- this may
not happen with the proposal, but it's a possibility with a naive Bloom
filter implementation)
(3) Bloom filters are interactive, so when A detects that B has included
some transactions that A does not know about, it has to send a message
to figure out what those transactions are.
Set reconciliation is O(delta), non-probabilistic, and non-interactive. The
naive version requires that one have some idea of the size of the delta,
but I think the paper has some discussion of how to handle the delta
estimate.
I have not gone through the full exercise of actually applying this trick to
the Bitcoin p2p protocol yet, but wanted to draw your attention to it.
If someone is interested in applying this stuff to Bitcoin, I'd be happy
to communicate further off list.
- egs
On Fri, Jul 18, 2014 at 12:55 PM, Jeff Garzik <jgarzik@bitpay.com> wrote:
> Related: We must handle some legitimate miner-privately-mined cases,
> such as miner payout TXs (outside coinbase) or side chain conditional
> TXs[1].
>
> [1] https://bitcointalk.org/index.php?topic=676703.msg7682680#msg7682680
>
> On Fri, Jul 18, 2014 at 3:51 PM, Kaz Wesley <keziahw@gmail.com> wrote:
> > I've updated the gist, and added an additional proposal that I think
> > meshes well:
> >
> https://gist.github.com/kazcw/43c97d3924326beca87d#ultra-fast-block-validation
> >
> > sparseblocks + UFBV would tighten the new-block process to this (when
> > txes have been received in advance):
> > - receive block (~2kB for 1000 tx)
> > - check whether block contains txes known to belong to conflict-sets,
> > and if so whether more than one tx from a single conflict-set has been
> > included (a few operations on very small sets)
> > - relay block (~2kB)
> >
> > The benefits of these changes only occur when the transactions have
> > been seen in advance, but incentivizing ahead-of-block transaction
> > propogation is a plus, as Jeff mentioned; working on a block without
> > first ensuring peers have its transactions would be very expensive
> > from a miner's point of view.
> >
> >
> ------------------------------------------------------------------------------
> > Want fast and easy access to all the code in your enterprise? Index and
> > search up to 200,000 lines of code with a free copy of Black Duck
> > Code Sight - the same software that powers the world's largest code
> > search on Ohloh, the Black Duck Open Hub! Try it now.
> > http://p.sf.net/sfu/bds
> > _______________________________________________
> > Bitcoin-development mailing list
> > Bitcoin-development@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
> --
> Jeff Garzik
> Bitcoin core developer and open source evangelist
> BitPay, Inc. https://bitpay.com/
>
>
> ------------------------------------------------------------------------------
> Want fast and easy access to all the code in your enterprise? Index and
> search up to 200,000 lines of code with a free copy of Black Duck
> Code Sight - the same software that powers the world's largest code
> search on Ohloh, the Black Duck Open Hub! Try it now.
> http://p.sf.net/sfu/bds
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
--001a11c2e3963dff4404fe815190
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><span style=3D"font-family:arial,sans-serif;font-size:12.7=
27272033691406px">I thought I'd chime in and point out some research re=
sults that might help.</span><div style=3D"font-family:arial,sans-serif;fon=
t-size:12.727272033691406px">
Even if they don't, there is a cool underlying technique that some of y=
ou</div><div style=3D"font-family:arial,sans-serif;font-size:12.72727203369=
1406px">might find interesting.<br><div><br><div>The problem being tackled =
here is very similar to "set reconciliation," where</div>
<div>peer A thinks that the set of transactions that should be in the block=
is S_A,</div><div>and peer B has actually included set S_B, and S_A and S_=
B are expected</div><div>to not differ much. Ideally, one would like the co=
mmunication complexity</div>
</div><div>between A and B to be O(delta), not O(S_B) as it is right now. A=
nd ideally,</div><div>one would like B to send a single message to A, and f=
or A to figure out the</div><div>difference between the two sets, without a=
ny lengthy back and forth=C2=A0</div>
<div>communication. In essence, I would like to give you some magical packe=
t</div><div>that is pretty small and communicates just the delta between wh=
at you and</div><div>I know.</div><div><br></div><div>This paper from Corne=
ll describes a scheme for achieving this:</div>
<div>=C2=A0 =C2=A0Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set recon=
ciliation with nearly optimal communication complexity. IEEE Transactions o=
n Information Theory 49(9): 2213-2218 (2003)</div><div>=C2=A0 =C2=A0<a href=
=3D"http://ipsit.bu.edu/documents/ieee-it3-web.pdf" target=3D"_blank">http:=
//ipsit.bu.edu/documents/ieee-it3-web.pdf</a><br>
</div><div><br></div><div>Those of you looking for a TL;DR should read the =
intro and then skip to</div><div>page 8 for the example. The underlying tri=
ck is very cool, comes from the</div><div>peer-to-peer/gossip literature, a=
nd it is underused. It'd be really cool if it</div>
<div>could be applied to this problem to reduce the size of the packets.</d=
iv><div><br></div><div>This approach has three benefits over the Bloom filt=
er approach (if I=C2=A0</div><div>understand the Bloom filter idea correctl=
y):=C2=A0</div>
<div><br></div><div>(1) Bloom filters require packets that are still O(S_A)=
,=C2=A0</div><div><br></div><div>(2) Bloom filters are probabilistic, so re=
quire extra complications</div><div>when there is a hash collision. In the =
worst case, A might get confused</div>
<div>about which transaction B actually included, which would lead to a=C2=
=A0</div><div>fork. (I am not sure if I followed the Bloom filter idea full=
y -- this may=C2=A0</div><div>not happen with the proposal, but it's a =
possibility with a naive Bloom</div>
<div>filter implementation)</div><div><br></div><div>(3) Bloom filters are =
interactive, so when A detects that B has included</div><div>some transacti=
ons that A does not know about, it has to send a message</div><div>to figur=
e out what those transactions are.=C2=A0</div>
<div><br></div><div>Set reconciliation is O(delta), non-probabilistic, and =
non-interactive. The</div><div>naive version requires that one have some id=
ea of the size of the delta,</div><div>but I think the paper has some discu=
ssion of how to handle the delta=C2=A0</div>
<div>estimate.</div><div><br></div><div>I have not gone through the full ex=
ercise of actually applying this trick to</div><div>the Bitcoin p2p protoco=
l yet, but wanted to draw your attention to it.=C2=A0</div><div>If someone =
is interested in applying this stuff to Bitcoin, I'd be happy=C2=A0</di=
v>
<div>to communicate further off list.</div><div><br></div><div>- egs</div><=
div><br></div></div></div><div class=3D"gmail_extra"><br><br><div class=3D"=
gmail_quote">On Fri, Jul 18, 2014 at 12:55 PM, Jeff Garzik <span dir=3D"ltr=
"><<a href=3D"mailto:jgarzik@bitpay.com" target=3D"_blank">jgarzik@bitpa=
y.com</a>></span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">Related: =C2=A0We must handle some legitimat=
e miner-privately-mined cases,<br>
such as miner payout TXs (outside coinbase) or side chain conditional<br>
TXs[1].<br>
<br>
[1] <a href=3D"https://bitcointalk.org/index.php?topic=3D676703.msg7682680#=
msg7682680" target=3D"_blank">https://bitcointalk.org/index.php?topic=3D676=
703.msg7682680#msg7682680</a><br>
<div class=3D"HOEnZb"><div class=3D"h5"><br>
On Fri, Jul 18, 2014 at 3:51 PM, Kaz Wesley <<a href=3D"mailto:keziahw@g=
mail.com">keziahw@gmail.com</a>> wrote:<br>
> I've updated the gist, and added an additional proposal that I thi=
nk<br>
> meshes well:<br>
> <a href=3D"https://gist.github.com/kazcw/43c97d3924326beca87d#ultra-fa=
st-block-validation" target=3D"_blank">https://gist.github.com/kazcw/43c97d=
3924326beca87d#ultra-fast-block-validation</a><br>
><br>
> sparseblocks + UFBV would tighten the new-block process to this (when<=
br>
> txes have been received in advance):<br>
> - receive block (~2kB for 1000 tx)<br>
> - check whether block contains txes known to belong to conflict-sets,<=
br>
> and if so whether more than one tx from a single conflict-set has been=
<br>
> included (a few operations on very small sets)<br>
> - relay block (~2kB)<br>
><br>
> The benefits of these changes only occur when the transactions have<br=
>
> been seen in advance, but incentivizing ahead-of-block transaction<br>
> propogation is a plus, as Jeff mentioned; working on a block without<b=
r>
> first ensuring peers have its transactions would be very expensive<br>
> from a miner's point of view.<br>
><br>
> ----------------------------------------------------------------------=
--------<br>
> Want fast and easy access to all the code in your enterprise? Index an=
d<br>
> search up to 200,000 lines of code with a free copy of Black Duck<br>
> Code Sight - the same software that powers the world's largest cod=
e<br>
> search on Ohloh, the Black Duck Open Hub! Try it now.<br>
> <a href=3D"http://p.sf.net/sfu/bds" target=3D"_blank">http://p.sf.net/=
sfu/bds</a><br>
> _______________________________________________<br>
> Bitcoin-development mailing list<br>
> <a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-d=
evelopment@lists.sourceforge.net</a><br>
> <a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-develo=
pment" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitco=
in-development</a><br>
<br>
<br>
<br>
</div></div><div class=3D"im HOEnZb">--<br>
Jeff Garzik<br>
Bitcoin core developer and open source evangelist<br>
BitPay, Inc. =C2=A0 =C2=A0 =C2=A0<a href=3D"https://bitpay.com/" target=3D"=
_blank">https://bitpay.com/</a><br>
<br>
</div><div class=3D"HOEnZb"><div class=3D"h5">-----------------------------=
-------------------------------------------------<br>
Want fast and easy access to all the code in your enterprise? Index and<br>
search up to 200,000 lines of code with a free copy of Black Duck<br>
Code Sight - the same software that powers the world's largest code<br>
search on Ohloh, the Black Duck Open Hub! Try it now.<br>
<a href=3D"http://p.sf.net/sfu/bds" target=3D"_blank">http://p.sf.net/sfu/b=
ds</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</div></div></blockquote></div><br></div>
--001a11c2e3963dff4404fe815190--
|