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 for inputs that are not spending SegWit or in the for SegWit spending inputs. They consist of the encoded and values and a so-called flag, which specifies which part of the transaction the signature signs. The and values are both 256 bit (32-byte) integers. SigScript Witness r s SigHash r s 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 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 from nodes using an older version of the library. proposed a consensus soft fork where only signatures strictly following the DER encoding are accepted. ANS.1 reject the chain BIP-66 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 and a value with an unset first bit as . high low A 73-byte high-r and high-s Bitcoin ECDSA signature The r and s-values are random. When both values are (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 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 and the other one is . In a 71-byte signature, both values have to be . high high high low low The share of the signatures with a value started to reduce the release of in March 2014. This release contained a change to the Bitcoin Core wallet to only create signatures. With the release of Bitcoin Core and in October 2015, signatures were made non-standard to completely remove the malleability vector. This forbids transactions with values from being relayed or used in mining. Starting December 2015, nearly all transactions on the blockchain have only values in their signatures. high-s Bitcoin Core v0.9.0 low-s v0.10.3 v0.11.1 high-s high-s low-s 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 and a value, which requires a prepended 0x00 byte. The 71-byte signatures are and . low-s high-r low-r low-s End of August 2017, the SegWit soft-fork activated. SegWit moves the contents of the , which contains, for example, the signature, into the . While the witness gets discounted when calculating the transaction weight, the signature size on the blockchain remains the same. SigScript Witness A 71-byte low-r and low-s Bitcoin ECDSA signature The Bitcoin Core 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 value is found. The technique has been adopted by other projects such as the library and the . v0.17.0 low NBitcoin Electrum Bitcoin Wallet Schnorr Signatures introduces Schnorr signatures for Bitcoin and 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. BIP-340 BIP-341 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 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 flag are 65 byte long. SigHash SigHash 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 contain only a single signature, more than 1MB of blockchain space is saved per day. 800.000 inputs spent per day Related reading - An RSA Laboratories Technical Note - 1993 A Layman’s Guide to a Subset of ASN.1, BER, and DER - Eternity Wall Blog - 2017 Create the shortest transaction - Eternity Wall Blog Exact probabilities of obtaining a DER encoded signature of a certain length This article was originally posted on b10c.me