WEBVTT - Automatic transcript; recognition may contain errors. Reviewed for technical wording and speaker labels. Times match the published episode. 00:00:07.220 --> 00:00:09.920 Live from Utrecht, this is the Van Wirdum Sjorsnado. 00:00:10.420 --> 00:00:10.620 Hello. 00:00:11.300 --> 00:00:11.780 Hey, Sjors. 00:00:12.120 --> 00:00:12.540 What's up? 00:00:14.200 --> 00:00:15.080 What's going on? 00:00:15.420 --> 00:00:16.000 Ruben is back. 00:00:16.280 --> 00:00:17.180 Ruben is back. 00:00:17.360 --> 00:00:17.560 Hello. 00:00:18.240 --> 00:00:18.620 Ruben. 00:00:19.120 --> 00:00:19.260 Yeah. 00:00:20.220 --> 00:00:22.880 Did you subscribe to the Van Wirdum Sjorsnado? 00:00:23.360 --> 00:00:25.720 Indeed, I did. I am a subscriber now. 00:00:25.940 --> 00:00:28.600 Nice. Because we do have our own RSS feed now. 00:00:29.070 --> 00:00:29.470 Awesome. 00:00:29.710 --> 00:00:33.450 You can find us in your favorite podcast app. I think this is the last time I'm 00:00:33.450 --> 00:00:36.570 going to mention it. Sjors, what do you think? Maybe one more time next week? 00:00:36.710 --> 00:00:40.030 Well, we have no influence over that because our editor can just make you say 00:00:40.030 --> 00:00:41.010 whatever he wants you to say. 00:00:41.150 --> 00:00:46.390 He'll just edit it in there if we forget, apparently. That's right. Ruben, you 00:00:46.390 --> 00:00:51.670 contacted us last week because you listened to our last episode about... Assume 00:00:51.670 --> 00:00:56.560 UTXO. That's what it was about. Assume UTXO. Yeah. And you told us, Aaron, Sjors, 00:00:56.760 --> 00:01:00.960 you're being such idiots. There's a huge difference between assume UTXO and 00:01:00.960 --> 00:01:01.980 assume valid, actually. 00:01:02.120 --> 00:01:03.600 No, that's not how I put it at all. 00:01:03.820 --> 00:01:09.280 So you're going to issue the correction for us now. What is the difference? By 00:01:09.280 --> 00:01:12.280 the way, this isn't what the episode is going to be about. That's right, yeah. 00:01:12.460 --> 00:01:16.320 Just to start out. What's the difference? What did we forget to mention? 00:01:16.480 --> 00:01:21.790 So there was just kind of one difference between assume UTXO and assume valid. i 00:01:21.790 --> 00:01:25.350 personally think is kind of interesting and i just wanted to kind of point that 00:01:25.350 --> 00:01:28.750 out and it's not you know there's nothing you didn't you guys didn't say anything 00:01:28.750 --> 00:01:32.610 wrong it was just something that i thought would be good to as an addition 00:01:32.610 --> 00:01:36.970 basically to what you guys were talking about so the specific difference is that 00:01:36.970 --> 00:01:41.090 with assume valid you have miners also 00:01:42.340 --> 00:01:47.800 indirectly saying that the most proof of work chain of headers is a valid chain. 00:01:48.220 --> 00:01:51.400 And because of that, you kind of have a double proof with assume valid. You have 00:01:51.400 --> 00:01:54.960 to prove that miners are saying it's correct. Presumably, this is kind of SPV 00:01:55.360 --> 00:01:57.760 proof security. So it's not something you want to fully rely on. 00:01:57.840 --> 00:02:01.700 As a quick recap. Yeah. And we're not going to redo the episode. I was going to say, 00:02:01.820 --> 00:02:03.040 listen to the last episode. 00:02:03.300 --> 00:02:09.220 Assume valid is you insert the hash somewhere in the code. Wait, I got to listen 00:02:09.220 --> 00:02:10.320 to our own episode. Exactly. 00:02:10.840 --> 00:02:12.040 That would be the best way of doing it. 00:02:12.120 --> 00:02:16.440 If that hash is in the blockchain, so it's a block header hash, then you assume 00:02:16.440 --> 00:02:20.500 that everything that happened before it has valid signatures. That's right. So at 00:02:20.500 --> 00:02:24.870 that point, you're trusting developers that they put in a hash that is in the 00:02:24.870 --> 00:02:30.310 valid version of the blockchain and you're also trusting miners that that is in 00:02:30.310 --> 00:02:34.990 the valid wait yeah so miners had to actually expend energy to produce that hash 00:02:34.990 --> 00:02:37.050 yeah and everything that came after it 00:02:37.050 --> 00:02:40.650 otherwise it wouldn't be in the most proof work chain anymore and then even 00:02:40.650 --> 00:02:44.970 though like let's say in bitcoin core it said lol this hash this block all the 00:02:44.970 --> 00:02:48.550 blocks before it all the signatures are valid but then that specific block is no 00:02:48.550 --> 00:02:50.650 longer in the longest most proof of work chain yeah 00:02:50.650 --> 00:02:54.450 so the thing is you're not just trusting developers even though you're kind of 00:02:54.450 --> 00:02:58.790 trusting them a bit yeah and you're also not just trusting miners yeah they gotta 00:02:58.790 --> 00:03:03.110 both collude somehow and that's why it's sort of secure that's right and now 00:03:03.110 --> 00:03:07.110 there's assume utxo and you're saying there's slightly slight difference yeah 00:03:07.110 --> 00:03:10.970 so i'm saying with assume utxo because there's not an actual commitment to the 00:03:10.970 --> 00:03:15.720 utxo set inside of each block it means that miners haven't really committed to 00:03:15.720 --> 00:03:21.600 that state. So what that means is that if in Bitcoin Core, you have to 00:03:21.600 --> 00:03:27.200 assume UTXO and somehow there's a mistake introduced inside of that UTXO set, 00:03:27.460 --> 00:03:31.920 then miners are not going to reject that block because the hash of that UTXO set 00:03:31.920 --> 00:03:35.720 is not going to be contained within that block. So you don't have that. double 00:03:35.720 --> 00:03:37.320 assurance of miners as well 00:03:37.320 --> 00:03:42.660 right so so the reason i think that's negligible yeah that's probably a very 00:03:42.660 --> 00:03:48.260 mispronunciation of that word negligible yeah exactly it's because the only way 00:03:48.260 --> 00:03:52.140 to use that to your benefits as a developer in this case let's say you're a 00:03:52.140 --> 00:03:57.980 developer and you create this utxo set for assume utxo yeah and you say hey 00:03:57.980 --> 00:04:03.070 i've actually on my address i got a thousand billion million bitcoins The only 00:04:03.070 --> 00:04:07.870 way you can ever benefit from that is if in a block after that, a miner is 00:04:07.870 --> 00:04:11.650 willing to include it. So you're still relying on proof of work in that sense. 00:04:11.790 --> 00:04:16.390 Unless you find an idiot that sells zero confirmation Lambos. I mean... 00:04:16.390 --> 00:04:21.930 Right. So I guess that would be the one example where it would be a difference. 00:04:22.290 --> 00:04:25.450 But a zero confirmation Lambo person, you can just double spend. 00:04:25.870 --> 00:04:28.910 Yeah, there are probably other ways to screw that person up, but that's true. 00:04:29.480 --> 00:04:34.620 All right, so far, last episode. Another episode with extra Ruben. This time 00:04:34.620 --> 00:04:39.420 we're not going to discuss one of your proposals. You're just here to discuss a 00:04:39.420 --> 00:04:45.100 proposal with us. And the proposal we're discussing this week is Utreexo. 00:04:45.260 --> 00:04:50.800 That is correct. Utreexo. And the tree is for a tree, the thing that grows in the forest. 00:04:51.500 --> 00:04:55.720 Did you know that was the pun, Ruben? I didn't realize. 00:04:56.120 --> 00:05:01.500 Well, I mean, I heard Tadge say that, so I was aware of that. 00:05:01.900 --> 00:05:06.400 But there is a very specific reason why I was kind of enthusiastic to talk about 00:05:06.400 --> 00:05:10.000 it. Well, one, I've kind of like used it in one of the things I've been working 00:05:10.000 --> 00:05:14.920 on. So I kind of like Utreexo a lot conceptually. But there is also a close 00:05:14.920 --> 00:05:19.880 friend of mine, Calvin Kim, who was a regular attendee of the Seoul Bitcoin 00:05:19.880 --> 00:05:25.340 meetup. who is now actively working on Utreexo together with Tadge and i i told 00:05:25.340 --> 00:05:29.260 him i would shout out the other guys that are working on the project Janus 00:05:29.260 --> 00:05:32.640 Troelsen, which is apparently not a dutch person i think he's like german or 00:05:32.640 --> 00:05:37.700 something and Niklas Gögge, hopefully i pronounced it correctly but those are the 00:05:37.700 --> 00:05:42.560 four guys that are currently kind of working on uh Utreexo hopefully kind of will 00:05:42.560 --> 00:05:46.800 eventually get to a point where This can be useful for Bitcoin Core. But we 00:05:46.800 --> 00:05:50.340 should obviously start explaining what Utreexo is because we're just talking 00:05:50.340 --> 00:05:51.780 about the kind of conceptual idea right now. 00:05:51.780 --> 00:05:52.740 Oh, we've got to keep it exciting. 00:05:53.040 --> 00:05:55.060 Well, really quick, are these guys with DGLab? 00:05:55.160 --> 00:06:00.120 No, no, that's completely separate. Yeah. There's MIT. I'm not super familiar 00:06:00.120 --> 00:06:04.940 with this, but Tadge is with MIT. And then the other three guys are just working 00:06:04.940 --> 00:06:09.640 on this separately. So they're not involved with MIT or DGLab. DGLab mainly works 00:06:09.640 --> 00:06:12.340 on DLC. That's kind of one of their main projects. 00:06:12.520 --> 00:06:16.730 Okay. So Sjors, what problem are we solving? 00:06:17.740 --> 00:06:23.700 Problem, problem, challenge. So one of the constraints when 00:06:23.700 --> 00:06:28.480 you're syncing a new Bitcoin node, we talked about sync a couple of times, is the 00:06:28.480 --> 00:06:32.640 amount of RAM memory you have. Now, it's not a hard constraint. You don't need a 00:06:32.640 --> 00:06:37.250 lot of RAM, but if you want to sync it fast, you do. And the reason is this thing 00:06:37.250 --> 00:06:41.450 called the UTXO set. The UTXO set is the list of coins that you own. We talked 00:06:41.450 --> 00:06:46.070 about that last time, I guess. But every time the new block comes in, what you do 00:06:46.070 --> 00:06:49.890 is for every transaction in the block, you check if it's spending something that 00:06:49.890 --> 00:06:55.570 exists, namely one UTXO. And so in order to check if something exists, 00:06:55.910 --> 00:07:00.490 well, it has to be somewhere. It has to be in a database of sorts. And where is 00:07:00.490 --> 00:07:05.600 that database? Well, if that database is sitting in your RAM memory, That's 00:07:05.600 --> 00:07:10.360 extremely fast. If on the other hand, that database is sitting on your hard disk, 00:07:10.520 --> 00:07:12.660 if it's an SSD drive, it's meh. 00:07:12.900 --> 00:07:17.920 What you mean is it's much faster to look up if it's in there. If it's in your 00:07:17.920 --> 00:07:22.000 RAM, then your computer will be able to look it up within, well, I don't know how 00:07:22.000 --> 00:07:25.460 fast, but faster than if it's on your drive. It's 00:07:25.460 --> 00:07:29.240 probably at least 10 times faster than if it's on your SSD drive. And if you're 00:07:29.240 --> 00:07:33.960 using a magnetic drive, it's even worse. And then the other side of it is... once 00:07:33.960 --> 00:07:38.280 you create this new coin, which the transaction does on the output side, it has 00:07:38.280 --> 00:07:42.300 to store that. So it has to write it somewhere on the disk, which is also slow. 00:07:42.380 --> 00:07:47.080 And if you have a magnetic spin disk, then it has to move to read somewhere and 00:07:47.080 --> 00:07:51.460 it has to move somewhere else to write again. These are gigabytes apart. So 00:07:51.460 --> 00:07:52.220 that's horrible. 00:07:52.460 --> 00:07:56.680 So to make it very concrete, I guess the biggest difference you would notice when 00:07:56.680 --> 00:08:02.040 you're syncing a new node and if you would somehow be able to keep the UTXO set 00:08:02.040 --> 00:08:05.410 in RAM, It will only take, I don't know, a couple hours. 00:08:05.650 --> 00:08:08.790 But it depends on your computer. I have a somewhat recent MacBook Pro, and I 00:08:08.790 --> 00:08:11.070 think I can sync the whole chain in five hours. 00:08:11.270 --> 00:08:12.390 If you keep it in RAM. 00:08:12.750 --> 00:08:18.060 But that takes about 11 gigabytes of RAM. But if you do it on, say, a typical 00:08:18.060 --> 00:08:22.360 Raspberry Pi, you might have, I don't know, two gigabytes these days, maybe four. 00:08:22.880 --> 00:08:26.340 So that means you're going to sync the chain and you're going to keep as much as 00:08:26.340 --> 00:08:30.720 possible in RAM. But at some point it overflows, the UTXO set. And then usually 00:08:30.720 --> 00:08:34.910 what it does is it writes everything to disk. clears everything, and then it 00:08:34.910 --> 00:08:40.270 starts caching again. And this takes a long time. It can take days on these machines. 00:08:40.470 --> 00:08:45.230 Right. So the point being, as you can keep more of the UTXO set in RAM, you'll 00:08:45.230 --> 00:08:51.130 sync faster, or your node will just work faster, operate faster in general. So it 00:08:51.130 --> 00:08:55.430 would be good if we could somehow decrease the size of the UTXO set. 00:08:55.630 --> 00:08:59.030 Well, we can't decrease the size of the UTXO set. That's kind of the problem. 00:08:59.110 --> 00:08:59.530 That's a bummer. 00:08:59.690 --> 00:09:01.590 There is a limit on the size of blocks. 00:09:02.510 --> 00:09:03.690 Well, it can decrease. 00:09:04.110 --> 00:09:08.390 Four megabytes. It can decrease. It's just not something we can do. Yeah, it 00:09:08.390 --> 00:09:09.730 decreases when people spend... 00:09:09.730 --> 00:09:14.210 I don't know how many UTXOs you own. I bet a lot. So maybe you could play a part 00:09:14.210 --> 00:09:15.450 in decreasing the UTXO. 00:09:15.770 --> 00:09:21.170 Millions of UTXOs on testnet. No. So the idea is that if you're spending more 00:09:21.170 --> 00:09:24.890 coins than you're creating, then obviously the number of UTXOs goes down and the 00:09:24.890 --> 00:09:30.100 RAM usage goes down. But there's a lot of junk in the UTXO set. Because there 00:09:30.100 --> 00:09:34.520 were people in the old days that created transactions to multi-sig addresses that 00:09:34.520 --> 00:09:38.920 were fake just in order to put pictures of Obama in the blockchain. And those are 00:09:38.920 --> 00:09:43.280 all sitting in your RAM because your node has no idea that they're nonsense. But 00:09:43.280 --> 00:09:46.800 the other thing is if we expect everybody in the world eventually to use Bitcoin 00:09:46.800 --> 00:09:52.560 and everybody to have at least one or two UTXOs, then, well, that's a lot of 00:09:52.560 --> 00:09:56.940 RAM. That's like 7 billion people. And there's really no limit to how big that 00:09:56.940 --> 00:10:00.440 can get. There's no constraint. It might take a while because it takes a lot of 00:10:00.440 --> 00:10:04.720 fees to create all these transactions, but eventually it could take as much RAM 00:10:04.720 --> 00:10:08.360 as, you know, there's no limit. And we don't like things that don't have a limit. 00:10:08.840 --> 00:10:10.320 Unbounded stuff, it's a bit bad. 00:10:11.180 --> 00:10:15.640 Yeah, you mean the UTXO set can get as big as it will get until the point where 00:10:15.640 --> 00:10:18.380 not everyone can use it, can sync it from RAM. 00:10:18.420 --> 00:10:22.540 Fewer and fewer people will have enough RAM to sync it quickly, and that could 00:10:22.540 --> 00:10:23.740 become a problem, right? 00:10:24.400 --> 00:10:29.520 Okay, so you agree it's a problem, not just a challenge, it's a problem, Sjors. 00:10:29.760 --> 00:10:30.820 Now, how do we solve it? 00:10:30.920 --> 00:10:36.550 Yeah, it's a challenge, obviously. Well, one way to solve it is Tadge Dryja's 00:10:36.810 --> 00:10:41.910 proposal, the Utreexo. And the idea there, I guess that's what we'll need to 00:10:41.910 --> 00:10:43.150 explain, right? How that works. 00:10:43.390 --> 00:10:45.970 Well, Ruben wanted to explain it to us. So let's hear it. 00:10:46.110 --> 00:10:50.810 I first wanted to say that I thought, Aaron, your analogy with basically saying 00:10:50.810 --> 00:10:55.450 that it's pruning for the UTXO set. I thought that was a very good analogy where 00:10:55.450 --> 00:10:57.290 currently we have pruning in Bitcoin. 00:10:57.510 --> 00:10:58.710 This was an off-record analogy. 00:10:59.010 --> 00:11:03.520 Yeah. Now it's on record. Now it's on record. Yes, I'm repeating something that 00:11:03.520 --> 00:11:07.600 you told me before the show. So with Bitcoin, currently you have pruning in the 00:11:07.600 --> 00:11:12.560 sense that you take a block, you process it, you extract the UTXO set out 00:11:12.560 --> 00:11:15.980 basically from all the blocks. And then that's all that you keep. You only keep 00:11:15.980 --> 00:11:19.440 the UTXO set. And then you can throw everything else away. And that's called 00:11:19.440 --> 00:11:24.560 pruning. There is a downside, which is that then you don't have the blocks. So if 00:11:24.560 --> 00:11:28.600 you want to prove to another person that the UTXO set is valid, you don't 00:11:28.600 --> 00:11:31.480 actually. You can't actually give them the blocks, but the assumption is that 00:11:31.480 --> 00:11:34.420 somebody else will have the blocks, so it's fine. And here, what you're pruning 00:11:34.420 --> 00:11:39.040 is something else. You're pruning UTXO sets, and you're essentially taking out 00:11:39.040 --> 00:11:43.040 all the, you're throwing away all the transactions, and you're just keeping a 00:11:43.040 --> 00:11:47.320 Merkle root. And inside of that Merkle root is basically a commitment. Every 00:11:47.320 --> 00:11:53.120 single UTXO is committed in there, and you only keep the Merkle proofs of the 00:11:53.120 --> 00:11:55.360 UTXOs that you care about, that you own. 00:11:55.760 --> 00:11:57.100 What is a Merkle root? 00:11:57.220 --> 00:12:00.620 Yeah. Or maybe to put it in another way, normally when somebody sends you a 00:12:00.620 --> 00:12:06.240 transaction, the transaction says, I'm spending this input. And you, as the 00:12:06.240 --> 00:12:10.600 person running a node, has the responsibility to check whether that input exists 00:12:10.600 --> 00:12:13.680 in your own database. And you're flipping this around and you're telling the 00:12:13.680 --> 00:12:17.540 other node, I have no idea which coins exist because, you know, I don't have RAM. 00:12:17.820 --> 00:12:22.060 You proved to me that this coin actually existed. Yeah. And that's what you used 00:12:22.060 --> 00:12:26.460 this Merkle proof for. So the burden of evidence is reversed here. You need to 00:12:26.460 --> 00:12:30.080 prove that a transaction exists. And then the question is, how are we going to do that? 00:12:30.300 --> 00:12:33.720 Okay, so we're reversing the burden of proof. Usually when you're sending a 00:12:33.720 --> 00:12:39.530 transaction, when I send a transaction to you, Sjors, then you check inside your 00:12:39.530 --> 00:12:43.970 node in the database with your UTXO set whether the transaction is spending valid 00:12:43.970 --> 00:12:49.400 UTXOs. Yes. Now... I'm actually going to have to provide you with the proof that 00:12:49.400 --> 00:12:55.080 my transaction is spending existing UTXOs. However, you still need something in 00:12:55.080 --> 00:13:00.680 order to make sure that my proof is valid. And that's this Utreexo, 00:13:00.800 --> 00:13:02.300 which is a hash tree. 00:13:02.460 --> 00:13:03.760 Yes, a Merkle tree. 00:13:04.040 --> 00:13:06.140 Right. So what is this and how does it work? 00:13:06.240 --> 00:13:10.320 So it's kind of nice. All the UTXOs that are in existence would be put into this 00:13:10.320 --> 00:13:14.300 tree. And everybody can construct this tree if you replay the whole blockchain. 00:13:14.920 --> 00:13:16.880 But the question is... 00:13:16.880 --> 00:13:21.160 It's not an actual tree, though, is it? It's not an actual tree. Do you give it 00:13:21.160 --> 00:13:22.260 water? No. 00:13:22.700 --> 00:13:27.400 Basically, what the tree would look like is you have the first UTXO, and then the 00:13:27.400 --> 00:13:31.100 second UTXO right next to each other. And then you take the hash of those two, 00:13:31.220 --> 00:13:34.960 basically combined. And that is one new hash. So you see this little pyramid 00:13:34.960 --> 00:13:40.130 shape. And you can do that again for another two. UTXOs that exist. 00:13:40.850 --> 00:13:45.470 They're their own little mini tree. But now you see, oh, there's two trees. Let 00:13:45.470 --> 00:13:46.690 me just combine those two trees. 00:13:47.170 --> 00:13:49.790 Two hashes, and you're combining these two hashes. So 00:13:49.790 --> 00:13:54.770 now you have four UTXOs, and two of them are shared, and then those two are 00:13:54.770 --> 00:13:55.270 shared again. 00:13:55.470 --> 00:13:56.970 Yeah, so you end up with one hash. 00:13:57.130 --> 00:14:02.050 You end up with one hash. Now the key here is that these things are so-called, I 00:14:02.050 --> 00:14:07.870 believe, perfect trees, which means that they are always a multiple of two. 00:14:08.400 --> 00:14:14.160 Right, yeah. So now the challenge is that for every new block, this tree needs to 00:14:14.160 --> 00:14:20.140 be updated, right? Because we have one big tree for all of the UTXOs. Now a 00:14:20.140 --> 00:14:24.980 new block is found. It includes all sorts of new transactions. So new UTXOs exist 00:14:24.980 --> 00:14:29.080 and old UTXOs are destroyed. So now we need a new tree. 00:14:29.580 --> 00:14:34.440 Yeah, well, it's even more than one tree, right? It is a forest. Because every 00:14:34.440 --> 00:14:38.880 tree has to be a multiple of two, So there can be four things at the bottom or 00:14:38.880 --> 00:14:42.960 eight things at the bottom or 16 things at the bottom. When you have a number of 00:14:42.960 --> 00:14:46.420 transactions that doesn't fit that way, you'll have multiple trees that look like 00:14:46.420 --> 00:14:50.570 that. So you have a collection of trees. for which you really only need to 00:14:50.570 --> 00:14:55.690 remember the top hashes. And now the question is, how do you add something to that tree? 00:14:55.830 --> 00:15:00.050 So you might have one tree with 16 at the bottom, one tree with 8 at the bottom, 00:15:00.670 --> 00:15:05.670 one tree with 2 UTXOs at the bottom. Yeah, exactly. So you have multiple trees. 00:15:06.390 --> 00:15:12.100 And now, in order to prove that something is in this tree... And also to 00:15:12.100 --> 00:15:16.640 replace it with, say, the output, because basically you destroy one UTXO that 00:15:16.640 --> 00:15:20.060 you're spending and you create a new UTXO that you're creating. So you can 00:15:20.060 --> 00:15:25.600 actually take the UTXO that you're spending out of the tree. and then put the new 00:15:25.600 --> 00:15:31.000 one into the tree. And in order to do that, you need to provide, you need to 00:15:31.000 --> 00:15:34.740 recalculate the tree, and you do that by knowing its neighbors. So the way you 00:15:34.740 --> 00:15:39.880 prove that something is inside a Merkle tree is to say, well, at the bottom of 00:15:39.880 --> 00:15:44.300 the tree, there's these two pairs, and I'm going to give you the other side. And 00:15:44.300 --> 00:15:47.240 then at the next level, again, there's a pair, and I'm going to give you the 00:15:47.240 --> 00:15:51.930 other side, and again, and again, and again. And that proves that something is 00:15:51.930 --> 00:15:55.550 actually in the tree. And that's exactly the same information that you need to 00:15:55.550 --> 00:15:57.390 put something else at the bottom of the tree. 00:15:57.590 --> 00:16:03.070 Right. So by putting something else at the bottom of the tree, to be clear, the 00:16:03.070 --> 00:16:07.390 entire tree changes, or at least the one hash you end up with changes. Like 00:16:07.390 --> 00:16:10.670 you're just computing a whole new tree. But you're able to do that because you 00:16:10.670 --> 00:16:14.910 have all the data you need. Yes. So you can add things to the forest and you can 00:16:14.910 --> 00:16:17.890 remove things from the forest. It's actually possible. It's actually easier 00:16:17.890 --> 00:16:21.820 than... I thought it would be when I saw Tadge explain it. I don't know if it's 00:16:21.820 --> 00:16:24.160 going to be easy when people hear us explain it. I would 00:16:24.160 --> 00:16:29.080 recommend looking at Tadge explain it after you hear us explain it. Because you 00:16:29.080 --> 00:16:33.060 need to see it. Yeah, visuals. Visuals really help. Exactly. I think 00:16:33.060 --> 00:16:36.620 his presentations are great. He's very good at explaining it. And yeah, he has 00:16:36.620 --> 00:16:39.700 slides. So that's a lot easier than what we're doing. We're trying to explain it 00:16:39.700 --> 00:16:43.340 in words, especially in Merkle Trees. I think it's great if you have an actual 00:16:43.340 --> 00:16:43.820 picture there. 00:16:44.100 --> 00:16:47.550 But now the idea is that you're not tracking everything, right? Yeah. So you 00:16:47.550 --> 00:16:50.830 could, when you're syncing the blockchain, keep track of the entire tree, but 00:16:50.830 --> 00:16:54.710 then you need a lot of RAM, just like in the original scenario. But what you'll 00:16:54.710 --> 00:16:58.010 actually do is you're going to remember the top of every tree, and there might be 00:16:58.010 --> 00:17:01.930 10 or 20 or whatever trees. And that's all you're going to remember. And when 00:17:01.930 --> 00:17:05.890 somebody has a new transaction that you want to verify, they need to give you the 00:17:05.890 --> 00:17:09.870 Merkle proofs for all the inputs that they're spending. So they prove that they 00:17:09.870 --> 00:17:14.800 exist. And then they also tell you which outputs are there. which are going to be 00:17:14.800 --> 00:17:19.240 swapped in at the same places where those inputs were, plus new trees if it's 00:17:19.240 --> 00:17:19.700 making more. 00:17:19.840 --> 00:17:23.660 Yeah, but in the blocks, right? Yeah. Yeah, so that's really, I think, the very 00:17:23.660 --> 00:17:29.400 elegant side of Utreexo, where the same proofs that are proving that 00:17:29.400 --> 00:17:35.280 these UTXOs are in the UTXO set are also exactly what you need to remove them 00:17:35.280 --> 00:17:41.260 from the set, update your root hash, and add the new UTXOs 00:17:41.260 --> 00:17:44.620 from the latest block. So that works out quite elegantly. 00:17:44.840 --> 00:17:50.440 Okay, so in an ideal scenario, let's say what we've been explaining so far is 00:17:50.440 --> 00:17:54.920 sort of the ultimate version of Utreexo, so let's stick with that for a minute. 00:17:55.120 --> 00:18:00.040 So I wanted to send a transaction to the network and you, Sjors, you had a node 00:18:00.040 --> 00:18:04.950 and you wanted to validate the transaction. You have this tree in your own... in 00:18:04.950 --> 00:18:07.530 your RAM, apparently. That's what's nice about it. 00:18:07.570 --> 00:18:09.210 I have the top of the trees in my RAM. 00:18:09.450 --> 00:18:09.590 Yeah, 00:18:10.910 --> 00:18:15.130 exactly. So now I want to send this transaction. So now it's my responsibility to 00:18:15.130 --> 00:18:19.940 send to you the transaction as well as... 00:18:20.790 --> 00:18:25.410 the proof that the transaction is valid, which also includes information for you 00:18:25.410 --> 00:18:28.210 so you know where to find it in the forest, right? 00:18:28.390 --> 00:18:31.790 Exactly. You need to prove to me that the things you are spending are in the 00:18:31.790 --> 00:18:34.210 forest because I forgot what the forest looked like. 00:18:34.490 --> 00:18:38.310 Right. All right. So that's me sending the transaction with the proof. Now, the 00:18:38.310 --> 00:18:42.410 other way you could get the transaction is if it's already in the block. So if a 00:18:42.410 --> 00:18:47.940 miner mines a block and the transaction is in there, you still have your Utreexo 00:18:47.940 --> 00:18:50.890 thing or your nodes. But how do you now get the proof? 00:18:51.170 --> 00:18:54.770 Right, because if you spend the transaction, you're not going to talk to every 00:18:54.770 --> 00:18:58.250 node that ever downloaded the block to send that proof around. So how does that 00:18:58.250 --> 00:18:58.950 proof get to the node? 00:18:58.990 --> 00:19:00.930 That wouldn't scale very well, at least. 00:19:01.170 --> 00:19:05.870 No. Well, what you would probably want to have is something called a bridge node. 00:19:06.500 --> 00:19:07.420 A bridge node. 00:19:07.620 --> 00:19:12.540 A bridge node would be a node that has the actual UTXO set, the old-fashioned 00:19:12.540 --> 00:19:18.300 way, so it has lots of RAM, or it's just slow, and it produces all these proofs, 00:19:18.360 --> 00:19:20.120 and it sends them around to whoever wants them. 00:19:21.370 --> 00:19:26.110 Yeah, so what essentially happens is that when this bridge node receives a 00:19:26.110 --> 00:19:30.750 transaction, and this transaction does not have a Merkle proof proving the 00:19:30.750 --> 00:19:36.330 inclusion in the Utreexo root, This bridge node basically just takes the proof 00:19:36.330 --> 00:19:41.070 that they have and they attach it to the transaction. And now they send it on to 00:19:41.070 --> 00:19:45.910 other Utreexo nodes. It's a bridge between Utreexo nodes and non-Utreexo nodes. 00:19:46.050 --> 00:19:51.050 Yeah, but they could also construct the proof themselves, right? If they see a 00:19:51.050 --> 00:19:53.910 certain transaction is included in a block, they can just figure it out. 00:19:53.910 --> 00:19:56.710 That's right. Every node, there's nothing secret here. So if you have the 00:19:56.710 --> 00:20:01.390 original UTXO set in memory somewhere, you can construct the proof for any 00:20:01.390 --> 00:20:01.810 transaction. 00:20:02.090 --> 00:20:06.190 And they have the entire tree, essentially. So the entire UTXO tree that you 00:20:06.190 --> 00:20:09.350 create and then prune, they just don't prune it, essentially. So they just have 00:20:09.350 --> 00:20:14.910 the full UTXO set, basically the UTXO set with all the Merkle proofs connecting 00:20:14.910 --> 00:20:19.430 to it. So then they can just take any UTXO in there. and create a proof from it 00:20:19.430 --> 00:20:22.450 and just send it on or for an entire block or whatever. Right. 00:20:22.710 --> 00:20:27.390 So what would happen in practice is your node would see a transaction in a block 00:20:27.390 --> 00:20:30.270 and it would wonder, hmm, is there actually proof for that? I never saw the 00:20:30.270 --> 00:20:33.610 transaction before. And you would request it from a bridge node. 00:20:33.910 --> 00:20:37.790 Yeah, my guess is when you get the whole block, you're going to call a bridge 00:20:37.790 --> 00:20:39.950 node and say, give me the proof for that entire block. 00:20:40.540 --> 00:20:44.980 Or just all of them? Yeah. Why not just the ones you need, the ones you haven't 00:20:44.980 --> 00:20:45.440 seen before? 00:20:45.580 --> 00:20:49.280 My guess is that's too much back and forth, because if you have to call a node 00:20:49.280 --> 00:20:53.280 for every single individual transaction, then that's a lot of overhead, whereas 00:20:53.280 --> 00:20:56.840 just downloading a couple hundred kilobytes is easier. 00:20:57.000 --> 00:20:58.520 Anyways, that's an implementation detail. 00:20:58.780 --> 00:21:02.580 Yeah, but I think this is just an automated process, right, where you just 00:21:02.580 --> 00:21:07.230 connect. to the network but like the problem is like when you're the first 00:21:07.230 --> 00:21:11.290 Utreexo node right and you're pruning all the data and then everybody else on the 00:21:11.290 --> 00:21:15.790 network is an old-fashioned node like the way we run it today nobody's going to 00:21:15.790 --> 00:21:20.390 give you the proofs right so what you need is at least a single bridge node so at 00:21:20.390 --> 00:21:24.030 least you can connect to that one and then other people are connecting to the 00:21:24.030 --> 00:21:27.370 bridge node because the bridge node basically speaks both languages right they 00:21:27.370 --> 00:21:31.750 speak the Utreexo language and they they speak the old-fashioned language yeah so 00:21:31.750 --> 00:21:35.750 they translate for you and as long as one bridge node exists it kind of can 00:21:35.750 --> 00:21:39.030 bootstrap the network essentially but they don't they don't have to have like 00:21:39.030 --> 00:21:43.330 special rules it's like from the perspective of the Utreexo node the bridge node 00:21:43.330 --> 00:21:47.050 is just also Utreexo node and from the perspective of the old-fashioned nodes 00:21:47.050 --> 00:21:48.690 it's just an old-fashioned node 00:21:48.690 --> 00:21:52.250 right that's another point so yeah you don't need everybody to do this 00:21:52.250 --> 00:21:56.560 translation yeah Only one person needs to do it or a couple. The other nodes know 00:21:56.560 --> 00:22:01.380 how to relay that information even if they can't produce it. So that's good news. 00:22:01.660 --> 00:22:05.260 Can we have a future without bridge nodes? 00:22:05.560 --> 00:22:09.260 Well, we should point out what the problem is with these bridge nodes because 00:22:09.260 --> 00:22:14.800 they are nice people. We don't want to rely on nice people. That's not how we roll. 00:22:16.020 --> 00:22:18.340 So because nice people can stop being nice. 00:22:18.560 --> 00:22:20.440 Or they can be forced to stop being nice. 00:22:20.560 --> 00:22:25.080 Or they can just disappear or run out of battery. Yeah. So yeah, then you can 00:22:25.080 --> 00:22:28.660 look at the longer term picture. Like could this, you know, if people like this, 00:22:28.780 --> 00:22:33.640 give any advantages or even if they don't like it, if the UTXO set just becomes 00:22:33.640 --> 00:22:38.660 insane and it just takes too long to sync on any normal computer, then you could 00:22:38.660 --> 00:22:44.350 basically make a soft fork which contains the proofs. So the proofs. become part 00:22:44.350 --> 00:22:47.770 of the blockchain. Just like SegWit added a whole bunch of data to blocks, you 00:22:47.770 --> 00:22:52.850 could then add these proofs to the blocks, making the blocks even bigger. But the 00:22:52.850 --> 00:22:57.510 trade-off there is you have more bandwidth, but you have less RAM need. 00:22:58.210 --> 00:23:01.950 Yeah, the reason this could be done as a soft fork, same with SegWit, is because 00:23:01.950 --> 00:23:07.890 you'd include the hash of... the proofs somewhere in like 00:23:07.890 --> 00:23:12.030 the Coinbase transaction or something like that. Old nodes just won't notice 00:23:12.030 --> 00:23:16.850 anything interesting, but upgraded nodes will see like a whole tree which they 00:23:16.850 --> 00:23:19.850 share with each other, which does make the blocks a bit bigger for them. 00:23:20.210 --> 00:23:23.090 Yeah, so old nodes keep doing what they're doing. They get blocks, they can 00:23:23.090 --> 00:23:25.970 verify those blocks because nothing changes about the transactions in the blocks. 00:23:26.270 --> 00:23:30.350 New nodes will save some RAM memory. They'll use that extra data. They'll 00:23:30.350 --> 00:23:34.020 download that extra data. and they'll use it. That's generally the idea. 00:23:34.440 --> 00:23:40.300 Yeah. So personally, at least, I think this is not likely to happen until we 00:23:40.300 --> 00:23:44.920 really get a UTXO set bloating issue where the UTXO set becomes so big that 00:23:44.920 --> 00:23:48.960 people start liking this trade-off to the point where it's preferable. I think as 00:23:48.960 --> 00:23:52.760 long as we're not at that point, I don't think we'll see this as a soft fork, but 00:23:52.760 --> 00:23:54.200 that's my personal view. 00:23:54.340 --> 00:23:56.160 I do want to point out some cool things you can do with it. 00:23:56.500 --> 00:23:58.100 Yes. Tell us the bullish. 00:23:58.490 --> 00:24:02.730 The bullish part. You know, I'm all just copy pasting from what Tadge said. We 00:24:02.730 --> 00:24:07.830 like to do that. Basically, because you don't need a lot of RAM, you can start 00:24:07.830 --> 00:24:12.410 doing things in specialized hardware like an ASIC. Because one of the things 00:24:12.410 --> 00:24:16.190 that's kind of hard to do in an ASIC is lots of memory. And having specialized 00:24:16.190 --> 00:24:20.310 hardware, maybe it's a part of your chip. So maybe, you know, Bitcoin becomes the 00:24:20.310 --> 00:24:26.270 standard and every phone that you buy has a CPU and, you know, has 00:24:26.270 --> 00:24:29.810 a... little mini processor right next to it that just checks all the bitcoin 00:24:29.810 --> 00:24:34.930 validation rules and because it's custom silicon it might be able to validate the 00:24:34.930 --> 00:24:37.830 entire blockchain at the speed that it can download it which is pretty 00:24:37.830 --> 00:24:41.070 an asic for regular nodes exactly right 00:24:41.560 --> 00:24:45.460 So not to mine coins, but to verify coins, which would be cool. And then, you 00:24:45.460 --> 00:24:48.880 know, you have the protocol literally set in stone or at least set in silicon. 00:24:49.280 --> 00:24:53.020 And of course, soft forks can still happen under that circumstance. But if 00:24:53.020 --> 00:24:56.400 somebody wants to do a hard fork, you'd have to break all the node hardware, not 00:24:56.400 --> 00:25:00.320 just all the mining hardware. So that's a nice extra barrier to not do hard 00:25:00.320 --> 00:25:02.300 forks. It's an ossification of network. 00:25:02.740 --> 00:25:05.620 It's also not perfect for soft forks. Is that what you just said, Ruben? 00:25:05.800 --> 00:25:07.040 No, I mean, that's what... 00:25:07.040 --> 00:25:11.040 No, no. It makes it harder to verify soft forks because if you didn't... if you 00:25:11.040 --> 00:25:15.120 don't have to verify the soft fork but you soft fork but you can't verify the 00:25:15.120 --> 00:25:18.880 soft fork at least not with the accelerated hardware yeah so your computer would 00:25:18.880 --> 00:25:22.420 have to slow down to check all the new rules whenever it encounters it. 00:25:22.840 --> 00:25:25.880 Yeah, or you have to buy a new phone because the soft fork happens. 00:25:26.420 --> 00:25:26.860 Exactly. 00:25:27.740 --> 00:25:31.160 If your phone is too old, maybe it's possible, right? That's what happens now. 00:25:31.260 --> 00:25:34.380 People buy new phones every couple of years, so maybe it's not too much to ask. 00:25:34.580 --> 00:25:39.980 The other thing is, we talked last week about this assume UTXO thing, where one 00:25:39.980 --> 00:25:44.480 of the problems is, now when you start, you still need to get that three gigabyte 00:25:44.480 --> 00:25:49.170 thing from somewhere. And if this thing becomes 100 gigabytes, you have to get 00:25:49.170 --> 00:25:55.110 that from somewhere. But now we have, with this proposal, we just have a 00:25:55.110 --> 00:26:01.030 kilobyte. So you can put the entire UTXO set, you can represent it in 00:26:01.030 --> 00:26:06.450