Analyzing Bitcoin's Signature Size: How It Evolved Over The Years

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

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

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

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

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

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

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.

Related reading

• A Layman’s Guide to a Subset of ASN.1, BER, and DER - An RSA Laboratories Technical Note - 1993
• Create the shortest transaction - Eternity Wall Blog - 2017
• Exact probabilities of obtaining a DER encoded signature of a certain length - Eternity Wall Blog

This article was originally posted on b10c.me