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
|
Return-Path: <el33th4x0r@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 50AB089C
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 2 Dec 2015 18:58:08 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qg0-f54.google.com (mail-qg0-f54.google.com
[209.85.192.54])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5C27D151
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 2 Dec 2015 18:58:07 +0000 (UTC)
Received: by qgeb1 with SMTP id b1so41511571qge.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 02 Dec 2015 10:58:06 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc:content-type;
bh=gxTGGTskNsy1vocG+IfQlPyqdHWzz5TbculpQMsFjWk=;
b=NKOywq0giHk6eOli7mzIeYR1SWyHApsIwqGi6xdciM0iMbXXNFV7TtaSI+ttHma27h
gMlcjumLxD1PgVUT45fMMRUSlTrzf0gr41UaEb5Feh4qC6f6lyfnudmd/raiHr21ekyB
ugUk8gu2WFQJNj1vJ4iazeU3ykMY8PbxE64ohiyST663DxEbpM3WC5NMU76cf9MZa4q+
J82IBg+KjFzngNiKyw7IrkNEd49u6UZBswBlpyGICuReO50nGmvn3hJLgFWh7532Du/E
cFOMsVQmFF7By1NZQ+DtnL2adyRSt4lJUZnpJN4lYAwpEXJO9TFAZbb+sKSchyHxzzPR
zltQ==
X-Received: by 10.140.91.109 with SMTP id y100mr6033317qgd.20.1449082686521;
Wed, 02 Dec 2015 10:58:06 -0800 (PST)
MIME-Version: 1.0
Received: by 10.140.19.132 with HTTP; Wed, 2 Dec 2015 10:57:46 -0800 (PST)
In-Reply-To: <90EF4E6C-9A71-4A35-A938-EAFC1A24DD24@mattcorallo.com>
References: <565CD7D8.3070102@gmail.com>
<90EF4E6C-9A71-4A35-A938-EAFC1A24DD24@mattcorallo.com>
From: =?UTF-8?Q?Emin_G=C3=BCn_Sirer?= <el33th4x0r@gmail.com>
Date: Wed, 2 Dec 2015 13:57:46 -0500
Message-ID: <CAPkFh0t9SwVOLrPnL7z80s-Rriezhqxn_3vXKYRxr6JVGNiUZQ@mail.gmail.com>
To: Matt Corallo <lf-lists@mattcorallo.com>
Content-Type: multipart/alternative; boundary=001a113a75b2c7c7f80525eedafd
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [BIP Draft] Datastream compression of Blocks and
Transactions
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 02 Dec 2015 18:58:08 -0000
--001a113a75b2c7c7f80525eedafd
Content-Type: text/plain; charset=UTF-8
Thanks Peter for the careful, quantitative work.
I want to bring one additional issue to everyone's consideration, related
to the choice of the Lempel-Ziv family of compressors.
While I'm not familiar with every single compression engine tested, the
Lempel-Ziv family of compressors are generally based on "compression
tables." Essentially, they assign a short unique number to every new
subsequence they encounter, and when they re-encounter a sequence like "ab"
in "abcdfdcdabcdfabcdf" they replace it with that short integer (say, in
this case, 9-bit constant 256). So this example sequence may turn into
"abcdfd<258 for cd><256 for ab><258 for cd>f<261 for abc><259 for df>"
which is slightly shorter than the original (I'm doing this off the top of
my head so the counts may be off, but it's meant to be illustrative). Note
that the sequence "abc" got added into the table only after it was
encountered twice in the input.
This is nice and generic and works well for English text where certain
letter sequences (e.g. "it" "th" "the" "this" "are" "there" etc) are
repeated often, but it is nowhere as compact as it could possibly be for
mostly binary data -- there are opportunities for much better compression,
made possible by the structured reuse of certain byte sequences in the
Bitcoin wire protocol.
On a Bitcoin wire connection, we might see several related transactions
reorganizing cash in a set of addresses, and therefore, several reuses of a
20-byte address. Or we might see a 200-byte transaction get transmitted,
followed by the same transaction, repeated in a block. Ideally, we'd learn
the sequence that may be repeated later on, all at once (e.g. a Bitcoin
address or a transaction), and replace it with a short number, referring
back to the long sequence. In the example above, if we knew that "abcdf"
was a UNIT that would likely be repeated, we would put it into the
compression table as a whole, instead of relying on repetition to get it
into the table one extra byte at a time. That may let us compress the
original sequence down to "abcdfd<257 for cd><256 for abcdf><256 for
abcdf>" from the get go.
Yet the LZ variants I know of will need to see a 200-byte sequence repeated
**199 times** in order to develop a single, reusable, 200-byte long
subsequence in the compression table.
So, a Bitcoin-specific compressor can perhaps do significantly better, but
is it a good idea? Let's argue both sides.
Cons:
On the one hand, Bitcoin-specific compressors will be closely tied to the
contents of messages, which might make it difficult to change the wire
format later on -- changes to the wire format may need corresponding
changes to the compressor. If the compressor cannot be implemented
cleanly, then the protocol-agnostic, off-the-shelf compressors have a
maintainability edge, which comes at the expense of the compression ratio.
Another argument is that compression algorithms of any kind should be
tested thoroughly before inclusion, and brand new code may lack the
maturity required. While this argument has some merit, all outputs are
verified separately later on during processing, so
compression/decompression errors can potentially be detected. If the
compressor/decompressor can be structured in a way that isolates bitcoind
from failure (e.g. as a separate process for starters), this concern can be
remedied.
Pros:
The nature of LZ compressors leads me to believe that much higher
compression ratios are possible by building a custom, Bitcoin-aware
compressor. If I had to guess, I would venture that compression ratios of
2X or more are possible in some cases. In some sense, the "O(1) block
propagation" idea that Gavin proposed a while ago can be seen as extreme
example of a Bitcoin-specific compressor, albeit one that constrains the
order of transactions in a block.
Compression can buy us some additional throughput at zero cost, modulo code
complexity.
Given the amount of acrimonious debate over the block size we have all had
to endure, it seems
criminal to leave potentially free improvements on the table. Even if the
resulting code is
deemed too complex to include in the production client right now, it would
be good to understand
the potential for improvement.
How to Do It
If we want to compress Bitcoin, a programming challenge/contest would be
one of the best ways to find the best possible, Bitcoin-specific
compressor. This is the kind of self-contained exercise that bright young
hackers love to tackle. It'd bring in new programmers into the ecosystem,
and many of us would love to discover the limits of compressibility for
Bitcoin bits on a wire. And the results would be interesting even if the
final compression engine is not enabled by default, or not even merged.
--001a113a75b2c7c7f80525eedafd
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><span style=3D"font-size:12.8px">Thanks Peter for the care=
ful, quantitative work.</span><div style=3D"font-size:12.8px"><br></div><di=
v><span style=3D"font-size:12.8px">I want to bring one additional issue to =
everyone's consideration, related to the choice of the Lempel-Ziv famil=
y of compressors.=C2=A0</span><div style=3D"font-size:12.8px"><br></div><di=
v style=3D"font-size:12.8px">While I'm not familiar with every single c=
ompression engine tested, the Lempel-Ziv family of compressors are generall=
y based on "compression tables." Essentially, they assign a short=
unique number to every new subsequence they encounter, and when they re-en=
counter a sequence like "ab" in "abcdfdcdabcdfabcdf" th=
ey replace it with that short integer (say, in this case, 9-bit constant 25=
6). So this example sequence may turn into "abcdfd<258 for cd>&l=
t;256 for ab><258 for cd>f<261 for abc><259 for df>&qu=
ot; which is slightly shorter than the original (I'm doing this off the=
top of my head so the counts may be off, but it's meant to be illustra=
tive). Note that the sequence "abc" got added into the table only=
after it was encountered twice in the input.=C2=A0</div><div style=3D"font=
-size:12.8px"><br></div><div style=3D"font-size:12.8px">This is nice and ge=
neric and works well for English text where certain letter sequences (e.g. =
"it" "th" "the" "this" "are&qu=
ot; "there" etc) are repeated often, but it is nowhere as compact=
as it could possibly be for mostly binary data -- there are opportunities =
for much better compression, made possible by the structured reuse of certa=
in byte sequences in the Bitcoin wire protocol.</div><div><div style=3D"fon=
t-size:12.8px"><br></div><div style=3D"font-size:12.8px">On a Bitcoin wire =
connection, we might see several related transactions reorganizing cash in =
a set of addresses, and therefore, several reuses of a 20-byte address. Or =
we might see a 200-byte transaction get transmitted, followed by the same t=
ransaction, repeated in a block. Ideally, we'd learn the sequence that =
may be repeated later on, all at once=C2=A0(e.g. a Bitcoin address or a tra=
nsaction), and replace it with a short number, referring back to the long s=
equence. In the example above, if we knew that "abcdf" was a UNIT=
that would likely be repeated, we would put it into the compression table =
as a whole, instead of relying on repetition to get it into the table one e=
xtra byte at a time. That may let us compress the original sequence down to=
"abcdfd<257 for cd><256 for abcdf><256 for abcdf>&q=
uot; from the get go.</div><div style=3D"font-size:12.8px"><br></div><div s=
tyle=3D"font-size:12.8px">Yet the LZ variants I know of will need to see a =
200-byte sequence repeated **199 times** in order to develop a single, reus=
able, 200-byte long subsequence in the compression table.=C2=A0</div><div><=
div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">So=
, a Bitcoin-specific compressor can perhaps do significantly better, but is=
it a good idea? Let's argue both sides.</div><div style=3D"font-size:1=
2.8px"><br></div><div><div><span style=3D"font-size:12.8px">Cons:</span></d=
iv><div><span style=3D"font-size:12.8px"><br></span></div><div><span style=
=3D"font-size:12.8px">On the one hand, Bitcoin-specific compressors will be=
closely tied to the contents of messages, which might make it difficult to=
change the wire format later on -- changes to the wire format may need cor=
responding changes to the compressor.=C2=A0 If the compressor cannot be imp=
lemented cleanly, then the protocol-agnostic, off-the-shelf compressors hav=
e a maintainability edge, which comes at the expense of the compression rat=
io.=C2=A0</span></div><div><span style=3D"font-size:12.8px"><br></span></di=
v><div><span style=3D"font-size:12.8px">Another argument is that compressio=
n algorithms of any kind should be tested thoroughly before inclusion, and =
brand new code may lack the maturity required. While this argument has some=
merit, all outputs are verified separately later on during processing, so =
compression/decompression errors can potentially be detected. If the compre=
ssor/decompressor can be structured in a way that isolates bitcoind from fa=
ilure (e.g. as a separate process for starters), this concern can be remedi=
ed.</span></div><div><span style=3D"font-size:12.8px"><br></span></div><div=
><span style=3D"font-size:12.8px">Pros:</span></div><div><span style=3D"fon=
t-size:12.8px"><br></span></div><div><span style=3D"font-size:12.8px">The n=
ature of LZ compressors leads me to believe that much higher compression ra=
tios are possible by building a custom, Bitcoin-aware compressor. If I had =
to guess, I would venture that compression ratios of 2X or more are possibl=
e in some cases. In some sense, the "O(1) block propagation" idea=
that Gavin proposed a while ago can be seen as extreme example of a Bitcoi=
n-specific compressor, albeit one that constrains the order of transactions=
in a block.</span></div><div><span style=3D"font-size:12.8px"><br></span><=
/div><div><span style=3D"font-size:12.8px">Compression can buy us some addi=
tional throughput at zero cost, modulo code complexity.=C2=A0</span></div><=
div><span style=3D"font-size:12.8px">Given the amount of acrimonious debate=
over the block size we have all had to endure, it seems=C2=A0</span></div>=
<div><span style=3D"font-size:12.8px">criminal to leave potentially free im=
provements on the table. Even if the resulting code is</span></div><div><sp=
an style=3D"font-size:12.8px">deemed too complex to include in the producti=
on client right now, it would be good to understand</span></div><div><span =
style=3D"font-size:12.8px">the potential for improvement.</span></div><div>=
<span style=3D"font-size:12.8px"><br></span></div><div><span style=3D"font-=
size:12.8px">How to Do It</span></div><div><span style=3D"font-size:12.8px"=
><br></span></div><div><span style=3D"font-size:12.8px">If we want to compr=
ess Bitcoin, a</span><span style=3D"font-size:12.8px">=C2=A0programming cha=
llenge/contest would be one of the best ways to find the best possible, Bit=
coin-specific compressor. This is the kind of self-contained exercise that =
bright </span><span style=3D"font-size:12.8px">young hackers love to tackle=
. It'd bring in new programmers into the ecosystem, and many of us woul=
d love to discover the limits of compressibility for Bitcoin bits on a wire=
. And the results would be interesting even if the final compression engine=
is not enabled by default, or not even merged.</span></div><div><br></div>=
</div></div></div></div></div>
--001a113a75b2c7c7f80525eedafd--
|
