[bitcoin-dev] Composable MuSig

[bitcoin-dev] Composable MuSig

[ZmnSCPxj]

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.

Re: [bitcoin-dev] Composable MuSig

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 24911 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 26929 bytes --]

Re: [bitcoin-dev] Composable MuSig

[ZmnSCPxj]

Good morning Lloyd, and list,

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

So the Pedersen commitment commits to a tweak on `X`, which is revealed later so we can un-tweak `X`.
Am I correct in assuming that you propose to use `X` for the contribution to `R` for a participant?
How is it different from using ElGamal commitments?


-------


Some number of people have noted, including at least one MuSig author, that in the ElGamal case it would be possible to prove your knowledge of the `q` behind `q * G`, and thus prevent the cancellation attack shown.
We already have a general proof-of-knowledge-of-secret-key, the Schnorr signature signing algorithm itself.

Thus, together with `q * G` in the ElGamal commitment, we could include a Schnorr signature using `q * G`, either of the target message itself, or any constant string.

This seems highly appropriate, yo dawg, I heard you like MuSig, so I put an aggregate in your aggregate, so you could sign (singly) while you sign (multiply).

In terms of a *composable* MuSig, e.g. MuSig(MuSig(A, B), C), both A and B will select `q[a]` and `q[b]` and will generate a shared `q[ab] * G` as the MuSig of `q[a] * G` and `q[b] * G`.
Since they know the corresponding `q[a]` and `q[b]` they will also known the contributions they each will need to generate `q[ab] * H`, but note that there is no proof of this until they reveal `q[a]` and `q[b]`, which may lead to further attacks, this time on `q[ab] * H` instead.
So at least for `q` it seems not to be a good idea, though I have not put much thought into this.

Indeed, it seems to me that signatures using the contributions `R[a]` and `R[b]` as public keys seems to be another way to commit to `R` while ensuring that your own `R` cannot have cancelled the other participant `R`.
You would have to exchange the (single) signatures of `R[a]` and `R[b]` first, however, otherwise a Wagner attack may be possible if you exchange `R[a]` and `R[b]` first (i.e. the signatures replace the `R` commitment phase of 3-phase MuSig).

The complexity of either sign-while-you-sign idea, however, is much greater.
Your signing algorithm now requires delegating to another signing algorithm, which while at least fair in that you are now signing while you sign because you aggregated while you aggregated, is more complicated to implement practically.



Regards,
ZmnSCPxj

Re: [bitcoin-dev] Composable MuSig

[Lloyd Fournier]

Hi ZmnSCPxj,

> > 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.
>
> So the Pedersen commitment commits to a tweak on `X`, which is revealed later so we can un-tweak `X`.
> Am I correct in assuming that you propose to use `X` for the contribution to `R` for a participant?
> How is it different from using ElGamal commitments?

Yes. It's not significantly different. It is unconditionally hiding
rather than binding (ElGamal is unconditionally binding). I just
thought of it while reading your post so I mentioned it. The real
question is what properties does the commitment scheme need to be
appropriate for MuSig R coin tossing?
In the security proof, the commitment hash is modelled as a random
oracle rather than as an abstract commitment scheme. I wonder if any
MuSig author has an opinion on whether the H_com interaction can be
generalised to a commitment scheme with certain properties (e.g
equivocal, extractable). By the looks of it, the random oracle is
never explicitly programmed except with randomly generated values so
maybe there is hope that a non ROM commitment scheme can do the job. I
guess the reduction would then be to either breaking the discrete
logarithm problem OR some property of the commitment scheme.

Cheers,

LL

Re: [bitcoin-dev] Composable MuSig

[ZmnSCPxj]

Good morning Lloyd,

> The real
> question is what properties does the commitment scheme need to be
> appropriate for MuSig R coin tossing?

It seems to me that what is needed for a composable MuSig is to have a commitment scheme which is composable.

Let me define a composable commitment scheme:

Given:

* `A` and `B`, two points to be committed to.
* `c[A]` and `c[B]`, commitments to the above points respectively.
* `r[A]` and `r[B]`, openings of the above commitments respectively.

Then a composable commitment scheme must have these operations:

* `ComposeCommitments(c[A], c[B])`, which returns a commitment to the point `A + B`.
* `ComposeOpenings(r[A], r[B])`, which returns an opening of the above commitment to the point `A + B`.

My multi-`R` proposal is a composable commitment scheme:

* A commitment `c[A]` is the list `{h(A)}` where `h()` is some hash function.
* `ComposeCommitments(c[A], c[B])` is the concatenation on lists of hashes of points.
* An opening `r[A]` is the list `{A}`.
* `ComposeOpenings(r[A], r[B])` is the concatenation on lists of points.

The property we want to have, is that:

* There must not exist some operation `NegateCommitment(c[A])`, such that:
  * `ComposeCommitments(ComposeCommitments(c[B], NegateCommitment(c[A])), c[A]) == c[B]`.

My multi-`R` proposal works as a composable commitment scheme appropriate for composable MuSig because there is no way to create an input to a concatenation operation such that the concatenation operation becomes a "search and delete" operation.
Pedersen and ElGamal commitments, I think, cannot work here, because commitments in those schemes are negatable in such a way that composing the commitments allows a commitment to be cancelled.

-----

Let us now turn to signature schemes.
I conjecture that the Schnorr and ECDSA signature schemes are also commitment schemes on points.

To create a commitment `c[A]` on the point A, such that `A = a * G`, the committer:

* Generates random scalars `r` and `m`.
* Computes `R` as `r * G`.
* Computes `s` as `r + h(R | m) * a`.
* Gives `c[A]` as the tuple `(R, s)`.

The opening `r[A]` of the above is then the tuple `(m, A)`.
The verifier then validates that the commitment was indeed to the point `A` by doing the below:

* Computes `S[validator]` as `R + h(R | m) * A`.
* Validates that `S[validator] == s * G`.

Now, we know that signatures can be composed in such a way that points (public keys) cannot be cancelled, i.e. preventing the creation of a `NegateCommitment()` operation.
Thus, a signature can be used as a composable commitment in composable MuSig scheme.

In summary, I conjecture that:

* We need a composable commitment scheme that does not allow cancellation, and any such commitment scheme can be "slotted" into the 3-phase MuSig framework.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Composable MuSig

[Lloyd Fournier]

Hi ZmnSCPxj,

I think you're idea of allowing multiple Rs is a fine solution as it
would essentially mean that you were just doing a three party MuSig
with more specific communication structure. As you mentioned, this is
not quite ideal though.

> It seems to me that what is needed for a composable MuSig is to have a commitment scheme which is composable.

Maybe. Showing certain attacks don't work is a first step. It would
take some deeper analysis of the security model to figure out what
exactly the MuSig requires of the commitment scheme.

> To create a commitment `c[A]` on the point A, such that `A = a * G`, the committer:
>
> * Generates random scalars `r` and `m`.
> * Computes `R` as `r * G`.
> * Computes `s` as `r + h(R | m) * a`.
> * Gives `c[A]` as the tuple `(R, s)`.

This doesn't look binding. It's easy to find another ((A,a),m) which
would validate against (R,s). Just choose m and choose a = (s - r)
h(R||m)^-1.

Cheers,

LL

Re: [bitcoin-dev] Composable MuSig

[Erik Aronesty]

[-- Attachment #1: Type: text/plain, Size: 24928 bytes --]

> Thus, two-phase MuSig is potentially unsafe.
> https://eprint.iacr.org/2018/417.pdf describes the argument.

One solution is to add a signature timeout to the message (say a block
height) .

A participant refuses to sign if that time is too far in the future, or is
at all in the past, or if a message M is the same as any previous message
within that time window.

Seems to resolve the attacks on 2 round musig.












On Mon, Nov 25, 2019, 6:00 AM 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
>

[-- Attachment #2: Type: text/html, Size: 28658 bytes --]

Re: [bitcoin-dev] Composable MuSig

[Tim Ruffing]

On Sun, 2020-02-23 at 02:27 -0500, Erik Aronesty via bitcoin-dev wrote:
> > Thus, two-phase MuSig is potentially unsafe.
> > https://eprint.iacr.org/2018/417.pdf describes the argument.
> 
> One solution is to add a signature timeout to the message (say a
> block height) .  
> 
> A participant refuses to sign if that time is too far in the future,
> or is at all in the past, or if a message M is the same as any
> previous message within that time window.
> 
> Seems to resolve the attacks on 2 round musig.

I don't understand this. Can you elaborate?

Best,
Tim

Re: [bitcoin-dev] Composable MuSig

[Erik Aronesty]

Basically just some mechanism for preventing repeated signings of the
same message, and using a "validity" time window so that the amount of
state you need to enquire about isn't unbounded.

The Drijvers, et al paper is specifically concerned with parallel and
aborted signings, where ksums can be used.  In general, the more
variables that an attacker can control ,the more "k" lists they can
form, and the more likely they can find collisions.

If signers refused to sign "stale" messages, refused to sign in
parallel beyond a certain limit, and refused to sign the same message
twice, it should help reduce the attack surface.

On Mon, Feb 24, 2020 at 6:41 AM Tim Ruffing via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Sun, 2020-02-23 at 02:27 -0500, Erik Aronesty via bitcoin-dev wrote:
> > > Thus, two-phase MuSig is potentially unsafe.
> > > https://eprint.iacr.org/2018/417.pdf describes the argument.
> >
> > One solution is to add a signature timeout to the message (say a
> > block height) .
> >
> > A participant refuses to sign if that time is too far in the future,
> > or is at all in the past, or if a message M is the same as any
> > previous message within that time window.
> >
> > Seems to resolve the attacks on 2 round musig.
>
> I don't understand this. Can you elaborate?
>
> Best,
> Tim
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Composable MuSig

[Tim Ruffing]

The only thing that matters is the number of parallel sessions. If you
bound this to something like 2 or 3, then the resulting scheme may be
secure. But you need to the actual math of Wagner's attack, and who
knows how efficient it can be implemented in practice. 

Timeouts on top of this won't help. And who needs 2 or 3 parallel
sessions? If you need parallel sessions (or not), use 3-round MuSig and
the entire issue is simply eliminated.

Tim  

On Mon, 2020-02-24 at 10:30 -0500, Erik Aronesty wrote:
> Basically just some mechanism for preventing repeated signings of the
> same message, and using a "validity" time window so that the amount
> of
> state you need to enquire about isn't unbounded.
> 
> The Drijvers, et al paper is specifically concerned with parallel and
> aborted signings, where ksums can be used.  In general, the more
> variables that an attacker can control ,the more "k" lists they can
> form, and the more likely they can find collisions.
> 
> If signers refused to sign "stale" messages, refused to sign in
> parallel beyond a certain limit, and refused to sign the same message
> twice, it should help reduce the attack surface.
> 
> On Mon, Feb 24, 2020 at 6:41 AM Tim Ruffing via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > On Sun, 2020-02-23 at 02:27 -0500, Erik Aronesty via bitcoin-dev
> > wrote:
> > > > Thus, two-phase MuSig is potentially unsafe.
> > > > https://eprint.iacr.org/2018/417.pdf describes the argument.
> > > 
> > > One solution is to add a signature timeout to the message (say a
> > > block height) .
> > > 
> > > A participant refuses to sign if that time is too far in the
> > > future,
> > > or is at all in the past, or if a message M is the same as any
> > > previous message within that time window.
> > > 
> > > Seems to resolve the attacks on 2 round musig.
> > 
> > I don't understand this. Can you elaborate?
> > 
> > Best,
> > Tim
> > 
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev