path: root/4c/bdd4bfd38154878f406ba2ae917ff4e3cd34d5

Return-Path: <ZmnSCPxj@protonmail.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 21634C0878
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 25 Nov 2019 11:00:32 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by silver.osuosl.org (Postfix) with ESMTP id 08840204A2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 25 Nov 2019 11:00:32 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id WkTN7+0cgHnp
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 25 Nov 2019 11:00:28 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40135.protonmail.ch (mail-40135.protonmail.ch
 [185.70.40.135])
 by silver.osuosl.org (Postfix) with ESMTPS id 090D5203A6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 25 Nov 2019 11:00:27 +0000 (UTC)
Date: Mon, 25 Nov 2019 11:00:22 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=default; t=1574679624;
 bh=ccMw412i+0drsf1l3UUVy3+gXSrXmY8DfOSTsC5jwls=;
 h=Date:To:From:Reply-To:Subject:Feedback-ID:From;
 b=KTrfO83/uWMl//3mLVrDCWBLZah0hyTycyJkVYG5zD29pDXhz4oaNFqtqFB0pYO34
 VyZ8GpoT5INAAd+pn6z6n+58QhuBrw1XS9sjuoiQft6UTmWnbxu3SIK6BQFWY4PdUd
 0h0E+3wfKSRpYHPEZSw3V1ERQJsswbZBk9oa5F+c=
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <u1IeyK5A7zyklXzl26UpCliJrFEsDp5SXUGbtXGBCrEWw6Wi7vNcoy4HNv2WXUTG_SBuMURDLhvh3YCwL2r53rL0Yj19TZpumYFD5WqmYL8=@protonmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: [bitcoin-dev] Composable MuSig
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 25 Nov 2019 11:00:32 -0000

So I heard you like MuSig.


Introduction
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Previously on lightning-dev, I propose Lightning Nodelets, wherein one sign=
atory of a channel is in fact not a single entity, but instead an aggregate=
: https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-October/00=
2236.html

Generalizing:

* There exists some protocol that requires multiple participants agreeing.
  * This can be implemented by use of MuSig on the public keys of the parti=
cipants.
* One or more of the participants in the above protocol is in fact an aggre=
gate, not a single participant.
  * Ideally, no protocol modification should be needed to support such aggr=
egates, "only" software development without modifying the protocol layer.
  * Obviously, any participant of such a protocol, whether a direct partici=
pant, or a member of an aggregated participant of that protocol, would want=
 to retain control of its own money in that protocol, without having to det=
ermine if it is being Sybilled (and all other participants are in fact just=
 one participant).
  * Motivating example: a Lightning Network channel is the aggregate of two=
 participants, the nodes creating that channel.
    However, with nodelets as proposed above, one of the participants is ac=
tually itself an aggregate of multiple nodelets.
    * This requires that a Lightning Network channel with a MuSig address, =
to have one or both participants, be potentially an aggregate of two or mor=
e nodelet participants, e.g. `MuSig(MuSig(A, B), C)`

This is the "MuSig composition" problem.
That is, given `MuSig(MuSig(A, B), C)`, and the *possibility* that in fact =
`B =3D=3D C`, what protocol can A use to ensure that it uses the three-phas=
e MuSig protocol (which has a proof of soundness) and not inadvertently use=
 a two-phase MuSig protocol?

Schnorr Signatures
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

The scheme is as follows.

Suppose an entity A needs to show a signature.
At setup:

* It generates a random scalar `a`.
* It computes `A` as `A =3D a * G`, where `G` is the standard generator poi=
nt.
* It publishes `A`.

At signing a message `m`:

* It generates a random scalar `r`.
* It computes `R` as `R =3D r * G`.
* It computes `e` as `h(R | m)`, where `h()` is a standard hash function an=
d `x | y` denotes the serialization of `x` concatenated by the serializatio=
n of `y`.
* It computes `s` as `s =3D r + e * a`.
* It publishes as signature the tuple of `(R, s)`.

An independent validator can then get `A`, `m`, and the signature `(R, s)`.
At validation:

* It recovers `e[validator]` as so: `e[validator] =3D h(R | m)`
* It computes `S[validator]` as so: `S[validator] =3D R + e[validator] * A`=
.
* It checks if `s * G =3D=3D S[validator]`.
  * If `R` and `s` were indeed generated as per signing algorithm above, th=
en:
    * `S[validator] =3D R + e[validator] * A`
    * `=3D=3D r * G + e[validator] * A`; subbstitution of `R`
    * `=3D=3D r * G + h(R | m) * A`; substitution of `e[validator]`
    * `=3D=3D r * G + h(R | m) * a * G`; substitution of `A`.
    * `=3D=3D (r + h(R | m) * a) * G`; factor out `G`
    * `=3D=3D (r + e * a) * G`; substitution of `h(R | m)` with `e`
    * `=3D=3D s * G`; substitution of `r + e * a`.

MuSig
=3D=3D=3D=3D=3D

Under MuSig, validation must remain the same, and multiple participants mus=
t provide a single aggregate key and signature.

Suppose there exist two participants A and B.
At setup:

* A generates a random scalar `a` and B generates a random scalar `b`.
* A computes `A` as `A =3D a * G` and B computes `B` as `B =3D b * G`.
* A and B exchange `A` and `B`.
* They generate the list `L`, by sorting their public keys and concatenatin=
g their representations.
* They compute their aggregate public key `P` as `P =3D h(L) * A + h(L) * B=
`.
* They publish the aggregate public key `P`.

Signing takes three phases.

1.  `R` commitment exchange.
  * A generates a random scalar `r[a]` and B generates a random scalar `r[b=
]`.
  * A computes `R[a]` as `R[a] =3D r[a] * G` and B computes `R[b]` as `R[b]=
 =3D r[b] * G`.
  * A computes `h(R[a])` and B computes `h(R[b])`.
  * A and B exchange `h(R[a])` and `h(R[b])`.
2.  `R` exchange.
  * A and B exchange `R[a]` and `R[b]`.
  * They validate that the previous given `h(R[a])` and `h(R[b])` matches.
3.  `s` exchange.
  * They compute `R` as `R =3D R[a] + R[b]`.
  * They compute `e` as `h(R | m)`.
  * A computes `s[a]` as `s[a] =3D r[a] + e * h(L) * a` and B computes `s[b=
]` as `s[b] =3D r[b] + e * h(L) * b`.
  * They exchange `s[a]` and `s[b]`.
  * They compute `s` as `s =3D s[a] + s[b]`.
  * They publish the signature as the tuple `(e, s)`.

At validation, the validator knows `P`, `m`, and the signature `(R, s)`.

* It recovers `e[validator]` as so: `e[validator] =3D h(R | m)`
* It computes `S[validator]` as so: `S[validator] =3D R + e[validator] * P`=
.
* It checks if `s * G =3D=3D S[validator]`.
  * `S[validator] =3D R + e[validator] * P`
  * `=3D=3D R[a] + R[b] + e[validator] * P`; substitution of `R`
  * `=3D=3D r[a] * G + r[b] * G + e[validator] * P`; substitution of `R[a]`=
 and `R[b]`
  * `=3D=3D r[a] * G + r[b] * G + e * P`; substitution of `e[validator]` wi=
th `e`
  * `=3D=3D r[a] * G + r[b] * G + e * (h(L) * A + h(L) * B)`; substitution =
of `P`
  * `=3D=3D r[a] * G + r[b] * G + e * h(L) * A + e * h(L) * B`; distributio=
n of `e` inside parentheses.
  * `=3D=3D r[a] * G + r[b] * G + e * h(L) * a * G + e * h(L) * b * G`; sub=
stitution of `A` and `B`.
  * `=3D=3D (r[a] + r[b] + e * h(L) * a + e * h(L) * b) * G`; factoring out=
 of `G`
  * `=3D=3D (r[a] + e * h(L) * a + r[b] + e * h(L) * b) * G`; rearrangement=
 of terms
  * `=3D=3D (s[a] + s[b]) * G`; substitution of `r[a] + e * h(L) * a` and `=
r[b] + e * h(L) * b`
  * `=3D=3D s * G`;  substitution of `s[a] + s[b]`


Two-Phase MuSig Unsafe
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Original proposal of MuSig only had two phases, `R` exchange and `s` exchan=
ge.
However, there was a flaw found in the security proof in this two-phase MuS=
ig.
In response, an earlier phase of exchanging commitments to `R` was added.

Thus, two-phase MuSig is potentially unsafe.

https://eprint.iacr.org/2018/417.pdf describes the argument.
Briefly, with two-phase MuSig, one of the participants can deliberately del=
ay its side of a `R` exchange and control the resulting sum `R` by cancelli=
ng the `R` of the other participant.
Executed over many (aborted) signing sessions, one participant can induce t=
he other to create a signature for a message it might not agree to, by usin=
g the Wagner Generalized Birthday Paradox attack.

Briefly, a two-phase MuSig signing would go this way:

1.  `R` exchange.
  * A generates random scalar `r[a]` and B generates random scalar `r[b]`.
  * A computes `R[a]` as `r[a] * G` and B computes `R[b]` as `r[b] * G`.
  * They exchange `R[a]` and `R[b]`.
2.  `s` exchange.
  * They compute `R` as `R =3D R[a] + R[b]`.
  * They compute `e` as `h(R | m)`.
  * A computes `s[a]` as `s[a] =3D r[a] + e * h(L) * a` and B computes `s[b=
]` as `s[b] =3D r[b] + e * h(L) * b`.
  * They exchange `s[a]` and `s[b]`.
  * They compute `s` as `s =3D s[a] + s[b]`.
  * They publish the signature as the tuple `(R, s)`.

The sticking point is "exchange" here.
Given that we live in a relativistic universe where there is no such thing =
as simultaneity-in-time-without-simultaneity-in-space, it is impossible to =
ensure that both A and B send their data "at the same time" in such a way t=
hat it is impossible for, for example, the send of B to be outside the futu=
re light cone of the send of A.
Or in human-level terms, it is not possible to ensure over the network that=
 B will not send `R[b]` *after* it receives `R[a]`.

Suppose that instead of B generating a random `r[b]` and *then* computing `=
R[b] =3D r[b] * G`, it instead selects an arbitrary `R[selected]` it wants =
to target, then compute `R[b]` as `R[selected] - R[a]`.
Then at `s` exchange:

* They compute `R` as `R[a] + R[b]`, which is in fact `R[a] + R[selected] -=
 R[a]`, or `R[selected]`, i.e. `R =3D=3D R[selected]`.
* They compute `e` as `h(R[selected] | m)`.
* A computes `s[a]` as `s[a] =3D r[a] + e * h(L) * a`.
* B is unable to compute `s[b]` as it has no `r[b]` it can use in the compu=
tation, and aborts the signing.

The attack involved is that multiple such signing sessions, for the same me=
ssage or for separate distinct messages, might be done in parallel.
Suppose that there are `n` such sessions, such that A provides `n` differen=
t `R[a][i]`, e.g. `R[a][1]`, `R[a][2]`, `R[a][3]` up to `R[a][n]`.
Then:

* B delays each session, pretending to have Internet connectivity problems.
* B selects a message `m[target]` that it knows A will never sign (e.g. "I,=
 A, give all my money to B").
* B computes `R[target]` as `sum where i =3D 1 to n of R[a][i]`.
* B uses the Wagner Generalized Birthday Paradox technique to find `R[selec=
ted][i]` with the following constraint:
  * `h(R[target] | m[target]) =3D=3D sum where i =3D 1 to n of h(R[selected=
][i] | m[i])`.
  * Given a large enough number of parallel sessions `n`, this can greatly =
reduce the effort from 2^128 to find a match to within the realm of a large=
 computer to compute within a few seconds.
* B computes `R[b][i]` as `R[selected][i] - R[a][i]`, for each `i` from 1 t=
o `n`.
* B provides `R[b][i]` for each session.
* A computes `R[i]` as `R[a][i] + R[b][i]` for each session.
  * However we know that `R[b][i] =3D=3D R[selected][i] - R[a][i]` for each=
 session, cancelling out `R[a][i]` and leaving `R[i] =3D=3D R[selected][i]`
* A computes `s[a][i]` as `r[a][i] + h(R[selected][i] | m[i]) * h(L) * a` f=
or each session.
* A gives `s[a][i]` for each session.
* B aborts each session.
* B sums up all the `s[a][i]`:
  * `(sum where i =3D 1 to n of r[a][i]) + (sum where i =3D 1 to n of h(R[s=
elected][i] | m[i]) * h(L) * a)`.
  * Remember, B has specifically selected `R[selected][i]` such that `h(R[t=
arget] | m[target])` is equal to the sum of `h(R[selected][i] | m[i])`.
  * `=3D=3D (sum where i =3D 1 to n of r[a][i]) + h(R[target] | m[target]) =
* h(L) * a)`.
* B adds `h(R[target] | m[target]) * h(L) * b` to the above sum.
  * This results in a signature for MuSig(A, B) to the message `m[target]`,=
 even though A would never have agreed to this message.

Thus, 2-phase MuSig enables a Wagner attack on the participant, thus it is =
unsafe.

Now, any method of ensuring a "simultaneous" exchange of `R` points is larg=
ely the same as adding a "commit to `R`" phase, i.e. the fix for this is si=
mply to add the "`R` commitment exchange" phase.

References: https://eprint.iacr.org/2018/417.pdf

MuSig Composition
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Let us suppose that we have some protocol that requires a MuSig signing ses=
sion between signers with public keys `P` and `C`.
Let us further suppose that in fact, `P =3D MuSig(A, B)`, i.e. one of the p=
ublic keys in this protocol is, in reality, itself a MuSig of two participa=
nts.

At the point of view of signer C, P is a single participant and it acts as =
such.
However, in reality, P is an aggregate.

We want to have the following properties:

* C should never need to know that P is in fact an aggregate.
* Even if B is secretly the same as C, the entire protocol as a whole (incl=
uding the aggregate signing of `MuSig(A, B)`) should remain three-phase MuS=
ig.

Now, from the point of view of C, what it sees are:

At setup:

* It generates a random scalar `c` and the public key `C` as `C =3D c * G`.
* It exchanges keys with P and gets the public key `P`.
* It computes `L` by sorting `C` and `P` and concatenating them.
* It determines their aggregate key as `h(L) * C + h(L) * P`.

At signing:

1.  `R` commitment exchange.
  * It generates a random scalar `r[c]` and computes `R[c]` as `R[c] =3D r[=
c] * G`.
  * It computes `h(R[c])`.
  * It exchanges the hash `h(R[c])` with P and gets `h(R[p])`.
2.  `R` exchange.
  * It exchanges `R[c]` with P and gets `R[p]`.
  * It validates that the hash `h(R[p])` matches the previously-committed h=
ash.
3.  `s` exchange.
  * It computes `R` as `R =3D R[c] + R[p]`.
  * It computes `e` as `e =3D h(R | m)`.
  * It computes `s[c]` as `s[c] =3D r[c] + e * c`.
  * It exchanges `s[c]` with P and gets `s[p]`.
  * It computes `s` as `s =3D s[c] + s[p]`.

However, from point of view of A and B, what actually happens is this:

At setup:

* A generates a random scalar `a` and computes `A =3D a * G`, B generates a=
 random scalar `b` and computes `B =3D b * G`.
* They exchange `A` and `B`.
* They generate their own `L[ab]`, by sorting `A` and `B` and concatenating=
 their representations.
* They compute the inner MuSig pubkey `P` as `P =3D h(L[ab]) * A + h(L[ab])=
 * B`.
* They exchange `P` with C, and get `C`.
* They compute the outer MuSig pubkey as `h(L) * P + h(L) * C`.

At signing:

1.  `R` commitment exchange.
  * A generates a random scalar `r[a]` and computes `R[a] =3D r[a] * G`, B =
generates a random scalar `r[b]` and computes `R[b] =3D r[b] * G`.
  * A computes `h(R[a])`, B computes `h(R[b])`.
  * They exchange `h(R[a])` and `h(R[b])`.
  * They need to compute `h(R[p])` for the protocol with C.
    * However, even if we know `R[p] =3D=3D R[a] + R[b]`, we cannot generat=
e `h(R[p])`.
    * Thus, they have no choice but to exchange `R[a]` and `R[b]` at this p=
hase, even though this is supposed to be the `R` commitment exchange phase =
(and they should not share `R[a]` and `R[b]` yet)!

Unfortunately, this means that, between A and B, we are now reduced to a tw=
o-phase MuSig.
This is relevant if B and C happen to be the same entity or are cooperating=
.

Basically, before C has to provide its `h(R[c])`, B now knows the generated=
 `R[a]` and `R[b]`.
If B and C are really the same entity, then C can compute `R[c]` as `R[sele=
cted] - R[a] - R[b]` before providing `h(R[c])`.
Then this devolves to the same attack that brings down 2-phase MuSig.

Thus, composition with the current MuSig proposal is insecure.

Towards a Composable Multi-`R` MuSig
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

A key element is that the first phase simply requires that all participants=
 provide *commitments* to their individual `R`, and the second phase reveal=
s their `R`.

I propose here the modification below:

* In the first phase, any participant in the MuSig may submit one *or more*=
 `R` commitments.
* In the second phase, the participant in the MuSig submits each `R` that d=
ecommits each of the `R` commitments it sent.

I call this the Remote R Replacement Remanded: Redundant R Required Realist=
ically, or, in shorter terms, the Multi-`R` proposal.

This is a simple and direct extension of the MuSig protocol, and expected t=
o not have any effect on the security proof of MuSig.

In the case where all MuSig participants are singletons and each participan=
t just generates and sends a single `R` commitment, then this proposal redu=
ces to the original MuSig proposal.

However, in the case where one participant is in reality itself an aggregat=
e, then we shall describe it below.
The below example is `MuSig(MuSig(A, B), C)`.

1.  `R` commitment exchange.
  * A generates a random number `r[a]`, B generates a random number `r[b]`,=
 C generates a random number `r[c]`.
  * A computes `R[a]` as `r[a] * G`, B computes `R[b]` as `r[b] * G`, C com=
putes `R[c]` as `r[c] * G`.
  * A computes `h(R[a])`, B computes `h(R[b])`, C computes `h(R[c])`.
  * A and B exchange their hashes with each other.
  * A and B jointly exchange their `h(R[a])` and `h(R[b])` with the `h(R[c]=
)` from C.
2.  `R` exchange.
  * A and B reveal their `R[a]` and `R[b]` with each other.
  * A and B validate the given `R[a]` matches `h(R[a])` and the given `R[b]=
` matches `h(R[b])`.
  * A and B jointly exchange their `R[a]` and `R[b]` with the `R[c]` from C=
.
  * C validates `R[a]` and `R[b]`, A and B validate `R[c]`.
  * They compute `R` as the sum of all `R[a] + R[b] + R[c]`.
3.  `s` exchange.
  * They compute `e` as `h(R | m)`.
  * A computes `s[a]` as `r[a] + e * h(L[abc]) * h(L[ab]) * a`, B computes =
`s[b]` as `r[b] + e * h(L[abc]) * h(L[ab]) * b`.
  * C computes `s[c]` as `r[c] + e * h(L[abc]) * c`.
  * A and B exchange `s[a]` and `s[b]`.
  * A and B compute `s[ab]` as `s[a] + s[b]`.
  * A and B jointly exchange their `s[ab]` with `s[c]` from C.
  * They compute `s` as `s[ab] + s[c]`.
  * They publish the signature as the tuple `(R, s)`.

Of note, is that the number of `R` a participant provides is a strong hint =
as to whether it is actually an aggregate or not, and forms an upper bound =
as to the size of the aggregate (i.e. an aggregate of `n` members can prete=
nd to be an aggregate of `m` members where `n < m`, but cannot pretend with=
 `n > m`).
Thus, C here learns that its counterparty is actually itself an aggregate r=
ather than a singleton.
This may be acceptable as a weak reduction in privacy (in principle, C shou=
ld never learn that it is talking to an aggregate rather than a single part=
y).

Alternative Composable MuSig Schemes
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

The above proposal is not the only one.
Below are some additional proposals which have various flaws, ranging from =
outright insecurity to practical implementation complexity issues.

Pedersen Commitments in Phase 1
-------------------------------

My initial proposal was to use Pedersen commitments in phase 1.
At phase 1, each party would generate a `r[x]` and `q[x]`, and exchange the=
 Pedersen commitments `r[x] * G + q[x] * H`, where `H` is a NUMS point used=
 as a second standard generator.
Then at phase 2, each party reveals its `q[x]`.
All the Pedersen commitments are summed, then all `q[x]` are summed, multip=
lied by `H`, then subtracted from the sum of Pedersen commitments.

Unfortunately, this leads to a Wagner attack.

Suppose A and B have an aggregate MuSig(A, B).

* B initiates multiple parallel signing sessions with A.
* B selects a message `m[target]` that it knows A will never sign (e.g. "I,=
 A, give all my money to B").
* In the first phase, B selects random points `R[b][i]` for each session `i=
` and provides that as its Pedersen commitment, receiving `R[a][i] + q[a][i=
] * H` in exchange.
* In the second phase, B delays each session, pretending to have Internet c=
onnectivity problems.
* A sends B the `q[a][i]` for all `i`.
* B computes `R[a][i]` for all `i` by subtracting `q[a][i] * H` from the Pe=
dersen commitments given by A.
* B computes `R[target]` as `sum where i =3D 1 to n of R[a][i]`.
* B uses the Wagner Generalized Birthday Paradox technique to find `q[b][i]=
` with the following constraint:
  * First compute `R[selected][i]` as `R[a][i] +  R[b][i] - q[b][i] * H` fo=
r all `i`.
  * Then ensure this constraint: `h(R[target] | m[target]) =3D=3D sum where=
 i =3D 1 to n of h(R[selected][i] | m[i])`.
* B sends the `q[b][i]` found above.
* A computes `R[i]` as `R[a][i] + q[a][i] * H + R[b][i] - q[a][i] * H - q[b=
][i] * H` for all `i`.
  * This resolves down to `R[a][i] + R[b][i] - q[b][i] * H`, or `R[selected=
][i]`.
* A computes `s[a][i]` as `r[a][i] + h(R[selected][i] | m[i]) * a` for all =
`i`.
* B sums all `s[a][i]` for all `i` together, forming `(sum where i =3D 1 to=
 n of r[a][i]) + (sum where i =3D 1 to n of h(R[selected][i] | m[i])) * a`.
  * This is also a valid signature on `m[target]`, since `sum where i =3D 1=
 to n of h(R[selected][i] | m[i])` equals `h(R[target] | m[target])`.

Thus, Pedersen commitments for phase 1 are insecure, as it allows counterpa=
rties to control `R`.

ElGamal Commitments in Phase 1
------------------------------

ElGamal commitments prevent B from just giving random `q[b][i]`, thus preve=
nting the above Wagner attack.
However, it is still possible for B to control the resulting `R`, but in do=
ing so this prevents the protocol from completing (thus, even with full con=
trol of `R`, B is still unable to promote this to an `R`-reuse attack or th=
e above Wagner attack schema).
This is not quite as bad as the above case, but having just one participant=
 control the nonce `R` should make us worry that other attacks may now beco=
me possible (unless we acquire some proof that this will be equivalent in s=
ecurity to the hash-using MuSig).

Briefly, with ElGamal commitments in Phase 1:

1. `R` commitment exchange.
  * A generates random numbers `r[a]` and `q[a]`, B generates random number=
s `r[b]` and `q[b]`.
  * A computes its commitment as two points, `q[a] * G` and `r[a] * G + q[a=
] * H`, B computes its commitment as two points, `q[b] * G` and `r[b] * G +=
 q[b] * H`.
    * `H` is a NUMS point used as a second standard generator.
    * Note that one point uses `q[] * G` while the other adds `q[] * H` to =
`r[] * G`.
  * They exchange their pairs of points.
2. `R` exchange.
  * They exchange `q[a]` and `q[b]`, and the points `r[a] * G` (=3D=3D `R[a=
]`) and `r[b] * G` (=3D=3D `R[b]`).
  * They validate the exchanged data from the previous `R` commitments.
  * They compute `R` as `R[a]` + `R[b]`.
3. `s` exchange.
  * Same as before.

B can attack this by delaying its phases as below:

1. `R` commitment exchange.
  * B generates random `q[selected]`.
  * B selects target `R[selected]`.
  * After receiving `q[a] * G` and `r[a] * G + q[a] * H`, B computes `q[sel=
ected] * G - q[a] * G` and `R[selected] + q[selected] * H - r[a] * G - q[a]=
 * H` and sends those points as its own commitment.
2. `R` exchange.
  * After receiving `q[a]` and `R[a]`, B computes `q[b]` as `q[selected] - =
q[a]` and computes `R[b]` as `R[selected] - R[a]` and sends both as its dec=
ommitment.
  * The resulting `R` will now be `R[selected]` chosen by B.

`s` exchange cannot complete, as that would require that B know `r[selected=
] - r[a]` where `R[selected] =3D r[selected] * G`.
Even if B generates `R[selected]` from `r[selected]`, it does not know `r[a=
]`.
A would provide `r[a] + h(R[selected] | m) * h(L[ab]) * a`, but B would be =
unable to complete this signature.

The difference here is that B has to select `R[selected]` before it learns =
`R[a]`, and thus is unable to mount the above Wagner attack schema.
In particular, B first has to compute an `R[target]` equal to `sum where i =
=3D 1 to n of R[a][i]` across `n` sessions numbered `i`, in addition to sel=
ecting a message `m[i]`.
Then B has to perform a Wagner attack with the constraint `h(R[target] | m[=
target]) =3D=3D sum where i =3D 1 to n of h(R[selected][i] | m[i])`
Fortunately for this scheme, B cannot determine such an `R[target]` before =
it has to select `R[selected]`, thus preventing this attack.

It may be possible that this scheme is safe, however I am not capable of pr=
oving it safe.

Acknowledgments
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

I contacted Yannick Seurin, Andrew Poelstra, Pieter Wuille, and Greg Maxwel=
l, the authors of MuSig, regarding this issue, and proposing to use Pederse=
n commitments for the first phase.
They informed me that Tim Ruffing had actually been thinking of similar iss=
ue before I did, and also pointed out that Pedersen commitments do not comm=
it to `r * G`, only to `r` (i.e. would have to reveal `r` to serve as a ver=
ifiable commitment).
It seemed to me that the general agreement was that ElGamal commitments sho=
uld work for committing to `r * G`.
However as I show above, this still allows a delaying participant to cancel=
 the `R` contributions of the other parties, allowing it to control the agg=
regate `R` (though not quite to launch a Wagner attack).

`nickler` and `waxwing` on IRC confirmed my understanding of the attack on =
2-phase MuSig.
`waxwing` also mentioned that the paper attacking 2-phase MuSig really atta=
cks CoSi, and that the paper itself admits that given a knowledge-of-secret=
-keys, CoSi (and presumably 2-phase MuSig) would be safe.