From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 21634C0878 for ; 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 ; 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 ; 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 ; 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 From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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.