Segregated Witness (Segwit)

Segwit

Introduction

Segregated Witness (Segwit) [1], proposed in BIP 141 [5], was activated on August 24, 2017. The contributions of Segwit [2]:

1) solve transaction malleability [3]

2) mitigate block size limitation problem

Problem

1. Transaction malleability:

When transaction is signed, the signature (script_sig) does not cover all the data in a transaction. Specifically, the script_sig is part of the transaction, the signature will not be able to sign script_sig. So the signature does not cover script_sig. The script_sig is added, after the transaction is created and signed.

The script_sig is the tempering point. If script_sig changes, TXID will change. The script_sig can be changed by anyone has access to the corresponding private keys.

2) Block size limitation problem

Originally, Bitcoin does not have limit on block size. This allowed attackers to create large size block data. So a 1MB block size was introduced. The 1MB was a tradeoff, between network propagation times, node capability, and number of transactions that can fit into one block, etc [4].

Proposal

Segwit defines a new structure called witness. Signature and redeem script are moved into this structure, which is not included in the 1MB block size limit.

1)Transaction structure

The conventional transaction structure is used in TXID calculation, and script_sig is empty. Even if script_sig is tempered with, TXID does not change.

2) Lock/Unlock script

For a conventional P2PKH:

scriptPubKey (lock script)

OP_DUP OP_HASH160 <pubkey hash> OP_EQUALVERIFY OP_CHECKSIG

scriptSig (unlock script)

<sig> <pubkey>

For Segwit P2WPKH:

scriptPubKey (lock script)

0 <pubkey hash>

(unlock script)

scriptSig	Witness
Empty	<sig> <pubkey>

In scriptPubKey, there are no opcodes, only 2 data (version and hash) is pushed. When the lock script of this pattern is set, it is evaluated as a conventional P2PKH script.  The signature and public key are obtained from witness instead of scriptSig.

3) Witness extension method

In the extension, Segwit introduces OP_CLTV (OP_NPO2) and OP_CSV (OP_NOP3)

The witness structure

<witness version>

<witness program>

For Segwit, witness version is 0, the witness program is P2WPKH if hash length is 20 bytes and P2WSH if it is 32 bytes.

4) Address format

Segwit uses Bech32 address format. It is based on BCH code instead of previously used Base58 encoding, so that error correction is possible [6]. There is no distinction between uppercase and lowercase letters. QR code is also compact

5) Increase of block size

The increase of block size from Segwit depends on the types of transaction.

• Before Segwit

block data ≦ 1,000,000 MB

• After Segwit

block weight = base size × ３ + total size
base size： Size of transaction data not including witness

total size： Size of transaction data including witness

block weight ≦ 4,000,000 MB

• blocks are non-Segwit transactions, block size is 1MB, same as before

• all transactions in the block are transactions of P2WPKH with 1 input, 2 output, block size is about 1.6 MB.
• block has one output and all other transactions are P2WPKH input, it is huge Tx, the block size is about 2.1 MB.
• block consists of transactions of P2WSH with huge witness (all 15-of-15 multisig etc), the block size is about 3.7 MB.

6) Changes in signature data

The convention message digest items are based on the conventional transaction structure. The message digest items are:

version, txin count, txins, txout count, txouts, locktime, sighash type

For Segwit, the message digest items are:

version
hashPrevouts	Hash of all input outpoint
hashSequence	Hash of all input sequence (TxIns)
outpoint	Previous output (32byte TXID + 4byte index) in TxIns
script code
value	amount of coins held by TxIns
sequence	Sequence of TxIns
hash output	Hash of all outputs (TxOuts)
locktime
sighash type

Segwit changes the calculation of transaction hash for signatures, so that each byte of a transaction is hashed twice, at most [7]. The sighash calculation cost is reduced.

7) Witness commitment in Coinbase transaction

For a conventional transaction, the merkle root calculation is shown as below. The merkle root is calculated using original Tx format. 

Segwit adds the witness commitment. Merkle tree is constructed based on transaction data including signature data of witness. That merkle root is stored in one of coinbase transaction output to make commitment including the witness data.

Effects and Challenges

Segwit changes the consensus, P2P message, address format of Bitcoin protocol. It is amazing Segwit could be realised in soft fork.

Segwit introduces witness extension method. It cancels transaction malleability and increases block size. The actual block size increase depends on the transaction type.

References

1. https://en.bitcoin.it/wiki/Segregated_Witness
2. https://en.wikipedia.org/wiki/SegWit
3. https://en.bitcoin.it/wiki/Transaction_malleability
4. https://en.bitcoin.it/wiki/Block_size_limit_controversy
5. https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki
6. https://en.wikipedia.org/wiki/BCH_code
7. https://bitcoincore.org/en/2016/01/26/segwit-benefits/#linear-scaling-of-sighash-operations