Partnered With:

The Evolution of Bitcoin Signatures

Read this article in 11 Minutes

Learn about ECDSA and Schnorr in one article

Original title: "Stone from Other Mountains丨Hard Core Explains How to Shorten Bitcoin Signature Step by Step"

Original Compilation: Binance Blockchain Research Institute

Digital signatures are an important building block in the Bitcoin protocol, accounting for a large portion of the data stored on the blockchain. This post details how Encoded Elliptic Curve Digital Signature Algorithm (ECDSA) signature sizes have continued to decrease over the past few years, and compares the length of newly proposed Schnorr signatures to those currently in use with ECDSA.

In the Bitcoin protocol, there is no Segregated Witness (Segwit) transaction, The digital signature is stored in the SigScript field of input in UTXO, and the transaction using isolated witness is stored in the Witness field. A digital signature consists of encoded r and s values, both 256-bit (32-byte) integers, and a SigHash flag indicating which part of the transaction was signed.

DER-encoded ECDSA signature

Bitcoin client since the first version, Both rely on OpenSSL for signature verification and encoding. ECDSA signatures are encoded using the Unique Encoding Rules (DER) defined in the ANS.1 Encoding Rules. While the DER encoding only allows a sequence of bytes to represent a signature in only one way, the OpenSSL library considers other encodings derived from the DER standard to be valid as well. When this feature changes in the OpenSSL library, it causes some nodes using newer OpenSSL versions to reject chains from nodes using older versions of the library. For this reason, BIP-66 proposed a soft fork (Soft fork) proposal, and only signatures that strictly follow the DER encoding will be accepted.

A DER encoded ECDSA signature ends with a 0x30 identifier to identify a composite structure. Next comes a length byte, indicating the length of the structure, and then the composite structure itself. The compound structure contains integer values of r and s preceded by the 0x02 identifier used to represent integers, followed by a length byte defining the length of the respective value.

The digital signature format of DER encoding in Bitcoin

< p>However, signed integers (Signed) are used in the ANS.1 coding rules, while the r and s values in ECDSA are unsigned integers (Unsigned), so when the first bit of the r or s value is set When it is 1, the value will be wrongly judged. To fix this, a 0x00 byte is prefixed to the value to encode the unsigned integer as a positive integer. In the original r and s values, we call it high if the first bit is 1, and low otherwise.

73 bytes consisting of high r and high s Coin ECDSA signature

The generation of r value and s value is random, when both values are high (the first bit of both values is 1), they both require a 0x00 byte at the beginning. Adding two extra bytes and the SigHash flag, the total length of the signature is 73 bytes. It can be found that in the same signature, the probability that both r and s are high is 25%. Until early 2014, a distribution of approximately 25% at 73 bytes, 50% at 72 bytes, and approximately 25% at 71 bytes could be observed for signatures on the Bitcoin blockchain. In a 72-byte signature, one of the two values is high and the other is low, while in a 71-byte signature, both values are low.

After the release of Bitcoin Core v0.9.0 in March 2014, the proportion of signatures with high s-values started to decrease. This release includes a modification to the Bitcoin Core wallet to only create signatures with low s values. With the release of Bitcoin Core v0.10.3 and v0.11.1 in October 2015, signatures with high s-values were considered non-standard signatures to completely eliminate mutability vectors. This prohibits transactions with high s values from being forwarded or used for mining. Starting in December 2015, almost all transactions on the Bitcoin blockchain have low s in their signatures.

72-byte Bitcoin ECDSA signature composed of high r and low s

December 2015 to early 2018 , the almost average length of a signature on the blockchain is between 72 and 71 bytes. The 72-byte signature has a high r value and a low s value, and requires a prepended 0x00 byte. And the 71-byte signature consists of a low r value and a low s value.

At the end of August 2017, the Segregated Witness (Segwit) soft fork was activated. Segregated Witness moves the SigScript containing the signature etc. into the Witness field. While the signature of a SegWit transaction will not be counted when calculating the size of the transaction, the size of the signature on the blockchain is effectively constant.

71-byte Bitcoin ECDSA signature composed of low r and low s

Bitcoin released in October 2018 The Core v0.17.0 release includes improvements to the Bitcoin Core wallet to only generate 71-byte signatures. By re-signing the transaction with a different nonce, new r-values can be generated until a low r-value is found. The technology has been adopted by other projects such as the NBitcoin library and the Electrum bitcoin wallet.

Schnorr signature

BIP-340 introduces Schnorr signature for Bitcoin, And BIP-341 proposes the first version of SegWit output types and their spending rules based on Schnorr signatures, Taproot and Merkle branches. Unlike ECDSA signatures, Schnorr signatures are not DER encoded.

Schnorr signature format

A Schnorr signature consists of a 32-byte r-value and a 32-byte s-value. The most commonly used SigHash flag, SIGHASH_ALL, is the default and does not need to be set explicitly, while the other SigHash flags are placed after the s value. A Schnorr signature with the default SIGHASH_ALL flag is exactly 64 bytes long, and a signature with a different SigHash flag is 65 bytes long.

A 64-byte SIGHASH_ALL Bitcoin Schnorr signature

Compared with ECDSA signature, Schnorr signature is shortened by 6 to 9 characters Festival. These savings come from the removed encoding overhead and default SigHash flags. With Schnorr signature adoption at 20%, assuming only one signature is included in the 800,000 UTXO inputs spent per day, this saves more than 1MB of blockchain space per day.

The Evolution of Bitcoin Signatures

DER-encoded ECDSA signature

Schnorr signature

Related reading