Utreexo w/ Ruben Somsen - NADO 15

Aaron van Wirdum Live from Utrecht, this is the Van Wirdum Sjorsnado.

Sjors Provoost Hello.

Aaron van Wirdum Hey, Sjors.

Sjors Provoost What's up? What's going on?

Aaron van Wirdum Ruben is back.

Sjors Provoost Ruben is back.

Ruben Somsen Hello.

Aaron van Wirdum Ruben.

Ruben Somsen Yeah.

Aaron van Wirdum Did you subscribe to the Van Wirdum Sjorsnado?

Ruben Somsen Indeed, I did. I am a subscriber now.

Aaron van Wirdum Nice. Because we do have our own RSS feed now.

Ruben Somsen Awesome.

Aaron van Wirdum You can find us in your favorite podcast app. I think this is the last time I'm going to mention it. Sjors, what do you think? Maybe one more time next week?

Sjors Provoost Well, we have no influence over that because our editor can just make you say whatever he wants you to say.

Aaron van Wirdum He'll just edit it in there if we forget, apparently. That's right. Ruben, you contacted us last week because you listened to our last episode about... Assume UTXO. That's what it was about. Assume UTXO. Yeah. And you told us, Aaron, Sjors, you're being such idiots. There's a huge difference between assume UTXO and assume valid, actually.

Ruben Somsen No, that's not how I put it at all.

Aaron van Wirdum So you're going to issue the correction for us now. What is the difference? By the way, this isn't what the episode is going to be about. That's right, yeah. Just to start out. What's the difference? What did we forget to mention?

Ruben Somsen So there was just kind of one difference between assume UTXO and assume valid. i personally think is kind of interesting and i just wanted to kind of point that out and it's not you know there's nothing you didn't you guys didn't say anything wrong it was just something that i thought would be good to as an addition basically to what you guys were talking about so the specific difference is that with assume valid you have miners also indirectly saying that the most proof of work chain of headers is a valid chain. And because of that, you kind of have a double proof with assume valid. You have to prove that miners are saying it's correct. Presumably, this is kind of SPV proof security. So it's not something you want to fully rely on.

Aaron van Wirdum As a quick recap. Yeah. And we're not going to redo the episode. I was going to say,

Ruben Somsen listen to the last episode.

Aaron van Wirdum Assume valid is you insert the hash somewhere in the code. Wait, I got to listen to our own episode. Exactly.

Ruben Somsen That would be the best way of doing it.

Aaron van Wirdum If that hash is in the blockchain, so it's a block header hash, then you assume that everything that happened before it has valid signatures. That's right. So at that point, you're trusting developers that they put in a hash that is in the valid version of the blockchain and you're also trusting miners that that is in the valid wait yeah so miners had to actually expend energy to produce that hash yeah and everything that came after it

Ruben Somsen otherwise it wouldn't be in the most proof work chain anymore and then even though like let's say in bitcoin core it said lol this hash this block all the blocks before it all the signatures are valid but then that specific block is no longer in the longest most proof of work chain yeah

Aaron van Wirdum so the thing is you're not just trusting developers even though you're kind of trusting them a bit yeah and you're also not just trusting miners yeah they gotta both collude somehow and that's why it's sort of secure that's right and now there's assume utxo and you're saying there's slightly slight difference yeah

Ruben Somsen so i'm saying with assume utxo because there's not an actual commitment to the utxo set inside of each block it means that miners haven't really committed to that state. So what that means is that if in Bitcoin Core, you have to assume UTXO and somehow there's a mistake introduced inside of that UTXO set, then miners are not going to reject that block because the hash of that UTXO set is not going to be contained within that block. So you don't have that. double assurance of miners as well

Aaron van Wirdum right so so the reason i think that's negligible yeah that's probably a very mispronunciation of that word negligible yeah exactly it's because the only way to use that to your benefits as a developer in this case let's say you're a developer and you create this utxo set for assume utxo yeah and you say hey i've actually on my address i got a thousand billion million bitcoins The only way you can ever benefit from that is if in a block after that, a miner is willing to include it. So you're still relying on proof of work in that sense.

Ruben Somsen Unless you find an idiot that sells zero confirmation Lambos. I mean...

Aaron van Wirdum Right. So I guess that would be the one example where it would be a difference.

Sjors Provoost But a zero confirmation Lambo person, you can just double spend.

Ruben Somsen Yeah, there are probably other ways to screw that person up, but that's true.

Aaron van Wirdum All right, so far, last episode. Another episode with extra Ruben. This time we're not going to discuss one of your proposals. You're just here to discuss a proposal with us. And the proposal we're discussing this week is Utreexo.

Sjors Provoost That is correct. Utreexo. And the tree is for a tree, the thing that grows in the forest.

Aaron van Wirdum Did you know that was the pun, Ruben? I didn't realize.

Ruben Somsen Well, I mean, I heard Tadge say that, so I was aware of that. But there is a very specific reason why I was kind of enthusiastic to talk about it. Well, one, I've kind of like used it in one of the things I've been working on. So I kind of like Utreexo a lot conceptually. But there is also a close friend of mine, Calvin Kim, who was a regular attendee of the Seoul Bitcoin meetup. who is now actively working on Utreexo together with Tadge and i i told him i would shout out the other guys that are working on the project Janus Troelsen, which is apparently not a dutch person i think he's like german or something and Niklas Gögge, hopefully i pronounced it correctly but those are the four guys that are currently kind of working on uh Utreexo hopefully kind of will eventually get to a point where This can be useful for Bitcoin Core. But we should obviously start explaining what Utreexo is because we're just talking about the kind of conceptual idea right now.

Aaron van Wirdum Oh, we've got to keep it exciting.

Sjors Provoost Well, really quick, are these guys with DGLab?

Ruben Somsen No, no, that's completely separate. Yeah. There's MIT. I'm not super familiar with this, but Tadge is with MIT. And then the other three guys are just working on this separately. So they're not involved with MIT or DGLab. DGLab mainly works on DLC. That's kind of one of their main projects.

Aaron van Wirdum Okay. So Sjors, what problem are we solving?

Sjors Provoost Problem, problem, challenge. So one of the constraints when you're syncing a new Bitcoin node, we talked about sync a couple of times, is the amount of RAM memory you have. Now, it's not a hard constraint. You don't need a lot of RAM, but if you want to sync it fast, you do. And the reason is this thing called the UTXO set. The UTXO set is the list of coins that you own. We talked about that last time, I guess. But every time the new block comes in, what you do is for every transaction in the block, you check if it's spending something that exists, namely one UTXO. And so in order to check if something exists, well, it has to be somewhere. It has to be in a database of sorts. And where is that database? Well, if that database is sitting in your RAM memory, That's extremely fast. If on the other hand, that database is sitting on your hard disk, if it's an SSD drive, it's meh.

Aaron van Wirdum What you mean is it's much faster to look up if it's in there. If it's in your RAM, then your computer will be able to look it up within, well, I don't know how fast, but faster than if it's on your drive. It's

Sjors Provoost probably at least 10 times faster than if it's on your SSD drive. And if you're using a magnetic drive, it's even worse. And then the other side of it is... once you create this new coin, which the transaction does on the output side, it has to store that. So it has to write it somewhere on the disk, which is also slow. And if you have a magnetic spin disk, then it has to move to read somewhere and it has to move somewhere else to write again. These are gigabytes apart. So that's horrible.

Aaron van Wirdum So to make it very concrete, I guess the biggest difference you would notice when you're syncing a new node and if you would somehow be able to keep the UTXO set in RAM, It will only take, I don't know, a couple hours.

Sjors Provoost But it depends on your computer. I have a somewhat recent MacBook Pro, and I think I can sync the whole chain in five hours.

Aaron van Wirdum If you keep it in RAM.

Sjors Provoost But that takes about 11 gigabytes of RAM. But if you do it on, say, a typical Raspberry Pi, you might have, I don't know, two gigabytes these days, maybe four. So that means you're going to sync the chain and you're going to keep as much as possible in RAM. But at some point it overflows, the UTXO set. And then usually what it does is it writes everything to disk. clears everything, and then it starts caching again. And this takes a long time. It can take days on these machines.

Aaron van Wirdum Right. So the point being, as you can keep more of the UTXO set in RAM, you'll sync faster, or your node will just work faster, operate faster in general. So it would be good if we could somehow decrease the size of the UTXO set.

Sjors Provoost Well, we can't decrease the size of the UTXO set. That's kind of the problem.

Aaron van Wirdum That's a bummer.

Sjors Provoost There is a limit on the size of blocks.

Aaron van Wirdum Well, it can decrease.

Sjors Provoost Four megabytes. It can decrease. It's just not something we can do. Yeah, it decreases when people spend...

Aaron van Wirdum I don't know how many UTXOs you own. I bet a lot. So maybe you could play a part in decreasing the UTXO.

Sjors Provoost Millions of UTXOs on testnet. No. So the idea is that if you're spending more coins than you're creating, then obviously the number of UTXOs goes down and the RAM usage goes down. But there's a lot of junk in the UTXO set. Because there were people in the old days that created transactions to multi-sig addresses that were fake just in order to put pictures of Obama in the blockchain. And those are all sitting in your RAM because your node has no idea that they're nonsense. But the other thing is if we expect everybody in the world eventually to use Bitcoin and everybody to have at least one or two UTXOs, then, well, that's a lot of RAM. That's like 7 billion people. And there's really no limit to how big that can get. There's no constraint. It might take a while because it takes a lot of fees to create all these transactions, but eventually it could take as much RAM as, you know, there's no limit. And we don't like things that don't have a limit. Unbounded stuff, it's a bit bad.

Aaron van Wirdum Yeah, you mean the UTXO set can get as big as it will get until the point where not everyone can use it, can sync it from RAM.

Sjors Provoost Fewer and fewer people will have enough RAM to sync it quickly, and that could become a problem, right?

Aaron van Wirdum Okay, so you agree it's a problem, not just a challenge, it's a problem, Sjors. Now, how do we solve it?

Sjors Provoost Yeah, it's a challenge, obviously. Well, one way to solve it is Tadge Dryja's proposal, the Utreexo. And the idea there, I guess that's what we'll need to explain, right? How that works.

Aaron van Wirdum Well, Ruben wanted to explain it to us. So let's hear it.

Ruben Somsen I first wanted to say that I thought, Aaron, your analogy with basically saying that it's pruning for the UTXO set. I thought that was a very good analogy where currently we have pruning in Bitcoin.

Aaron van Wirdum This was an off-record analogy.

Ruben Somsen Yeah. Now it's on record. Now it's on record. Yes, I'm repeating something that you told me before the show. So with Bitcoin, currently you have pruning in the sense that you take a block, you process it, you extract the UTXO set out basically from all the blocks. And then that's all that you keep. You only keep the UTXO set. And then you can throw everything else away. And that's called pruning. There is a downside, which is that then you don't have the blocks. So if you want to prove to another person that the UTXO set is valid, you don't actually. You can't actually give them the blocks, but the assumption is that somebody else will have the blocks, so it's fine. And here, what you're pruning is something else. You're pruning UTXO sets, and you're essentially taking out all the, you're throwing away all the transactions, and you're just keeping a Merkle root. And inside of that Merkle root is basically a commitment. Every single UTXO is committed in there, and you only keep the Merkle proofs of the UTXOs that you care about, that you own.

Aaron van Wirdum What is a Merkle root?

Sjors Provoost Yeah. Or maybe to put it in another way, normally when somebody sends you a transaction, the transaction says, I'm spending this input. And you, as the person running a node, has the responsibility to check whether that input exists in your own database. And you're flipping this around and you're telling the other node, I have no idea which coins exist because, you know, I don't have RAM. You proved to me that this coin actually existed. Yeah. And that's what you used this Merkle proof for. So the burden of evidence is reversed here. You need to prove that a transaction exists. And then the question is, how are we going to do that?

Aaron van Wirdum Okay, so we're reversing the burden of proof. Usually when you're sending a transaction, when I send a transaction to you, Sjors, then you check inside your node in the database with your UTXO set whether the transaction is spending valid UTXOs. Yes. Now... I'm actually going to have to provide you with the proof that my transaction is spending existing UTXOs. However, you still need something in order to make sure that my proof is valid. And that's this Utreexo, which is a hash tree.

Sjors Provoost Yes, a Merkle tree.

Aaron van Wirdum Right. So what is this and how does it work?

Sjors Provoost So it's kind of nice. All the UTXOs that are in existence would be put into this tree. And everybody can construct this tree if you replay the whole blockchain. But the question is...

Aaron van Wirdum It's not an actual tree, though, is it? It's not an actual tree. Do you give it water? No.

Sjors Provoost Basically, what the tree would look like is you have the first UTXO, and then the second UTXO right next to each other. And then you take the hash of those two, basically combined. And that is one new hash. So you see this little pyramid shape. And you can do that again for another two. UTXOs that exist. They're their own little mini tree. But now you see, oh, there's two trees. Let me just combine those two trees.

Aaron van Wirdum Two hashes, and you're combining these two hashes. So

Sjors Provoost now you have four UTXOs, and two of them are shared, and then those two are shared again.

Aaron van Wirdum Yeah, so you end up with one hash.

Sjors Provoost You end up with one hash. Now the key here is that these things are so-called, I believe, perfect trees, which means that they are always a multiple of two.

Aaron van Wirdum Right, yeah. So now the challenge is that for every new block, this tree needs to be updated, right? Because we have one big tree for all of the UTXOs. Now a new block is found. It includes all sorts of new transactions. So new UTXOs exist and old UTXOs are destroyed. So now we need a new tree.

Sjors Provoost Yeah, well, it's even more than one tree, right? It is a forest. Because every tree has to be a multiple of two, So there can be four things at the bottom or eight things at the bottom or 16 things at the bottom. When you have a number of transactions that doesn't fit that way, you'll have multiple trees that look like that. So you have a collection of trees. for which you really only need to remember the top hashes. And now the question is, how do you add something to that tree?

Aaron van Wirdum So you might have one tree with 16 at the bottom, one tree with 8 at the bottom, one tree with 2 UTXOs at the bottom. Yeah, exactly. So you have multiple trees.

Sjors Provoost And now, in order to prove that something is in this tree... And also to replace it with, say, the output, because basically you destroy one UTXO that you're spending and you create a new UTXO that you're creating. So you can actually take the UTXO that you're spending out of the tree. and then put the new one into the tree. And in order to do that, you need to provide, you need to recalculate the tree, and you do that by knowing its neighbors. So the way you prove that something is inside a Merkle tree is to say, well, at the bottom of the tree, there's these two pairs, and I'm going to give you the other side. And then at the next level, again, there's a pair, and I'm going to give you the other side, and again, and again, and again. And that proves that something is actually in the tree. And that's exactly the same information that you need to put something else at the bottom of the tree.

Aaron van Wirdum Right. So by putting something else at the bottom of the tree, to be clear, the entire tree changes, or at least the one hash you end up with changes. Like you're just computing a whole new tree. But you're able to do that because you have all the data you need. Yes. So you can add things to the forest and you can remove things from the forest. It's actually possible. It's actually easier than... I thought it would be when I saw Tadge explain it. I don't know if it's going to be easy when people hear us explain it. I would

Sjors Provoost recommend looking at Tadge explain it after you hear us explain it. Because you need to see it. Yeah, visuals. Visuals really help. Exactly. I think

Ruben Somsen his presentations are great. He's very good at explaining it. And yeah, he has slides. So that's a lot easier than what we're doing. We're trying to explain it in words, especially in Merkle Trees. I think it's great if you have an actual picture there.

Sjors Provoost But now the idea is that you're not tracking everything, right? Yeah. So you could, when you're syncing the blockchain, keep track of the entire tree, but then you need a lot of RAM, just like in the original scenario. But what you'll actually do is you're going to remember the top of every tree, and there might be 10 or 20 or whatever trees. And that's all you're going to remember. And when somebody has a new transaction that you want to verify, they need to give you the Merkle proofs for all the inputs that they're spending. So they prove that they exist. And then they also tell you which outputs are there. which are going to be swapped in at the same places where those inputs were, plus new trees if it's making more.

Ruben Somsen Yeah, but in the blocks, right? Yeah. Yeah, so that's really, I think, the very elegant side of Utreexo, where the same proofs that are proving that these UTXOs are in the UTXO set are also exactly what you need to remove them from the set, update your root hash, and add the new UTXOs from the latest block. So that works out quite elegantly.

Aaron van Wirdum Okay, so in an ideal scenario, let's say what we've been explaining so far is sort of the ultimate version of Utreexo, so let's stick with that for a minute. So I wanted to send a transaction to the network and you, Sjors, you had a node and you wanted to validate the transaction. You have this tree in your own... in your RAM, apparently. That's what's nice about it.

Sjors Provoost I have the top of the trees in my RAM.

Aaron van Wirdum Yeah, exactly. So now I want to send this transaction. So now it's my responsibility to send to you the transaction as well as... the proof that the transaction is valid, which also includes information for you so you know where to find it in the forest, right?

Sjors Provoost Exactly. You need to prove to me that the things you are spending are in the forest because I forgot what the forest looked like.

Aaron van Wirdum Right. All right. So that's me sending the transaction with the proof. Now, the other way you could get the transaction is if it's already in the block. So if a miner mines a block and the transaction is in there, you still have your Utreexo thing or your nodes. But how do you now get the proof?

Sjors Provoost Right, because if you spend the transaction, you're not going to talk to every node that ever downloaded the block to send that proof around. So how does that proof get to the node?

Aaron van Wirdum That wouldn't scale very well, at least.

Sjors Provoost No. Well, what you would probably want to have is something called a bridge node.

Aaron van Wirdum A bridge node.

Sjors Provoost A bridge node would be a node that has the actual UTXO set, the old-fashioned way, so it has lots of RAM, or it's just slow, and it produces all these proofs, and it sends them around to whoever wants them.

Ruben Somsen Yeah, so what essentially happens is that when this bridge node receives a transaction, and this transaction does not have a Merkle proof proving the inclusion in the Utreexo root, This bridge node basically just takes the proof that they have and they attach it to the transaction. And now they send it on to other Utreexo nodes. It's a bridge between Utreexo nodes and non-Utreexo nodes.

Aaron van Wirdum Yeah, but they could also construct the proof themselves, right? If they see a certain transaction is included in a block, they can just figure it out.

Sjors Provoost That's right. Every node, there's nothing secret here. So if you have the original UTXO set in memory somewhere, you can construct the proof for any transaction.

Ruben Somsen And they have the entire tree, essentially. So the entire UTXO tree that you create and then prune, they just don't prune it, essentially. So they just have the full UTXO set, basically the UTXO set with all the Merkle proofs connecting to it. So then they can just take any UTXO in there. and create a proof from it and just send it on or for an entire block or whatever. Right.

Aaron van Wirdum So what would happen in practice is your node would see a transaction in a block and it would wonder, hmm, is there actually proof for that? I never saw the transaction before. And you would request it from a bridge node.

Sjors Provoost Yeah, my guess is when you get the whole block, you're going to call a bridge node and say, give me the proof for that entire block.

Aaron van Wirdum Or just all of them? Yeah. Why not just the ones you need, the ones you haven't seen before?

Sjors Provoost My guess is that's too much back and forth, because if you have to call a node for every single individual transaction, then that's a lot of overhead, whereas just downloading a couple hundred kilobytes is easier.

Aaron van Wirdum Anyways, that's an implementation detail.

Ruben Somsen Yeah, but I think this is just an automated process, right, where you just connect. to the network but like the problem is like when you're the first Utreexo node right and you're pruning all the data and then everybody else on the network is an old-fashioned node like the way we run it today nobody's going to give you the proofs right so what you need is at least a single bridge node so at least you can connect to that one and then other people are connecting to the bridge node because the bridge node basically speaks both languages right they speak the Utreexo language and they they speak the old-fashioned language yeah so they translate for you and as long as one bridge node exists it kind of can bootstrap the network essentially but they don't they don't have to have like special rules it's like from the perspective of the Utreexo node the bridge node is just also Utreexo node and from the perspective of the old-fashioned nodes it's just an old-fashioned node

Sjors Provoost right that's another point so yeah you don't need everybody to do this translation yeah Only one person needs to do it or a couple. The other nodes know how to relay that information even if they can't produce it. So that's good news.

Aaron van Wirdum Can we have a future without bridge nodes?

Sjors Provoost Well, we should point out what the problem is with these bridge nodes because they are nice people. We don't want to rely on nice people. That's not how we roll. So because nice people can stop being nice.

Aaron van Wirdum Or they can be forced to stop being nice.

Sjors Provoost Or they can just disappear or run out of battery. Yeah. So yeah, then you can look at the longer term picture. Like could this, you know, if people like this, give any advantages or even if they don't like it, if the UTXO set just becomes insane and it just takes too long to sync on any normal computer, then you could basically make a soft fork which contains the proofs. So the proofs. become part of the blockchain. Just like SegWit added a whole bunch of data to blocks, you could then add these proofs to the blocks, making the blocks even bigger. But the trade-off there is you have more bandwidth, but you have less RAM need.

Aaron van Wirdum Yeah, the reason this could be done as a soft fork, same with SegWit, is because you'd include the hash of... the proofs somewhere in like the Coinbase transaction or something like that. Old nodes just won't notice anything interesting, but upgraded nodes will see like a whole tree which they share with each other, which does make the blocks a bit bigger for them.

Sjors Provoost Yeah, so old nodes keep doing what they're doing. They get blocks, they can verify those blocks because nothing changes about the transactions in the blocks. New nodes will save some RAM memory. They'll use that extra data. They'll download that extra data. and they'll use it. That's generally the idea.

Ruben Somsen Yeah. So personally, at least, I think this is not likely to happen until we really get a UTXO set bloating issue where the UTXO set becomes so big that people start liking this trade-off to the point where it's preferable. I think as long as we're not at that point, I don't think we'll see this as a soft fork, but that's my personal view.

Sjors Provoost I do want to point out some cool things you can do with it.

Aaron van Wirdum Yes. Tell us the bullish.

Sjors Provoost The bullish part. You know, I'm all just copy pasting from what Tadge said. We like to do that. Basically, because you don't need a lot of RAM, you can start doing things in specialized hardware like an ASIC. Because one of the things that's kind of hard to do in an ASIC is lots of memory. And having specialized hardware, maybe it's a part of your chip. So maybe, you know, Bitcoin becomes the standard and every phone that you buy has a CPU and, you know, has a... little mini processor right next to it that just checks all the bitcoin validation rules and because it's custom silicon it might be able to validate the entire blockchain at the speed that it can download it which is pretty

Aaron van Wirdum an asic for regular nodes exactly right

Sjors Provoost So not to mine coins, but to verify coins, which would be cool. And then, you know, you have the protocol literally set in stone or at least set in silicon. And of course, soft forks can still happen under that circumstance. But if somebody wants to do a hard fork, you'd have to break all the node hardware, not just all the mining hardware. So that's a nice extra barrier to not do hard forks. It's an ossification of network.

Aaron van Wirdum It's also not perfect for soft forks. Is that what you just said, Ruben?

Ruben Somsen No, I mean, that's what...

Sjors Provoost No, no. It makes it harder to verify soft forks because if you didn't... if you don't have to verify the soft fork but you soft fork but you can't verify the soft fork at least not with the accelerated hardware yeah so your computer would have to slow down to check all the new rules whenever it encounters it.

Aaron van Wirdum Yeah, or you have to buy a new phone because the soft fork happens.

Sjors Provoost Exactly.

Ruben Somsen If your phone is too old, maybe it's possible, right? That's what happens now. People buy new phones every couple of years, so maybe it's not too much to ask.

Sjors Provoost The other thing is, we talked last week about this assume UTXO thing, where one of the problems is, now when you start, you still need to get that three gigabyte thing from somewhere. And if this thing becomes 100 gigabytes, you have to get that from somewhere. But now we have, with this proposal, we just have a kilobyte. So you can put the entire UTXO set, you can represent it in a kilobyte, which can just be inside the source code. So you don't need a hash and then go and fetch something, you just put the thing itself in there. And nodes can start instantly at that height and then do the same thing that we described. Yeah, last week, right? So sync all the way to the type tip and then start the genesis and make sure everything is what it should be.

Ruben Somsen Yeah, that's a really nice kind of feature that you have the entire UTXO set in essentially a single hash or a forest.

Sjors Provoost Yeah, a small little forest. One kilobyte.

Aaron van Wirdum What's not to... Are there more benefits?

Sjors Provoost Yeah, so the last one would be you could sync with a phone node. So right now, if you have a node on your phone, it might be very slow. Maybe with this proposal, it wouldn't be slow, but let's say it's still slow. What you would do is you sync your node on your desktop or whatever it is. You scan a QR code, which can be pretty long. And now your little phone has the recent UTXO set. And that doesn't even require any kind of commitments, right? Because your phone trusts your laptop. So that's a feature you could use right now.

Aaron van Wirdum Yep. Are there any downsides or risks? Ruben, you thought about this?

Ruben Somsen Sure, but I want to add one more interesting feature that we haven't discussed yet.

Aaron van Wirdum Before we burn it all down.

Ruben Somsen Before we burn it down, yeah. It's a good question, though. And that's parallel validation. So what you can do is you can theoretically take two computers. and just take a Utreexo hash off the middle state of the blockchain so you know if at block 2000, you just take block 1000 and you take the Utreexo hash from that moment in time and then you start validating 1000 to 2000 and on the other computer you start validating 0 to 1000 and if they match up after you validated both, then you validate the entire blockchain while splitting up the work. And that's interesting and can be very useful, I think, maybe in the future also when you have more and more CPUs on a single chip.

Sjors Provoost Right, so it wouldn't be necessarily multiple computers doing this, but just multiple chips doing it because we see that clock speed is not going up much. But you get more and more parallel stuff. And the problem with the Bitcoin chain is you can verify... You can verify signatures in parallel, and a Bitcoin node does that. But some things are intrinsically serial, so you cannot verify block 10 before you verify block 9. And it's nice if you can get rid of that.

Ruben Somsen Yeah, so now you can, essentially.

Sjors Provoost You can too, if you assume UTXO, but you need multiple very large snapshots. Yeah, exactly. So, yeah, very cool stuff. So, let's burn it down. Right.

Aaron van Wirdum Go for the kill, Ruben.

Ruben Somsen Yeah, one more thing to add is apparently you can also do backwards validation. I'm not sure exactly how it works, but apparently you can go from block 1000 to 999. So yeah, so that's possible too.

Sjors Provoost Well, you need to because you need to be able to roll back.

Ruben Somsen That too, yeah. So I just haven't looked into that sufficiently to fully grasp it.

Sjors Provoost Well, we just explained that in order to prove that something is in a Merkle tree, that's the same thing you can do to change something in a Merkle tree. So you can change the old thing with the new thing that way, or you can change the new thing with the old thing.

Ruben Somsen Right. Yeah. Yeah. So it makes sense. I agree with that. I just haven't like sat down and just gone through it.

Sjors Provoost One other thing we can also mention is that this tree that we just described is the general name for it is an accumulator. It's something that you can use to. add stuff to, and in this case also remove stuff from. But there are all sorts of mathematical tricks you can deploy to do this. This is something that's conceptually simple. I mean, if other people than us explain it and you see it in front of you, it's very simple with the Merkle trees. But there's been other proposals, like an RSA accumulator. There's all sorts of cool cryptographic math you can do to just add things to a set and remove them from a set, essentially. Perhaps another mechanism would be used eventually.

Ruben Somsen And that's maybe also one of the downsides that we can talk about now, where if you start using this and then later somebody finds a better accumulator, then you have to yet again switch to that next proposal, which is OK as long as you don't commit it into a block. But once you make this an actual soft fork and then you find, oh, there's this even better accumulator that we should have been using. Now you're kind of stuck because you can't undo a soft fork, at least not unless you put in some kind of sunset date or something. But that's generally not really. done, at least hasn't been done so far.

Sjors Provoost No. So that's another reason why you wouldn't expect this to be a soft fork unless like the world is burning or it's been used for so and so long that people think, okay, this is mature. We're nowhere near that. It's pretty experimental as many of the things we discuss here.

Ruben Somsen And I guess the second thing that I consider a downside is that bandwidth seems to be pretty much the bottleneck right now for Bitcoin. And this is something that makes that bottleneck worse. So for that reason, I personally see this as kind of a more of an option that people can opt into if in their case bandwidth isn't a problem, but their CPU or disk IO restricted or RAM restricted, or maybe they want to use an ASIC or something like that. From that perspective, I don't expect everybody to use this. But I also think Sjors has pointed out correctly that if the UTXO set grows to a significant degree where it does become a burden and it slows down validation, then maybe this becomes more appealing.

Sjors Provoost Yeah, so keep an eye on it.

Aaron van Wirdum Yeah. And I guess the increased block size in one of the variants could be considered a downside. Although I think

Sjors Provoost that's what we meant with more bandwidth.

Ruben Somsen Yeah, exactly.

Sjors Provoost That's, you know, just...

Aaron van Wirdum Okay, fair enough. Then I guess that's it, isn't it?

Sjors Provoost Let's see if I had anything else on the list. Nope. I think that's it. Thank you for listening to the Van Wirdum Sjorsnado Special Somsen Edition.

Aaron van Wirdum There you go. There you go.