What are Schnorr signatures? What is Taproot?

What is the Schnorr signature scheme?

The Schnorr signature scheme is a digital signature scheme that allowsincrease the privacy and scalability of the bitcoin network.

Who invented the Schnorr signature scheme when?

Schnorr Signature Scheme and Taproot Technology - Thissuggestions for improving the Bitcoin protocol BIP-340 and BIP-341. On January 21, 2020, developer Peter Welle included in the request for acceptance of changes for the soft fork.

Schnorr's signature scheme was proposed in 1991 by German cryptographer, professor of 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 publication of the scheme, Schnorr got a number on it.patents that 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 toselect 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.

ECDSA in Bitcoin has become faster and more efficient thanks to the work of Peter Welle and his colleagues, who created an improved elliptic curve,secp256k1.

ECDSA has some flaws, and developerswere 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?

Security

Like ECDSA, Schnorr's signatures use the taskdiscrete logarithm. 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's signatures are provably inflexiblewhereas ECDSA signatures are flexible, which gives a third party that does not have access to the private key the opportunity to change the existing valid signature and make a double waste.

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 theymay be subject to 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.

Schnorr's signature linearity property allowsaggregate 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-out-5 multi-signature, we have M = 3 signatures (out of n = 5) as part of the transaction inputs.

M-of-n multi-signature transactions require at least M signatories and verification of each signature. To confirm ownership of the UTXO multisig key, unlock scriptscriptSigmust contain the number M of ECDSA signatures. Sizescriptsigsgrows linearly with the number M of 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.

Observer will no longer be able to bind signaturetransactions with one person, many people, or a threshold number of people. Although the addresses and amounts in transactions are still publicly available, Schnorr's signatures make it difficult to use wallet / fingerprint identification technology.

Decrease transaction size and increase verification speed

Schnorr signatures are 11% smaller in sizeexisting signatures that occupy approximately 70–72 bytes per 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 containsmany 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 needonly 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 opt out of checking 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 call in the environmentdevelopers of objections. They consider this scheme to be the best existing one, 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, ordinarythe 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 exit and a new way to determine the spending conditions.

Taproot close, or the next step in the evolution of bitcoin

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 Poelstrapublished a mathematical proof of security (security proof). In July of that year, Xapo engineer and Bitcoin Core developer Anthony Townes proposed a solution to increase the amount of data used by Taproot.

May 6, 2019 Peter Velle publishedsuggestions 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.

On January 21, 2020, Velle included Taproot in a request for changes for the next soft fork.

What features does Taproot provide?

If Schnorr's Signatures Allow Multi-SignedSince transactions 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 given the appearance of standard transactions:

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 can sometimes lead to the fact that all parties agree with the result.

These four categories of use casesrepresent 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.

Other 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.

Thanks to SegWit on the Bitcoin network, the MAST concept got a second life

The MAST (Merkle Tree-based Abstract Syntax Tree) technology was proposed in 2016 by the 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 contractswith many different qualifiers. Only the executable script is opened, which saves space in the blockchain and allows you to implement more complex scripts / contracts.

Merkle tree is created through individualHashing each script to get 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 repeats and continues untiluntil 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), MASTallows you to structure many conditions of spending 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 thatsays that the party cannot spend its coins before the expiration of the month (timelock), or the coins can be spent through a 3 out of 5 multi-signature transaction, then both conditions will be revealed as soon as the coins are spent (this scheme works now in bitcoin) .

MAST gives the following opportunity: if any data in the Merkle tree is disclosed, then the Merkle root and some additional data (referred to as 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.

Complex contract users can createsmaller 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 may even add tothe MAST structure has a longer chain of beneficiaries 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 the default formaintaining 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 other spending conditions exist. 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, sohow the changes necessary 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.

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 openeduntil a waste has been made. Different scripts can be organized in the Merkle tree, and the outputs can also be spent by opening one of the qualifiers.

If we spend transaction using primarythe waste script, we just give Merkel's proof, which consists of the primary waste script and the hash of the alternative waste script - this is enough to confirm that the primary waste script is contained in the script tree.

Taproot uses the MAST structure to hidethe 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, MAST structurehidden thanks to Taproot exits. 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 variations of multi-signature2 out of 2. 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 parties agree, the result looks as if someone has used up this output using a regular signature, sending it 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, TapBranch hash onthe chart 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 privatethe 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 changed 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 Bobagree 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 script used is expanded. 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 treeoffers 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 allow significantsave on commissions, because scripts that require processing a large amount of data no longer have to pay commissions whose amounts 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 you to exercisecomplicated 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.

In terms of privacy, Taproot allowsminimize information on spending conditions for the exit of the 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 Schnorr's scheme allows you to givemulti-subscription transactions, the visibility of ordinary Pay-to-Public-Key-Hash transactions, Taproot expands the range of transactions that can be given such visibility (make Pay-to-Public-Key-Hash and Pay-to-Script-Hash indistinguishable).

Read this: