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--