Episode 75: Multisig (And Musig)

Aaron van Wirdum Live from Utrecht this is Bitcoin

Sjors Provoost Explained.

Aaron van Wirdum Hey Sjors.

Sjors Provoost Hello.

Aaron van Wirdum we're back and today we're gonna talk about multisig and cool MuSig.

Sjors Provoost Music?

Aaron van Wirdum That pun is too easy even for our show Sjors. Okay, but first of all you want we gave you your special part of the show I'll give you the…

Sjors Provoost Are you going to do the song again?

Aaron van Wirdum Of course. Sjors stacks sats. Sjors stacks sats. Sjors stacks sats.

Sjors Provoost And of course our editor will run it through the auto tune so that it sounds cool. Yeah. So we've got one from Slim Shady. And he sends us 101 sats for the tune. And another one.

Aaron van Wirdum I'm not even getting the money.

Sjors Provoost You're not. And from Vake, 6,000 sats. Learning a lot from each episode. So.

Aaron van Wirdum That's good. Glad to hear that. And congratulations on the money. Ready for the rest of the episode?

Sjors Provoost yes

Aaron van Wirdum okay so we're going to discuss multisig which is of course a topic, we've mentioned probably many times by now but we've never done a full episode on multisig so that's what we're doing today. and we're going to discuss sort of how multisig has evolved over the years so the different ways of doing multisig all of which are still possible I guess right? we don't you know we don't remove options from Bitcoin, so every option that we're going to discuss is actually available today.

Sjors Provoost Well, some of them are not, but we'll get to those.

Aaron van Wirdum I guess at the very end we're going to discuss some future potential ways to do multisig. Is that what you're referring to or not?

Sjors Provoost No, I was referring to some early bugs.

Aaron van Wirdum Oh, okay. I guess I'll hear about that in a minute then, as well you are the listener.

Sjors Provoost Yeah, and we're also not going to talk about the combination of multisig and timelocks and all these kind of things you can do. We're going to talk about pretty much the opcode of multisig and its successor in Taproot.

Aaron van Wirdum yeah there are some tie-ins with our previous episode that's also where we got the idea to do this episode because in our previous episode on P2SH we kind of touched on some of this stuff I don't think the previous episode is required listening for this episode but it might help Right, Sjors?

Sjors Provoost Yeah, it's not.

Aaron van Wirdum Yeah, okay, so first of all let's let's start at the beginning as always, in, very general terms what is multisig? Do you even want to...

Sjors Provoost Yeah, the idea is that you can create a transaction that can be signed using not just one key, but either multiple keys or one out of keys. So you might say, okay, there's three possible keys that I can sign with, three of my different hardware wallet devices, and I only need to provide two of them or one of them. Or three of them that's what multisig does.

Aaron van Wirdum Yeah, I think in technical terms usually you're the one using the technical terms and then I try to dumb it down but in technical terms it's M of M or M of N am I saying that's right?

Sjors Provoost Yeah, M of N.

Aaron van Wirdum Or N of N right? that's also so N of N would be I mean M of N means that…

Sjors Provoost N of M. N of N means that M is equal to N. But yes we then you call it N of N.

Aaron van Wirdum Anyways, it means you can have a number of potential keys to sign with, and then another equal or smaller number of these keys.

Sjors Provoost We're making this more confusing. Yes, and the cryptographers who try to explain this stuff like to write things down, so they don't care that the word M is pronounced almost the same as N.

Aaron van Wirdum Right. Okay, well, I think everyone knows what multisig is anyways, so we don't have to really get into that. Well, okay, one more thing. Why would people want to use this? Do you want to give some examples of that?

Sjors Provoost Yeah, I mean, the initial use case was a thought of use case was escrow. So the idea would be that you would send money to a third party, but then there would be an escrow agent in the middle who would hold the money for you. And the idea is that this escrow person or company would have one key and you, the sender, has one key and me, the recipient, has another key. And then you need two out of three. So I send it to the escrow. And then if we both agree, we both sign and it goes away from the escrow. The escrow agent is not necessary. If we disagree, then the escrow agent will either, you know, will provide a signature either to send it back or to send it forward.

Aaron van Wirdum Yeah, or another way to use this is something we've discussed in a previous episode about... smart contracts maybe I think where we could we can sort of construct proto smart contracts using this where we for example bet on I think the example we used was the winner of the world cup and then we have a neutral party and we all the three of us have a key you and I bet.

Sjors Provoost yeah that was in the episode about discreet log contracts so you can do fairly… you can do Lightning obviously that also uses multisig so but the initial use case I think was escrow Because that's sort of what people were talking about in the comments on GitHub. and even in the source code it was kind of referring to escrow but obviously you can do more with it.

Aaron van Wirdum yeah well another very basic example is for example you split your own funds across multiple keys right so you sent your own funds you you store you save your money your Bitcoin in a multisig address of your own and you for example have three keys and you keep these three keys on three different machines could be three hardware wallets for example and you store these hardware wallets in different locations that way a hacker would have to steal two of your three hardware wallets in order to even have a chance to get your funds. yeah for example that that's another or another example would be I'll after this example we'll move on but another other example would be three people want to or two or whatever number of course they want to just store funds collectively and only if some subset of them agree to spend the funds they can do it so for example a board of a company that consists of you know three board members and they agree that two of them will have to sign off to spend money then they can set up a two of three multisig address so that would be another example and there's plenty of other examples but we won't bore you anymore with that we'll get to the meat of the episode So it's yours, multisig. Multisig has been in Bitcoin since the very beginning, I think, right?

Sjors Provoost Yeah. I thought you were going to make a pun about raw meat.

Aaron van Wirdum Feel free to make it. What's the pun?

Sjors Provoost Well, the original version is called raw multisig. Or actually, it's called bare multisig.

Aaron van Wirdum There's some potential for a pun then.

Sjors Provoost I think I wrote it down incorrectly.

Aaron van Wirdum You're right. Let's get to the raw meat, raw multisig of the episode. It's yours. So it's been in Bitcoin since the very beginning. Satoshi implemented multisig.

Sjors Provoost Yeah. So from the beginning, it was an op code. So that's one of the commands that you can put in a script. And it was just called OP_MULTISIG. And it's just there, OP_CHECKMULTISIG. And this was, well, the idea was that this you would put as the recipient, you would provide the script saying OP_MULTISIG. And then you would also provide two or three or whatever keys. And you would specify the threshold. So you would say two and then you would list three keys. That would mean you need two out of three signatures to satisfy the script.

Aaron van Wirdum Right.

Sjors Provoost And there was no address format for this to be able to communicate this. So we talked about that with P2SH because you, the sender, will have to put that script on the blockchain. So that means if you wanted to do a 20 out of 20 multisig, the sender would have to make a very long transaction and pay the fees for your complicated setup.

Aaron van Wirdum Yeah, that was one of the problems, right? So I'm the one… I want to receive the coins in a specific way but now you Sjors, who are sending the money to me you have to pay for that rather than me having to pay for that was one of the exact problems with the original multisig.

Sjors Provoost yeah so and and that and the fact that there's no standard address format for it, although that of course that could be invented Now, the more interesting part is that originally this had no limit. So you could, at least from a consensus point of view, I don't know about standardness. So standardness is what nodes will relay to each other and what miners will mine by default. But consensus means that even if it's in a block, you're going to check by less strict rules. And there was no limit on the size of a multisig, as far as I know, in the consensus rules. And this is a problem because verifying signatures...

Aaron van Wirdum So hang on, you could make a... 6,382 out of 18,723 multisig?

Sjors Provoost As far as I know, yes. There may have been a limit on the size of the transaction itself, but that's it, yeah.

Aaron van Wirdum That's pretty good.

Sjors Provoost So that was pretty cool.

Aaron van Wirdum What's the problem? This sounds great.

Sjors Provoost Yeah, the problem is the way the script is evaluated, the way the blockchain basically checks the validity of the script. And roughly this works as follows. You take the pile of public keys. And then the person who spends it will have to provide one or a whole pile of signatures. Now they have to be in the correct sequence. So it's not a random order that would have been even worse, but they have to be in the right sequence, but there could be gaps, right? So in the simple example of one out of three, I'm providing one signature and there are three public keys. Now, what the script does is it will look at the signature and... It will look at the first key. It will see if the signature is correct for that first key. If not, it will look at the second key. It will check if the signature is correct for the second key. And if not, it will try the third key. And if you have two out of three, it's a little bit more efficient. So it will look at the first. If you have two signatures out of three, it will look at the first signature using the algorithm I just described. And then if it finds a match, it tosses that signature and that public key. And then it moves on to the next one. So they do have to be in the correct order because otherwise it won't find it. But it's still pretty slow because if you have a one out of a million multisig, then you're going to try a million public keys before you find it.

Aaron van Wirdum Well, only if it's the very last one, right? You might get lucky. It might be the first one.

Sjors Provoost Yeah, but if you're trying to attack Bitcoin, you make sure that Bitcoin does not get lucky.

Aaron van Wirdum Right. And if it's the 6,852 out of 18,731, I guess the math gets very complicated. But the bottom line is it will take your computer a long time to verify this.

Sjors Provoost Yeah.

Aaron van Wirdum It will just take a long time because it has to check for every key that's in there. Whether the signature matches and then go on to the next one one.

Sjors Provoost Yeah, so there's a little bit of acceleration in there that it doesn't like you can't you can't I think you cannot provide them in any order that would be really Bad. yeah but still but it's still pretty bad yeah so it was bad enough that Satoshi decided very quickly in 2010 to in september 2010, to add a limit to say you can only have 20 as in 20 pub keys.

Aaron van Wirdum okay so it can be a one out of 20 or 20 out of 20 according to that.

Sjors Provoost Yes.

Aaron van Wirdum I guess that was a soft fork then?

Sjors Provoost Yes, it was that was one of the first soft forks

Aaron van Wirdum and it was a so that was a consensus rule implemented by Satoshi in Bitcoin to limit the size of multisig

Sjors Provoost Yeah, he did okay really two things but this was in version 0.3.13 for those who want to look it up.

Aaron van Wirdum When was this did you mention this?

Sjors Provoost September 2010. So it was released in October 2020. so around the time of the one megabyte limit too right? And this was introduced in his usual style so the commit so the change that was made which is called something like clean up various stuff and in it would be that critical change because if people saw what the change was they would try and attack Bitcoin using it

Aaron van Wirdum Right. You say that's his usual way. That was Satoshi's usual way of implementing, of changing the Bitcoin protocol, essentially.

Sjors Provoost He would basically say, well, from this block height, here are the new rules, and that would be in the code. But if you didn't check the code, you wouldn't know that the new rules came out there because he wouldn't announce it, or he might later announce it, or other people would figure it out later.

Aaron van Wirdum Right. So he probably did this because he figured out that the unlimited multisig thing was a problem for the reason you just mentioned.

Sjors Provoost Yep.

Aaron van Wirdum But he never actually explained that. He just... hit it in the code somewhere.

Sjors Provoost He may have. I didn't check if he did, but he usually didn't.

Aaron van Wirdum Right.

Sjors Provoost Or he sometimes didn't. So the other limit he also introduced is a per block limit. And the idea there would be that there's a limited number of these multisigs that you can have in a given block. This is called the ops limit. And that's still there, although it's changed a bit.

Aaron van Wirdum Wait, so what's the limit, first of all, I guess?

Sjors Provoost The limit was, at the time, you could have 1,000... multisig transactions in a single block, no matter how big they were. Because initially, you would get 20 points, essentially, for each multisig transaction in a block. And the limit was 20,000 for the whole block. So if you had 1,000 multisig transactions, no matter how small they were, that was the max you were allowed to put in a block. And regular transactions counted as a score of 1. So a single-sig transaction would give you 1 point. So you could have 20,000 single-sig transactions in a block. or a thousand multisig transactions or some combination

Aaron van Wirdum so what happens if there's a thousand multisig transactions in waiting in the mempool say and now you want to send me a multisig transaction you're just out of luck

Sjors Provoost No, the mempool can have as many as you want

Aaron van Wirdum Yeah, but it's not going to be included in the block.

Sjors Provoost no it'll go into the next block So miners have to be careful when they create a block that they don't violate this rule, but as long as you do that correctly.

Aaron van Wirdum So maybe this is getting into weeds, but would this work based on fee markets as well?

Sjors Provoost No, this is one of the...

Aaron van Wirdum Like which transaction gets priority, I mean, if there's 1,001.

Sjors Provoost Well, so a rational miner would have to do some complicated math to figure out whether he'd want the multisigs in there or not. So at the time, there was no fee market, so that helped. And also, if you looked at the original mining code, so the standard mining code as it existed at the time was very conservative. I think it would only put in maybe 20 of them. like some some really small number oh because there were almost no multisig transactions anyway right of course any miner could do it differently but he was pretty much the only miner probably

Aaron van Wirdum so yeah just to be clear because we're talking about this kind of in the past tense but does this limit still exist in Bitcoin I know we do other ways of doing multisig now, but does this technical limit still exist?

Sjors Provoost Yes, but we'll get to that in P2SH. The limit is slightly more intelligent.

Aaron van Wirdum Okay.

Sjors Provoost But for this bare multisig, so multisig without P2SH, and for P2SH multisig, this limit exists.

Aaron van Wirdum Today?

Sjors Provoost Yes, but not for Taproot.

Aaron van Wirdum Right. Interesting. I don't think I knew that.

Sjors Provoost Yeah. So I don't know how that plays into the fee market. If there's too many multisig transactions. candidates yeah I guess then as a miner you'd have to do the math what what makes more sense to include the transaction with the higher fee but it has a multisig are you going to kick out some some other transaction or are you going to say well I'd rather have the single-sick transactions than the multisig transactions because you know how the fees work out because you get a limit

Aaron van Wirdum okay so we're going to talk about other ways of doing multisig but my curiosity is triggered now so spoiler alert we're also going to talk about P2SH multisig SegWit multisig Taproot multisig and MuSig Which of these types of multisig are relevant in context of this limit? Is it only bare multisig or other?

Sjors Provoost All of them except Taproot.

Aaron van Wirdum Really? So SegWit multisig is also affected by this limit?

Sjors Provoost Yes.

Aaron van Wirdum From 2010.

Sjors Provoost That's one of the reasons for the change in Taproot, because this limit is annoying for all sorts of reasons.

Aaron van Wirdum Okay, I guess we'll get there. We're skipping ahead now, but this will...

Sjors Provoost So there's also the standardness rules, right? So as far as I can tell, when he introduced this limit, the standardness rule was two out of two. So you could have a one out of two or two out of two multisig. And then several years later, or actually one year later in December 2011, I think Gavin Andresen raised the limit to three. So you could have a two out of three or a three out of three.

Aaron van Wirdum Right.

Sjors Provoost And we know that because that limit led to the OP_RETURN wars that we did another episode on.

Aaron van Wirdum Yeah. Okay. So the limit was brought back. The consensus rule was made 20 by Satoshi in 2010. And then the standardness rule was made two.

Sjors Provoost Yeah.

Aaron van Wirdum Okay. And three later by Gavin Andresen. Okay. So that's raw multisig, right?

Sjors Provoost Yeah.

Aaron van Wirdum We've now explained what raw multisig is.

Sjors Provoost Yes. Or bare multisig, I think is the correct term, but it doesn't really matter.

Aaron van Wirdum Okay. Then, and this is what we discussed last week as well. Regardless, we'll go over it. Then the next type of multisig in Bitcoin was pay-to-script hash, P2SH, multisig. So how did it evolve from bare multisig?

Sjors Provoost Yeah, so the difference is, again, the recipient now pays for the fees because the recipient provides a hash of the script. And inside that script can be some sort of multisig construction. But the sender doesn't have to care. The hash of the script is always the same size. So when you pay a detection fee for the outputs, that's always going to be the same. It also makes addresses easy. Well, that's what we explained in the last episode. It also gives you a little bit better privacy because you can't see what the script is until you try to spend it. Now, there is a new limit. which is 15 at the consensus level. I didn't check what the standardness was. Maybe the standardness was also 15.

Aaron van Wirdum Wait, so the limit was decreased?

Sjors Provoost Well, the consensus limit was decreased from 20 to 15, and the standardness limit, I think, was increased either immediately or later on to 15.

Aaron van Wirdum Right, so the consensus limit and the standardness limit were made the same at that point.

Sjors Provoost Yeah, and the consensus limit is accidental because there is a limit of 20 that's still there. but you never reach that limit because the script can only be 512 bytes in P2SH. And if you divide 512 bytes by the number of bytes that one public key requires, you end up with 15.

Aaron van Wirdum Okay, this is getting complicated, but I do think I'm following you.

Sjors Provoost Yeah, basically it means you cannot spend a multisig with more than 15 keys in it.

Aaron van Wirdum Yeah, but not because that's a specific rule concerning multisig, but a more general rule concerning script.

Sjors Provoost Yes.

Aaron van Wirdum And that just happens to, the math just happens to end up at 15 in that case.

Sjors Provoost Yeah, because in order to spend a multisig transaction, you, the recipient, have to specify which keys are involved. All of them, not just the ones you're using. And so that's 15.

Aaron van Wirdum So if… Because at first it's sent to a hash, right? So then the script… Yeah.

Sjors Provoost and then you reveal the actual script. So the script contains all the public keys.

Aaron van Wirdum So if there's a 16 out of 16 multisig, let's say, it just means it can't be spent?

Sjors Provoost Yep, you can't reveal it. If you try to reveal the script, it's invalid because it's too long.

Aaron van Wirdum Wasn't this an incompatibility, like a backwards? compatibility issue at the time?

Sjors Provoost yeah the limit of 512 is a backwards compatibility issue because the I think the size of stuff that can be on the stack so the size of each element on the stack is 512 bytes and the old nodes what they would see if you're using P2SH they would see something on the stack and they would hash it so that something on the stack has to be 512 bytes now the new nodes don't interpret it that way anymore but you have to be backwards compatible hence the 512 limit yeah so if you want to lose your coins that's one way to do it.

Aaron van Wirdum right okay anything else we discussed this last week so we probably don't want to get into too much in rehashing mode but what else is new with P2SH is there anything else we need to know about that?

Sjors Provoost yeah so one other thing is that like we said this sigops limit that we talked about It used to be that you just get 20 points for any multisig, no matter how big it was. So that's kind of annoying because if you're making a small multisig, you're not paying, but you're using up a limit in the block that's quite high. And now it was changed to the actual number of public keys. So if you do a two out of three multisig, you get three sigops.

Aaron van Wirdum Right. Again, this sounds to me...

Sjors Provoost Or two. I forgot if the limit is the number of public keys or the number of signatures.

Aaron van Wirdum I'm just wondering out loud here, but when this was changed at the time, again, wouldn't that lead to backwards incompatibility issues where different nodes are making different calculations?

Sjors Provoost No, because this new limit, this new way of counting only applies to the P2SH scripts. So the multisig that you were using bare script for... they would still count as 20 but if you were using P2SH it's it's essentially a discount for P2SH not so much a discount in fees but a discount in how many of these things you can put in a single block again it didn't matter in practice, because blocks were not anywhere near full.

Aaron van Wirdum yeah no I I get that I think that that makes sense okay so

Sjors Provoost But other than that, this worked exactly the same. So as soon as you've unwrapped the P2SH thing, you have an OP_CHECKMULTISIG and it works exactly the same way as it used in the old consensus code. It is the same code that is checking it, the same lines of code that are checking it.

Aaron van Wirdum Yeah, the same opcode.

Sjors Provoost Yeah, it's the same piece of C++ code that is just used in both situations.

Aaron van Wirdum Right. Okay, so that was bare multisig and that was... P2SH as well now we move to SegWit so SegWit also changed things about how multisig works

Sjors Provoost yeah well one thing that SegWit changes is SegWit also had a its own P2SH essentially wrapped P2SH or pay to SegWit script hash and this hash could be the script could be as big as you want I think there's no limit or at least the limit is large enough for this purpose, which means now the limit is actually 20. So the original limit of 20 that's in the consensus code is now actually relevant for SegWit. So it wasn't that SegWit decided to make it 20. It's just that they removed the 512 limit on the script size.

Aaron van Wirdum Right. Yeah, that's what we just... discussed so there wasn't an actual explicit limit on multisig but there was a practical limit because there was a more general script limit and this more general script limit was removed in the case of SegWit, and therefore we went back to the original Satoshi imposed multisig limit consensus limit is that right

Sjors Provoost the super sneaky soft fork that he introduced Yep.

Aaron van Wirdum Okay, right. So then because of SegWit, we went back to 20.

Sjors Provoost Yes, and also the limit per block, so that we talked about the sigops limit per block. SegWit also multiplied that by four. So if you wanted to use multisig and you did it inside of SegWit, it would be cheaper. You would be able to put more of them in a block.

Aaron van Wirdum okay where now now I'm getting lost again so where is this limit? does this question even make sense?

Sjors Provoost yeah the sigops limit is per block so there is a counter that says the number of sigops and every time it sees a normal signature it says okay one sees another normal signature

Aaron van Wirdum but it's all in the witness right?

Sjors Provoost It doesn't matter where the signature is. But this counter is different for where it is. So before SegWit, there was one counter, and if it saw a single sig, it would give you one point. If it saw a multisig, it would give you n points, depending on what n was. Except if it was a raw multisig, then it would give you 20 points. Now the new rule is that all of these examples from before would get four points. So that was multiplied by four. But if it was in SegWit, it would only get one point.

Aaron van Wirdum Yeah, that's the weight limit, essentially, what we're talking about, right?

Sjors Provoost It's the same trick as with the weight limit, but it's not the same thing. It's a different counter, but it gets the same discount as everything else at SegWit.

Aaron van Wirdum I see. Okay. So once again, we're talking about a specific limit on...

Sjors Provoost Well, not SegWit.

Aaron van Wirdum There's a point system.

Sjors Provoost Yeah. The point system was...

Aaron van Wirdum The thing is, we're not talking about the block size limit itself. We're talking about another type of limit for the types of transactions that can be put in blocks and that different transactions can score different points.

Sjors Provoost Yeah. And for some reason, that was also multiplied by four. I don't know what the reason is because as far as I know, the problems with this inefficient evaluation is still there.

Aaron van Wirdum Yeah. Well, my mind is going to... why wouldn't that be backwards incompatible? But I guess the reason is because it is in the witness, so you can just do whatever at that point. It doesn't have to be backwards compatible because all the nodes don't see the witness, right?

Sjors Provoost Exactly, yeah.

Aaron van Wirdum Okay.

Sjors Provoost All the nodes are only looking at all the transactions, and because that score is multiplied by four, it is effectively the same thing.

Aaron van Wirdum Well, they're also looking at new transactions, just not the witness part.

Sjors Provoost Yeah, so they're seeing all these new transactions and they don't see the script of those new transactions. They just ignore them.

Aaron van Wirdum Yeah.

Sjors Provoost So they don't count the number of signatures in it.

Aaron van Wirdum Right. Okay. So there was still a limit when SegWit was imposed, which was four times what used to be the limit. Wait. So the number of…

Sjors Provoost Basically, the number of signatures per block was increased by four. And I guess that makes sense.

Aaron van Wirdum And to remind me and our listeners maybe, if they have the same type of memory as I do, what was the original limit?

Sjors Provoost 20,000, and so it became 80,000.

Aaron van Wirdum Oh, yeah, but that was 1,000, right? Because it was 20 points per...

Sjors Provoost Well, only if you had these 20 out of 20 [unclear]. So in practice, the limit before SegWit was about 1,000 multisig transactions per block if they were using the full size. A bit more because the full size was 16.

Aaron van Wirdum Right.

Sjors Provoost And with SegWit, SegWit, you could do more. Basically four times as many.

Aaron van Wirdum Okay, sure. Is there a nice...

Sjors Provoost But I'm not aware of a single block that was produced that was violating that limit. And I don't know if that's because miners are brilliant or just because there's not that many multisig transactions and nobody hit the limit or because the miners use Bitcoin Core and Bitcoin Core makes sure you don't make that mistake.

Aaron van Wirdum Real quick, if people want to look up what all these limits are, especially the current limits, I guess, is there a nice website for this or something? Where are you finding this?

Sjors Provoost The Bitcoin Core source code.

Aaron van Wirdum Oh, God.

Sjors Provoost Mostly.

Aaron van Wirdum Well, I guess, like you said, wallets are taking care of it.

Sjors Provoost Sometimes.

Aaron van Wirdum Hopefully.

Sjors Provoost Okay.

Aaron van Wirdum Okay. So that's SegWit. I think we've discussed how SegWit changed Multisig from P2SH, right?

Sjors Provoost Yeah, it's a very small change.

Aaron van Wirdum Okay. Then there was another update to how Multisig works when Taproot was introduced, right?

Sjors Provoost Yes.

Aaron van Wirdum Okay. So what changed with Taproot?

Sjors Provoost Well, Taproot got rid of the multisig opcode, the specific opcode. Because of this weirdness that you just throw a bucket of signatures and public keys and you don't tell which public key corresponds to which signature. That weirdness is all gone.

Aaron van Wirdum So basically the reason that we even have limits on this kind of stuff.

Sjors Provoost Yeah, and it was replaced with something a little simpler called OP_CHECKSIGADD. And what OP_CHECKSIGADD does... is it basically checks the signature and then it adds the number one to the stack. And so it's essentially a counter. So what you do is you say, okay, you call this OP_CHECKSIGADD 10 times. And so if that gives you 10 valid signatures, then the number on the counter is going to be 10. And then at the end of the script, you say, okay, is the number more than five? And then you've created a five out of 10 multisig. So you don't create one line that says this is a multisig. You just... It implicitly is a multisig by using this opcode in an intelligent way.

Aaron van Wirdum Okay. What does that mean? Why is this better?

Sjors Provoost Well, it's better because when you call this OP_CHECKSIGADD, as the spender, when you're spending it, you don't just give it a pile of signatures. You actually have to specifically say for each public key which signature you're giving. And the way you do that is by if you don't have a specific public key, because let's say you have only one out of the three keys, then when you don't see your key, you just give it an empty signature. And then when you do see your key, you give it a real signature. And this makes the evaluation of the script a lot easier because now the rule is every signature is either valid or it's empty. And this also means in the future we can aggregate signatures. So we can basically evaluate the script and just say, okay, every time we see OP_CHECKSIGADD with a signature, we just kind of assume that it's correct. And then at the end of the block, we take all the public keys and all the signatures and evaluate them in one go with this key aggregation tricks, which would make block evaluation faster.

Aaron van Wirdum Let me try to make this very sort of practical. See if this is kind of a translation of what you just said. So if I have a 12 out of 15 multisig and I'm spending it and there at this point there's 15 pub keys and I'm saying these are signatures numbers one two three six eight etc

Sjors Provoost yeah, exactly.

Aaron van Wirdum And that's and so now you know exactly the rest of the network all nodes know exactly where to look and check it.

Sjors Provoost yeah whereas in the original one you would just give 12 signatures and the network would have to figure out which signature belongs to which key.

Aaron van Wirdum yeah okay that makes sense that sounds like a sort of very obvious improvement that makes me wonder why wasn't this already the case was it just originally kind of sloppy implementation by Satoshi? or well I think how should we think about this?

Sjors Provoost I'm not entirely sure, but one of the things is that because Taproot also introduced Schnorr, and these signatures are Schnorr, they're not ECDSA, if I remember correctly, they are easier to aggregate in general. So... This new way of doing it in the future can take advantage of Schnorr. So there was not as good a reason to do this earlier because things like aggregating keys was not really a practical thing with ECDSA.

Aaron van Wirdum I didn't realize we're not talking about aggregating keys.

Sjors Provoost No, but it basically means in the future we could without a soft fork even… because what you can do is you can take a block and now we evaluate the script and while we evaluate the script, we have to evaluate every signature. We have to check every individual signature. which is very slow. But in the future, what you could do is you could say, well, we're going to evaluate all the scripts. We're going to pretend that they're okay. And then at the end of the block, we're going to evaluate all the signatures in the block or at least all the Taproot signatures in the block in one operation. And this would be faster than doing it as individual operations. So by enforcing this structure, now we are making it easier later to make the valuation faster.

Aaron van Wirdum Okay, so that sounds to me like that's a good reason to do it this way. But even without that, it's still better to do it this way, right?

Sjors Provoost Probably, yes. Yeah, I mean, yeah, very probably.

Aaron van Wirdum Is there a downside? It just sounds like this is less work.

Sjors Provoost Yeah, well, the downside is it's more... I guess a bit more tedious to write the script, but I don't know if that really matters.

Aaron van Wirdum Okay.

Sjors Provoost The script might be bigger.

Aaron van Wirdum Right.

Sjors Provoost But I guess there's no limit anyway to the script size, so... Yeah, no, so this is better, yeah. But it may have not been worth the risk of making a consensus mistake if the advantages are not big enough. And nobody really needs those really big multisig things. It's just that this happens to make it possible to make a 999 multisig.

Aaron van Wirdum Which is now literally possible.

Sjors Provoost Yeah, so Mr. Burak did a demonstration. He made a 998 out of 999 multisig.

Aaron van Wirdum Yeah.

Sjors Provoost But as far as I know, he could have done a 1999 out of 1999 multisig too. I'm not entirely sure.

Aaron van Wirdum That's the transaction that crashed the btcd nodes, which we also made an episode about.

Sjors Provoost Yes, two episodes even, because we talked about it in the second episode after that, about the second attack.

Aaron van Wirdum Okay, but just hold on, because I don't think we've mentioned this explicitly. So with Taproot, the limit was removed entirely. Is that right?

Sjors Provoost Yes. So OP_CHECKSIGADD has no limit itself.

Aaron van Wirdum This is the new multisig opcode.

Sjors Provoost Yes. It intrinsically has no limit because all it does is it checks one signature and it adds a number to another number. So it has no idea how many signatures there are. So in that sense, there [unclear] be a limit.

Aaron van Wirdum Okay.

Sjors Provoost And there's also no more sigops. So this block counter that we talked about, the sigops counter, doesn't apply to Taproot. It still applies for SegWit and the old stuff, but it doesn't apply to Taproot.

Aaron van Wirdum Okay.

Sjors Provoost So this complexity that we just talked about is gone.

Aaron van Wirdum So basically what you're saying is... That's weird. Makes me think of the Cathy Newman interview.

Sjors Provoost Yeah, exactly. So what you're saying is Bitcoin is not really signatures, is it?

Aaron van Wirdum Okay, so basically what you're saying is Taproot completely changed how multisig works at all, right?

Sjors Provoost Yes.

Aaron van Wirdum It's a new opcode. There's no limits. All the old limits are gone. And we can even...

Sjors Provoost Well, not all the old limits are gone. There's still a block size limit. But there's another limit.

Aaron van Wirdum All the multisig... Oh, there's another limit?

Sjors Provoost All the limits we just talked about are gone.

Aaron van Wirdum Okay, yes.

Sjors Provoost I agree.

Aaron van Wirdum Right.

Sjors Provoost But there was another limit out there that we never ran into because our multisigs were very small because of these earlier limits. But now if you try to make the multisig bigger and bigger and bigger, you run into another limit. which is called the stack size limit. And remember, the stack is like a pile of plates, like a stack of plates. And when you want to spend a multisig, you put a signature on a plate or you put a zero on a plate for each placeholder, basically. So if you want to do a 999 multisig, one of 999 doesn't matter, you have to create a plate of 999 plates. And one of these plates or more have a signature on it and the others have zero on it. And there's a limit in the Bitcoin code that says if the stack is more than a thousand, the script is invalid.

Aaron van Wirdum So what you're saying is Bitcoin is now in the restaurant business.

Sjors Provoost Yes.

Aaron van Wirdum Got it.

Sjors Provoost And in case the listener is curious why the limit is 999 for the multisig and not 1000, it's because the stack can only be a thousand. And now you have to kind of look at what happens exactly when you're spending it under the hood. Essentially, what you're doing is when you're spending it, you put all the signatures on the stack, right? So that's 999. But then the script has to also put the pub keys on the stack. Not all of them at once, but one by one. So when the script starts, it puts one pub key on the stack. Now your stack is 1000 high. And then it goes down because once it's verified the public key and the signature, it removes both the public key and the signature from the stack. So now you're down to 999 and then the next signature you're down to 998, etc.

Aaron van Wirdum Okay, that makes sense.

Sjors Provoost But because you have to put one public key on the stack, that's why you hit the 1,000 limit.

Aaron van Wirdum That makes a lot of sense. What I do wonder, though, is why is there a limit of 1,000? You just explained why the limit is 999 for...

Sjors Provoost Because I think, as far as I know, Satoshi put in the limit of 1,000, so it's an old consensus rule.

Aaron van Wirdum Oh, so that rule also existed already.

Sjors Provoost Yep. And, of course, Taproot could have removed it, but people felt no need to remove it.

Aaron van Wirdum 1,000 should be enough for your average

Sjors Provoost type of transaction. And this is also why the ordinals have a limit because or not. I forgot.

Aaron van Wirdum Ordinals just have the block size limit as limited as far as I know. The inscriptions is what I mean.

Sjors Provoost The inscriptions, yeah, you might be right. I thought there was something about the 1,002, but maybe not.

Aaron van Wirdum No, I think they, I mean, we've seen blocks of 4 megabytes, right? That are basically just one inscription.

Sjors Provoost That's true, yeah. So anyway, this 1000 limit exists. So that's basically the naive way in Taproot to do multisig.

Aaron van Wirdum Okay, just to recap this real quick. Taproot basically just changed how multisig works in a technical way in that it uses a new opcode. It removed all the limits we've just mentioned. And the only limit, it just ran into a new limit that was also already there and that was kept of 1000, which is the stack limit. Right? So that was the Taproot version of multisig.

Sjors Provoost And keep in mind that with Taproot, you can have a tree of different scripts. So you can probably make a much bigger multisig effectively by spreading all the keys over different parts of the tree.

Aaron van Wirdum Yeah.

Sjors Provoost But then you might be ruling out certain combinations, right? So you might say, okay, there's 2,000 keys in total, and you need one of the first 1,000 keys, and you need one of the second 1,000 keys. And then both of these would be a separate tapleaf, a different leaf. So if you want to spend using one of the thousand keys, you pick one of the leaves that you have the key from. But that means you can actually make a one out of a million multisig if you want to, because you can make a thousand leaves with each with a thousand keys. And when you're spending it, you pick one of the thousand leaves and then you produce one of the thousand keys. Well, 999.

Aaron van Wirdum Yep. Yeah, and also there's another way of doing, for example, two out of three, which is you make three branches with two out of two with the different two out of the same three.

Sjors Provoost Yep. Exactly. And the advantage could be that it gives better privacy because you would not reveal any key that you're not using.

Aaron van Wirdum It might also be more compact or not because you know it's the same.

Sjors Provoost Yeah, it's also more compact.

Aaron van Wirdum Oh, it is?

Sjors Provoost Yeah, because the individual scripts that you're using only have two keys in them. So the scripts are smaller.

Aaron van Wirdum Yeah, but you only need to publish two signatures anyways, right?

Sjors Provoost Yeah, but you also need to publish the original script.

Aaron van Wirdum Right, yeah. So it is more compact then, right? Yeah. Okay, so that's another way of doing it in Taproot. Taproot opens the possibility of doing multisig in multiple ways.

Sjors Provoost Yes.

Aaron van Wirdum and potentially therefore it's even more flexible. Interesting.

Sjors Provoost And we haven't even talked about the best way to do it.

Aaron van Wirdum Let's talk about the best way to do it, Sjors. What is the best way to do multisig?

Sjors Provoost Well, the best way to do multisig, in theory, doesn't really exist yet. But it is by using the key-spend path of Taproot. So Taproot has two ways of spending. One is you provide a script, as we just described, similar to P2SH. And the other is you provide a key, a public key and its signature. Now, from the point of view of the blockchain, that is one public key and one signature. So it looks like a one of one. I guess, but under the hood, you can actually use key aggregation strategies to combine multiple public keys into one. Now you could already do this with before Taproot with signatures, but Schnorr makes it easier to do this and to make proof that it's secure. And one of the ways to do that is MuSig2 as an algorithm, which we have, well, we haven't talked about MuSig2, but we have talked about Taproot. And sort of this phenomenon that you can aggregate keys before.

Aaron van Wirdum Yes, episode two was about Taproot. Yeah. But still, let's recap it a little bit.

Sjors Provoost So TL;DR, there is a way. As far as the blockchain is concerned, it doesn't matter how you do it, what cryptographic trick you're using. As far as not losing your coins, you want to make sure that you use a cryptographic trick that is actually safe. Because from the consensus point of view, if the cryptographic trick is not safe, you could lose your coins either by theft or by making them unspendable. and MuSig2 is a paper by the Blockstream folks and there's even a BIP for it now that is basically it describes a procedure of how to make these keys and they are n of n so 2 of 2 or 3 of 3 or 4 of 4 and it describes exactly how each of the participants come together and construct the key and then how the participants come together and sign a transaction in a way that's safe

Aaron van Wirdum yeah so basically Taproot, we always call it Taproot, but I think the official name of the upgrade was Schnorr Taproot, right? Because the other big thing it did was...

Sjors Provoost Add Schnorr.

Aaron van Wirdum Add Schnorr, Schnorr, another type of signature. And the sort of very simple way of explaining how this would work is you have several... public keys and you create several which also have several private keys of course and then you create several signatures and you can essentially just mathematically add up the public keys and you get a new public key and then you can also add up the different signatures that you created with the different private keys and then the signatures also add up to a valid signature for that valid combined public key Right, that's that's exactly right. Yeah, so that's why you can, for example, have three people, all three have their own public key. But then if they all three sign off to a transaction, then their combined signatures would match their combined public keys. and therefore you can spend it. All the while on the blockchain itself, it looks like a very regular one out of one transaction.

Sjors Provoost Yeah, and there's the caveat there is that if you do it in the naive way, which is just to add up the keys, which you can do from a mathematical point of view. then it's not safe, but we can get into that some other episode or never.

Aaron van Wirdum Yeah, or maybe is there a one sentence explanation?

Sjors Provoost I mean, if you Google something like rogue key attack. So the idea is that I give you my key and then you give me your key. But if you're mean, then you could actually take my key and put a minus in front of it. And so you would use minus my key. And so if I add my key to your key, that's zero. Basically the effect of that. And that means you can steal the money. And of course you wouldn't do it that way. You would probably add another key to it so that I wouldn't be able to see it. But it basically boils down to that. If you can take the negative of my key, you can steal my money. And that's prevented with some tricks to make sure you can't do that.

Aaron van Wirdum Right. And that's a pretty decent one sentence explanation.

Sjors Provoost That's not the only way you can get fucked, but that is definitely the most.

Aaron van Wirdum Right. So MuSig, it spells M-U-S-I-G in case anyone was wondering. It's short [unclear]. That is available in Bitcoin now, right? People can do it if they want to since Schnorr is there.

Sjors Provoost I think if they have to, yeah, but they'd have to write their own wallet basically.

Aaron van Wirdum Right, so it's available. I mean, we can't even know if people are using it because it would just look like one out of one. But as far as you know, as far as I know, there's no wallet that's actually using it now.

Sjors Provoost Nope.

Aaron van Wirdum Okay, so it's conceptually possible.

Sjors Provoost I think, though, that there are Lightning implementations that are using it or are almost ready to use it because one nice use case, because the MuSig ritual, as we could call it, is a bit complicated for humans to do, but it's very easy for machines to do. So when two Lightning nodes talk to each other, they create a two out of two multisig, and they can use MuSig for that. And it's relatively straightforward for Lightning to add that. So that might already be happening or happening soon TM. Now, the downside is it's N of N. And so there are other proposals out there that will let you do M of N. So do a three or et cetera in the same way that looks like one signature. Those I think are a bit more experimental, but coming.

Aaron van Wirdum Are we still talking about MuSig or would this get a new name?

Sjors Provoost No, they would not be called. They would have a new name.

Aaron van Wirdum Okay. But it's essentially using the same Schnorr trick, right?

Sjors Provoost In the end, as far as the Bitcoin chain is concerned, it's just Schnorr. And in the future, somebody can come up with completely different ways of doing this. So that's the nice future-proof aspect of this.

Aaron van Wirdum What do you mean by completely new ways of doing this?

Sjors Provoost Well, some new algorithm. So MuSig2 has a specific way of saying, take your key, then take the next key, and do this hash on this key, and do this hash on this other key. And you can have a different way to do it, as long as the end result is a Schnorr signature.

Aaron van Wirdum Sure. Okay, yeah.

Sjors Provoost And so the other thing to mention, and then I think we've pointed out everything, is that you can combine these two things. So you can use... In the OP_CHECKSIGADD opcode, you don't have to put a single signature in there. You can also put a Schnorr threshold signature or multisig in there. So you could have a trillion out of a trillion multi… one out of trillion multisig, for example. where the way to spend it, I don't know, some sort of weird threshold signature inside a tapscript. So you'd have, you need one out of a thousand keys in order to create a regular Schnorr signature that is then part of one of the leaves that is part of a million different leaves. Or sorry, that is one. So again, one out of a thousand signatures. Keys will allow you to produce a valid Schnorr signature that will look like a one of one. You put that inside the OP_CHECKSIGADD in one of the leaves, which each have a thousand possible keys, and then there are a thousand leaves. So that is a one out of a billion multisig.

Aaron van Wirdum Could we make a multisig that's big enough for all of humanity and sort of to protect us from the Martians when they come?

Sjors Provoost Yeah, I mean this would be a one out of a billion…

Aaron van Wirdum What would be the best threshold for that, do you think?

Sjors Provoost Well, the opposite would be like a 4 billion out of 8 billion multisig.

Aaron van Wirdum So just majority, you think that's good?

Sjors Provoost And so that would definitely require something like a MuSig or probably a threshold signature because you can only have a thousand in each of the script leaves. So each of these 1,000 keys will have to represent the majority of a million people or so in order to get there. And the question is, can you make an algorithm that lets a million people combine their keys and signatures and produce a signature? I don't know if that's possible because a lot of these algorithms, they get exponentially slower. So as you add more participants, it doesn't take twice as long. If you add more participants, it might take four times as long. And so maybe if you add a million participants, it gets two to the times a million harder.

Aaron van Wirdum Yeah, but maybe not if it's a million out of a million, right? Then it just takes...

Sjors Provoost Maybe that's easier, but it's still a question of... If you look at MuSig, I don't know what the pattern there is, but my guess is that making MuSig from, say, two of two... versus making a MuSig of four of four is not twice as slow it's like four times as slow or eight times as slow so it grows exponentially or some other thing

Aaron van Wirdum Okay, so that's not…

Sjors Provoost but you'd have to ask the Blockstream cryptographers they probably can give you a chart that shows exactly what happens when you do a million of them? right? my guess is it'll get exponentially hard and it'll it'll break down but somebody might come up with a way to do a and you definitely don't want to do N of N with the whole planet, because then if one person doesn't show up which is pretty likely with a big population…

Aaron van Wirdum so that was that was my first question like what do you think would be a good threshold if we want to protect ourselves from you know we want to protect our funds from martians and with humanity like what threshold would you opt for?

Sjors Provoost I don't know because it depends on what the martians are capable of doing. if they can just read all the private keys then no threshold helps. so I don't know.

Aaron van Wirdum Well, no, the problem is more that maybe some of us will be corrupted by the Martians. So we want to be careful that we, you know, if we let anyone spend the funds, then the Martians only have to corrupt that specific person. So that's probably not good. But how many humans would you trust not to be corrupted?

Sjors Provoost It really depends on how the Martians operate. So yeah, I think we've talked enough. So unless you have anything to add or summarize?

Aaron van Wirdum No. Have we discussed anything? Yeah. You think we've had everything? then I'm good with this episode, Sjors?

Sjors Provoost Excellent. Well, then thank you for listening to Bitcoin,

Aaron van Wirdum Explained.