Bitcoin Forum

Reading the "Simple Schnorr Multi-Signatures with Applications to Bitcoin" by Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille .pdf link (https://eprint.iacr.org/2018/068.pdf). 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 a_i = H_agg(L,X_i) 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+32_compressed))?:
a₁=Hash(pub1 || pub2 || pub1)
a₂=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 = H_sig(X^~ ,R,m)

Also I am assuming H_sig, H_agg,.. 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?

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.

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 G^x.  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... :)  My main contribution was probably just finding an actual attack on an earlier construction that Pieter had, which we already suspected might be weak... :)]

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.

Sorry for my laziness, copying from PDF is hard :P

---

I must still be missing something here (possibly in Hash steps) because I get a false in my verification step whereas I can do it fine with alternate version for collective signature creation.

Here is the (stripped off) code: https://gist.github.com/Coding-Enthusiast/6596a29fe361695a169f40ffd7d1e1f7
Maybe someone can see where I am messing things up?

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-signature/blob/78e6883a6e953c67b730a45304b6f042fbb81441/schnorr.cpp#L311, but that's where my knowledge stops ^^"

Edit : In this implem too https://github.com/AlexConnat/Schnorr-Signature-Scheme/blob/2428cc3a04d859aa80fbed872100ee012e77ac29/schnorr.go#L115 the guy hashes (msg + R) instead of (X0 + R + msg) as I think you do.

@darosior
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!