From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1D97BC0032 for ; 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 ; 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 ; 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 ; 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 To: Fabian , Bitcoin Protocol Discussion Message-ID: References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="mf8888XFawM+QEOQ" Content-Disposition: inline In-Reply-To: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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--