summaryrefslogtreecommitdiff
path: root/96/c773876bba33f7f509012a778f9f45ce97f130
blob: ceb4642ab182d099255e10d94a74d8f1726cdb20 (plain)
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
Return-Path: <jjxtra@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id A43EBBA3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 27 Nov 2017 02:11:29 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f51.google.com (mail-it0-f51.google.com
	[209.85.214.51])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D27EEF4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 27 Nov 2017 02:11:28 +0000 (UTC)
Received: by mail-it0-f51.google.com with SMTP id o130so19167547itg.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 26 Nov 2017 18:11:28 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:from:date:message-id:subject:to;
	bh=mhk6idCg/vumO6w6uI2N94PBml87vy2a2k6azzpdGyg=;
	b=JnXw1SpwZwRbAtvlyjmgfV+Sq3HKHa5G/+hLGG6UaMPQ1oe1yaE7GUOlp+MUx2f3Yz
	jRMVwED6+LDK8t3gGAqpxWLfJSngK9L8rm61tebwU1/3VIPAfApDERpJD16Pw00dVL5n
	a2SLrWu+pHwt+GaR3WCQHPIzm0mIdfYcJln1RFZx2AW+C20CSYdvCG7mGR2HwbAvEifY
	yFtdxm6eNGKuWgJI1XnTYqArGYTIZbA4a70bM4q4enJyk5Xp5b4QtqTbky1oNDLvnkGw
	uHbQfy8w6qWeqsgVYzYCvLcCX7eepWTM1dGVQDZXIO9Hz9vQUJkmj5RJluenH8xRylcE
	Kd8g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
	bh=mhk6idCg/vumO6w6uI2N94PBml87vy2a2k6azzpdGyg=;
	b=VLQz/COoTPLh+tLc6k52Kgy7gLzgvZk23LlLCBindgB39MJnw35DMWkbNSn02o//E1
	in4+KNhAoS7r9wwMJZ6a6uYybay6xL3owbSKTnWFcjnXiwd0bDHD/Mr8VCc7qmSJUGeP
	4Moax4XzE7hmNV0xxJ9/FFp97TjjsyRLD/ZkDhSQlF5pJXjZGsuhCmh+i6lGHZ2c7g7O
	YPOZZKmSJeXzc+Il8hnImX0uM2+A2Q/adrMLKEVrCcCQO3XpV6REclZxReFlCBayRNqq
	22r0O/cMLiLEjfJp7oy4vhzK53XKyUeDmQOpOj25yQ3s38dhQDBXQmbgdjC5CG60QLhn
	6R2w==
X-Gm-Message-State: AJaThX5BOOYo3etGRJTbRu24raB4rtzTQNBANZLmcBTjE50pbuBsulfQ
	iesunadTl2kuf1nNpt90ZdkkHyN2nQsN2ZdSKVTZXACf
X-Google-Smtp-Source: AGs4zMbAuIvpmPollQ/dfTzvfKz9p+ibY4hxQ4U8ToE7nTeh9s6JQHx2y5Bs57nxvvmAYrFJu67wEMuY+4n+T7QJyRE=
X-Received: by 10.36.175.17 with SMTP id t17mr18098403ite.66.1511748688066;
	Sun, 26 Nov 2017 18:11:28 -0800 (PST)
MIME-Version: 1.0
Received: by 10.79.11.195 with HTTP; Sun, 26 Nov 2017 18:11:27 -0800 (PST)
From: Jeff Johnson <jjxtra@gmail.com>
Date: Sun, 26 Nov 2017 19:11:27 -0700
Message-ID: <CAHAcUENRbrz6pv_HSe4KDAY-onyMKnMJk8H6yUhqx4LoK0NeEw@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="94eb2c1984008abecf055eed6b57"
X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HK_RANDOM_ENVFROM,
	HK_RANDOM_FROM, 
	HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Mon, 27 Nov 2017 02:12:53 +0000
Subject: [bitcoin-dev] Block compression
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: Mon, 27 Nov 2017 02:11:29 -0000

--94eb2c1984008abecf055eed6b57
Content-Type: text/plain; charset="UTF-8"

I'm new to this mailing list and apologize if this has been suggested
before. I was directed from the Bitcoin core github to this mailing list
for suggestions.

I'd just like to post a possible solution that increases the amount of data
in a block without actually increasing the size on disk or the size in
memory or the size transmitted over the Internet. Simply applying various
compression algorithms, I was able to achieve about a 50% compression
ratio. Here are my findings on a recent Bitcoin block using max compression
for all methods:

Raw block
998,198 bytes

Gzip
521,212 bytes (52% ratio)
(needs 2MB to decompress).

LZMA
415,308 bytes (41% ratio)
(1MB dictionary, needs 3MB to decompress)

- ZStandard: 469,179 bytes (47% ratio)
(1MB memory to decompress)

- LZ4: 641,063 bytes (64% ratio)
(32-64K to decompress)

The compression time on my modest laptop (2 years old) was "instant". I ran
all from the command line and did not notice any lag as I pressed enter to
do the compression, so easily less than a second. But compression time
doesn't matter, decompression time is what matters as blocks will be
decompressed billions of times more than they will be compressed.
Decompression speed for LZ4 is the fastest of the above methods, at 3.3GB /
second, slightly less than half the speed of memcpy, see char at (
https://github.com/lz4/lz4).

If decompression speed, CPU and memory usage is a concern, LZ4 is a no
brainer. You basically get a 33% larger block size for "free". But
ZStandard, in my opinion, makes the most sense as it offers greater than
50% compression ratio with a very good decompression ratio of 900MB /
second.

If this were implemented in the Bitcoin protocol, there would need to be a
place to specify the compression type in a set of bits somewhere, so that
future compression algorithms could potentially be added.

Miners could do nothing and keep sending blocks as is, and these blocks
would have "no compression" as the type of compression, just as today. Or
they could opt in to compress blocks and choose how many transactions they
want to stuff into the block, keeping the compressed size under the limit.

The bitcoin client code would also need to be able to handle the
appropriate compression bits, and limits of signature data, etc. modified
to deal with the compression.

I understand schnorr signatures are on the roadmap as a 25% compression
gain which is great, I suspect that schnorr signatures would compress even
further when compressed with the above compression methods.

Here is a link to the block that I compressed:
https://mega.nz/#!YPIF2KTa!4FxxLvqzjqIftrkhXwSC2h4G4Dolk8dLteNUolEtq98

Thanks for reading, best wishes to all.

-- Jeff Johnson

--94eb2c1984008abecf055eed6b57
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>I&#39;m new to this mailing list and apologize if thi=
s has been suggested before. I was directed from the Bitcoin core github to=
 this mailing list for suggestions.</div><div><br></div>I&#39;d just like t=
o post a possible solution that increases the amount of data in a block wit=
hout actually increasing the size on disk or the size in memory or the size=
 transmitted over the Internet. Simply applying various compression algorit=
hms, I was able to achieve about a 50% compression ratio. Here are my findi=
ngs on a recent Bitcoin block using max compression for all methods:<div><b=
r></div><div>Raw block</div><div>998,198 bytes</div><div><br></div><div>Gzi=
p</div><div>521,212 bytes (52% ratio)</div><div>(needs 2MB to decompress).<=
/div><div><br></div><div>LZMA</div><div>415,308 bytes (41% ratio)</div><div=
> (1MB dictionary, needs 3MB to decompress)</div><div><br></div><div>- ZSta=
ndard:=C2=A0469,179 bytes (47% ratio)</div><div>(1MB memory to decompress)<=
/div><div><br></div><div>- LZ4:=C2=A0641,063 bytes (64% ratio)</div><div>(3=
2-64K to decompress)</div><div><br></div><div>The compression time on my mo=
dest laptop (2 years old) was &quot;instant&quot;. I ran all from the comma=
nd line and did not notice any lag as I pressed enter to do the compression=
, so easily less than a second. But compression time doesn&#39;t matter, de=
compression time is what matters as blocks will be decompressed billions of=
 times more than they will be compressed. Decompression speed for LZ4 is th=
e fastest of the above methods, at 3.3GB / second, slightly less than half =
the speed of memcpy, see char at (<a href=3D"https://github.com/lz4/lz4">ht=
tps://github.com/lz4/lz4</a>).</div><div><br></div><div>If decompression sp=
eed, CPU and memory usage is a concern, LZ4 is a no brainer. You basically =
get a 33% larger block size for &quot;free&quot;. But ZStandard, in my opin=
ion, makes the most sense as it offers greater than 50% compression ratio w=
ith a very good decompression ratio of 900MB / second.</div><div><br></div>=
<div>If this were implemented in the Bitcoin protocol, there would need to =
be a place to specify the compression type in a set of bits somewhere, so t=
hat future compression algorithms could potentially be added.<br></div><div=
><br></div><div>Miners could do nothing and keep sending blocks as is, and =
these blocks would have &quot;no compression&quot; as the type of compressi=
on, just as today. Or they could opt in to compress blocks and choose how m=
any transactions they want to stuff into the block, keeping the compressed =
size under the limit.</div><div><br></div><div>The bitcoin client code woul=
d also need to be able to handle the appropriate compression bits, and limi=
ts of signature data, etc. modified to deal with the compression.</div><div=
><br></div><div>I understand=C2=A0schnorr signatures are on the roadmap as =
a 25% compression gain which is great, I suspect that schnorr signatures=C2=
=A0would compress even further when compressed with the above compression m=
ethods.</div><div><br></div><div>Here is a link to the block that I compres=
sed:=C2=A0<a href=3D"https://mega.nz/#!YPIF2KTa!4FxxLvqzjqIftrkhXwSC2h4G4Do=
lk8dLteNUolEtq98">https://mega.nz/#!YPIF2KTa!4FxxLvqzjqIftrkhXwSC2h4G4Dolk8=
dLteNUolEtq98</a><br></div><div><span class=3D"gmail-file-link-info gmail-k=
ey" style=3D"font-size:13px;outline:none;color:rgb(217,0,7);font-family:sou=
rce_sans_proregular,Arial;white-space:pre-wrap"><br></span></div><div>Thank=
s for reading, best wishes to all.</div><div><br></div><div>-- Jeff Johnson=
<br></div></div>

--94eb2c1984008abecf055eed6b57--