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:
-
Packing transaction metadata before it and each of its inputs and outputs to determine the following data structure.
-
Replacing 32-bit numeric values with either variable-length integers (VarInts) or compact integers (CompactSizes).
-
Using compressed signatures and public key recovery upon decompression.
-
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.