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]
  Print  
Author Topic: A couple of questions regarding Schnorr MuSig algorithm math notation  (Read 119 times)
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 572
Merit: 701


Novice C♯ Coder


View Profile WWW
January 18, 2019, 08:40:47 AM
Last edit: January 19, 2019, 06:35:57 PM by Coding Enthusiast
Merited by dbshck (4), Welsh (4), ETFbitcoin (3), bones261 (2)
 #1

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 box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

1550423682
Hero Member
*
Offline Offline

Posts: 1550423682

View Profile Personal Message (Offline)

Ignore
1550423682
Reply with quote  #2

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 Offline

Posts: 1550423682

View Profile Personal Message (Offline)

Ignore
1550423682
Reply with quote  #2

1550423682
Report to moderator
Anonymous Kid
Member
**
Offline Offline

Activity: 185
Merit: 22


View Profile
January 19, 2019, 01:30:03 AM
 #2



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
*
qt
Offline Offline

Activity: 2660
Merit: 1973



View Profile
January 19, 2019, 05:10:02 PM
Merited by dbshck (5), suchmoon (4), ETFbitcoin (3)
 #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... 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.
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 572
Merit: 701


Novice C♯ Coder


View Profile WWW
January 19, 2019, 07:15:46 PM
 #4

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


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 box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Pages: [1]
  Print  
 
Jump to:  

Bitcointalk.org is not available or authorized for sale. Do not believe any fake listings.
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!