Technological breakthroughs are the engine that promotes the advancement of the blockchain industry. Binance China Blockchain Research Institute and ChainNews are both organizations that pay close attention to the forefront of technological development in the fields of blockchain and cryptography. The “Stone” column introduces the world’s most noteworthy blockchain technology developments to readers in the Chinese world, as well as the latest application analysis and developments in finance and other industries, in order to provide reference and thinking for China’s blockchain industry to “teach jade”
This article introduces that the Schnorr signature proposed by BIP-340 is 6 to 9 bytes shorter than the ECDSA signature, which can save more blockchain space.
Written: 0xB10C, Bitcoin developer translation: Chen Bo Yu, Hsu Tzu Hsiu
Digital signatures are an important component in the Bitcoin protocol and account for a large part of the data stored on the blockchain. This article details how the coded elliptic curve digital signature algorithm (ECDSA) signature size has been continuously reduced in the past few years, and compares the length of the newly proposed Schnorr signature with the current ECDSA signature.
In the Bitcoin protocol, for transactions that do not use Segregated Witness (Segwit), the digital signature is stored in the SigScript field of input in UTXO, while transactions that use Segregated Witness are stored in the Witness field. A digital signature consists of the encoded r and s values and a SigHash flag indicating which part of the transaction was signed. The r and s values are both 256-bit (32-byte) integers.
DER-encoded ECDSA signature
Since the first version of the Bitcoin client, it has relied on OpenSSL for signature verification and encoding. ECDSA signatures are encoded using the unique encoding rule (DER) defined in the ANS.1 encoding rules. Although the DER encoding only allows a sequence of bytes to represent a signature in a unique way, the OpenSSL library treats other encodings derived from the DER standard as valid. When this feature in the OpenSSL library changes, it will cause some nodes that use newer OpenSSL versions to reject chains from nodes that use the old version of the library. For this reason, BIP-66 proposed a soft fork (Soft fork) proposal, only signatures that strictly follow the DER encoding will be accepted.
A DER-encoded ECDSA signature starts with a 0x30 identifier to identify a composite structure. Next is a length byte, indicating the length of the structure, and then the composite structure itself. The composite structure contains the integer values of r and s. These values will put the 0x02 identifier used to represent the integer at the beginning, followed by a length byte to define the length of each value.
DER-encoded digital signature format in Bitcoin
However, the ANS.1 encoding rules use signed integers (Signed), and the r value and s value in ECDSA are unsigned integers (Unsigned), so when the first bit of the r value or s value is set to 1 The hour value will be wrongly judged. In order to solve this problem, a 0x00 byte is added before the value, so that the unsigned integer is encoded as a positive integer. In the original r value and s value, if the first bit is 1, we call it high, otherwise it is called low.
73-byte Bitcoin ECDSA signature composed of high r and high s
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 need to add a 0x00 byte at the beginning. With the addition of 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 the values of r and s are high is 25%. Until the beginning of 2014, signatures on the Bitcoin blockchain could observe a distribution of approximately 25% of 73 bytes, 50% of 72 bytes, and approximately 25% of 71 bytes. 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 Bitcoin Core v0.9.0 was released in March 2014, the proportion of signatures with high s values began to decrease. This version includes changes to the Bitcoin Core wallet, allowing the 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 recognized as non-standard signatures to completely eliminate the variability vector. This prohibits transactions with high s value from being forwarded or used for mining. Since December 2015, the value of s in the signature of almost all transactions on the Bitcoin blockchain has been low.
72-byte Bitcoin ECDSA signature composed of high r and low s
From December 2015 to early 2018, the almost average length of signatures on the blockchain was between 72 and 71 bytes. The 72-byte signature has a high r value and a low s value, and requires a preset 0x00 byte. The 71-byte signature is composed 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 SigScript containing signatures and other content into the Witness field. Although when calculating the size of the transaction, the signature of the Segregated Witness transaction will not be included in the calculation, but the size of the signature on the blockchain is actually unchanged.
71-byte Bitcoin ECDSA signature composed of low r and low s
The Bitcoin Core v0.17.0 version released in October 2018 includes improvements to the Bitcoin Core wallet and only generates 71-byte signatures. By re-signing the transaction with a different nonce, a new r value can be generated until a low r value is found. This technology has been adopted by other projects such as NBitcoin library and Electrum Bitcoin wallet.
Schnorr signature
BIP-340 introduced Schnorr signatures for Bitcoin, and BIP-341 proposed the first version of SegWit output types and their spending rules based on Schnorr signatures, Taproot and Merkle branches. The difference with ECDSA signature is that Schnorr signature is not DER encoded.
Schnorr signature format
The Schnorr signature contains 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 explicitly set, while other SigHash flags are placed after the s value. The length of the Schnorr signature using the default SIGHASH_ALL flag is exactly 64 bytes, and the length of the signature using different SigHash flags is 65 bytes.
A 64-byte SIGHASH_ALL Bitcoin Schnorr signature
Compared with ECDSA signature, Schnorr signature is shortened by 6 to 9 bytes. These savings come from the removal of encoding overhead and the default SigHash flag. With a Schnorr signature adoption rate of 20%, assuming that only one signature is included in the 800,000 UTXO inputs spent every day, more than 1MB of blockchain space can be saved every 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
Source link: b10c.me
