SegWit Upgrade

Bitcoin Soft-Fork Introduced in 2017

Introduction

Segregated Witness (SegWit) is a 2017 soft-fork to the Bitcoin protocol introduced in BIP 141, which proposes a solution to the transaction malleability of ECDSA cryptographic signatures that limited the scalability of the original protocol.

It introduces several changes to Bitcoin transactions, including a Block Size Increase, a new Witness Commitment Scheme, and a new SegWit Address standard.

Background

The SegWit soft-fork aimed to solve the malleability of ECDSA (Elliptic Curve Digital Signature Algorithm) cryptographic signatures used in Bitcoin transactions.

Using a person's public/secret key pair $(sk, pk)$, they can sign a message $M$using a signing function and their secret key: $\sigma = sign(sk, M)$, obtaining a signature $\sigma$. Anyone can verify the signature is valid given the public key of the signer pk, the signed message M, the signature $\sigma$, and a verify function: $Ver(pk,M,\sigma)$. A secure signature scheme is designed with the property that without knowing the secret key, it would be impossible (in polynomial time) to come up with such that $Ver(pk,M',\sigma ')$ returns true. This means once a message is signed, it is practically impossible to be tempered with.

It turns out ECDSA has this undesired property of malleability: Given $(pk,M,\sigma)$ such that $Ver(pk,M,\sigma)$ returns true, it is trivial to come up with $\sigma '$ such that $Ver(pk,M,\sigma ')$ returns true. Thus, it is possible to come up with valid signatures on messages without knowing the secret key with which the message is signed.

Bitcoin protocol requiring UTXO transactions to be signed by the owner when they want to spend them in a transaction, combined with the fact that transactions are identified by TXID which is the hash of the entire transaction, leads to the problem of transaction malleability. In effect, a single transaction may have multiple different TXIDs, and an adversarial party can broadcast transactions with an altered signature.

This thus introduces an attack vector, which has contributed to several major security incidents on the network, including playing a role in the collapse of Mt Gox, a once-popular Bitcoin-fiat exchange platform [1].

Importantly, this problem of malleability does not severely affect Bitcoin protocol transactions, as transactions are still valid and still cannot be modified once signed. However, the fact that transactions cannot be uniquely identified by TXIDs (their hash) makes it hard to use transactions that are not confirmed on chain, which makes Layer 2 protocols like payment channels hard to build.

BIP 141

SegWit is introduced in BIP 141, a soft-fork that includes multiple revisions to the original protocol while still being backward compatible.

Change to TX format

1. An emty scriptSig field.

2. n <pkhash> scriptPubKey field indicating the transaction is a SegWit transaction with version number n.

3. A witness field.

Here’s the format of a SegWit native P2WPKH tx:

{
   witness:      <signature> <pubkey>
   scriptSig:    (empty)
   scriptPubKey: 0 <20-byte-key-hash>
                  (0x0014{20-byte-key-hash})
}

Note with an empty scriptSig and the scriptPubKey being n <pkhash>, a SegWit transaction will still be considered a valid transaction with no signatures from the point of view of a node that does not support SegWit, this is how BIP 141 achieved backward compatibility. By putting signatures in the witness field, transaction id will now be non-malleable for SegWit transactions.

Block Size Increase

For nodes that do not support SegWit, witness data is ignored and a SegWit transaction is viewed as a non-SegWit transaction with empty scriptSig. As the result of the witness data not being counted towards the size of a SegWit transaction, a SegWit transaction can be much smaller from the view of an old node than from a SegWit compatible node.

Although witness data is ignored by the old nodes, SegWit compatible nodes still see and store it. To prevent people from spamming new nodes by issuing transactions with very large witness data, a new rule about block size is introduced in BIP 141: the block size limit is increased to 4 MB, and the way the “size” (defined as block weight in BIP 141) of a block is calculated is by multiplying the size of nonwitness data by 4 and add it to the size of witness data.

As a result, there are approximately 80% more transactions per block on average since the introduction of SegWit.

Witness Commitment

A witness commitment scheme is introduced in BIP141.

Image Source: https://ocw.mit.edu/courses/mas-s62-cryptocurrency-engineering-and-design-spring-2018/resources/mas-s62s18-lec12/

In order to incorporate the witness data into the Merkle root of a block, a Merkle tree on the witness data is built, then the Merkle root of witness (wit root) is put into the coinbase transaction, which will then be hashed into the Merkel root of all transactions in a block.

Linear Scaling of SigHash Operations

Before Segwit, the signature operation is $O(n^2)$, because doubling the size of a transaction usually doubles both the number of signature operations as well the amount of data that has to be hashed for those signatures [5]. This is fixed in BIP 143, which is introduced together with the SegWit upgrade’s BIP 141, by changing the calculation of the transaction hash for the signature such that each byte of data only has to be hashed once [3]. This makes the operation $O(n)$. As a result, very large transactions can be signed and verified in a reasonably fast fashion.

SegWit Address

The native SegWit transactions’ output addresses cannot be parsed by non-SegWit compatible software.

For backward compatibility, BIP141 proposed BIP16 nested SegWit transaction so that SegWit transactions can still be sent and received via software that do not support SegWit.

P2WPKH nested in BIP16 P2SH:

   witness:      <signature> <pubkey>
   scriptSig:    <0 <20-byte-key-hash>>
                  (0x160014{20-byte-key-hash})
   scriptPubKey: HASH160 <20-byte-script-hash> EQUAL
                  (0xA914{20-byte-script-hash}87)

This decision results in three types of addresses:

1. Legacy address starting from 1…

2. Segwit address starting from bc1…

3. Nested SegWit address starting from 3… [6]

Legacy and Impact

Malleability and Lightning Network

Malleability is solved by Segwit, as now the signatures of transactions are no longer a part of the hash that determines the TXID. This means that the TXID is unique for every transaction in the network, which makes L2 payment channel possible, in the sense that unconfirmed transactions now won’t have invalid UTXOs in them. This improvement gives rise to the Lightning Network, an L2 protocol that increases the transaction speed and reduces transaction costs.

Block Size Increase and Ordinals

The introduction of the witness data field in the TX format in BIP 141 allows for storing arbitrary data such as text, image, etc on chain, also on a larger volume because the block size is increased as a result of the BIP141. One implication is that NFT, or digital artifacts, is possible to implement now on Bitcoin. Segwit, together with Taproot update, has led to the rise of Bitcoin Ordinals, which is a metaprotocol that allows people to order, identify, and inscribe digital content on satoshis to create digital artifacts.

Block Size Debate and Bitcoin Cash Hardfork

BIP141 is designed in a backward-compatible manner, as a soft-fork of the protocol. While being a soft-fork has the advantage of better adaptability, some in the blockchain community think BIP 141, especially the increasing of blocksize, should have been implemented as a hard-fork instead of a soft-fork. As the result of this disagreement, a group of developers initiated a hard-fork called Bitcoin Cash, which increases the block size to 8MB.

References

[1] Mt Gox: https://www.coindesk.com/markets/2014/02/07/mt-gox-halts-all-bitcoin-withdrawals-price-drop-follows/

[2] BIP 141:https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki

[3] BIP 143: https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki

[4] SegWit History: https://web.archive.org/web/20210224032019/https://bitcoinmagazine.com/articles/long-road-segwit-how-bitcoins-biggest-protocol-upgrade-became-reality

[5] SigOp: https://en.bitcoin.it/wiki/OP_CHECKSIG

[6] Legacy vs Segwit Address https://medium.com/@buddhasource/bitcoin-legacy-vs-segwit-wallet-address-what-is-the-difference-cb2e71ab8381

Edited By: Liwen Ouyang