BIP 0337

BIP: 337
 Layer: API/RPC
 Title: Compressed Transactions
 Author: Tom Briar <tombriar11@protonmail.com>
 Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0337
 Status: Draft
 Type: Standards Track
 Created: 2024-02-01
 License: BSD-3-Clause
 Post-History: https://github.com/bitcoin/bitcoin/pull/29134
 https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-August/021924.html
== Introduction ==
=== Abstract ===
This document proposes a serialization scheme for compressing Bitcoin transactions. The compressed Bitcoin transactions can reach a serialized size of less than 50% of the original serialized transaction. One method for compressing involves reducing the transaction outpoints in a potentially lossy way. Therefore, it is an optional path for compression. Compressing the outpoints is necessary for compressed transactions to reach less than 70% of the original size.
=== Motivation ===
Typical Bitcoin transactions usually contain a large amount of white space and padding due to specific fields that are often one of a minimal number of possibilities. We can use this fact and a few similar methods to create an encoding for 90% of Bitcoin transactions that are roughly 25-50% smaller.
There exists a working-in-progress app that allows the use of steganography to encode data in images to be passed around via various social media groups. When used in conjunction with this compression scheme and an elligator squared encryption, this would allow for a very secure and private form of broadcasting bitcoin transactions.
=== Rationale ===
The four main methods to achieve a lower transaction size are:
1. Packing transaction metadata before it and each of its inputs and outputs to determine the following data structure.
2. Replacing 32-bit numeric values with either variable-length integers (VarInts) or compact integers (CompactSizes).
3. Using compressed signatures and public key recovery upon decompression.
4. Replacing the 36-byte Outpoint txid/vout pair with a block height and index.
=== Backwards Compatibility ===
There are no concerns with backwards compatibility.
=== Specification ===
==== Primitives ====
Name 	Width 	Description
CompactSize 	1-5 Bytes	For 0-253, encode the value directly in one byte. For 254-65535, encode 254 followed by two little-endian bytes. For 65536-(2^32-1), encode 255 followed by four little-endian bytes.
CompactSize Flag	2 Bits 	1, 2, or 3 indicate literal values. 0 indicates that a CompactSize encoding of the value will follow.
VarInt 	1+ Bytes 	7-bit little-endian encoding, with each 7-bit word encoded in a byte. The highest bit of each byte is one if more bytes follow, and 0 for the last byte.
VLP-Bytestream 	2+ Bytes 	A VarInt Length Prefixed Bytestream. It uses the prefixed VarInt to determine the length of the following byte stream.
==== General Schema ====
Name 	Width 	Description
Transaction metadata 	1 Bytes 	Information on the structure of the transaction. See Transaction Metadata
Version 	0-5 Bytes	If present according to the metadata field, a CompactSize encoding of the transaction version.
Input Count 	0-5 Bytes	If present according to the metadata field, a CompactSize encoding of the transaction input count.
Output Count 	0-5 Bytes	If present according to the metadata field, a CompactSize encoding of the transaction output count.
LockTime 	0-5 Bytes	If present according to the metadata field, a CompactSize encoding of the transaction LockTime.
Minimum Blockheight 	1-5 Bytes	If present according to the metadata field, a VarInt encoding of the minimum block height for transaction compressed inputs and LockTime.
Input Metadata+Output Metadata	1+ Bytes 	An encoding containing the metadata for all the inputs followed by all the outputs of the transaction. For each input, see Input Metadata, and for each output, see Output Metadata.
Input Data 	66+ Bytes	See Input Data.
Output Data 	3+ Bytes 	See Output Data.
==== Transaction Metadata ====
Name 	Width 	Description
Version 	2 Bits	A CompactSize flag for the transaction version.
Input Count 	2 Bits	A CompactSize flag for the transaction input count.
Output Count 	2 Bits	A CompactSize flag for the transaction output count.
LockTime 	1 Bit 	A boolean to indicate if the transaction has a LockTime.
Minimum Blockheight	1 Bit 	A boolean to indicate if the transaction minimum block height is greater than zero.
==== Input Metadata ====
Name 	Width 	Description
Compressed Signature	1 Bit 	A Boolean do determine if this input's signature is compressed. The signature is only compressed for P2TR on a key spend and for P2SH when it is a wrapped P2SH-WPKH.
Standard Hash 	1 Bit 	A Boolean to determine if this input's signature hash type is standard (0x00 for Taproot, 0x01 for Legacy/Segwit).
Standard Sequence 	2 Bits	A CompactSize flag for this input's sequence. Encode literal values as follows: 1 = 0x00000000, 2 = 0xFFFFFFFE, 3 = 0xFFFFFFFF.
Compressed OutPoint 	1 bit 	A Boolean to determine if the input's outpoint is compressed.
==== Output Metadata ====
Name 	Width 	Description
Encoded Script Type	3 Bits	Encoded Script Type.
==== Script Type Encoding ====
Script Type 	Value
Uncompressed Custom Script	0b000
Uncompressed P2PK 	0b001
Compressed P2PK 	0b010
P2PKH 	0b011
P2SH 	0b100
P2WPKH 	0b101
P2WSH 	0b110
P2TR 	0b111
==== Input Data ====
Name 	Width 	Description
Outpoint 	2-37 Bytes	The Outpoint Txid/Vout are determined to be compressed or otherwise by the "Compressed Outpoint" Boolean in the input metadata. For each compressed outpoint see Compressed Outpoint. For each uncompressed signature see Uncompressed Outpoint.
Signature	64+ Bytes 	The Signature is determined to be compressed or otherwise by the output script of the previous transaction. For each compressed signature see Compressed Signature. For each uncompressed signature see Uncompressed Signature.
Sequence 	0-5 Bytes 	If present due to a non-standard sequence, a VarInt encoding of the sequence.
==== Compressed Outpoint ====
Name 	Width 	Description
Txid Block Height	1-5 Bytes	A VarInt containing the offset from Minimum Blockheight for this Txid.
Txid Block Index 	1-5 Bytes	A VarInt containing the flattened index from the Txid block height for the Vout.
==== Uncompressed Outpoint ====
Name	Width 	Description
Txid	32 Bytes 	Contains the 32 Byte Txid.
Vout	1-5 Bytes	A CompactSize Containing the Vout of the Txid.
==== Compressed Signature ====
Name 	Width 	Description
Signature 	64 Bytes 	Contains the 64 Byte signature.
Pubkey Hash	0-20 Bytes	If input is P2SH-P2WPKH contains the 20 byte hash of the public key.
Hash Type 	0-1 Bytes 	An Optional Byte containing the Hash Type if it was non-standard.
==== Uncompressed Signature ====
Name 	Width 	Description
Signature	2+ Bytes	A VLP-Bytestream containing the signature.
==== Output Data ====
Name 	Width 	Description
Output Script	2+ Bytes 	A VLP-Bytestream containing the output script.
Amount 	1-9 Bytes	A VarInt containing the output amount.
==== Ideal Transaction ====
The compression scheme was designed to be optimal for a "typical" transaction, spending a few close-in-age inputs and having one or two outputs. Here are size
values for such a transaction, which demonstrate the effectiveness of the compression.
Field 	Requirements 	Savings Up To
Version 	Less than four 	30 Bits
Input Count 	Less than four 	30 Bits
Output Count 	Less than four 	30 Bits
LockTime 	0 	30 Bits
Input Sequence 	0x00, 0xFFFFFFFE, or 0xFFFFFFFF 	62 Bits For Each Input
Input Txid 	Compressed Outpoint 	23 - 31 Bytes For Each Input
Input Vout 	Compressed Outpoint 	(-1) - 3 Bytes For Each Input
Input Signature	Non-custom Script Signing 	40 - 72 Bytes For Each Legacy Input
Input Hash Type	0x00 for Taproot, 0x01 for Legacy	7 Bits For Each Input
Output Script 	Non-custom Scripts 	2 - 5 Bytes For Each Output
Output Amount 	No Restrictions 	(-1) - 7 Bytes For Each Output
=== Reference Implementation ===
This reference implementation adds two new RPC endpoints, compressrawtransaction and decompressrawtransaction. The first accepts a raw hex-encoded transaction and returns a compact hex-encoded transaction; also included in the output is a list of warnings to help ensure there are no unexpected uncompressed values. The second accepts a compact hex transaction and returns the uncompressed raw hex-encoded transaction.
https://github.com/bitcoin/bitcoin/pull/29134
=== Test Vectors ===
==== Taproot ====
===== Uncompressed =====
020000000001017ad1d0cc314504ec06f1b5c786c50cf3cda30bd5be88cf08ead571b0ce7481fb0000000000fdffffff0188130000000000001600142da377ed4978fefa043a58489912f8e28e16226201408ce65b3170d3fbc68e3b6980650514dc53565f915d14351f83050ff50c8609495b7aa96271c3c99cdac1a92b1b45e77a4a870251fc1673596793adf2494565e500000000
===== Compressed =====
96b1ec7f968001b0218ce65b3170d3fbc68e3b6980650514dc53565f915d14351f83050ff50c8609495b7aa96271c3c99cdac1a92b1b45e77a4a870251fc1673596793adf2494565e58efefefe7d2da377ed4978fefa043a58489912f8e28e162262a608
==== P2WPKH ====
===== Uncompressed =====
0200000000010144bcf05ab48b8789268a7ca07133241ad654c0739ac7165015b2d669eadb10ea0000000000fdffffff0188130000000000001600142da377ed4978fefa043a58489912f8e28e16226202473044022043ab639a98dfbc704f16a35bf25b8b72acb4cb928fd772285f1fcf63725caa85022001c9ff354504e7024708bce61f30370c8db13da8170cef4e8e4c4cdad0f71bfe0121030072484c24705512bfb1f7f866d95f808d81d343e552bc418113e1b9a1da0eb400000000
===== Compressed =====
96b1ec71968001932643ab639a98dfbc704f16a35bf25b8b72acb4cb928fd772285f1fcf63725caa8501c9ff354504e7024708bce61f30370c8db13da8170cef4e8e4c4cdad0f71bfe8efefefe7d2da377ed4978fefa043a58489912f8e28e162262a608
==== P2SH-P2WPKH ====
===== Uncompressed =====
0200000000010192fb2e4332b43dc9a73febba67f3b7d97ba890673cb08efde2911330f77bbdfc00000000171600147a1979232206857167b401fdac1ffbf33f8204fffdffffff0188130000000000001600142da377ed4978fefa043a58489912f8e28e16226202473044022041eb682e63c25b85a5a400b11d41cf4b9c25f309090a5f3e0b69dc15426da90402205644ddc3d5179bab49cce4bf69ebfaeab1afa34331c1a0a70be2927d2836b0e8012103c483f1b1bd24dd23b3255a68d87ef9281f9d080fd707032ccb81c1cc56c5b00200000000
===== Compressed =====
96b1ec7c9e8001981641eb682e63c25b85a5a400b11d41cf4b9c25f309090a5f3e0b69dc15426da9045644ddc3d5179bab49cce4bf69ebfaeab1afa34331c1a0a70be2927d2836b0e87a1979232206857167b401fdac1ffbf33f8204ff8efefefe7d2da377ed4978fefa043a58489912f8e28e162262a608
==== P2PKH ====
===== Uncompressed =====
02000000015f5be26862482fe2fcc900f06ef26ee256fb205bc4773e5a402d0c1b88b82043000000006a473044022031a20f5d9212023b510599c9d53d082f8e07faaa2d51482e078f8e398cb50d770220635abd99220ad713a081c4f20b83cb3f491ed8bd032cb151a3521ed144164d9c0121027977f1b6357cead2df0a0a19570088a1eb9115468b2dfa01439493807d8f1294fdffffff0188130000000000001600142da377ed4978fefa043a58489912f8e28e16226200000000
===== Compressed =====
96b1ec7c968001981431a20f5d9212023b510599c9d53d082f8e07faaa2d51482e078f8e398cb50d77635abd99220ad713a081c4f20b83cb3f491ed8bd032cb151a3521ed144164d9c8efefefe7d2da377ed4978fefa043a58489912f8e28e162262a608
== Acknowledgements ==
Thank you to Andrew Poelstra, who helped invent and develop the ideas in the proposal and the code for reference implementation.