A couple of questions regarding Schnorr MuSig algorithm math notation

Liam

New member
Reading the "Simple Schnorr Multi-Signatures with Applications to Bitcoin" by Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille .pdf link. I have some questions about some notations. I am generating a signature but the verification doesn't pass which leads me to believe I am misunderstanding some stuff here.

in ai = Hagg(L,Xi) what do we hash? Is it the all public keys (L) "concatenated" together then public key i "concatenated" at the end?
Don't think this makes a difference if consistency is kept but are pub keys in compressed form or uncompressed?
For example with 2 keys is it calculated like this (so hash of a 99 byte long array: 3*(1+32compressed))?:
a1=Hash(pub1 || pub2 || pub1)
a2=Hash(pub1 || pub2 || pub2)


Similarly for calculation of 'c' is it again concatenation of bytes, also are the points (X~ and R) in their compressed form or uncompressed (again I don't think it makes a difference but want to make sure)?
c = Hsig(X~ ,R,m)

Also I am assuming Hsig, Hagg,.. are all the same hash function like SHA256.


And finally in verification step shouldn't it be R + X~ in the following equation since they are both points, multiplication doesn't make any sense?
 

Diego

Member
And finally in verification step shouldn't it be R + X~ in the following equation since they are both points, multiplication doesn't make any sense?
i think yes. when i was creating a schnorr implementation using wikipidia as a reference i was confused by this as well. but the "RX" notation actually means R + X not R*X. but it was about two months ago now so cant really remember that well.
 

Cole

Member
Group computation can be written either in multiplicative or exponential notation, it's the same thing, just a different convention--

If you take the group operation (combination of two points) to be addition, then you write it as P+Q and something like key generation as xG. If you take the group operation to be multiplication then you write it as PQ and key generation becomes Gx. I personally prefer additive notation, but the multiplicative style is more common in the literature presumably owing to the fact that finite field operations in the ring of integers mod P literally uses integer multiplication.

[Aside, don't just credit me on that work, the other authors there are far more significant than I am...
Smiley
My main contribution was probably just finding an actual attack on an earlier construction that Pieter had, which we already suspected might be weak...
Smiley
]

Indeed, it doesn't really make a difference to use compressed vs uncompressed, but compressed can sometimes be somewhat less computationally expensive to use (less data to hash, potentially less effort needed to compute the Y value completely), so it's usually preferred
 

Ivan

Member
BUMP!
I still need help figuring out why I am getting false when trying to verify the signature.
https://gist.github.com/Coding-Enthusiast/6596a29fe361695a169f40ffd7d1e1f7
Hi,

I don't know the signature nor the verification algorithm but I thought I would checkout some code (other implems) to help you. It indeed seems that you don't hash the same thing at the verification step :
https://gist.github.com/Coding-Enthusiast/6596a29fe361695a169f40ffd7d1e1f7#file-schnorr-cs-L64 vs https://github.com/spff/schnorr-sig...3c67b730a45304b6f042fbb81441/schnorr.cpp#L311, but that's where my knowledge stops ^^"

Edit : In this implem too https://github.com/AlexConnat/Schno...859aa80fbed872100ee012e77ac29/schnorr.go#L115 the guy hashes (msg + R) instead of (X0 + R + msg) as I think you do
 

Kingston

Member
I believe that it does not matter what you hash as long as you use the same algorithm for verification too. Meaning during verification if you calculated c by hashing (msg + R) you do the same thing again which I do since I use the same value for c that was already calculated! By the way the Musig paper is saying you should hash (Xagg + R + msg).
I actually checked a couple of libraries last night and it seems like everyone is doing a different thing when it comes to MuSig!
 
Top