MuSig: Schnorr Multisig and signature aggregation

[achow101]

Pieter Wuille, Andrew Poelstra, Greg Maxwell, and Yannick Seurin recently published a new multisignature and key aggregation scheme called MuSig. This new scheme uses Schnorr signatures.

The MuSig paper can be found here: https://eprint.iacr.org/2018/068.pdf

A high level overview of MuSig is available here: https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatures.html


MuSig is a secure non-interactive key aggregation and multisig scheme. It builds upon the Bellare-Nevan multisignature scheme which allows for multiple public keys to be used to create just one signature. This contrasts the traditional multisignature scheme used by Bitcoin where there are multiple signatures.

MuSig builds upon Bellare-Nevan by allowing for key aggregation. Key aggregation means that multiple public keys are combined into one public key. By combining this key aggregation scheme and the Bellare-Nevan multisig scheme, MuSig allows for a multisignature spend to contain only one public key and one signature (both of which can only be constructed with the multiple parties). This means that MuSig allows for additional privacy (an outside observer only sees the one signature and combined public key so they don't know how many people are involved and what the threshold is) and reduces the size of a multisig signature (instead of multiple public keys and multiple signatures, only the combined public key and signature are used). This reduces the size of transactions which means that more transactions could fit into a block thus increasing Bitcoin's capacity.

Furthermore, the multisig aspect of MuSig (aka the Bellare-Nevan part) lets transactions to have only one signature which verifies for all of the public keys involved in a transaction. That means that a transaction with multiple inputs will only have one signature which signs for all inputs. This further reduces the size of a transaction and allows for more transactions to fit in a block and thus increasing Bitcoin's capacity.


It is important to note that MuSig is just the signature scheme and is applicable to more things than just Bitcoin. For actual use in Bitcoin, additional changes will need to be made to support it such as new script opcodes. For that to happen, there will need to be a BIP which is several months off (perhaps a year or more away).

[cellard]

This sounds great, I remember reading about schnorr signatures a long time ago, apparently it was needed for confidential transactions to properly work.

Will this be deployed as a regular BIP or does it need another soft-fork like BIP141? because im not looking forward to years of segregated witness drama part 2, im getting too old to manage that stress  

[achow101]

Will this be deployed as a regular BIP or does it need another soft-fork like BIP141? because im not looking forward to years of segregated witness drama part 2, im getting too old to manage that stress  

Deployment will need another soft fork, and it will be BIP'ified as usual.

[cellard]

Will this be deployed as a regular BIP or does it need another soft-fork like BIP141? because im not looking forward to years of segregated witness drama part 2, im getting too old to manage that stress  

Deployment will need another soft fork, and it will be BIP'ified as usual.

Oh man, here we go then... do you predict a similar outcome to segwit? namely, miners playing cat and mouse for a long term until the community pushes them really hard against the ropes and they are basically forced to do so? possibly another UASF scenario? Or is this less controversial and therefore will go in smoothly?

What will the activation threshold be? I think it was 95% for 2 weeks for BIP141 or something like that innit?

[achow101]

What will the activation threshold be? I think it was 95% for 2 weeks for BIP141 or something like that innit?

It will likely be the same as that is just following the BIP 9 specification.

Again, there currently is not BIP nor is there an actual proposal for using this in Bitcoin yet. We won't know the actual details until that happens.

[achow101]

Soft fork? I wonder if it's possible since MuSig use different signature format which older nodes won't able to recognize or there will be backwards compatibility just like SegWit where older nodes only can see non-witness data?

The fork would presumably use the witness program versioning thing that segwit introduced. This would mean that it uses a new witness program version, so older software will just ignore it as it is a new version it does not understand.

[Carlton Banks]

Enthusiastic about this possibility, as it actually improves Bitcoin's on-chain transaction scaling (instead of increasing resource usage at the same scale). It also makes increases to the blockweight limit viable, as signature aggregation should reduce the burden of signature validation in every Bitcoin block.

So, the blockweight limit could be safely increased by the factor that sig-aggregation improves validation performance after a MuSig softfork was activated on the network.

[cellard]

Enthusiastic about this possibility, as it actually improves Bitcoin's on-chain transaction scaling (instead of increasing resource usage at the same scale). It also makes increases to the blockweight limit viable, as signature aggregation should reduce the burden of signature validation in every Bitcoin block.

So, the blockweight limit could be safely increased by the factor that sig-aggregation improves validation performance after a MuSig softfork was activated on the network.

Yep, I can only see positives coming from this, the question is, is there any possible negative in which the /r/btc / bcash crowd could gather in order to block bitcoin from getting this improvement?

What arguments could be potentially used to make this Schnorr sigs seem as controversial? The arguments for segwit were that miners could potentially collide and steal funds in segwit addresses. What could they claim to avoid this?

I just find 95% of agreement extremely difficult at this point (im not saying it should be lowered tho, the main point of bitcoin is precisely that it's hard to change).

[Carlton Banks]

What arguments could be potentially used to make this Schnorr sigs seem as controversial?

Hilariously bad arguments.

• Segwit made it safer to increase the size of Bitcoin blocks. Big Blockers hated it, of course
• Aggregated signatures would make it safer to increase the size of Bitcoin blocks. Big Blockers will hate it, too. What else!

When Big Blockers don't want tech improvements that safely permit big blocks, and Small-Blockers do, you have to wonder (as usual) what this "blocksize wars" argument is actually all about

[franky1]

MuSig is a secure non-interactive key aggregation and multisig scheme.

also known as a k of n multisig
this means that in a 2-of-5 multisig where 3 people dont have to sign,

as oppose to
interactive, where by its n of n, meaning it has to be a 5 of 5 or a 3 of 3 where everyone has to sign

This means that MuSig allows for additional privacy (an outside observer only sees the one signature and combined public key so they don't know how many people are involved and what the threshold is)

this means when users see the funding public key, they dont know how many other signers there are or are needed in total
and when the funds do move.. never get to know who specifically did sign

because the address doesnt tell them it is a 2 of 5..
because the address doesnt tell them who the other 4 people are

making it easy for whomever set it up to tell 3 guys its a 3 of 3 when in reality its a 2 of 5, and in reality whomever set it up owns 2 keys himself

so the 3 innocent guys dont realise its a 5 counterparty address.. all they can see is that their key is part of AN address.. but not know how much of a part...


much like a rigged poker game where 2 people set up the game, but hide in the backroom, letting  another 3 people play a table thinking they are only playing a 3 man game between themselves... then the 2 backroom guys can crash the poker game and steal all the chips. leaving the other 3 penniless and wondering who stole their chips. blaming each other

coding may work for privacy and lack of sole control.. but those same utility and features allow the ability to steal/blackmail

even carlton banks highlighted last year that a 'fund manager' with a special key can be sole controller while everyone else is offline, when he was describing how he can get rich offering services as a fund manager/escrow/arbitrator for second layer / multisig proposals.

lets hope bitcoin goes down the n of n (interactive) route to avoid fund manager thieves while others sleep. and not the k of n(non interactive) route
though the pitfall of n of n. is that if one users system crashes and they lose their key.. everyone elses funds are locked.

so i feel musig still needs ALOT more work and running scenario's before even being close to being a BIP

[Anti-Cen]

When Big Blockers don't want tech improvements that safely permit big blocks, and Small-Blockers do, you have to wonder (as usual) what this "blocksize wars" argument is actually all about

The "Block" debate at best offers a short term sticking plaster and it should be about replicated monolithic database
against Distributed Network Architecture (DNA) and about on-block or off block

Competition without naming names is going to take over unless the development team stops concluding
with the miners to make them rich and that includes turning them into banking hubs with lightning network
even if it is DNA using centralization

A degree of centralization is not such a bad thing but i am darned if the banking hubs and there fees
should form the basis of that centralization, I did warn you that Bob and Alice channels would not work
and now here is the proof since you would not admit it https://lnmainnet.gaben.win/

The table has magnets under it, fixed game

[ArithmomanicVampire]

I don't quite get yet how the k-of-n threshold scheme comes in (maybe it's out of the scope of that paper?), but in general, this is great news. I hope a BIP detailing the actual implementation into Bitcoin will be forthcoming soon.

[achow101]

also known as a k of n multisig
this means that in a 2-of-5 multisig where 3 people dont have to sign,

as oppose to
interactive, where by its n of n, meaning it has to be a 5 of 5 or a 3 of 3 where everyone has to sign

No, that is not what interactive means.

In traditional cryptography, interactive means that the participants in the multisig must verify that the other participants actually control the private keys to their public keys, not that it is n-of-n. Non-interactive does not mean that it is k-of-n, it just means that there is no key exchange and verification protocol that must be executed.

Anyways, MuSig is specifically an n-of-n multisig scheme as it is a multisig scheme in the context of traditional cryptography.

this means when users see the funding public key, they dont know how many other signers there are or are needed in total

The same is with current multisig using P2SH. Hell, you don't even know whether a given P2SH address is multisig or not, so if you are a participant in any multisig, you should always be asking for the redeemScript, or, if using something based on MuSig, you should be asking for the public keys involved and make sure they calculate to the given aggregate public key.

and when the funds do move.. never get to know who specifically did sign

because the address doesnt tell them it is a 2 of 5..
because the address doesnt tell them who the other 4 people are

making it easy for whomever set it up to tell 3 guys its a 3 of 3 when in reality its a 2 of 5, and in reality whomever set it up owns 2 keys himself

so the 3 innocent guys dont realise its a 5 counterparty address.. all they can see is that their key is part of AN address.. but not know how much of a part...

This is completely incorrect, did you even read the paper or the linked blog post?

As I said earlier, MuSig is only a n-of-n scheme so this concern is completely invalid. To do k-of-n, additional work is required.

I don't quite get yet how the k-of-n threshold scheme comes in (maybe it's out of the scope of that paper?), but in general, this is great news. I hope a BIP detailing the actual implementation into Bitcoin will be forthcoming soon.

k-of-n is out of scope for the paper. MuSig is only n-of-n, but with additional Bitcoin specific things, can be done in a k-of-n fashion.

[Anti-Cen]

Again the OP comes to my rescue because I need something like a four party transaction with two stage commit on the
data and was going to ask if anyone knew the answer before trying to roll my own.

In my case it's a little more complicate because three of the parties are clusters used for redundancy
Ledger one  (2-10) nodes
Ledger Two  (2-10) nodes
Coordinators (10-50) nodes
Manager       (1) node

All have public keys and the Coordinators could generate a on-the-fly public/private key pair just for the transaction
if needs be so yes thanks again OP

 

[LeGaulois]

I was reading an article saying that the Schnorr signatures are considered as "the best of the best" among cryptographers. If so, why this authentication protocol has never managed to become popular? Given that it has existed since the years '80-'90

[Samarkand]

I was reading an article saying that the Schnorr signatures are considered as "the best of the best" among cryptographers. If so, why this authentication protocol has never managed to become popular? Given that it has existed since the years '80-'90

I´m just speculating here so take this with a grain of salt.

Schnorr signatures were covered by a patent that expired in 2008.

Wikipedia:

In cryptography, a Schnorr signature is a digital signature produced by the
Schnorr signature algorithm. Its security is based on the intractability of certain discrete
 logarithm problems. The Schnorr signature is considered the simplest[1] digital signature
scheme to be provably secure in a random oracle model.[2] It is efficient and
generates short signatures. It was covered by U.S. Patent 4,995,082 which expired in February 2008.

Maybe being covered by a patent could have hampered the popularity?

Now that the patent has expired everyone is free to use Schnorr signatures,
which could obviously incentivize the usage of them.

I have also been doing some reading on Schnorr signatures and the resulting potential improvements
for Bitcoin and was especially surprised about the discovery that the usage of Schnorr signatures actually
enables you to increase the security of your Bitcoin holdings.

[LeGaulois]

I see. Indeed you may be right, but it's been patented by himself, and there's a large time period between 2008 and today (by the way, I found this discussion while searching DSA (Digital Signature Standard) and the Schnorr Patents)

The only things I understand about it, are: it's more efficient than ECDSA, helps for scalability, spam attacks and improve the user's privacy. Anything else I am in "reading mode" xD

[franky1]

This is completely incorrect, did you even read the paper or the linked blog post?

As I said earlier, MuSig is only a n-of-n scheme so this concern is completely invalid. To do k-of-n, additional work is required.

i read it. and then thought about the bitcoin utlity... not traditional meaning
hint below:

I don't quite get yet how the k-of-n threshold scheme comes in (maybe it's out of the scope of that paper?), but in general, this is great news. I hope a BIP detailing the actual implementation into Bitcoin will be forthcoming soon.

k-of-n is out of scope for the paper. MuSig is only n-of-n, but with additional Bitcoin specific things, can be done in a k-of-n fashion.

oh look MUsig for bitcoin can be K-of-n
but anyway, on this bitcoin forum, i was thinking of bitcoins utilisation (which WE BOTH noted k-of-n is possible) and which insuch scenario the poker players wont know about the backroom guys if non interactive
(sorry i summarised it in the context of a ELI-5 bitcoin utility pitfall... shame on me for worrying about bitcoin pitfalls)

but to ELI-5 traditional.. instead of ELI-5 bitcoin
non interact = not asking to see the backroom before playing poker
interactive= asking to see the backroom so the 2 backroom guys cannot hide

ELI-5 bitcoin: easy to be a fund manager scammer if non interactive.. (as many devs/fund manager propose to have it k-of-n for bitcoin)

(maybe i should avoid dumbing down to ELI-5 and instead do ELI-21 step-by-step as a multipage detailed explanation to avoid the laughable knitpick..... rather than the summation and simplification based on what devs and 'fund managers' are hoping will be in bitcoin)

emphasis: i read the paper. then thought about bitcoin. i did not limit my summary to the 'traditional meaning' but the bitcoin possibility
so dont limit your rebuttles to the 'traditional meaning'(that skirting of the issue doesnt fly with me) but to the realistic pitfalls of possibilities of a bitcoin version
afterall this is a bitcoin forum

in short
non-interactive
k-of-n: backroom fund manager scammer risk
n-of-n: whole fund locked risk if one party offline/loses key/PC crashes  

[achow101]

oh look MUsig for bitcoin can be K-of-n

No, it can't. MuSig itself cannot be k-of-n, but it can be used in applications that are k-of-n. Additional work must be done to make that happen, and it can and will be done where the participants in the multisig know who the others are and have proof that there are actually n people in the multisig, not some other number.

-snip-

Again, you don't seem to understand what interactive and non-interactive means. It has nothing to do with "seeing the backroom players". All that interactive means is that the people in the multisig prove that they didn't make up some bullshit public key. Yes, they will see everyone involved. But you can still do that with a non-interactive scheme. Work is still being done on this topic to create a secure k-of-n scheme which avoids rogue key attacks (which is the class of attacks you are describing).

You seem to think that we don't know that k-of-n needs more work to make it secure. You seem to think that we don't know that the participants want proof of the other participants. Well, here's the thing, we're not stupid. All of the stuff that you thought of are things that we already thought of and are working on ways of solving. It's not like MuSig is immediately ready to be used for all Bitcoin multisig transactions and that was never claimed to be the case.

If you read the paper, you'll notice in the section on Applications to Bitcoin, k-of-n is briefly discussed. In it, various schemes are briefly proposed that would avoid rogue key attacks but still allow for non-interaction and secure-ness. Things like just not doing key aggregation at all for an actual multisig or using merkle trees to prove the existence of keys.


I'm done with arguing with someone who refuses to even understand the technology he is arguing about. Back to my ignore list you go.