mini_multisig.md

Mini Schnorr multisig

NOTE: This is not a work of a cryptographer and should thus be considered flawed.

Consider we have N parties that want to construct a N-N multisig. Musig2 allows for an out of order 2 rounds multisig creation.

This is an attempt at the simplest variant of a secure 2 round Schnorr multisig under the assumption that parties choose a pubkey just in time (no pubkey reuse).

2-round order preserving

The protocol has a linear flow where every party first adds their keys (pubkey, nonce) and on the way back they sign the message.

                    add key phase                                        sign phase
(addKeyA -> addKeyB -> addKeyC -> addKeyD -> addKeyE) -> (signE -> signD -> signC -> signB -> signA)

We use the observation that:

1. At the add key stage, the keys before yours could not have done a rogue key attack on your key because they were created before your key was picked
2. At the sign stage, the keys after yours could not have done a rogue key attack if they provide a valid partial signature

This means that before adding their key, a party has to remember the keys of the previous parties and needs to check the partial signatures of keys that were added later before producing their own a partial signature. For example party C remembers [addKeyA, addKeyB] keys when doing addKeyC step and when signing verifies the partial sigs of other keys that came after which are the [addKeyD, addKeyE]keys.

If these two checks are valid, we can sign a message on H(M | P1 + P2 + ... + Pn | R1 + R2 + ... + Rn) because no key could've done a rogue key attack on our key.

This requires:

1. picking keys just in time
2. remembering keys that were picked prior to your key and requiring a valid partial signature for every other key before signing your partial sig

Round key compression

As a side effect, I think this might allow aggregating keys on the fly during both addKey and sign phase. For example, when party C does addKey phase they could receive a single joint pubkey A+B and a joint nonce RA+RB and remember these rather than the individual nonces and keys. Similarly, when C signs, they could receive a joint pubkey, nonce and partial signature of D and E meaning they get D+E, RD+RE, part_sigD+part_sigE as if there was a single key involved. This means every party could receive a single key information (joint pubkeys and nonces) before them and verify a single aggregated partial signature (joint pubkey, nonces and partial sigs) after them to keep them safe.

Blinding participant number

Since we only receive a single joint pubkey and nonce for parties before us, we can't really tell whether there's 1 or more parties involved before us. Similarly, when signing we again receive a single pubkey, nonce and a partial signature which doesn't give information on how many parties come after us. This might allow for schemes where you're a part of a multisig where you don't know how many parties are actually involved.

Use cases

One potential use case could be multisigs that are used to prove a property rather than locking coins in a multisig scheme e.g. Mimblewimble kernels that prove transaction validity. Parties could create an interactive multiparty transaction without knowing how many parties are involved. Each would sign only for their own state of inputs and outputs and they would jointly create a transaction with a single kernel.

Extending the model to reused pubkeys (NOTE: very unchecked!)

We might be able to allow signing with existing pubkeys rather than making them up on the go. Party at position i could pick a random scalar x_i and scale its pubkey as Pi' = xi*Pi. This would mean the parties before party i could not cancel P_i completely because they wouldn't know x_i. If the parties after party i wanted to cancel P_i key, they wouldn't be able to construct a valid partial signature for it.