Skip to content

Instantly share code, notes, and snippets.

@sipa

sipa/tx_compression.md Secret

Last active March 15, 2019 23:13
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save sipa/1d29c1019e00874a61e533b2b050046f to your computer and use it in GitHub Desktop.
Save sipa/1d29c1019e00874a61e533b2b050046f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
tx_compression.md

(see http://people.xiph.org/~greg/compacted_txn.txt for original)

Goal

This is a proposal for a transaction compression scheme. It does not change signatures, or txids, or hashes. It's merely a more efficient encoding for transactions, and software using it should always convert the transactions back to the normative standard transaction encoding before computing txids and wtxids.

It is designed to be compact, but without relying on any context beyond a single transaction. This makes it applicable for transaction and block storage on disk, for transfer in the P2P network (including inside BIP152), and for storage in wallet software.

Specification

Transaction serialization:

  • TxHeader: byte
  • nLockTime: varint or uint32 (if not implied by TxHeader)
  • nVersion: int32 (if not implied by TxHeader)
  • For each input:
    • TxInHeader: byte (includes a bit to indicate whether more inputs follow)
    • prevout.n: varint (if not implied by TxHeader)
    • prevout.hash: uint256 (if not implied by TxHeader)
    • nSequence: uint32 (if not implied by TxHeader)
    • ScriptSigHeader: varint
    • Data: byte[], vector, or vectors (size and type implied by ScriptSigHeader)
  • For each output:
    • TxOutHeader: byte (includes a bit to indicate whether more outputs follow)
    • Data: byte[] (size implied by TxOutHeader)
    • Amount: varint

TxHeader

TxHeader = LockTimeCode + 3 * TxVersionCode

  • LockTimeCode:
    • 0: nLockTime = 0
    • 1: nLockTime explicitly coded as varint
    • 2: nLockTime explicitly coded as uint32
  • TxVersionCode:
    • 0-14: nVersion
    • 15: nVersion explicitly coded as int32

Values above 47 are reserved for future versions.

TxInHeader

TxInHeader = TxInCont + 2 * (PrevOutCode + 25 * SequenceCode)

  • TxInCont: whether another input follows (continuation flag)
  • PrevOutCode:
    • 0-22: prevout.n = PrevOutCode
    • 23: coinbase (prevout.hash = uint256(0), prevout.n = 0xFFFFFFFF)
    • 24: prevout.n explicitly coded as varint
  • SequenceCode:
    • 0: nSequence = 0
    • 1: nSequence = 0xFFFFFFFF
    • 2: nSequence = 0xFFFFFFFE
    • 3: nSequence is last explicitly coded value (or, if no explicitly coded value came before, 0xFFFFFFFD)
    • 4: nSequence is explicitly coded as uint32

Values above 249 are reserved for future versions.

ScriptSigHeader

The ScriptSigHeader is a varint that encodes which template the scriptSig/scriptWitness matches, and what encoding to use for the bytes that follow.

In the description that follows:

  • scriptSig is byte array containing the input's scriptSig field
  • scriptWitness is a vector of byte arrays stored in the input's scriptWitness field
  • empty is the empty byte array
  • 0x... constructs a constant non-empty byte array written in hex
  • + refers to concatenation of byte arrays
  • {a,b,...,z} where the variables refer to byte arrays constructs an array of byte arrays
  • push(a,b,...,z) is a function that takes byte arrays as input, prepends each with a length-based prefix, and concatenates the result into a single byte array.
    • The prefix for lengths 0-75 is the single byte (length)
    • The prefix for lengths 76-255 is the two bytes (0x4c,length)
    • The prefix for lengths 256-520 is the three bytes (0x4d,length & 0xFF,length / 256)
  • var[a] and var[a:b] use Python-like notation to index into byte arrays
  • Variables named pubkey... implicitly require that they're either:
    • 33 bytes and starting with 0x02 or 0x03
    • 65 bytes, starting with 0x04, and satisfying IsFullyValid()
  • Variables named dersig... implicitly require that they match DER encoding, matching this function: https://github.com/bitcoin/bitcoin/blob/v0.17.0/src/script/interpreter.cpp#L97L170

It is:

  • 0 P2SH_P2WSH_OTHER:
    • ScriptSigHeader = 0
    • Requires:
      • scriptWitness contains 1 element or more.
      • scriptSig = push(0x0020 + SHA256(scriptWitness[-1])).
    • Data:
      • The scriptWitness as-is.
  • 1 WIT_OTHER:
    • ScriptSigHeader = 1
    • Requires:
      • scriptSig = empty
    • Data:
      • Store the scriptWitness as-is.
  • 2 NONWIT_OTHER:
    • ScriptSigHeader = 2
    • Requires:
      • scriptWitness = {}
    • Data:
      • The scriptSig as-is.
  • 3 P2SH_UW:
    • ScriptSigHeader = 3
    • Requires nothing.
    • Data:
      • The scriptSig as-is
      • The scriptWitness as-is.
  • 4-5 P2PK:
    • ScriptSigHeader = 4 + bitSigHashNotAll
    • Requires:
      • scriptWitness={}
      • scriptSig=push(dersig)
    • bitSigHashNotAll = dersig[-1] != 0x01.
    • Data:
      • The signature in 64-byte compact format.
      • If bitSigHashNotAll: dersig[-1] as 1 byte.
  • 6-13 P2PKH:
    • ScriptSigHeader = 6 + bitSigHashNotAll + 2bitOddY + 4bitUncompressed
    • Requires:
      • scriptWitness={}
      • scriptSig=push(dersig,pubkey).
    • bitSighHashNotAll = dersig[-1] != 0x01.
    • bitUncompressed = pubkey[0] == 0x04.
    • bitOddY = (pubkey[0] == 0x03) OR (pubkey[0] == 0x04 AND (pubkey[64] & 1) == 1).
    • Data:
      • The signature in 64-byte compact format.
      • If bitSigHashNotAll: dersig[-1] as 1 byte.
      • Store xcoord = pubkey[1:33] as 32 bytes (the public key's X coordinate).
    • Decoding:
      • If bitUncompressed == 0: the pubkey is ((0x02 | bitOddY) + xcoord).
      • if bitUncompressed == 1: the pubkey is Decompress((0x02 | bitOddY) + xcoord).
  • 14-17 P2WPKH:
    • ScriptSigHeader = 14 + bitSigHashNotAll + 2*bitOddY
    • Requires:
      • scriptSig=empty
      • scriptWitness={dersig,pubkey}.
      • Pubkey is uncompressed (starts with 0x02 or 0x03).
    • bitSigHashNotAll = dersig[-1] != 0x01.
    • bitOddY = (pubkey[0] == 0x03).
    • Data:
      • The signature in 64-byte compact format.
      • If bitSigHashNotAll: dersig[-1] as 1 byte.
      • Store xcoord = pubkey[1:33] as 32 bytes (the public key's X coordinate).
    • Decoding: the pubkey is ((0x02 + bitOddY) || xcoord).
  • 22-25 P2SH_P2WPKH:
    • ScriptSigHeader = 22 + bitSigHashNotAll + 2*bitOddY
    • Requires:
      • scriptWitness={dersig,pubkey}
      • scriptSig=push(0x0014 + Hash160(pubkey)).
      • Pubkey is uncompressed (starts with 0x02 or 0x03).
    • Apart from scriptSig, bits, data, and decoding are identical to P2WPKH.
  • 30-33 P2SH_P2WSH_P2WPKH:
    • ScriptSigHeader = 30 + bitSigHashNotAll + 2*bitOddY
    • Requires:
      • scriptWitness={dersig,pubkey,push(0x76a914 + Hash160(pubkey) + 0x88ac)}
      • scriptsig=push(0x0020 + SHA256(push(0x76a914 + Hash160(pubkey) + 0x88ac)))
      • Pubkey is uncompressed (starts with 0x02 or 0x03).
    • Apart from scriptSig and the last scriptWitness element, bits, data, and decoding are identical to P2WPKH.
    • This should be pretty uncommon, maybe don't bother implementing.
  • 38-194 MS (mod 4 = 2)
    • ScriptSigHeader = 38 + 4bitSigHashNotAll + 8(k-1)
    • Requires:
      • scriptWitness={}
      • scriptSig=0x00 + push(dersig_1,dersig_2,...,dersig_k)
      • 1 <= k <= 20
    • bitSigHashNotAll is 1 if at least one of dersig_1, ..., dersig_k does not end with 0x01; 0 otherwise
    • Data:
      • For i = 1..k:
        • Store dersig_i in compact 64-byte format
        • If bitSigHashNotAll: store dersig_i[-1] in 1 byte
  • 39-1027 P2SH_MS (mod 4 = 3)
    • ScriptSigHeader = 39 + 4bitSigHashNotAll + 8KNCode(k,n)
      • KNCode(k,n) for 1 <= k <= n, is defined as:
        • KNCode(1,1) = 0, KNCode(1,2) = 1, KNCode(2,2) = 2, KNCode(2,3) = 3, KNCode(2,4) = 4, KNCode(3,4) = 5, KNCode(3,5) = 6
        • KNCode(k,n) = (((n * (n - 1)) / 2) + k + 3) otherwise
    • Requires:
      • scriptWitness={}
      • scriptSig=0x00 + push(dersig_1,dersig_2,...,dersig_k,push(pubkey_1,pubkey_2,...,pubkey_n) + 0xae)
      • 1 <= k <= n <= 15
    • bitSigHashNotAll is 1 if at least one of dersig_1, ..., dersig_k does not end with 0x00; 0 otherwise
    • Data:
      • For i = 1..n:
        • Store 2 bits (filling up from high bit to low bit):
          • pubkey_i[0] == 0x04
          • (pubkey_i[0] == 0x03) OR (pubkey_i[0] == 0x04 AND (pubkey_i[64] & 1) == 1)
      • Pad out with 0 zero bits to a multiple of bytes
      • For i = 1..k:
        • Store dersig_i in compact 64-byte format
        • If bitSigHashNotAll: store dersig_i[-1] in 1 byte
      • For i = 1..n:
        • Store pubkey_i[1:33] as 32 bytes
  • 40-1748 P2WSH_MS (mod 4 = 0)
    • ScriptSigHeader = 40 + 4bitSigHashNotAll + 8KNCode(k,n)
    • Requires:
      • scriptWitness(empty,dersig_1,dersig_2,...,dersig_k,push(pubkey_1,pubkey_2,...,pubkey_n) + 0xea)
      • scriptSig=empty
      • 1 <= k <= n <= 20
    • Apart from the ScriptSigHeader and the scriptWitness/scriptSig, it is identical to P2SH_MS.
  • 41-1749 P2SH_P2WSH_MS (mod 4 = 1)
    • ScriptSigHeader = 41 + 4bitSigHashNotAll + 8KNCode(k,n)
    • Requires:
      • scriptWitness(empty,dersig_1,dersig_2,...,dersig_k,push(pubkey_1,pubkey_2,...,pubkey_n) + 0xae)
      • scriptSig=push(0x0020 + SHA256(push(pubkey_1,pubkey_2,...,pubkey_n) + 0xae))
      • 1 <= k <= n <= 20
    • Apart from the ScriptSigHeader and the scriptWitness/scriptSig, it is identical to P2SH_MS.

Values above 1749 are reserved for future versions.

Backreferences

TxOutHeader

TxOutHeader = TxOutCont + 2 * TxOutCode

  • TxOutCont: 1 if more TxOuts follow
  • TxOutCode:
    • 0: P2PKH (20 bytes follow)
    • 1: P2SH (20 bytes follow)
    • 2: P2WPKH (20 bytes follow)
    • 3: P2WSH (32 bytes follow)
    • 4 + (pubkeyprefix-2): P2PK (32 bytes follow)
    • 8 + N (N in 0..15): Witness VN (+ 1 byte length L) (+ L bytes)
    • 24 + L (L in 0..75): Arbitrary data (+ L bytes)
    • 100: Custom (+ varint (L-76) ) (+ L bytes)

Values above 201 are reserved for future versions.

Amount

Amounts are encoded as a transformed number:

  • amount 0: 0
  • amount x * 10^e (e in [0..8]): 1 + 10 * (9 * [b..c] + [a] - 1) + e
  • amount x * 10^9: 1 + 10 * ([a..b] - 1) + 9

Analysis

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment