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
|
Return-Path: <apoelstra@wpsoftware.net>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 1D97BC0032
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 1 Sep 2023 13:56:23 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id ECEC383B94
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 1 Sep 2023 13:56:22 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org ECEC383B94
Authentication-Results: smtp1.osuosl.org;
dkim=pass (2048-bit key) header.d=mail.wpsoftware.net
header.i=@mail.wpsoftware.net header.a=rsa-sha256 header.s=default
header.b=ByyMSMZu
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.107
X-Spam-Level:
X-Spam-Status: No, score=-1.107 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
autolearn=no autolearn_force=no
Received: from smtp1.osuosl.org ([127.0.0.1])
by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id fyssAnomlbK0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 1 Sep 2023 13:56:21 +0000 (UTC)
Received: from mail.wpsoftware.net (unknown [66.183.0.205])
by smtp1.osuosl.org (Postfix) with ESMTP id DC57083B7F
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 1 Sep 2023 13:56:20 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org DC57083B7F
Received: from camus (camus-andrew.lan [192.168.0.190])
by mail.wpsoftware.net (Postfix) with ESMTPSA id 2596640107;
Fri, 1 Sep 2023 13:56:20 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mail.wpsoftware.net;
s=default; t=1693576580;
bh=lK8ahrew01ZTm/DLT0JLEgQ52n9wYJmo2QDmzTRiKo4=;
h=Date:From:To:Cc:Subject:References:In-Reply-To;
b=ByyMSMZuI535hSuaEzzrM5Az8YGjdDDjvJQfQ/F2pPgZgxzyCz04y1PfLWndLsbsO
QG999hJ7njtBpNQTkiV//G7bCmVI7qUgWPmnKPNMqHRZKjYQkh/VE2SoeQyWelLPlB
NT8M3nh3ccoj8soiZMFbe7avxi7bpsooodXZJsc4orYFL2iuNBlvQaT668NrKv34da
zaqokHflsJSf3HaZ4qKKy1iesQ9COPxEF4nX5VNQHzavOACY+sLCd3KSUuw5/9wlHl
cEZCffHN+pfBBfC6ZwpWG7rB7Q6t/kcjIwcynj8mcylWQYRB9+t+WBub/st3i9pxZW
wGAS5wckcdSEA==
Date: Fri, 1 Sep 2023 13:56:18 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Fabian <fjahr@protonmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <ZPHtgiJQ4Yqrr941@camus>
References: <WJoM7dyrk0o8ujOZOo462r66wS2Kl3L1ZZRodvaLK-HKEUc90yvwOqXbUUrGbV1lk6cOywTqLoCyHzk2Tm3TtBFyUL0NZ6D7v9NmTXypJPA=@protonmail.com>
<KSmH1MBTPLuXMF4TWbWq6vaft_K_7IZS2YcoZ1iHwtHY06It1DjExVgSdrLBMQZA8mLGz8xdOzyXRHAZ2qCAugwG8gMtEGsGj-XNTPN0v0w=@protonmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="mf8888XFawM+QEOQ"
Content-Disposition: inline
In-Reply-To: <KSmH1MBTPLuXMF4TWbWq6vaft_K_7IZS2YcoZ1iHwtHY06It1DjExVgSdrLBMQZA8mLGz8xdOzyXRHAZ2qCAugwG8gMtEGsGj-XNTPN0v0w=@protonmail.com>
Subject: Re: [bitcoin-dev] Compressed Bitcoin Transactions
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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: Fri, 01 Sep 2023 13:56:23 -0000
--mf8888XFawM+QEOQ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Hi Fabian,
We did consider indexing all txos -- even, amusingly, by using ordinals --
but decided that the extra index requirements for the decompressor (which
otherwise just requires a bit of extra CPU cycles but nothing beyond a
normal Core node).
A while ago we looked into putting the whole UTXOset into a trie so that
we could do prefix lookups. I think we discarded this idea for the same
reason, and because it could lead to surprising behavior for users since
a compressed tx might get invalidated by some UTXO showing up whose
prefix is too close to one of its inputs. Where "prefix" likely means
some special-purpose hash of the prevout that users will never otherwise
encounter.
We were also a bit put off by the data structure complexity since the
UTXO set no longer fits in RAM so it takes nontrivial effort to
implement a new index :) plus it drops our chances of getting code into
Core by a very large factor.
We can swag what the space savings would be: there are 122MM utxos right
now, which is a bit under 2^27. So assuming a uniform distribution of
prefixes we'd need to specify 28 bits to identify a UTXO. To contrast,
to identify a blockheight we need 20 bits and then maybe 12 more bits to
specify a TXO within a block. Plus whatever varint overhead we have.
(I've been working on this project but busy with family stuff and don't
remember exactly where we landed on the varints for this. I think we
agreed that there was room for improvement but didn't want to hold up
posting the rest of the concept because of it.)
The TL;DR is that we probably save a little less than a byte per input,
on average, which is not trivial but probably not worth the decreased
UX and greatly increased implementation complexity.
Best
Andrew
On Fri, Sep 01, 2023 at 10:24:54AM +0000, Fabian via bitcoin-dev wrote:
> Hi Tom,
>=20
> without having gone into the details yet, thanks for the great effort you=
have put into this research and implementation already!
>=20
> > The bulk of our size savings come from replacing the prevout of each in=
put by a block height and index.
>=20
> Have you also considered using just an index from a sorted UTXO set inste=
ad? The potential additional space saving might be minor but this would mak=
e the scheme compatible with pruning. I had this on my list as a future res=
earch topic but didn't get around to it yet.
>=20
> Thanks,
> Fabian
> ------- Original Message -------
> On Thursday, August 31st, 2023 at 11:30 PM, Tom Briar via bitcoin-dev <bi=
tcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> > Hey everyone,
> >
> > I've been working on a way to compress bitcoin transactions for transmi=
ssion throughsteganography, satellite broadcasting,
> > and other low bandwidth channels with high CPU availability on decompre=
ssion.
> >
> > [compressed_transactions.md](https://github.com/TomBriar/bitcoin/blob/2=
023-05--tx-compression/doc/compressed_transactions.md)
> >
> > In the document I describe a compression schema that's tailored for the=
most common transactions single parties are likely to make.
> > In every case it falls back such that no transaction will become malfor=
med or corrupted.
> > Here's a PR for implementing this schema.
> >
> > [2023 05 tx compression](https://github.com/TomBriar/bitcoin/pull/3)
> > Thanks-
> > Tom.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
--=20
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
--mf8888XFawM+QEOQ
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmTx7YEACgkQxYjWPOQb
l8EvqQf/VL6tG3pUpEWPiiSMZ37QOj7liIr9c8sNTzcRuKd6Wpmtn3G1qw8EApBP
4JV5hFFGd2mPbSTLmkcKjQ1QsscZxCraUsRzndV+M15FNDX5tgMl6gNCA3+DomXF
gJLTSOG3jPZWwL0UcEktRl0yHNhfTOe1wrvefRm8Dm0GWxozEN5MbL4r4TGtc/cL
+qSULlqyVU+n7vzoBxKb/+NSWVWi84s2T/0Em1UAtpwtlOYI0KT0tJU+VlPKz7NA
e2fOx3FSFODbQ8iRFADn64/2maaXPvnEydoySuKItq0R7SQvyS8025P1U2VaHV8F
kFPaIynOL8XAMvcHy9UJCwus/h46Rw==
=rrZh
-----END PGP SIGNATURE-----
--mf8888XFawM+QEOQ--
|
