What is the Schnorr signature scheme?
Schnorr Signature Scheme is a digital signature scheme that allows you to increase the privacy and scalability of the Bitcoin network.
Who invented the Schnorr signature scheme when?
Schnorr's signature scheme and Taproot technology are suggestions for improving the BIP-340 and BIP-341 bitcoin protocol. On January 21, 2020, developer Peter Velle included in the request for acceptance of changes for the soft fork.
Schnorr's signature scheme was proposed in 1991 by German cryptographer, professor at Frankfurt University Klaus-Peter Schnorr.
The scheme proposed by Schnorr is a modification of the schemes of El-Gamal (1985) and Fiat-Shamir (1986), but has a smaller signature size, and also uses the achievements of the cryptographer David Chaum .
Before the scheme was published, Schnorr received a number of patents for it, which expired in 2008, when Satoshi Nakamoto introduced Bitcoin. Schnorr's signatures could already be used at that time, but they were not standardized and not widely used.
When Nakamoto created Bitcoin, he had to choose one of the existing signature schemes. He needed an easy-to-use and safe open source algorithm. ECDSA met these requirements . The predecessor of ECDSA, the DSA algorithm, was a hybrid of the Schnorr scheme and the El-Gamal scheme and was created to circumvent Schnorr patents.
Bitcoin's ECDSA has become faster and more efficient thanks to the work of Peter Welle and his colleagues who created an improved elliptical curve, secp256k1 .
ECDSA has some flaws, and developers are looking for an alternative. The first discussions on the possible implementation of Schnorr's signatures on the Bitcoin network took place in 2014, and a few years later, developer Peter Velle published Schnorr BIP .
What are the key technical features of Schnorr signatures and their advantages over ECDSA?
Safety
Like ECDSA, Schnorr signatures use the discrete logarithm problem. The advantage of Schnorr signatures is that they use fewer assumptions and have reliable formal logical proof: their safety is easy to prove using the random oracle model and the rather complicated discrete logarithm problem in the group of elliptic curve points (ECDLP).
Schnorr Signatures is a more transparent application technology that is easier for cryptographers to work with.
Inflexibility
Schnorr signatures are provably inflexible, while ECDSA signatures are flexible, which allows a third party that does not have access to the private key to modify the existing valid signature and spend double.
Linearity
A significant advantage of Schnorr signatures is the property of linearity, realized through linear mathematics.
Schnorr's signatures are linear in the sense that they can be the subject of addition or subtraction. The result of such operations is a valid signature corresponding to the same addition (or subtraction) of public keys. In the case of ECDSA, such a scheme does not work - subtracting or adding such digital signatures does not make sense.
The linearity property of Schnorr signatures allows aggregation of keys and signatures. Aggregation means the ability to combine several public keys into one so that all parties require one signature. By adding the keys of several inputs, they can be aggregated into a single signature, consisting of partial signatures of all signatories.
The equations below illustrate the aggregation process, possible due to the linearity property of Schnorr's signatures. No one except the participants knows that three people are behind one public key / signature.
In multi-subscription M-of-n transactions, partial signatures are known as threshold signatures. As the graph below shows, in 3-of-5 multi -signature, we have M = 3 signatures (of n = 5) as part of the transaction inputs.
M-of-n multisubscription transactions require at least M signatories and verification of each signature. To confirm UTXO ownership of the multi-subscription key, the release scriptSig script must contain the number M of ECDSA signatures. The size of scriptSigs grows linearly in accordance with the number of M signatures, which increases the size of these transactions (and the amount of transaction fees).
In addition, the observer will know that A, B, and C have signed the transaction and will be able to identify the multi-subscription scheme used.
Using Schnorr signatures, M signatures are aggregated into a single signature. Once public keys and threshold signatures are provided, the transaction is authorized and looks like a regular P2PKH transaction.
Schnorr's signatures allow you to create only one signature for all M parties. The release script will have one signature, which is an aggregate of all signatures of the participants.
The observer will no longer be able to associate the transaction signature with one person, many people, or a threshold number of people. Although the addresses and amounts in the transactions are still publicly available, Schnorr's signatures make it difficult to use wallet / fingerprint identification technology.
Decrease transaction size and increase verification speed
The size of the Schnorr signature is 11% smaller than the existing signatures, which occupy approximately 70-72 bytes in the transaction. Since they take up less space on the blockchain (their fixed size is 64 bytes), this allows you to reduce the size of the transaction and lower fees.
Also, if a bitcoin transaction contains many inputs, each of them needs a separate signature. For a Bitcoin transaction controlled by many signatories, each signatory must put a separate ECDSA signature. These signatures are verified individually. To effectively verify a group of signatures, it is necessary to use mathematical calculations.
Thanks to Schnorr's signatures, all inputs will need only one combined signature. Including one signature in a transaction provides additional options for other transactions. Reducing the size of transactions for multi-subscription transactions reduces commission. Aggregation of keys allows you to refuse verification of each individual entry and speed up the verification process.
Compact multi-signature with ECDSA is more difficult to create, since such signatures are encoded according to the DER standard , unlike Schnorr signatures, the encoding of which requires less space.
How will the Schnorr signature scheme be implemented?
BIP-340 is a standardization of Schnorr signatures, allowing you to integrate them into the Bitcoin protocol.
The update itself does not cause objection among developers. They consider this scheme to be the best of the existing ones, since its mathematical properties provide a high level of calculation accuracy, it is resistant to plasticity and relatively fast in terms of transaction confirmation.
If Schnorr's signatures are implemented, the average user will not actually notice their appearance (with the exception of one character in SegWit addresses). Schnorr's signatures will not replace ECDSA in bitcoin - both schemes will coexist.
What is Taproot (BIP-341)?
Taproot (BIP-341) is the second part of the offer, including Schnorr / Taproot / Tapscript. If the Schnorr scheme offers a new type of signature, then Taproot expands their functionality by introducing a new version of the transaction output and a new way to determine the spending conditions.
Who invented Taproot and when?
The technology of Taproot was designed and proposed by the developer of Bitcoin Core and the former CTO of Blockstream Gregory Maxwell.
In April 2018, mathematician Andrew Poelstra published a mathematical proof of security. In July of the same year, Anthony Townes, an Xapo engineer and Bitcoin Core developer, proposed a solution to increase the amount of data used by Taproot.
On May 6, 2019, Peter Velle published proposals for improving the Bitcoin protocol, in which he presented Taproot updates in conjunction with the Schnorr and MAST signatures. To implement the updates in the Bitcoin code base, Velle proposed a soft fork.
Features does Taproot provide?
While Schnorr signatures allow multi-subscription transactions to look like standard (Pay-to-Public-Key-Hash) transactions, then Taproot, in combination with Schnorr signatures, expands these possibilities by increasing the group of transaction types that can be made visible as standard:
- the use of P2PKH and P2WPKH, i.e., single spending;
- n-out-n spending with MuSig or equivalents (similar to the current use of P2SH and P2WSH 2-out-2 multi-signatures);
- k-of-n (for minimum n values) using the most common k signers;
- closures of channels in the Lightning Network , atomic swaps and other protocols, which sometimes can lead to the fact that all parties agree with the result.
These four categories of use cases represent the majority of bitcoin transactions to date. Regardless of the complexity of the contract, Taproot allows you to give the joint result in the blockchain the form of expenses for one key.
The remaining scripts displaying other results of the contract are not added to the blockchain, which frees up space for more complex transactions in a particular block.
How does Taproot work?
Understanding Taproot requires a prior understanding of the MAST solution.
MAST technology (abstract syntax tree based on the Merkle tree) was proposed in 2016 by developer Johnson Lau.
MAST offers the use of a new witness program and, using the Merkle tree, decodes mutually exclusive branches in a script.
The Merkle tree is a data structure; the term “tree” describes the structure of its branches. Typically, the Merkle tree is depicted as in the graph below: the root is at the top, the leaves are at the bottom of the graph.
Using MAST, you can create complex contracts with many different qualifiers. Only the executable script is opened, which saves space in the blockchain and allows you to implement more complex scripts / contracts.
The Merkle tree is created through the individual hashing of each script in order to obtain a short unique identifier. Next, each identifier is combined with another identifier and hashed again, creating another short unique identifier for this pair.
This process is repeated and continues until there is only one identifier, called the Merkle root (Address = Hash (1,2) in the graph above), which uniquely identifies the entire data set in several bytes. Merkle root can be considered as a "safe" for coins.
Unlike Pay-to-Script-Hash (P2SH), MAST allows you to structure many spending conditions in the Merkle tree. In this case, only the fulfilled conditions are revealed: with the help of the root and the Merkle tree, it is confirmed that the condition is in the Merkla tree. The rest of the tree remains hidden.
For example, if we have a complex script that says that a party cannot spend its coins before the expiration of a month (timelock), or coins can be spent through a 3-out-5 multi-signature transaction, then both conditions will be revealed as soon as the coins will be spent (such a scheme works now in bitcoin).
MAST provides the following opportunity: if any data in the Merkle tree is expanded, then the Merkle root and a number of additional data (called the Merkle path) can be used to confirm that specific data has been included in the Merkle tree. The rest of the tree (and, accordingly, other conditions) remain hashed and hidden. This means that, subject to the consent of all participants, it is only necessary to disclose the fulfilled condition.
Users of complex contracts can create smaller transactions, and the gain in efficiency is greater in the case of more complex contracts with a large number of subscripts. MAST, unlike any other existing mechanisms, allows you to have many additional branches, which allows you to create more advanced smart contracts without the additional cost that would burden the bitcoin nodes.
In the illustration above, Alice can even add a longer chain of beneficiaries to the MAST structure without changing the number of bytes used. The size of the commissions does not increase, since it still spends its bitcoins using only 32 bytes. At the network level, blocks will be able to handle more complex transactions.
The flaw is that by default, to maintain the proper level of privacy, everyone is forced to use the MAST structure. The upper branch of the Merkle tree is always visible, and observers can understand that there are other spending conditions. In addition, the load on most transactions that do not need an additional script increases, which leads to an increase in their value.
MAST is still not implemented in bitcoin, as the necessary changes for this are too complex and can lead to consequences that are not easy to calculate. A possible solution to the problem may be the Snorr / Taproot / Tapscript solution package, since it acts as a middle ground between simplicity and additional functionality.
nine
How does Taproot improve MAST?
Taproot offers its own version of the Merkle tree, called the script tree. Participants can choose to spend using:
- public key as an ordinary signature;
- spending with a script.
In the first option, this is the default spending path, where single or multilateral public keys are indistinguishable.
In the second case, hidden scripts are not revealed until a waste has been made. Different scripts can be organized into the Merkle tree, and the outputs can also be spent by opening one of the qualifiers.
If we spend the transaction using the primary spending script, we simply give Merkel's proof, which consists of the primary spending script and the hash of the alternative spending script - this is enough to confirm that the primary spending script is contained in the script tree.
Taproot uses the MAST structure to hide the conditions behind Merkle's root. The Merkle root itself in this scenario is hidden and allows direct spending through the key. Only a single key is sent to the blockchain - no one sees that there are additional conditions.
In combination with Schnorr signatures, the MAST structure is hidden thanks to Taproot outputs. At the top of the Merkle tree there is the option of publishing a single public key and signature. As a result, transactions P2PKH and P2SH look identical.
An illustration is the closure of the Lightning channel.
Lightning channels are 2-of-2 multi-signature variations. Instead of closing a transaction using a cumbersome script, Schnorr allows you to combine signatures and present Taproot as a public key / signature. When both sides agree, the result looks as if someone has used up this output using a regular signature by sending to two addresses. The observer will not be able to determine that this is a Lightning channel.
TapBranch is a script tree (TapTree) for closing the Lightning channel
To hide the MAST structure, the TapBranch hash in the graph above is hashed using an aggregated public key (thanks to the Schnorr scheme, Alice and Bob can add their public keys to create the Taproot internal key).
The resulting hash is used as a private key, from which another modified public key is derived. Changing keys, also known as hiding a key pair, involves embedding scripts 1 and 2.
Next, the modified public key is added to the Taproot internal key to create the Taproot exit key. The process is illustrated below:
As said, there are two key spending. The default spending path is when Alice and Bob agree to close the Lightning channel, and the Taproot exit key ensures that the transaction looks like a standard P2PKH transaction. In other scenarios, the used script is opened as soon as the coins are spent, while all other options remain hidden.
In the above example, if Alice and Bob agree to make a Lightning payment, they can combine the Schnorr signatures together, create the main public key, add the signatures together and create the main signature.
Both parties put partial signatures using their individual keys, and closing the Lightning channel looks like a direct payment to a public key.
In the case when the closure is incompatible, only the used script is opened. Verifiers will be able to determine that the threshold public key has been changed through the Merkle root. However, all other options / scripts will remain hidden.
The graph above shows that the script tree offers a new recovery option to gain access to bitcoins. Taproot provides a recovery option for lost coins (for users with updated wallets). If a single key is lost, it is lost forever. If the user loses the private key, and his funds are in the Taproot exit form, then there must be another way by which the rights to the coins can be claimed (for example, restore 3-of-5 backup keys held by the user's relatives).
Taproot enhances the privacy, efficiency and flexibility of bitcoin scripts, allowing developers to write complex scripts while minimizing the impact on the blockchain.
Complicated transactions can significantly save on commissions, since scripts requiring processing of a large amount of data no longer have to pay commissions, the amounts of which exceed the amount of commissions in the standard Pay-to-Public-Key-Hash transaction. The more complex the transactions, the higher their efficiency.
Because Taproot allows complex transactions with just one signature, the number of bytes used for aggregated keys and signatures does not change depending on the number of signers. When using Witness-Script-Hash (P2WSH) multi-signature, each additional public key adds 8.5 bytes, and each additional signature adds approximately 18.25 bytes.
From a privacy point of view, Taproot allows you to minimize information about the spending conditions for the exit of a transaction, which is disclosed in the blockchain. Thanks to Taproot, most applications can use a key-based spending path that is protected by privacy.
Although the Schnorr scheme allows you to make multi-subscription transactions appear as normal Pay-to-Public-Key-Hash transactions, Taproot expands the range of transactions that can be made visible (make Pay-to-Public-Key-Hash and Pay-to-Script-Hash indistinguishable )
