[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 sig]:

## 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) The code is: # Schnorr signature built using: # Elliptic Curve Cryptography using the BitCoin curve, SECG secp256k1 # This version uses the X,Y,Z "Jacobi coordinates" representation, for speed # Dr. Orion Lawlor, lawlor@alaska.edu, 2015-03-25 (Public Domain) from hashlib import sha256 from math import log from copy import copy from time import time # timing from fractions import gcd # Greatest Common Denominator from random import SystemRandom # cryptographic random byte generator rand=SystemRandom() # create strong random number generator import sys M="I am a fish"; # message if (len(sys.argv)>1): M=str(sys.argv[1]) # Convert a string with hex digits, colons, and whitespace to a long integer def hex2int(hexString): return int("".join(hexString.replace(":","").split()),16) # Half the extended Euclidean algorithm: # Computes gcd(a,b) = a*x + b*y # Returns only gcd, x (not y) # From http://rosettacode.org/wiki/Modular_inverse#Python def half_extended_gcd(aa, bb): lastrem, rem = abs(aa), abs(bb) x, lastx = 0, 1 while rem: lastrem, (quotient, rem) = rem, divmod(lastrem, rem) x, lastx = lastx - quotient*x, x return lastrem, lastx # Modular inverse: compute the multiplicative inverse i of a mod m: # i*a = a*i = 1 mod m def modular_inverse(a, m): g, x = half_extended_gcd(a, m) if g != 1: raise ValueError return x % m # An elliptic curve has these fields: # p: the prime used to mod all coordinates # a: linear part of curve: y^2 = x^3 + ax + b # b: constant part of curve # G: a curve point (G.x,G.y) used as a "generator" # n: the order of the generator class ECcurve: def __init__(self): return # Prime field multiplication: return a*b mod p def field_mul(self,a,b): return (a*b)%self.p # Prime field division: return num/den mod p def field_div(self,num,den): inverse_den=modular_inverse(den%self.p,self.p) return self.field_mul(num%self.p,inverse_den) # Prime field exponentiation: raise num to power mod p def field_exp(self,num,power): return pow(num%self.p,power,self.p) # Return the special identity point # We pick x=p, y=0 def identity(self): return ECpoint(self,self.p,0,1) # Return true if point Q lies on our curve def touches(self,Q): x=Q.get_x() y=Q.get_y() y2=(y*y)%self.p x3ab=(self.field_mul((x*x)%self.p+self.a,x)+self.b)%self.p return y2==(x3ab)%self.p # Return the slope of the tangent of this curve at point Q def tangent(self,Q): return self.field_div(Q.x*Q.x*3+self.a,Q.y*2) # Return a doubled version of this elliptic curve point # Closely follows Gueron & Krasnov 2013 figure 2 def double(self,Q): if (Q.x==self.p): # doubling the identity return Q S=(4*Q.x*Q.y*Q.y)%self.p Z2=Q.z*Q.z Z4=(Z2*Z2)%self.p M=(3*Q.x*Q.x+self.a*Z4) x=(M*M-2*S)%self.p Y2=Q.y*Q.y y=(M*(S-x)-8*Y2*Y2)%self.p z=(2*Q.y*Q.z)%self.p return ECpoint(self,x,y,z) # Return the "sum" of these elliptic curve points # Closely follows Gueron & Krasnov 2013 figure 2 def add(self,Q1,Q2): # Identity special cases if (Q1.x==self.p): # Q1 is identity return Q2 if (Q2.x==self.p): # Q2 is identity return Q1 Q1z2=Q1.z*Q1.z Q2z2=Q2.z*Q2.z xs1=(Q1.x*Q2z2)%self.p xs2=(Q2.x*Q1z2)%self.p ys1=(Q1.y*Q2z2*Q2.z)%self.p ys2=(Q2.y*Q1z2*Q1.z)%self.p # Equality special cases if (xs1==xs2): if (ys1==ys2): # adding point to itself return self.double(Q1) else: # vertical pair--result is the identity return self.identity() # Ordinary case xd=(xs2-xs1)%self.p # caution: if not python, negative result? yd=(ys2-ys1)%self.p xd2=(xd*xd)%self.p xd3=(xd2*xd)%self.p x=(yd*yd-xd3-2*xs1*xd2)%self.p y=(yd*(xs1*xd2-x)-ys1*xd3)%self.p z=(xd*Q1.z*Q2.z)%self.p return ECpoint(self,x,y,z) # "Multiply" this elliptic curve point Q by the scalar (integer) m # Often the point Q will be the generator G def mul(self,m,Q): R=self.identity() # return point while m!=0: # binary multiply loop if m&1: # bit is set #print(" mul: adding Q to R =",R); R=self.add(R,Q) #print(" mul: added Q to R =",R); m=m>>1 if (m!=0): #print(" mul: doubling Q =",Q); Q=self.double(Q) return R # A point on an elliptic curve: (x,y) # Using special (X,Y,Z) Jacobian point representation class ECpoint: """A point on an elliptic curve (x/z^2,y/z^3)""" def __init__(self,curve, x,y,z): self.curve=curve self.x=x self.y=y self.z=z # This self-check has a big performance cost. #if not x==curve.p and not curve.touches(self): # print(" ECpoint left curve: ",self) # "Add" this point to another point on the same curve def add(self,Q2): return self.curve.add(self,Q2) # "Multiply" this point by a scalar def mul(self,m): return self.curve.mul(m,self) # Extract non-projective X and Y coordinates # This is the only time we need the expensive modular inverse def get_x(self): return self.curve.field_div(self.x,(self.z*self.z)%self.curve.p); def get_y(self): return self.curve.field_div(self.y,(self.z*self.z*self.z)%self.curve.p); # Print this ECpoint def __str__(self): if (self.x==self.curve.p): return "identity_point" else: return "("+str(self.get_x())+", "+str(self.get_y())+")" # This is the BitCoin elliptic curve, SECG secp256k1 # See http://www.secg.org/SEC2-Ver-1.0.pdf secp256k1=ECcurve() secp256k1.p=hex2int("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F"); secp256k1.a=0 # it's a Koblitz curve, with no linear part secp256k1.b=7 # n is the order of the curve, used for ECDSA secp256k1.n=hex2int("FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141"); # SEC's "04" means they're representing the generator point's X,Y parts explicitly. secp256k1.G=ECpoint(curve=secp256k1, x = hex2int("79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798"), y = hex2int("483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8"), z = 1 # projective coordinates, start with Z==1 ); ################# # Test program: curve=secp256k1 Q=curve.G #print("Generator touches curve? ",curve.touches(Q)); #print("Curve order times generator: ",curve.mul(curve.n,Q)); start=time() # Hash the message M and the curve point R # (this isn't any offical scheme, but a simple ASCII concatenation) def hashThis(M,C): hash=sha256(); hash.update(M.encode()); hash.update(str(R).encode()); return int(hash.hexdigest(),16); # part 1 of signature # Make signing key G=curve.G; # generator of curve n=curve.n; # order of curve d=rand.getrandbits(256)%n # secret key Q=G.mul(d); # move down curve by x to make public key # Schnorr signature process: # uses message and secret key x print "Message:\t",M k=rand.getrandbits(256)%n; # message nonce print "Message nouce:\t",k print R=G.mul(k); # used to encode e=hashThis(M,R); # part 1 of signature s=(k-e*d)%n; # part 2 of signature print "Part 1 of signature (e):\t",e print "Part 2 of signature (s):\t",s print print("Signature (e,s)=",e,",",s); # Verification procss: # uses message, public key Y, signature e, s Rv=G.mul(s).add(Q.mul(e)); ev=hashThis(M,Rv); # check signature if (e==ev): print("Signature valid!"); else: print("Signature invalid: R=",R," and Rv=",Rv); #print("schnorr elapsed=",time()-start," seconds") print "\nElliptic curve details (secp256k1)" print "Generator (G):\t",G print "Order of curve:\t",n print "Secret key (d):\t",d print "Public key (Q):\t",Q ## Presentation |