Hackernoon logoAnalyzing Bitcoin's Signature Size: How It Evolved Over The Years by@0xb10c

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

Author profile picture

@0xb10c0xB10C

Freelance Bitcoin Developer and Researcher

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

This article was originally posted on b10c.me

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.