[Back] Schnorr signatures integrate "native multisig" which allows multiple signatures to be aggregated into a valid signature using the sum of the related keys:

## Schnorr multi-signatures## BackgroundLet's say we have a transaction, and Bob, Alice and Trent must authorise it. In a Bitcoin network this is defined as a "multisig" setup. Bob, Alice and Trent must then go away and create their own new "aggregated" signature, which will be their new public key for transactions. This is not efficient, and also reveals the Bob, Alice and Trent are working together. In an improved setup, we can define an n-from-m setup, where we can merge Bob, Alice and Trent's keys into one public key, and then use that. The public key will then not reveal that Bob, Alice and Trent are working together, but they will create a new public key which will validate the transaction. If we wanted just any two of them to validate it, we could ask for a 2-from-3 multisig. So if Bob, Alice and Trent are directors in a company, they could define that any two of them could validate a transaction. The Bitcoin network could have found a way to enable this type of signature merging of public keys, and it all points to the Schnorr method. In illustration below, we can see that the current method involves Bob, Alice and Trent getting together and creating a new public key (and an associated private). With Schnorr's key aggregation method, we can take Bob, Alice and Trent's public keys and then merge into a new transaction key. It will then not be possible to see the parties who created the transaction key. ## The ECDSA bottleneckBitcoin is a bit of a hotch-potch of cryptography, but it all seems to work. Unfortunately, it is having trouble scaling up, and one of the bottlenecks is the signature. For this we create a private key, and then use the Elliptic Curve DSA method to produce a signature of this key: In this way, the Bitcoin infrastructure knows that the person with the correct private key has signed the transaction. Unfortunately, ECDSA is not an efficient method. ## Schnorr's method of signature aggregationThis method, though, suffers from performance issues. In a paper by Maxwell etc at, they describe a way to bunch Schnorr's multi-signatures (multisig) data into a signature which improves performance and transaction privacy (paper). It will support one person sending a transaction from multiple sources, and which will produce a single signature. At the present time, multisig is trademarked, but the patent has elapsed. It also lacks standardisation, but this new application is likely to accelerate this process. Schnorr this allows multiple signatures to be merged into a single valid signature, by just summing the keys of the inputs. In a performance analysis, Schnorr is slightly faster than ECDSA, but it provides several significant performance improvements. A major advantage is that each of the input signatures do not need to be checked, as only the overall signature is checked. The output also provides a signature of the same size, no matter the number of users who provide their inputs. Another advantage is that this reduction in data will improve the capacity of the Bitcoin infrastructure. For privacy, Schnorr's method the transaction signatures will not be observable, and thus user privacy will be preserved. All that will be available is an overall signature for aggregated transactions. For many participants, it will not be possible to determine which of them was actually responsible for a transaction. ## Fixing the cancellation problemurrent challenge is related to the cancellation problem, and where a group of users could possibly create a validate transaction signature from the summation of their keys. For example if we have two public keys (K1 and K2). Normally they would advertise their keys as K1 and K2, but an adversary then maliciously advertises the keys as K2-K1 and K1. When summated we get the key of the adversary (K2) - see the diagram below. Now the funds which are sent to this joint public key will be associated to the owner of the K2 key (and the owner of the K1 key will not know about the transaction). The two key process is defined as a 2-of-2 multisig. The solution is now to multiple all of the keys when the summation of the keys is created, and then taking a hash of it. The transactions can then be signed. It is likely that Schnorr's signatures could be used in OP_CHECKSIG (which checks the ECDSA signature on a transaction against the public key) and OP_CHECKMULTISIG. With spend request with multiple signatures, the Bitcoin networks are currently required to call OP_CHECKMULTISIG, and this would be replaced by a signal call to OP_CHECKSIG (and thus improving privacy). Thus for a spend where n-of-m signatures are required to authorize a signature, OP_CHECKMULTISIG checks all of the public keys and their signatures (for up to n signatures), but now it can be checked by a single signature (and which combines all of the associated public keys). ## Method outlineThe following defines the method (from Wikipedia page): and a sample run is here: Message: Hello. How are you? Message nouce: 5514729472329197480356877131576666044583793826038073996340127152735130596118 Part 1 of signature (e): 112826057692783525864029497985844875565342980216708705561433697493208154933726 Part 2 of signature (s): 71671724344889042061558986776686333373351499384926538019936398986039255461877 ('Signature (e,s)=', 112826057692783525864029497985844875565342980216708705561433697493208154933726L, ',', 71671724344889042061558986776686333373351499384926538019936398986039255461877L) Signature valid! Elliptic curve details (secp256k1) Generator (G): (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) Order of curve: 115792089237316195423570985008687907852837564279074904382605163141518161494337 Secret key (d): 72541826218415106777373825743472310875233191059878020240249013045184824290527 Public key (Q): (48297987211257358412393956710601526126243412150755958193398666111265521397213, 68799584558249779175981250742970438468230076342822056016849262785882846025854) ## Presentation |