In this episode of Bitcoin, Explained, Aaron and Sjors discuss multi-signature (multisig), and the various ways that Bitcoin enables multisig; from bare multisig, to P2SH, SegWit, Taproot, and finally Musig, as well as some potential future solutions. Chapters 00:00:00 Introduction and listener support 00:02:41 What multisig is and why use it 00:06:43 Bare multisig and signature-checking limits 00:17:23 P2SH multisig: fees, privacy and script limits 00:22:23 SegWit multisig and the sigops discount 00:27:42 Taproot multisig with OP_CHECKSIGADD 00:33:21 Large multisigs and the stack size limit 00:38:08 Combining multisig scripts in Taproot trees 00:39:50 MuSig2, key aggregation and threshold signatures Episode Sponsor: https://voltage.cloud/ Sjors New Book: https://www.amazon.com/Bitcoin-Technical-innovations-Sjors-Provoost/dp/9090360425
Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.
Transcript
From the show. Tap a time to play from there.
Aaron van WirdumLive from Utrecht this is Bitcoin
Sjors ProvoostExplained.
Aaron van WirdumHey Sjors.
Sjors ProvoostHello.
Aaron van Wirdumwe're back and today we're gonna talk about multisig and cool MuSig.
Sjors ProvoostMusic?
Aaron van WirdumThat 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 ProvoostAnd 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 WirdumI'm not even getting the money.
Sjors ProvoostYou're not. And from Vake, 6,000 sats. Learning a lot from each episode. So.
Aaron van WirdumThat's good. Glad to hear that. And congratulations on the money. Ready for the rest of the episode?
Sjors Provoostyes
Aaron van Wirdumokay 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 ProvoostWell, some of them are not, but we'll get to those.
Aaron van WirdumI 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 ProvoostNo, I was referring to some early bugs.
Aaron van WirdumOh, okay. I guess I'll hear about that in a minute then, as well you are the listener.
Sjors ProvoostYeah, 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 Wirdumyeah 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 ProvoostYeah, it's not.
Aaron van WirdumYeah, 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 ProvoostYeah, 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 WirdumYeah, 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 ProvoostYeah, M of N.
Aaron van WirdumOr N of N right? that's also so N of N would be I mean M of N means that…
Sjors ProvoostN of M. N of N means that M is equal to N. But yes we then you call it N of N.
Aaron van WirdumAnyways, it means you can have a number of potential keys to sign with, and then another equal or smaller number of these keys.
Sjors ProvoostWe'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 WirdumRight. 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 ProvoostYeah, 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,
Sjors Provoostthen the escrow agent will either, you know, will provide a signature either to send it back or to send it forward.
Aaron van WirdumYeah, 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 Provoostyeah 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 Wirdumyeah 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
Aaron van Wirdumexample 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
Aaron van Wirdumother 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 ProvoostYeah. I thought you were going to make a pun about raw meat.
Aaron van WirdumFeel free to make it. What's the pun?
Sjors ProvoostWell, the original version is called raw multisig. Or actually, it's called bare multisig.
Aaron van WirdumThere's some potential for a pun then.
Sjors ProvoostI think I wrote it down incorrectly.
Aaron van WirdumYou'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 ProvoostYeah. 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 WirdumRight.
Sjors ProvoostAnd 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 WirdumYeah, 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 Provoostyeah 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 WirdumSo hang on, you could make a... 6,382 out of 18,723 multisig?
Sjors ProvoostAs 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 WirdumThat's pretty good.
Sjors ProvoostSo that was pretty cool.
Aaron van WirdumWhat's the problem? This sounds great.
Sjors ProvoostYeah, 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
Sjors Provoostsignature 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
Sjors Provoostfind 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 WirdumWell, only if it's the very last one, right? You might get lucky. It might be the first one.
Sjors ProvoostYeah, but if you're trying to attack Bitcoin, you make sure that Bitcoin does not get lucky.
Aaron van WirdumRight. 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 ProvoostYeah.
Aaron van WirdumIt 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 ProvoostYeah, 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 Wirdumokay so it can be a one out of 20 or 20 out of 20 according to that.
Sjors ProvoostYes.
Aaron van WirdumI guess that was a soft fork then?
Sjors ProvoostYes, it was that was one of the first soft forks
Aaron van Wirdumand it was a so that was a consensus rule implemented by Satoshi in Bitcoin to limit the size of multisig
Sjors ProvoostYeah, he did okay really two things but this was in version 0.3.13 for those who want to look it up.
Aaron van WirdumWhen was this did you mention this?
Sjors ProvoostSeptember 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 WirdumRight. You say that's his usual way. That was Satoshi's usual way of implementing, of changing the Bitcoin protocol, essentially.
Sjors ProvoostHe 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 WirdumRight. So he probably did this because he figured out that the unlimited multisig thing was a problem for the reason you just mentioned.
Sjors ProvoostYep.
Aaron van WirdumBut he never actually explained that. He just... hit it in the code somewhere.
Sjors ProvoostHe may have. I didn't check if he did, but he usually didn't.
Aaron van WirdumRight.
Sjors ProvoostOr 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 WirdumWait, so what's the limit, first of all, I guess?
Sjors ProvoostThe 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
Sjors Provoostblock. or a thousand multisig transactions or some combination
Aaron van Wirdumso 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 ProvoostNo, the mempool can have as many as you want
Aaron van WirdumYeah, but it's not going to be included in the block.
Sjors Provoostno 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 WirdumSo maybe this is getting into weeds, but would this work based on fee markets as well?
Sjors ProvoostNo, this is one of the...
Aaron van WirdumLike which transaction gets priority, I mean, if there's 1,001.
Sjors ProvoostWell, 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
Sjors Provoostpretty much the only miner probably
Aaron van Wirdumso 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 ProvoostYes, but we'll get to that in P2SH. The limit is slightly more intelligent.
Aaron van WirdumOkay.
Sjors ProvoostBut for this bare multisig, so multisig without P2SH, and for P2SH multisig, this limit exists.
Aaron van WirdumToday?
Sjors ProvoostYes, but not for Taproot.
Aaron van WirdumRight. Interesting. I don't think I knew that.
Sjors ProvoostYeah. 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 Wirdumokay 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 ProvoostAll of them except Taproot.
Aaron van WirdumReally? So SegWit multisig is also affected by this limit?
Sjors ProvoostYes.
Aaron van WirdumFrom 2010.
Sjors ProvoostThat's one of the reasons for the change in Taproot, because this limit is annoying for all sorts of reasons.
Aaron van WirdumOkay, I guess we'll get there. We're skipping ahead now, but this will...
Sjors ProvoostSo 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 WirdumRight.
Sjors ProvoostAnd we know that because that limit led to the OP_RETURN wars that we did another episode on.
Aaron van WirdumYeah. 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 ProvoostYeah.
Aaron van WirdumOkay. And three later by Gavin Andresen. Okay. So that's raw multisig, right?
Sjors ProvoostYeah.
Aaron van WirdumWe've now explained what raw multisig is.
Sjors ProvoostYes. Or bare multisig, I think is the correct term, but it doesn't really matter.
Aaron van WirdumOkay. 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 ProvoostYeah, 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.
Sjors ProvoostI didn't check what the standardness was. Maybe the standardness was also 15.
Aaron van WirdumWait, so the limit was decreased?
Sjors ProvoostWell, 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 WirdumRight, so the consensus limit and the standardness limit were made the same at that point.
Sjors ProvoostYeah, 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 WirdumOkay, this is getting complicated, but I do think I'm following you.
Sjors ProvoostYeah, basically it means you cannot spend a multisig with more than 15 keys in it.
Aaron van WirdumYeah, but not because that's a specific rule concerning multisig, but a more general rule concerning script.
Sjors ProvoostYes.
Aaron van WirdumAnd that just happens to, the math just happens to end up at 15 in that case.
Sjors ProvoostYeah, 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 WirdumSo if… Because at first it's sent to a hash, right? So then the script… Yeah.
Sjors Provoostand then you reveal the actual script. So the script contains all the public keys.
Aaron van WirdumSo if there's a 16 out of 16 multisig, let's say, it just means it can't be spent?
Sjors ProvoostYep, you can't reveal it. If you try to reveal the script, it's invalid because it's too long.
Aaron van WirdumWasn't this an incompatibility, like a backwards? compatibility issue at the time?
Sjors Provoostyeah 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 Wirdumright 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 Provoostyeah 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 WirdumRight. Again, this sounds to me...
Sjors ProvoostOr two. I forgot if the limit is the number of public keys or the number of signatures.
Aaron van WirdumI'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 ProvoostNo, 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 Wirdumyeah no I I get that I think that that makes sense okay so
Sjors ProvoostBut 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 WirdumYeah, the same opcode.
Sjors ProvoostYeah, it's the same piece of C++ code that is just used in both situations.
Aaron van WirdumRight. 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 Provoostyeah 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.
Sjors ProvoostSo 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 WirdumRight. 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 Provoostthe super sneaky soft fork that he introduced Yep.
Aaron van WirdumOkay, right. So then because of SegWit, we went back to 20.
Sjors ProvoostYes, 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 Wirdumokay where now now I'm getting lost again so where is this limit? does this question even make sense?
Sjors Provoostyeah 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 Wirdumbut it's all in the witness right?
Sjors ProvoostIt 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 WirdumYeah, that's the weight limit, essentially, what we're talking about, right?
Sjors ProvoostIt'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 WirdumI see. Okay. So once again, we're talking about a specific limit on...
Sjors ProvoostWell, not SegWit.
Aaron van WirdumThere's a point system.
Sjors ProvoostYeah. The point system was...
Aaron van WirdumThe 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 ProvoostYeah. 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 WirdumYeah. 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 ProvoostExactly, yeah.
Aaron van WirdumOkay.
Sjors ProvoostAll 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 WirdumWell, they're also looking at new transactions, just not the witness part.
Sjors ProvoostYeah, 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 WirdumYeah.
Sjors ProvoostSo they don't count the number of signatures in it.
Aaron van WirdumRight. 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 ProvoostBasically, the number of signatures per block was increased by four. And I guess that makes sense.
Aaron van WirdumAnd to remind me and our listeners maybe, if they have the same type of memory as I do, what was the original limit?
Sjors Provoost20,000, and so it became 80,000.
Aaron van WirdumOh, yeah, but that was 1,000, right? Because it was 20 points per...
Sjors ProvoostWell, 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 WirdumRight.
Sjors ProvoostAnd with SegWit, SegWit, you could do more. Basically four times as many.
Aaron van WirdumOkay, sure. Is there a nice...
Sjors ProvoostBut 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 WirdumReal 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 ProvoostThe Bitcoin Core source code.
Aaron van WirdumOh, God.
Sjors ProvoostMostly.
Aaron van WirdumWell, I guess, like you said, wallets are taking care of it.
Sjors ProvoostSometimes.
Aaron van WirdumHopefully.
Sjors ProvoostOkay.
Aaron van WirdumOkay. So that's SegWit. I think we've discussed how SegWit changed Multisig from P2SH, right?
Sjors ProvoostYeah, it's a very small change.
Aaron van WirdumOkay. Then there was another update to how Multisig works when Taproot was introduced, right?
Sjors ProvoostYes.
Aaron van WirdumOkay. So what changed with Taproot?
Sjors ProvoostWell, 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 WirdumSo basically the reason that we even have limits on this kind of stuff.
Sjors ProvoostYeah, 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
Sjors Provoostline that says this is a multisig. You just... It implicitly is a multisig by using this opcode in an intelligent way.
Aaron van WirdumOkay. What does that mean? Why is this better?
Sjors ProvoostWell, 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
Sjors Provoostbecause 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 WirdumLet 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 Provoostyeah, exactly.
Aaron van WirdumAnd that's and so now you know exactly the rest of the network all nodes know exactly where to look and check it.
Sjors Provoostyeah 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 Wirdumyeah 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 ProvoostI'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 WirdumI didn't realize we're not talking about aggregating keys.
Sjors ProvoostNo, 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
Sjors Provoostas individual operations. So by enforcing this structure, now we are making it easier later to make the valuation faster.
Aaron van WirdumOkay, 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 ProvoostProbably, yes. Yeah, I mean, yeah, very probably.
Aaron van WirdumIs there a downside? It just sounds like this is less work.
Sjors ProvoostYeah, 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 WirdumOkay.
Sjors ProvoostThe script might be bigger.
Aaron van WirdumRight.
Sjors ProvoostBut 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 WirdumWhich is now literally possible.
Sjors ProvoostYeah, so Mr. Burak did a demonstration. He made a 998 out of 999 multisig.
Aaron van WirdumYeah.
Sjors ProvoostBut as far as I know, he could have done a 1999 out of 1999 multisig too. I'm not entirely sure.
Aaron van WirdumThat's the transaction that crashed the btcd nodes, which we also made an episode about.
Sjors ProvoostYes, two episodes even, because we talked about it in the second episode after that, about the second attack.
Aaron van WirdumOkay, 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 ProvoostYes. So OP_CHECKSIGADD has no limit itself.
Aaron van WirdumThis is the new multisig opcode.
Sjors ProvoostYes. 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 WirdumOkay.
Sjors ProvoostAnd 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 WirdumOkay.
Sjors ProvoostSo this complexity that we just talked about is gone.
Aaron van WirdumSo basically what you're saying is... That's weird. Makes me think of the Cathy Newman interview.
Sjors ProvoostYeah, exactly. So what you're saying is Bitcoin is not really signatures, is it?
Aaron van WirdumOkay, so basically what you're saying is Taproot completely changed how multisig works at all, right?
Sjors ProvoostYes.
Aaron van WirdumIt's a new opcode. There's no limits. All the old limits are gone. And we can even...
Sjors ProvoostWell, not all the old limits are gone. There's still a block size limit. But there's another limit.
Aaron van WirdumAll the multisig... Oh, there's another limit?
Sjors ProvoostAll the limits we just talked about are gone.
Aaron van WirdumOkay, yes.
Sjors ProvoostI agree.
Aaron van WirdumRight.
Sjors ProvoostBut 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
Sjors Provoostof 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 WirdumSo what you're saying is Bitcoin is now in the restaurant business.
Sjors ProvoostYes.
Aaron van WirdumGot it.
Sjors ProvoostAnd 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
Sjors Provoostscript 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 WirdumOkay, that makes sense.
Sjors ProvoostBut because you have to put one public key on the stack, that's why you hit the 1,000 limit.
Aaron van WirdumThat 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 ProvoostBecause I think, as far as I know, Satoshi put in the limit of 1,000, so it's an old consensus rule.
Aaron van WirdumOh, so that rule also existed already.
Sjors ProvoostYep. And, of course, Taproot could have removed it, but people felt no need to remove it.
Aaron van Wirdum1,000 should be enough for your average
Sjors Provoosttype of transaction. And this is also why the ordinals have a limit because or not. I forgot.
Aaron van WirdumOrdinals just have the block size limit as limited as far as I know. The inscriptions is what I mean.
Sjors ProvoostThe inscriptions, yeah, you might be right. I thought there was something about the 1,002, but maybe not.
Aaron van WirdumNo, I think they, I mean, we've seen blocks of 4 megabytes, right? That are basically just one inscription.
Sjors ProvoostThat's true, yeah. So anyway, this 1000 limit exists. So that's basically the naive way in Taproot to do multisig.
Aaron van WirdumOkay, 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 ProvoostAnd 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 WirdumYeah.
Sjors ProvoostBut 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
Sjors Provoostone of the thousand keys. Well, 999.
Aaron van WirdumYep. 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 ProvoostYep. 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 WirdumIt might also be more compact or not because you know it's the same.
Sjors ProvoostYeah, it's also more compact.
Aaron van WirdumOh, it is?
Sjors ProvoostYeah, because the individual scripts that you're using only have two keys in them. So the scripts are smaller.
Aaron van WirdumYeah, but you only need to publish two signatures anyways, right?
Sjors ProvoostYeah, but you also need to publish the original script.
Aaron van WirdumRight, 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 ProvoostYes.
Aaron van Wirdumand potentially therefore it's even more flexible. Interesting.
Sjors ProvoostAnd we haven't even talked about the best way to do it.
Aaron van WirdumLet's talk about the best way to do it, Sjors. What is the best way to do multisig?
Sjors ProvoostWell, 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
Sjors Provoostthis 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 WirdumYes, episode two was about Taproot. Yeah. But still, let's recap it a little bit.
Sjors ProvoostSo 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
Sjors Provoostand 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 Wirdumyeah 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 ProvoostAdd Schnorr.
Aaron van WirdumAdd 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
Aaron van Wirdumkey 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 ProvoostYeah, 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 WirdumYeah, or maybe is there a one sentence explanation?
Sjors ProvoostI 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
Sjors Provoostcan 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 WirdumRight. And that's a pretty decent one sentence explanation.
Sjors ProvoostThat's not the only way you can get fucked, but that is definitely the most.
Aaron van WirdumRight. 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 ProvoostI think if they have to, yeah, but they'd have to write their own wallet basically.
Aaron van WirdumRight, 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 ProvoostNope.
Aaron van WirdumOkay, so it's conceptually possible.
Sjors ProvoostI 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
Sjors Provoostproposals 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 WirdumAre we still talking about MuSig or would this get a new name?
Sjors ProvoostNo, they would not be called. They would have a new name.
Aaron van WirdumOkay. But it's essentially using the same Schnorr trick, right?
Sjors ProvoostIn 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 WirdumWhat do you mean by completely new ways of doing this?
Sjors ProvoostWell, 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 WirdumSure. Okay, yeah.
Sjors ProvoostAnd 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
Sjors Provoostto 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 WirdumCould 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 ProvoostYeah, I mean this would be a one out of a billion…
Aaron van WirdumWhat would be the best threshold for that, do you think?
Sjors ProvoostWell, the opposite would be like a 4 billion out of 8 billion multisig.
Aaron van WirdumSo just majority, you think that's good?
Sjors ProvoostAnd 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
Sjors Provoostdoesn'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 WirdumYeah, but maybe not if it's a million out of a million, right? Then it just takes...
Sjors ProvoostMaybe 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 WirdumOkay, so that's not…
Sjors Provoostbut 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 Wirdumso 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 ProvoostI 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 WirdumWell, 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 ProvoostIt 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 WirdumNo. Have we discussed anything? Yeah. You think we've had everything? then I'm good with this episode, Sjors?
Sjors ProvoostExcellent. Well, then thank you for listening to Bitcoin,
Aaron and Sjors discuss Bitcoin Core 32.1 and its updated security disclosure policy in this live conference recording, followed by audience questions. Links Bitcoin Core 32.1 release announcement and release notes...
Aaron and Sjors discuss the COLDCARD hack: the bug itself, how it could have happened, and some reflections on having had Coinkite as a sponsor. Note: If you’re using a COLDCARD and still haven’t moved your funds to a...
The COLDCARD hardware wallet has a critical vulnerability. If you are using the COLDCARD to store bitcoin, move them to a secure location as soon as you can. More information:...
Aaron and Sjors discuss what’s new in Bitcoin Core 31. Chapters 00:00:00 Episode 100 and Core 31 00:02:41 Cluster Mempool 00:10:45 Package Relay and Fee Selection 00:18:59 Private Broadcast over Tor 00:24:03 ASMAP and...