MIME-Version: 1.0
References: <u1IeyK5A7zyklXzl26UpCliJrFEsDp5SXUGbtXGBCrEWw6Wi7vNcoy4HNv2WXUTG_SBuMURDLhvh3YCwL2r53rL0Yj19TZpumYFD5WqmYL8=@protonmail.com>
In-Reply-To: <u1IeyK5A7zyklXzl26UpCliJrFEsDp5SXUGbtXGBCrEWw6Wi7vNcoy4HNv2WXUTG_SBuMURDLhvh3YCwL2r53rL0Yj19TZpumYFD5WqmYL8=@protonmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Fri, 29 Nov 2019 16:50:33 +1100
Message-ID: <CAH5Bsr2rsiU9gV6VsGH3ZCWGRoTz=g5hXNq37P3P6HB+MmxUAA@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000007b9e81059875d021"
Subject: Re: [bitcoin-dev] Composable MuSig
Precedence: list

--0000000000007b9e81059875d021
Content-Type: text/plain; charset="UTF-8"

Hi ZmnSCPxj,

Very interesting problem.

Just a quick note: I think there is a way to commit to a point properly
with Pedersen commitments. Consider the following:
COM(X) = (y*G + z*H, y*G + X)  where y and z are random and the opening is
(y,z,X).  This seems to be a  unconditionally hiding and computationally
binding homomorphic commitment scheme to a point based on the DL problem
rather than DDH.

LL

On Mon, Nov 25, 2019 at 10:00 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> So I heard you like MuSig.
>
>
> Introduction
> ============
>
> Previously on lightning-dev, I propose Lightning Nodelets, wherein one
> signatory of a channel is in fact not a single entity, but instead an
> aggregate:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-October/002236.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
> participants.
> * One or more of the participants in the above protocol is in fact an
> aggregate, not a single participant.
>   * Ideally, no protocol modification should be needed to support such
> aggregates, "only" software development without modifying the protocol
> layer.
>   * Obviously, any participant of such a protocol, whether a direct
> participant, 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 determine 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
> actually 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
> more 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 == C`, what protocol can A use to ensure that it uses the three-phase
> MuSig protocol (which has a proof of soundness) and not inadvertently use a
> two-phase MuSig protocol?
>
> Schnorr Signatures
> ==================
>
> 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 = a * G`, where `G` is the standard generator
> point.
> * It publishes `A`.
>
> At signing a message `m`:
>
> * It generates a random scalar `r`.
> * It computes `R` as `R = r * G`.
> * It computes `e` as `h(R | m)`, where `h()` is a standard hash function
> and `x | y` denotes the serialization of `x` concatenated by the
> serialization of `y`.
> * It computes `s` as `s = 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] = h(R | m)`
> * It computes `S[validator]` as so: `S[validator] = R + e[validator] * A`.
> * It checks if `s * G == S[validator]`.
>   * If `R` and `s` were indeed generated as per signing algorithm above,
> then:
>     * `S[validator] = R + e[validator] * A`
>     * `== r * G + e[validator] * A`; subbstitution of `R`
>     * `== r * G + h(R | m) * A`; substitution of `e[validator]`
>     * `== r * G + h(R | m) * a * G`; substitution of `A`.
>     * `== (r + h(R | m) * a) * G`; factor out `G`
>     * `== (r + e * a) * G`; substitution of `h(R | m)` with `e`
>     * `== s * G`; substitution of `r + e * a`.
>
> MuSig
> =====
>
> Under MuSig, validation must remain the same, and multiple participants
> must 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 = a * G` and B computes `B` as `B = b * G`.
> * A and B exchange `A` and `B`.
> * They generate the list `L`, by sorting their public keys and
> concatenating their representations.
> * They compute their aggregate public key `P` as `P = 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] = r[a] * G` and B computes `R[b]` as `R[b]
> = 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 = R[a] + R[b]`.
>   * They compute `e` as `h(R | m)`.
>   * A computes `s[a]` as `s[a] = r[a] + e * h(L) * a` and B computes
> `s[b]` as `s[b] = r[b] + e * h(L) * b`.
>   * They exchange `s[a]` and `s[b]`.
>   * They compute `s` as `s = 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] = h(R | m)`
> * It computes `S[validator]` as so: `S[validator] = R + e[validator] * P`.
> * It checks if `s * G == S[validator]`.
>   * `S[validator] = R + e[validator] * P`
>   * `== R[a] + R[b] + e[validator] * P`; substitution of `R`
>   * `== r[a] * G + r[b] * G + e[validator] * P`; substitution of `R[a]`
> and `R[b]`
>   * `== r[a] * G + r[b] * G + e * P`; substitution of `e[validator]` with
> `e`
>   * `== r[a] * G + r[b] * G + e * (h(L) * A + h(L) * B)`; substitution of
> `P`
>   * `== r[a] * G + r[b] * G + e * h(L) * A + e * h(L) * B`; distribution
> of `e` inside parentheses.
>   * `== r[a] * G + r[b] * G + e * h(L) * a * G + e * h(L) * b * G`;
> substitution of `A` and `B`.
>   * `== (r[a] + r[b] + e * h(L) * a + e * h(L) * b) * G`; factoring out of
> `G`
>   * `== (r[a] + e * h(L) * a + r[b] + e * h(L) * b) * G`; rearrangement of
> terms
>   * `== (s[a] + s[b]) * G`; substitution of `r[a] + e * h(L) * a` and
> `r[b] + e * h(L) * b`
>   * `== s * G`;  substitution of `s[a] + s[b]`
>
>
> Two-Phase MuSig Unsafe
> ======================
>
> Original proposal of MuSig only had two phases, `R` exchange and `s`
> exchange.
> However, there was a flaw found in the security proof in this two-phase
> MuSig.
> 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
> delay its side of a `R` exchange and control the resulting sum `R` by
> cancelling the `R` of the other participant.
> Executed over many (aborted) signing sessions, one participant can induce
> the other to create a signature for a message it might not agree to, by
> using 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 = R[a] + R[b]`.
>   * They compute `e` as `h(R | m)`.
>   * A computes `s[a]` as `s[a] = r[a] + e * h(L) * a` and B computes
> `s[b]` as `s[b] = r[b] + e * h(L) * b`.
>   * They exchange `s[a]` and `s[b]`.
>   * They compute `s` as `s = 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
> that it is impossible for, for example, the send of B to be outside the
> future 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] = 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 == R[selected]`.
> * They compute `e` as `h(R[selected] | m)`.
> * A computes `s[a]` as `s[a] = r[a] + e * h(L) * a`.
> * B is unable to compute `s[b]` as it has no `r[b]` it can use in the
> computation, and aborts the signing.
>
> The attack involved is that multiple such signing sessions, for the same
> message or for separate distinct messages, might be done in parallel.
> Suppose that there are `n` such sessions, such that A provides `n`
> different `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 = 1 to n of R[a][i]`.
> * B uses the Wagner Generalized Birthday Paradox technique to find
> `R[selected][i]` with the following constraint:
>   * `h(R[target] | m[target]) == sum where i = 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
> to `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] == R[selected][i] - R[a][i]` for each
> session, cancelling out `R[a][i]` and leaving `R[i] == R[selected][i]`
> * A computes `s[a][i]` as `r[a][i] + h(R[selected][i] | m[i]) * h(L) * a`
> for 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 = 1 to n of r[a][i]) + (sum where i = 1 to n of
> h(R[selected][i] | m[i]) * h(L) * a)`.
>   * Remember, B has specifically selected `R[selected][i]` such that
> `h(R[target] | m[target])` is equal to the sum of `h(R[selected][i] |
> m[i])`.
>   * `== (sum where i = 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
> largely the same as adding a "commit to `R`" phase, i.e. the fix for this
> is simply to add the "`R` commitment exchange" phase.
>
> References: https://eprint.iacr.org/2018/417.pdf
>
> MuSig Composition
> =================
>
> Let us suppose that we have some protocol that requires a MuSig signing
> session between signers with public keys `P` and `C`.
> Let us further suppose that in fact, `P = MuSig(A, B)`, i.e. one of the
> public keys in this protocol is, in reality, itself a MuSig of two
> participants.
>
> 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
> (including the aggregate signing of `MuSig(A, B)`) should remain
> three-phase MuSig.
>
> 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 = 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] =
> 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
> hash.
> 3.  `s` exchange.
>   * It computes `R` as `R = R[c] + R[p]`.
>   * It computes `e` as `e = h(R | m)`.
>   * It computes `s[c]` as `s[c] = r[c] + e * c`.
>   * It exchanges `s[c]` with P and gets `s[p]`.
>   * It computes `s` as `s = 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 = a * G`, B generates a
> random scalar `b` and computes `B = 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 = 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] = r[a] * G`, B
> generates a random scalar `r[b]` and computes `R[b] = 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] == R[a] + R[b]`, we cannot generate
> `h(R[p])`.
>     * Thus, they have no choice but to exchange `R[a]` and `R[b]` at this
> phase, 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
> two-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[selected] - 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
> ====================================
>
> A key element is that the first phase simply requires that all
> participants provide *commitments* to their individual `R`, and the second
> phase reveals 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
> decommits each of the `R` commitments it sent.
>
> I call this the Remote R Replacement Remanded: Redundant R Required
> Realistically, or, in shorter terms, the Multi-`R` proposal.
>
> This is a simple and direct extension of the MuSig protocol, and expected
> to not have any effect on the security proof of MuSig.
>
> In the case where all MuSig participants are singletons and each
> participant just generates and sends a single `R` commitment, then this
> proposal reduces to the original MuSig proposal.
>
> However, in the case where one participant is in reality itself an
> aggregate, 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
> computes `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
> pretend 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
> rather than a singleton.
> This may be acceptable as a weak reduction in privacy (in principle, C
> should never learn that it is talking to an aggregate rather than a single
> party).
>
> Alternative Composable MuSig Schemes
> ====================================
>
> 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,
> multiplied 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
> connectivity 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
> Pedersen commitments given by A.
> * B computes `R[target]` as `sum where i = 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`
> for all `i`.
>   * Then ensure this constraint: `h(R[target] | m[target]) == sum where i
> = 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 = 1 to
> n of r[a][i]) + (sum where i = 1 to n of h(R[selected][i] | m[i])) * a`.
>   * This is also a valid signature on `m[target]`, since `sum where i = 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
> counterparties to control `R`.
>
> ElGamal Commitments in Phase 1
> ------------------------------
>
> ElGamal commitments prevent B from just giving random `q[b][i]`, thus
> preventing the above Wagner attack.
> However, it is still possible for B to control the resulting `R`, but in
> doing so this prevents the protocol from completing (thus, even with full
> control of `R`, B is still unable to promote this to an `R`-reuse attack or
> the 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 become possible (unless we acquire some proof that this will be
> equivalent in security 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
> numbers `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` (== `R[a]`)
> and `r[b] * G` (== `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[selected] * 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
> decommitment.
>   * 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] = 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
> = 1 to n of R[a][i]` across `n` sessions numbered `i`, in addition to
> selecting a message `m[i]`.
> Then B has to perform a Wagner attack with the constraint `h(R[target] |
> m[target]) == sum where i = 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
> proving it safe.
>
> Acknowledgments
> ===============
>
> I contacted Yannick Seurin, Andrew Poelstra, Pieter Wuille, and Greg
> Maxwell, the authors of MuSig, regarding this issue, and proposing to use
> Pedersen commitments for the first phase.
> They informed me that Tim Ruffing had actually been thinking of similar
> issue before I did, and also pointed out that Pedersen commitments do not
> commit to `r * G`, only to `r` (i.e. would have to reveal `r` to serve as a
> verifiable commitment).
> It seemed to me that the general agreement was that ElGamal commitments
> should 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 aggregate `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
> attacks CoSi, and that the paper itself admits that given a
> knowledge-of-secret-keys, CoSi (and presumably 2-phase MuSig) would be safe.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--0000000000007b9e81059875d021
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi ZmnSCPxj,<div><br></div><div>Very interesting problem.<=
/div><div><br></div><div>Just a quick note: I think there is a way to commi=
t to a point properly with Pedersen commitments. Consider the following:</d=
iv><div>COM(X) =3D (y*G + z*H, y*G=C2=A0+ X)=C2=A0 where y and z are random=
 and the opening is (y,z,X).=C2=A0 This seems to be a=C2=A0 unconditionally=
 hiding and computationally binding homomorphic commitment scheme to a poin=
t based on the DL problem rather than DDH.</div><div><br></div><div>LL</div=
><div></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"=
gmail_attr">On Mon, Nov 25, 2019 at 10:00 PM ZmnSCPxj via bitcoin-dev &lt;<=
a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.l=
inuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote=
" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);=
padding-left:1ex">So I heard you like MuSig.<br>
<br>
<br>
Introduction<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
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=
: <a href=3D"https://lists.linuxfoundation.org/pipermail/lightning-dev/2019=
-October/002236.html" rel=3D"noreferrer" target=3D"_blank">https://lists.li=
nuxfoundation.org/pipermail/lightning-dev/2019-October/002236.html</a><br>
<br>
Generalizing:<br>
<br>
* There exists some protocol that requires multiple participants agreeing.<=
br>
=C2=A0 * This can be implemented by use of MuSig on the public keys of the =
participants.<br>
* One or more of the participants in the above protocol is in fact an aggre=
gate, not a single participant.<br>
=C2=A0 * Ideally, no protocol modification should be needed to support such=
 aggregates, &quot;only&quot; software development without modifying the pr=
otocol layer.<br>
=C2=A0 * Obviously, any participant of such a protocol, whether a direct pa=
rticipant, or a member of an aggregated participant of that protocol, would=
 want to retain control of its own money in that protocol, without having t=
o determine if it is being Sybilled (and all other participants are in fact=
 just one participant).<br>
=C2=A0 * Motivating example: a Lightning Network channel is the aggregate o=
f two participants, the nodes creating that channel.<br>
=C2=A0 =C2=A0 However, with nodelets as proposed above, one of the particip=
ants is actually itself an aggregate of multiple nodelets.<br>
=C2=A0 =C2=A0 * This requires that a Lightning Network channel with a MuSig=
 address, to have one or both participants, be potentially an aggregate of =
two or more nodelet participants, e.g. `MuSig(MuSig(A, B), C)`<br>
<br>
This is the &quot;MuSig composition&quot; problem.<br>
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?<br>
<br>
Schnorr Signatures<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
The scheme is as follows.<br>
<br>
Suppose an entity A needs to show a signature.<br>
At setup:<br>
<br>
* It generates a random scalar `a`.<br>
* It computes `A` as `A =3D a * G`, where `G` is the standard generator poi=
nt.<br>
* It publishes `A`.<br>
<br>
At signing a message `m`:<br>
<br>
* It generates a random scalar `r`.<br>
* It computes `R` as `R =3D r * G`.<br>
* 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`.<br>
* It computes `s` as `s =3D r + e * a`.<br>
* It publishes as signature the tuple of `(R, s)`.<br>
<br>
An independent validator can then get `A`, `m`, and the signature `(R, s)`.=
<br>
At validation:<br>
<br>
* It recovers `e[validator]` as so: `e[validator] =3D h(R | m)`<br>
* It computes `S[validator]` as so: `S[validator] =3D R + e[validator] * A`=
.<br>
* It checks if `s * G =3D=3D S[validator]`.<br>
=C2=A0 * If `R` and `s` were indeed generated as per signing algorithm abov=
e, then:<br>
=C2=A0 =C2=A0 * `S[validator] =3D R + e[validator] * A`<br>
=C2=A0 =C2=A0 * `=3D=3D r * G + e[validator] * A`; subbstitution of `R`<br>
=C2=A0 =C2=A0 * `=3D=3D r * G + h(R | m) * A`; substitution of `e[validator=
]`<br>
=C2=A0 =C2=A0 * `=3D=3D r * G + h(R | m) * a * G`; substitution of `A`.<br>
=C2=A0 =C2=A0 * `=3D=3D (r + h(R | m) * a) * G`; factor out `G`<br>
=C2=A0 =C2=A0 * `=3D=3D (r + e * a) * G`; substitution of `h(R | m)` with `=
e`<br>
=C2=A0 =C2=A0 * `=3D=3D s * G`; substitution of `r + e * a`.<br>
<br>
MuSig<br>
=3D=3D=3D=3D=3D<br>
<br>
Under MuSig, validation must remain the same, and multiple participants mus=
t provide a single aggregate key and signature.<br>
<br>
Suppose there exist two participants A and B.<br>
At setup:<br>
<br>
* A generates a random scalar `a` and B generates a random scalar `b`.<br>
* A computes `A` as `A =3D a * G` and B computes `B` as `B =3D b * G`.<br>
* A and B exchange `A` and `B`.<br>
* They generate the list `L`, by sorting their public keys and concatenatin=
g their representations.<br>
* They compute their aggregate public key `P` as `P =3D h(L) * A + h(L) * B=
`.<br>
* They publish the aggregate public key `P`.<br>
<br>
Signing takes three phases.<br>
<br>
1.=C2=A0 `R` commitment exchange.<br>
=C2=A0 * A generates a random scalar `r[a]` and B generates a random scalar=
 `r[b]`.<br>
=C2=A0 * A computes `R[a]` as `R[a] =3D r[a] * G` and B computes `R[b]` as =
`R[b] =3D r[b] * G`.<br>
=C2=A0 * A computes `h(R[a])` and B computes `h(R[b])`.<br>
=C2=A0 * A and B exchange `h(R[a])` and `h(R[b])`.<br>
2.=C2=A0 `R` exchange.<br>
=C2=A0 * A and B exchange `R[a]` and `R[b]`.<br>
=C2=A0 * They validate that the previous given `h(R[a])` and `h(R[b])` matc=
hes.<br>
3.=C2=A0 `s` exchange.<br>
=C2=A0 * They compute `R` as `R =3D R[a] + R[b]`.<br>
=C2=A0 * They compute `e` as `h(R | m)`.<br>
=C2=A0 * 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`.<br>
=C2=A0 * They exchange `s[a]` and `s[b]`.<br>
=C2=A0 * They compute `s` as `s =3D s[a] + s[b]`.<br>
=C2=A0 * They publish the signature as the tuple `(e, s)`.<br>
<br>
At validation, the validator knows `P`, `m`, and the signature `(R, s)`.<br=
>
<br>
* It recovers `e[validator]` as so: `e[validator] =3D h(R | m)`<br>
* It computes `S[validator]` as so: `S[validator] =3D R + e[validator] * P`=
.<br>
* It checks if `s * G =3D=3D S[validator]`.<br>
=C2=A0 * `S[validator] =3D R + e[validator] * P`<br>
=C2=A0 * `=3D=3D R[a] + R[b] + e[validator] * P`; substitution of `R`<br>
=C2=A0 * `=3D=3D r[a] * G + r[b] * G + e[validator] * P`; substitution of `=
R[a]` and `R[b]`<br>
=C2=A0 * `=3D=3D r[a] * G + r[b] * G + e * P`; substitution of `e[validator=
]` with `e`<br>
=C2=A0 * `=3D=3D r[a] * G + r[b] * G + e * (h(L) * A + h(L) * B)`; substitu=
tion of `P`<br>
=C2=A0 * `=3D=3D r[a] * G + r[b] * G + e * h(L) * A + e * h(L) * B`; distri=
bution of `e` inside parentheses.<br>
=C2=A0 * `=3D=3D r[a] * G + r[b] * G + e * h(L) * a * G + e * h(L) * b * G`=
; substitution of `A` and `B`.<br>
=C2=A0 * `=3D=3D (r[a] + r[b] + e * h(L) * a + e * h(L) * b) * G`; factorin=
g out of `G`<br>
=C2=A0 * `=3D=3D (r[a] + e * h(L) * a + r[b] + e * h(L) * b) * G`; rearrang=
ement of terms<br>
=C2=A0 * `=3D=3D (s[a] + s[b]) * G`; substitution of `r[a] + e * h(L) * a` =
and `r[b] + e * h(L) * b`<br>
=C2=A0 * `=3D=3D s * G`;=C2=A0 substitution of `s[a] + s[b]`<br>
<br>
<br>
Two-Phase MuSig Unsafe<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
Original proposal of MuSig only had two phases, `R` exchange and `s` exchan=
ge.<br>
However, there was a flaw found in the security proof in this two-phase MuS=
ig.<br>
In response, an earlier phase of exchanging commitments to `R` was added.<b=
r>
<br>
Thus, two-phase MuSig is potentially unsafe.<br>
<br>
<a href=3D"https://eprint.iacr.org/2018/417.pdf" rel=3D"noreferrer" target=
=3D"_blank">https://eprint.iacr.org/2018/417.pdf</a> describes the argument=
.<br>
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.<br>
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.<br>
<br>
Briefly, a two-phase MuSig signing would go this way:<br>
<br>
1.=C2=A0 `R` exchange.<br>
=C2=A0 * A generates random scalar `r[a]` and B generates random scalar `r[=
b]`.<br>
=C2=A0 * A computes `R[a]` as `r[a] * G` and B computes `R[b]` as `r[b] * G=
`.<br>
=C2=A0 * They exchange `R[a]` and `R[b]`.<br>
2.=C2=A0 `s` exchange.<br>
=C2=A0 * They compute `R` as `R =3D R[a] + R[b]`.<br>
=C2=A0 * They compute `e` as `h(R | m)`.<br>
=C2=A0 * 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`.<br>
=C2=A0 * They exchange `s[a]` and `s[b]`.<br>
=C2=A0 * They compute `s` as `s =3D s[a] + s[b]`.<br>
=C2=A0 * They publish the signature as the tuple `(R, s)`.<br>
<br>
The sticking point is &quot;exchange&quot; here.<br>
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 &quot;at the same time&quot; in su=
ch a way that it is impossible for, for example, the send of B to be outsid=
e the future light cone of the send of A.<br>
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]`.<br>
<br>
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]`.<br>
Then at `s` exchange:<br>
<br>
* 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]`.<br>
* They compute `e` as `h(R[selected] | m)`.<br>
* A computes `s[a]` as `s[a] =3D r[a] + e * h(L) * a`.<br>
* B is unable to compute `s[b]` as it has no `r[b]` it can use in the compu=
tation, and aborts the signing.<br>
<br>
The attack involved is that multiple such signing sessions, for the same me=
ssage or for separate distinct messages, might be done in parallel.<br>
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]`.<br>
Then:<br>
<br>
* B delays each session, pretending to have Internet connectivity problems.=
<br>
* B selects a message `m[target]` that it knows A will never sign (e.g. &qu=
ot;I, A, give all my money to B&quot;).<br>
* B computes `R[target]` as `sum where i =3D 1 to n of R[a][i]`.<br>
* B uses the Wagner Generalized Birthday Paradox technique to find `R[selec=
ted][i]` with the following constraint:<br>
=C2=A0 * `h(R[target] | m[target]) =3D=3D sum where i =3D 1 to n of h(R[sel=
ected][i] | m[i])`.<br>
=C2=A0 * Given a large enough number of parallel sessions `n`, this can gre=
atly reduce the effort from 2^128 to find a match to within the realm of a =
large computer to compute within a few seconds.<br>
* B computes `R[b][i]` as `R[selected][i] - R[a][i]`, for each `i` from 1 t=
o `n`.<br>
* B provides `R[b][i]` for each session.<br>
* A computes `R[i]` as `R[a][i] + R[b][i]` for each session.<br>
=C2=A0 * 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]`<br>
* A computes `s[a][i]` as `r[a][i] + h(R[selected][i] | m[i]) * h(L) * a` f=
or each session.<br>
* A gives `s[a][i]` for each session.<br>
* B aborts each session.<br>
* B sums up all the `s[a][i]`:<br>
=C2=A0 * `(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]) * h(L) * a)`.<br>
=C2=A0 * Remember, B has specifically selected `R[selected][i]` such that `=
h(R[target] | m[target])` is equal to the sum of `h(R[selected][i] | m[i])`=
.<br>
=C2=A0 * `=3D=3D (sum where i =3D 1 to n of r[a][i]) + h(R[target] | m[targ=
et]) * h(L) * a)`.<br>
* B adds `h(R[target] | m[target]) * h(L) * b` to the above sum.<br>
=C2=A0 * This results in a signature for MuSig(A, B) to the message `m[targ=
et]`, even though A would never have agreed to this message.<br>
<br>
Thus, 2-phase MuSig enables a Wagner attack on the participant, thus it is =
unsafe.<br>
<br>
Now, any method of ensuring a &quot;simultaneous&quot; exchange of `R` poin=
ts is largely the same as adding a &quot;commit to `R`&quot; phase, i.e. th=
e fix for this is simply to add the &quot;`R` commitment exchange&quot; pha=
se.<br>
<br>
References: <a href=3D"https://eprint.iacr.org/2018/417.pdf" rel=3D"norefer=
rer" target=3D"_blank">https://eprint.iacr.org/2018/417.pdf</a><br>
<br>
MuSig Composition<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
Let us suppose that we have some protocol that requires a MuSig signing ses=
sion between signers with public keys `P` and `C`.<br>
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.<br>
<br>
At the point of view of signer C, P is a single participant and it acts as =
such.<br>
However, in reality, P is an aggregate.<br>
<br>
We want to have the following properties:<br>
<br>
* C should never need to know that P is in fact an aggregate.<br>
* 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.<br>
<br>
Now, from the point of view of C, what it sees are:<br>
<br>
At setup:<br>
<br>
* It generates a random scalar `c` and the public key `C` as `C =3D c * G`.=
<br>
* It exchanges keys with P and gets the public key `P`.<br>
* It computes `L` by sorting `C` and `P` and concatenating them.<br>
* It determines their aggregate key as `h(L) * C + h(L) * P`.<br>
<br>
At signing:<br>
<br>
1.=C2=A0 `R` commitment exchange.<br>
=C2=A0 * It generates a random scalar `r[c]` and computes `R[c]` as `R[c] =
=3D r[c] * G`.<br>
=C2=A0 * It computes `h(R[c])`.<br>
=C2=A0 * It exchanges the hash `h(R[c])` with P and gets `h(R[p])`.<br>
2.=C2=A0 `R` exchange.<br>
=C2=A0 * It exchanges `R[c]` with P and gets `R[p]`.<br>
=C2=A0 * It validates that the hash `h(R[p])` matches the previously-commit=
ted hash.<br>
3.=C2=A0 `s` exchange.<br>
=C2=A0 * It computes `R` as `R =3D R[c] + R[p]`.<br>
=C2=A0 * It computes `e` as `e =3D h(R | m)`.<br>
=C2=A0 * It computes `s[c]` as `s[c] =3D r[c] + e * c`.<br>
=C2=A0 * It exchanges `s[c]` with P and gets `s[p]`.<br>
=C2=A0 * It computes `s` as `s =3D s[c] + s[p]`.<br>
<br>
However, from point of view of A and B, what actually happens is this:<br>
<br>
At setup:<br>
<br>
* A generates a random scalar `a` and computes `A =3D a * G`, B generates a=
 random scalar `b` and computes `B =3D b * G`.<br>
* They exchange `A` and `B`.<br>
* They generate their own `L[ab]`, by sorting `A` and `B` and concatenating=
 their representations.<br>
* They compute the inner MuSig pubkey `P` as `P =3D h(L[ab]) * A + h(L[ab])=
 * B`.<br>
* They exchange `P` with C, and get `C`.<br>
* They compute the outer MuSig pubkey as `h(L) * P + h(L) * C`.<br>
<br>
At signing:<br>
<br>
1.=C2=A0 `R` commitment exchange.<br>
=C2=A0 * 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`.<br>
=C2=A0 * A computes `h(R[a])`, B computes `h(R[b])`.<br>
=C2=A0 * They exchange `h(R[a])` and `h(R[b])`.<br>
=C2=A0 * They need to compute `h(R[p])` for the protocol with C.<br>
=C2=A0 =C2=A0 * However, even if we know `R[p] =3D=3D R[a] + R[b]`, we cann=
ot generate `h(R[p])`.<br>
=C2=A0 =C2=A0 * Thus, they have no choice but to exchange `R[a]` and `R[b]`=
 at this phase, even though this is supposed to be the `R` commitment excha=
nge phase (and they should not share `R[a]` and `R[b]` yet)!<br>
<br>
Unfortunately, this means that, between A and B, we are now reduced to a tw=
o-phase MuSig.<br>
This is relevant if B and C happen to be the same entity or are cooperating=
.<br>
<br>
Basically, before C has to provide its `h(R[c])`, B now knows the generated=
 `R[a]` and `R[b]`.<br>
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])`.<br>
Then this devolves to the same attack that brings down 2-phase MuSig.<br>
<br>
Thus, composition with the current MuSig proposal is insecure.<br>
<br>
Towards a Composable Multi-`R` MuSig<br>
=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<br>
<br>
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`.<br>
<br>
I propose here the modification below:<br>
<br>
* In the first phase, any participant in the MuSig may submit one *or more*=
 `R` commitments.<br>
* In the second phase, the participant in the MuSig submits each `R` that d=
ecommits each of the `R` commitments it sent.<br>
<br>
I call this the Remote R Replacement Remanded: Redundant R Required Realist=
ically, or, in shorter terms, the Multi-`R` proposal.<br>
<br>
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.<br>
<br>
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.<br>
<br>
However, in the case where one participant is in reality itself an aggregat=
e, then we shall describe it below.<br>
The below example is `MuSig(MuSig(A, B), C)`.<br>
<br>
1.=C2=A0 `R` commitment exchange.<br>
=C2=A0 * A generates a random number `r[a]`, B generates a random number `r=
[b]`, C generates a random number `r[c]`.<br>
=C2=A0 * A computes `R[a]` as `r[a] * G`, B computes `R[b]` as `r[b] * G`, =
C computes `R[c]` as `r[c] * G`.<br>
=C2=A0 * A computes `h(R[a])`, B computes `h(R[b])`, C computes `h(R[c])`.<=
br>
=C2=A0 * A and B exchange their hashes with each other.<br>
=C2=A0 * A and B jointly exchange their `h(R[a])` and `h(R[b])` with the `h=
(R[c])` from C.<br>
2.=C2=A0 `R` exchange.<br>
=C2=A0 * A and B reveal their `R[a]` and `R[b]` with each other.<br>
=C2=A0 * A and B validate the given `R[a]` matches `h(R[a])` and the given =
`R[b]` matches `h(R[b])`.<br>
=C2=A0 * A and B jointly exchange their `R[a]` and `R[b]` with the `R[c]` f=
rom C.<br>
=C2=A0 * C validates `R[a]` and `R[b]`, A and B validate `R[c]`.<br>
=C2=A0 * They compute `R` as the sum of all `R[a] + R[b] + R[c]`.<br>
3.=C2=A0 `s` exchange.<br>
=C2=A0 * They compute `e` as `h(R | m)`.<br>
=C2=A0 * A computes `s[a]` as `r[a] + e * h(L[abc]) * h(L[ab]) * a`, B comp=
utes `s[b]` as `r[b] + e * h(L[abc]) * h(L[ab]) * b`.<br>
=C2=A0 * C computes `s[c]` as `r[c] + e * h(L[abc]) * c`.<br>
=C2=A0 * A and B exchange `s[a]` and `s[b]`.<br>
=C2=A0 * A and B compute `s[ab]` as `s[a] + s[b]`.<br>
=C2=A0 * A and B jointly exchange their `s[ab]` with `s[c]` from C.<br>
=C2=A0 * They compute `s` as `s[ab] + s[c]`.<br>
=C2=A0 * They publish the signature as the tuple `(R, s)`.<br>
<br>
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 &lt; m`, but cannot pretend w=
ith `n &gt; m`).<br>
Thus, C here learns that its counterparty is actually itself an aggregate r=
ather than a singleton.<br>
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).<br>
<br>
Alternative Composable MuSig Schemes<br>
=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<br>
<br>
The above proposal is not the only one.<br>
Below are some additional proposals which have various flaws, ranging from =
outright insecurity to practical implementation complexity issues.<br>
<br>
Pedersen Commitments in Phase 1<br>
-------------------------------<br>
<br>
My initial proposal was to use Pedersen commitments in phase 1.<br>
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.<br>
Then at phase 2, each party reveals its `q[x]`.<br>
All the Pedersen commitments are summed, then all `q[x]` are summed, multip=
lied by `H`, then subtracted from the sum of Pedersen commitments.<br>
<br>
Unfortunately, this leads to a Wagner attack.<br>
<br>
Suppose A and B have an aggregate MuSig(A, B).<br>
<br>
* B initiates multiple parallel signing sessions with A.<br>
* B selects a message `m[target]` that it knows A will never sign (e.g. &qu=
ot;I, A, give all my money to B&quot;).<br>
* 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.<br>
* In the second phase, B delays each session, pretending to have Internet c=
onnectivity problems.<br>
* A sends B the `q[a][i]` for all `i`.<br>
* B computes `R[a][i]` for all `i` by subtracting `q[a][i] * H` from the Pe=
dersen commitments given by A.<br>
* B computes `R[target]` as `sum where i =3D 1 to n of R[a][i]`.<br>
* B uses the Wagner Generalized Birthday Paradox technique to find `q[b][i]=
` with the following constraint:<br>
=C2=A0 * First compute `R[selected][i]` as `R[a][i] +=C2=A0 R[b][i] - q[b][=
i] * H` for all `i`.<br>
=C2=A0 * 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])`.<br>
* B sends the `q[b][i]` found above.<br>
* 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`.<br>
=C2=A0 * This resolves down to `R[a][i] + R[b][i] - q[b][i] * H`, or `R[sel=
ected][i]`.<br>
* A computes `s[a][i]` as `r[a][i] + h(R[selected][i] | m[i]) * a` for all =
`i`.<br>
* 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`.=
<br>
=C2=A0 * 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])`.<=
br>
<br>
Thus, Pedersen commitments for phase 1 are insecure, as it allows counterpa=
rties to control `R`.<br>
<br>
ElGamal Commitments in Phase 1<br>
------------------------------<br>
<br>
ElGamal commitments prevent B from just giving random `q[b][i]`, thus preve=
nting the above Wagner attack.<br>
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).<br>
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).<br>
<br>
Briefly, with ElGamal commitments in Phase 1:<br>
<br>
1. `R` commitment exchange.<br>
=C2=A0 * A generates random numbers `r[a]` and `q[a]`, B generates random n=
umbers `r[b]` and `q[b]`.<br>
=C2=A0 * 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`.<br>
=C2=A0 =C2=A0 * `H` is a NUMS point used as a second standard generator.<br=
>
=C2=A0 =C2=A0 * Note that one point uses `q[] * G` while the other adds `q[=
] * H` to `r[] * G`.<br>
=C2=A0 * They exchange their pairs of points.<br>
2. `R` exchange.<br>
=C2=A0 * 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]`).<br>
=C2=A0 * They validate the exchanged data from the previous `R` commitments=
.<br>
=C2=A0 * They compute `R` as `R[a]` + `R[b]`.<br>
3. `s` exchange.<br>
=C2=A0 * Same as before.<br>
<br>
B can attack this by delaying its phases as below:<br>
<br>
1. `R` commitment exchange.<br>
=C2=A0 * B generates random `q[selected]`.<br>
=C2=A0 * B selects target `R[selected]`.<br>
=C2=A0 * After receiving `q[a] * G` and `r[a] * G + q[a] * H`, B computes `=
q[selected] * G - q[a] * G` and `R[selected] + q[selected] * H - r[a] * G -=
 q[a] * H` and sends those points as its own commitment.<br>
2. `R` exchange.<br>
=C2=A0 * After receiving `q[a]` and `R[a]`, B computes `q[b]` as `q[selecte=
d] - q[a]` and computes `R[b]` as `R[selected] - R[a]` and sends both as it=
s decommitment.<br>
=C2=A0 * The resulting `R` will now be `R[selected]` chosen by B.<br>
<br>
`s` exchange cannot complete, as that would require that B know `r[selected=
] - r[a]` where `R[selected] =3D r[selected] * G`.<br>
Even if B generates `R[selected]` from `r[selected]`, it does not know `r[a=
]`.<br>
A would provide `r[a] + h(R[selected] | m) * h(L[ab]) * a`, but B would be =
unable to complete this signature.<br>
<br>
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.<br>
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]`.<br>
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])`<br>
Fortunately for this scheme, B cannot determine such an `R[target]` before =
it has to select `R[selected]`, thus preventing this attack.<br>
<br>
It may be possible that this scheme is safe, however I am not capable of pr=
oving it safe.<br>
<br>
Acknowledgments<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
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.<br>
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).<br>
It seemed to me that the general agreement was that ElGamal commitments sho=
uld work for committing to `r * G`.<br>
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).<br>
<br>
`nickler` and `waxwing` on IRC confirmed my understanding of the attack on =
2-phase MuSig.<br>
`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.<br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000007b9e81059875d021--