In MuSig2 how is multiplication of coordinates defined?

Question

In the MuSig2 paper each signer multiplies all the nonces together (in the naive version):

R_1 * R_2 * R_3 * .... R_n

where R_i = r_i * G. r_i is a scalar and G is the generator point (coordinate) hence R_i is a coordinate.

And all the public keys (coordinates) are multiplied together:

X_1 * X_2 * X_3 * .... X_n

Is the multiplication (over the cyclic group) defined here by multiplying the x cooordinates together and multiplying the y coordinates together?

e.g. (x_1, y_1) * (x_2, y_2) = (x_1 * x_2, y_1 * y_2)

It is not like the bytes() function in BIP340 is used where a coordinate is turned into a scalar by taking the x coordinate, the x coordinates are multiplied together and the y coordinates are dropped (the final y coordinate could be calculated later I guess from the final x coordinate)?

edit: I looked up the KeyAgg function in the MuSig2 (secure version) draft BIP and that states the aggregated key isn't calculated by multiplying the public keys, instead they are added with unique coefficients. I'm confused. Have we moved from a product (naive version) to a sum with unique coefficients (secure version)?

Q = a1⋅P1 + a2⋅P2 + ... + au⋅Pu

Answer 1

TL;DR: the multiplication operation you're asking about is actually what you're used to seeing referred to as point adition (when talking about elliptic curves).

The MuSig2 paper does not assume you're using an elliptic curve group, or even assume the objects operated on have a notion of "coordinates". The scheme is generic, and works for any cyclic group in which the discrete logarithm is assumed to be hard. That can be instantiated with an elliptic curve group like secp256k1, but it also works with very different groups.

Specifically, that means:

• We need a finite set of elements, containing at least a "neutral element" o and a "generator" g.
• There must be a function defined for all elements that takes two arguments; because its name and notation doesn't matter, we'll call it "blah(x,y)".
• For any x,y in the set, blah(x,y) is also in the set.
• For any x,y in the set, blah(x,y) and blah(y,x) are the same.
• For any x,y,z in the set, blah(blah(x,y),z) = blah(x,blah(y,z)).
• For any x,y in the set, there exists an element a in the set such that blah(x,a) = y.
• For any x in the set, blah(x,o) = blah(o,x) = x.
• Every element in the set can be written as blah(blah(blah(o,...),g),g), for some finite number of calls to blah, but given a random element x in the set, it must be hard to find how many g's need to be blah'ed together to obtain x.

This is all. If we use secp256k1 (or any other elliptic curve group) then we use the points on the curve as the set, the point at infinity as o, the secp256k1 generator as g, and the elliptic curve point addition formula as blah(). Repeated blah'ing in this case is denoted as a multiplication between the number of blah's and the point being blah'ed.

But the whole scheme can also be instantiated for other groups in which these properties hold, with different bandwidth/computation/security tradeoffs. For example, it's possible to use multiplication modulo a very large prime p. In that case o is the number 1, g is for example the number 2, blah is multiplying two numbers together modulo p, and repeated blahing is raising a number to a power modulo p.

And thus, the MuSig2 scheme, when described sufficiently abstractly, works on any such group. The same is true for Schnorr for example: BIP340 is an instantiation of the Schnorr signature scheme over the secp256k1 group, but Schnorr himself originally described it to operate on just integers modulo a prime.

This leads to a practical problem: if the scheme is generic, and works over any group with certain properties, how do you write it down? People working on elliptic curves are used to writing the group operation blah() as "+", and people working on integers are used to writing this operation as "*".

So what happens is that some authors choose one, and others use the other, depending on their background. Among Twitter cryptographers there are often heated (but usually friendly) arguments about which is better. And in the end, it doesn't matter - it's just notation. Both "+" and "*" work fine, as we just need a single operation, and both are much more readable than "blah()".

BIP340, BIP32, and many other BIPs and descriptions of the cryptography in Bitcoin, use "+", or additive notation, for the group operation, and "*" for repeated use of it.

MuSig2, as well as many other cryptography papers (but not all) use "*", or multiplicative notation for the group operation, and "^" for use of it. This is where the name "discrete logarithm problem" comes from. In additive notation, for consistency, we ought to be talking about the "discrete division problem".

To see the correspondence, BIP340 (in additive notation) uses equation sG = R + H(R || P || m)P for valid signatures. Using multiplicative notation it would instead be G^s = P^{H(R || P || m)}R, but this is just a notation choice - both describe exactly the same thing.

So in short: the multiplication operation you're asking about in the MuSig2 paper is just what would more commonly be referred to as elliptic curve point addition in Bitcoin-specific context. Multiplying the individual coordinates together is not a valid operation; this will generally not yield a point on the curve again.