Evolution of the signature size in Bitcoin

Tuesday, November 10, 2020

Digital signatures are an essential building block of the Bitcoin protocol and account for a large part of the data stored on the blockchain. We detail how the size of the encoded ECDSA signatures reduced multiple times over the last years and how the proposed Schnorr signature compares to the length of the currently used ECDSA signatures.

Digital signatures in Bitcoin transactions are located in the SigScript for inputs that are not spending SegWit or in the Witness for SegWit spending inputs. They consist of the encoded r and s values and a so-called SigHash flag, which specifies which part of the transaction the signature signs. The r and s values are both 256 bit (32-byte) integers.

DER Encoded ECDSA Signatures

Since its first version, the Bitcoin client relied on OpenSSL for signature validation and encoding. ECDSA signatures are encoded with the Distinguished Encoding Rules (DER) defined in the ANS.1 encoding rules. While the DER encoding only allows for exactly one way of representing a signature as a byte sequence, the OpenSSL library deemed derivations from the DER standard as valid. When this changed in the OpenSSL library, it caused some nodes with the newer OpenSSL version to reject the chain from nodes using an older version of the library. BIP-66 proposed a consensus soft fork where only signatures strictly following the DER encoding are accepted.

A DER-encoded ECDSA signature starts with a 0x30 identifier marking a compound structure. Next is a length byte containing the length of the structure followed by the compound structure itself. The compound contains the r- and s- values as integers. These are marked with the integer identifier 0x02 and followed by a length byte defining the respective lengths of the values.

Format of a DER-encoded Bitcoin signature with SigHash flag
Format of a DER-encoded Bitcoin signature with SigHash flag

While the ANS.1 encoding requires a signed integer, the r and s-values in ECDSA are expected to be unsigned integers. This causes an issue when the first bit of the r- or s-values are set. To solve this, the value is prepended with a 0x00 byte. Thus the unsigned integer is encoded as a positive, signed integer. A value with the first bit set is referred to as high and a value with an unset first bit as low.

A 73-byte high-r and high-s Bitcoin ECDSA signature
A 73-byte high-r and high-s Bitcoin ECDSA signature

The r and s-values are random. When both values are high (both have their first bit set), they both require a prepended 0x00 byte. With two extra bytes, the encoded r- and s-values and the SigHash flag result in a total signature length of 73 bytes. The probability of both values being high in the same signature is 25%. Until early 2014, a distribution of about 25% 73-byte, 50% 72-byte, and about 25% of 71-byte signatures can be observed on the blockchain. In the 72-byte signatures, one of the two values is high and the other one is low. In a 71-byte signature, both values have to be low.

The share of the signatures with a high-s value started to reduce the release of Bitcoin Core v0.9.0 in March 2014. This release contained a change to the Bitcoin Core wallet to only create low-s signatures. With the release of Bitcoin Core v0.10.3 and v0.11.1 in October 2015, high-s signatures were made non-standard to completely remove the malleability vector. This forbids transactions with high-s values from being relayed or used in mining. Starting December 2015, nearly all transactions on the blockchain have only low-s values in their signatures.

A 72-byte high-r and low-s Bitcoin ECDSA signature
A 72-byte high-r and low-s Bitcoin ECDSA signature

Between December 2015 and early 2018, the signatures on the blockchain are nearly evenly split between 72 and 71 bytes in length. The 72-byte signatures have a low-s and a high-r value, which requires a prepended 0x00 byte. The 71-byte signatures are low-r and low-s.

End of August 2017, the SegWit soft-fork activated. SegWit moves the contents of the SigScript, which contains, for example, the signature, into the Witness. While the witness gets discounted when calculating the transaction weight, the signature size on the blockchain remains the same.

A 71-byte low-r and low-s Bitcoin ECDSA signature
A 71-byte low-r and low-s Bitcoin ECDSA signature

The Bitcoin Core v0.17.0 release in October 2018 included an improvement to the Bitcoin Core wallet to produce only 71-byte signatures. By re-signing a transaction with a different nonce, a new r-value can be grinded until a low value is found. The technique has been adopted by other projects such as the NBitcoin library and the Electrum Bitcoin Wallet.

Schnorr Signatures

BIP-340 introduces Schnorr signatures for Bitcoin and BIP-341 proposes a new SegWit version 1 output type and its spending rules based on Schnorr signatures, Taproot, and Merkle branches. Unlike ECDSA signatures, the Schnorr signatures are not DER-encoded.

Format of a Bitcoin Schnorr signature
Format of a Bitcoin Schnorr signature

Schnorr signatures contain the 32 byte r-value followed by the 32 byte s-value. The most commonly used SigHash flag SIGHASH_ALL is assumed by default and does not need to be set explicitly. Other SigHash flags are placed after the s-value. Schnorr signatures with the default SIGHASH_ALL flag have a length of exactly 64 byte. Signatures with a different SigHash flag are 65 byte long.

A 64-byte SIGHASH_ALL Bitcoin Schnorr signature
A 64-byte SIGHASH_ALL Bitcoin Schnorr signature

Compared to ECDSA signatures, Schnorr signatures are between 6 and 9 byte shorter. These savings stem from the removed encoding overhead and the default SigHash flag. With a Schnorr signature adoption of 20%, and assuming all of the 800.000 inputs spent per day contain only a single signature, more than 1MB of blockchain space is saved per day.

This article was re-published on the Advancing Bitcoin blog and Hackernoon. Furthermore, it was translated into Chinese by Chen Bo Yu and Hsu Tzu Hsiu who published their translation on 链闻 ChainNews and Binance Blockchain Research Institute.

All text and images in this work are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License Creative Commons License


Image for On anyone-can-spend Pay-to-Taproot outputs before activation

July 23, 2021

On anyone-can-spend Pay-to-Taproot outputs before activation

While working on taproot support for transactionfee.info, it became apparent that there already exist a few Pay-to-Taproot (P2TR) outputs on mainnet. Anyone can spend these outputs, but they are non-standard and thus not relayed between nodes in the Bitcoin peer-to-peer network. However, a mining pool can include non-standard transactions in their block. We cover the six P2TR outputs already present on mainnet and explain why the outputs can be spent by anyone before taproot activates. With the help of the f2pool.com mining pool, four P2TR outputs are donated to brink.dev, a non-profit company focused on supporting open-source Bitcoin development.


Image for Frequently Asked Questions: Bitcoin Transaction Monitor

October 10, 2019

Frequently Asked Questions: Bitcoin Transaction Monitor

The Bitcoin Transaction Monitor provides deeper insights into the usage of the Bitcoin network by showing transactions by time and feerate. This post answers frequently asked questions about the Bitcoin Transaction Monitor itself.