Bitcoin Forum
February 24, 2019, 12:32:16 AM
 News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: A couple of questions regarding Schnorr MuSig algorithm math notation  (Read 159 times)
Coding Enthusiast
Hero Member

Offline

Activity: 576
Merit: 704

Novice C♯ Coder

 January 18, 2019, 08:40:47 AMLast edit: January 19, 2019, 06:35:57 PM by Coding EnthusiastMerited by dbshck (4), Welsh (4), ETFbitcoin (3), bones261 (2)

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?

 Projects List+Suggestion boxDonation link using BIP21Bech32 Donation link! BitcoinTransactionTool (0.9.2):  Ann - Source CodeWatch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source CodeSharpPusher (broadcast transactions) (0.10.0): Ann - Source Code
1550968336
Hero Member

Offline

Posts: 1550968336

Ignore
 1550968336

1550968336
 Report to moderator
1550968336
Hero Member

Offline

Posts: 1550968336

Ignore
 1550968336

1550968336
 Report to moderator
1550968336
Hero Member

Offline

Posts: 1550968336

Ignore
 1550968336

1550968336
 Report to moderator
The Ultimate Bitcoin mixer
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Anonymous Kid
Member

Offline

Activity: 184
Merit: 22

 January 19, 2019, 01:30:03 AM

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.

gmaxwell
Moderator
Legendary

Offline

Activity: 2660
Merit: 1995

 January 19, 2019, 05:10:02 PMMerited by dbshck (5), suchmoon (4), ETFbitcoin (3)

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...   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.
Coding Enthusiast
Hero Member

Offline

Activity: 576
Merit: 704

Novice C♯ Coder

 January 19, 2019, 07:15:46 PM

don't just credit me on that work
Sorry for my laziness, copying from PDF is hard

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?

 Projects List+Suggestion boxDonation link using BIP21Bech32 Donation link! BitcoinTransactionTool (0.9.2):  Ann - Source CodeWatch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source CodeSharpPusher (broadcast transactions) (0.10.0): Ann - Source Code
Coding Enthusiast
Hero Member

Offline

Activity: 576
Merit: 704

Novice C♯ Coder

 February 21, 2019, 07:33:51 AM

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

 Projects List+Suggestion boxDonation link using BIP21Bech32 Donation link! BitcoinTransactionTool (0.9.2):  Ann - Source CodeWatch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source CodeSharpPusher (broadcast transactions) (0.10.0): Ann - Source Code
darosior
Member

Offline

Activity: 112
Merit: 121

 February 21, 2019, 11:29:02 AMMerited by Coding Enthusiast (1)

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.

Coding Enthusiast
Hero Member

Offline

Activity: 576
Merit: 704

Novice C♯ Coder

 February 21, 2019, 01:02:48 PM

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

 Projects List+Suggestion boxDonation link using BIP21Bech32 Donation link! BitcoinTransactionTool (0.9.2):  Ann - Source CodeWatch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source CodeSharpPusher (broadcast transactions) (0.10.0): Ann - Source Code
 Pages: [1]