슈노 시그니쳐 (Schnorr Signatures)

<Sig A> <Sig B> <Sig C> 3 <PubKey A><PubKey B><PubKey C>  3 CHECKMULTISIG

<Sig Z> 1 <PubKey Z> 1 CHECKMULTISIG

그룹들의 signs 를 한방에 verify 할 수 있는데  아래와 같은 수식으로 표현 가능하다.

* 구글링을 통한 지식들을  통해 암호학을 공부를 해서 그런지 잘 모르고 사용하는게 많은데 ..그중 그룹서명에 대한 검증에서 
Group Signature 는 10명중 1명의 익명의 서명에 대한 검증에 관한 것이고
Aggregation Signature 는 10명중에 n 명의 서명에 대해 검증에 관한 것이고 
Threadhold Signature 는 10명중에 n 명의 익명의 서명에 대해 검증에 관한 것임을  모 대학 암호학 교수님을 통해 확인 했다. 

How Schnorr Signatures work

m = Message
x = Private key
G = Generator point
X = Public key (X = x*G, public key = private key * generator point)
(R, s) = Signature (R is the x co-ordinate of a random value after multiplying by the generator point, s is the signature)
H(x, y, z..) = Cryptographic Hashing function
* Capitalised letters are usually points on an Elliptic curve (except the Hashing function)
* Lower cased letters are usually scalars
==========================================================
Schnorr Signatures
==========================================================

Signature creation:
(R, s) = (r*G, r + H(X, R, m) * x)
* r is a random nonce
R = random nonce * generator point (becomes a point on the Elliptic Curve)
s = random nonce + Hash function(Users Public Key, Random point on Elliptic Curve, the message (transaction)) * Private Key

Signature verification:
s*G = R + H(X,R,m) * X
* Verification is a linear equation, both sides of the equation must be satisfied for the signature to be validsignature
* generator point = Random Point on Elliptic Curve + Hashing function(Public Key, Random Point on Elliptic Curve, message (transaction)) * Public Key

Naive implementation of Schnorr Signatures

=========================================================
Naive Schnorr Signatures
=========================================================

Signature creation:
X = the summation of each Public Key Point
* X = (Xi + (Xi+1) + (Xi+2)...)
R = the summation of each participants random nonce
* R = (Ri + (Ri+1) + (Ri+2)...)
s = the summation of each participants signature
* si = ri + H(X,R,m) * X
* s = (si + (si+1) + (si+2)...)
(R, s) = is the signature with s being the summation of all signatures

Signature verification:
s*G = R + H(X,R,m) * X
* X represents the summation of all participants Public Keys

Rogue Key Attacks

Rogue Key Attack:

* Alice and Bob want to create a 2-of-2 Multi-Sig
* Alice has a key pair of (xA, XA) (Private Key, Public Key)
* Bob has a key pair of (xB, XB) (Private Key, Public Key)
* We can assume that XAB (Aggregated Public Key) = XA + XB
* Bob sends a false Public Key: XBf = XB - XA
* This is important because the Aggregated Key (XAB) that emerges from using Bob's false Public Key is actually equal to Bob's true key XB
* Other users may think they are sending to a 2-of-2 controlled by Alice and Bob but it's simply an address controlled by Bob's true Public Key

An extremely simplistic example:
XA (Alice's Public Key) = 10
XBt (Bob's true Public Key) = 11
XBf (Bob's false Public Key) = XBt(11) - XA(10) = 1
XAB = XA(10) + XBf(1) = 11

* Bob has attacked the Aggregated Public Key, by sending a false key which after aggregation with other keys, equals his true Public Key
* Bob now controls the Multi-Sig

Bellare-Neven

===========================================================
Bellare-Neven
===========================================================

Signature creation:
L = H(Xi + (Xi+1)...)
* L is the hash of the summation of all Public Keys
R = (ri * G) + ((ri+1) * G)...
* R is the summation of each participants Random Point
* They share their Random Nonce Points with other signers
si = ri + H(L, Xi, R, m) * xi
* si is the signature generated for each participant
* si = random nonce + Hash(Hash of all Public Keys, Participants Public Key, Sum of all Random Points, message (transaction)) * Participants Private Key
s = (si) + (si+1) + (si+2)...
* s is the summation of each participants signature
* (R, s) is the final signature

Signature verification:
s*G = R + H(L,X1,R,m) * X1 + H(L,X2,R,m) * X2 +...
* Verification is a linear equation, both sides of the equation must be satisfied for the signature to be valid
* sum of participants signatures * generator point = sum of Random Nonce Points + Hash(Sum of all Public Keys, Participant 1’s Public Key, Sum of Random Nonce Points, message (transaction)) * Participants 1’s Public Key... same is repeated for each participant

Mu-sig

===========================================================
Mu-sig
===========================================================

Signature creation:
L = H(Xi + (Xi+1)...)
* L is the hashed summation of all Public Keys
X = ( (H(L, Xi) * Xi) + (H(L, Xi+1) * Xi+1)...)
* X is the sum of all Hashed Public Keys + Participants Public Key- Hash(Sum of all Public Keys hashed, Participant 1's Public Key) * Participant 1’s Public Key
R = (ri * G) + ((ri+1) * G)...
* R is the summation of each participants Random Point
* They share their Random Nonce Points with other signers
si = ri + H(X, R, m) * H(L, X) * xi
* si is the signature generated for each participant
* si = random nonce + Hash(X, Sum of all Participant's Random Points, message (transaction)) * Hash(Hashed sum of all Public Keys, X) * Participant's Private Key
s = (si) + (si+1) + (si+2)...
* s is the summation of each participants signature
* (R, s) is the final signature

Signature verification:
s*G = R + H(X, R, m) * X
* Verification is a linear equation, both sides of the equation must be satisfied for the signature to be valid
* sum of participants signatures * generator point = sum of Random Nonce Points + Hash(X, sum of Random Nonce Points, message (transaction)) * X

---

https://bitcointechtalk.com/scaling-bitcoin-schnorr-signatures-abe3b5c275d1
https://medium.com/digitalassetresearch/schnorr-signatures-the-inevitability-of-privacy-in-bitcoin-b2f45a1f7287
https://webusers.imj-prg.fr/~ricardo.perez-marco/blockchain/Seurin.pdfhttps://medium.com/digitalassetresearch/schnorr-signatures-the-inevitability-of-privacy-in-bitcoin-b2f45a1f7287

 

Scaling Bitcoin: Schnorr Signatures