Bitcoin Forum
February 17, 2019, 05:14:42 PM
 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 119 times)
Coding Enthusiast
Hero Member

Offline

Activity: 572
Merit: 701

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
1550423682
Hero Member

Offline

Posts: 1550423682

Ignore
 1550423682

1550423682
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1550423682
Hero Member

Offline

Posts: 1550423682

Ignore
 1550423682

1550423682
 Report to moderator
Anonymous Kid
Member

Offline

Activity: 185
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: 1973

 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: 572
Merit: 701

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
 Pages: [1]