BIP 0337

From Bitcoin Wiki
Jump to navigation Jump to search

This page describes a BIP (Bitcoin Improvement Proposal).
Please see BIP 2 for more information about BIPs and creating them. Please do not just create a wiki page.

Please do not modify this page. This is a mirror of the BIP from the source Git repository here.

  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.