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

Activity: 576
Merit: 704


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

1550968336
Hero Member
*
Offline Offline

Posts: 1550968336

View Profile Personal Message (Offline)

Ignore
1550968336
Reply with quote  #2

1550968336
Report to moderator
1550968336
Hero Member
*
Offline Offline

Posts: 1550968336

View Profile Personal Message (Offline)

Ignore
1550968336
Reply with quote  #2

1550968336
Report to moderator
1550968336
Hero Member
*
Offline Offline

Posts: 1550968336

View Profile Personal Message (Offline)

Ignore
1550968336
Reply with quote  #2

1550968336
Report to moderator
Your Bitcoin transactions
The Ultimate Bitcoin mixer
made truly anonymous.
with an advanced technology.
Mix coins
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 Offline

Activity: 184
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: 1995



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: 576
Merit: 704


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

Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 576
Merit: 704


Novice C♯ Coder


View Profile WWW
February 21, 2019, 07:33:51 AM
 #5

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

darosior
Member
**
Offline Offline

Activity: 112
Merit: 121


View Profile WWW
February 21, 2019, 11:29:02 AM
Merited by Coding Enthusiast (1)
 #6

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 Offline

Activity: 576
Merit: 704


Novice C♯ Coder


View Profile WWW
February 21, 2019, 01:02:48 PM
 #7

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