CESC2020: Bitcoin Nodes: Decoupling trust and storage with Utreexo

2020 Ford F150. Hello, I'm tired of driving to talk about Bitcoin notes. Decoupling trust and storage with you tree x o m. I t digital currency initiative. Previous work. I've done. Is the author of the lightning Network paper working on What is a new? You know, what are these things called nodes in Bitcoin, how they work? I'm going to talk about the history of big, Pocono State and verification have a fit together. Verifying the state of Bitcoin with minimal trusted data. And then you drink soda when they're designed properties,

Awesome notes. What's a note from Latin? Notice not, I don't know if that really wise but serious or the dots that are connected by the Bitcoin similar networks. These are the endpoint. These are the computers running. What's the number to well, mainly sends and receives transactions and if the hope is that everyone agrees on Google, right? So you send these transactions to move coins around and ideally when it works, everyone agrees on who owns. What do you do this? There's a bunch of things that nodes do

specifically to propagate messages, send surf, blocks, check, proof-of-work, check transactions with Steve coins and keys. In the easiest to hardest who probably getting messages. It's really easy from a computer science, one of you, you don't have to actually have much memory or storage. You don't need to know what a signature is people to send you messages and you could have signed them around people but you don't need to actually validate sending Queens is actually easy. So if you have the information needed to send the Bitcoin signing is very quick,

you don't actually need to know Watch about the system this sign and broadcast, the transaction serving blocks. So if you're a full node and you give blocks and archived know to give blocks other people, again, it's actually really easy. You don't have to verify anyting. When people request a block you requested by ass. You can just send the walk out and have no idea what it sort of like being a web server. That I'm checking the work to see if a block has the ballad of work, a little more complex, but probably tastes really quick and then you get to the hard part, right? Checking transactions

and signatures in order to receive a coin. You know, whether the only difference between checking the transaction receipt of the point is who ends up being the beneficiary. But once you check all the transactions, you can buy To verify the transaction is the hard part. People are sending points and are these transaction, okay? So you need to know so many things about this. So much data goes behind. Whether a transaction is Ballard a transaction in isolation. You can't tell, right? Cuz it's

at the right place, has enough of them. What are the cheese and other signatures? Okay, and there's so many different verification. Check just looking it up to 300 bikes. Looking at an isolation, you don't know if it's you need in practice today you have to have gigabytes in gigabytes of space to to verify what single transaction political history. Right? So the blockchain and sell is history. But you only need the blockchain to get to the current state of who owns what? And that's change date, or utxo set to keeping track of the

currency is hard, and you can't directly share it with other. So if you say, oh I've got this current utxo set, let me give it to you. There's no messages to do that. Really, there's no way to export uup exocet, because you can't write. I know that here is all the list of who owns what of this address as this year. This you hit, so at this point, but I can't share that have to share the actual box Natural History. So keeping track of history is easier, right? If you just want to Archive the blocks compute much and it's only really done to help others. The only reason you need to store

blocks is to give them another people. But your current state is the correct. Can you get someone else to do the hard part right? Can, can we we can throw away the history right to approve knows other than common for many years. Were you play through the history and then delete it? Can we do the same thing with the state song? There's a new no type that I'm working on call nutrients. So I will call it a full moon, it's fully verifies, but it does not contain the full stay in the system.

But you don't keep track of the whole state of the world. What? You can't look up. The coins on your desk. You don't have a database at all. Really. So instead the people spending the coins or when someone's giving you a transaction, they need to prove that those coins exist makes spending one's a little harder, but it makes it easier. Who's sign is instead of keeping track, right by The Ledger of who owns, what which is built by the blockchain, who sent what we're keeping track of the full lecture. Keep track of your own points and approved the days. And then you

said, I keep a hash of everything else. Writes all those seventy million other UT EXO's and Bitcoin transaction outputs you. Just keep this hash of that is very small and then when people want to send coins, they prove that they're going to Exist by giving you a proof there coins are in this actually you already accumulated. Just basically cryptographic construction where you can throw data into it, you can't get the babies for a win back out, but you can prove that you threw something into it. So

it's not in this bottomless box and you can throw as much data as you want them to it. You never get any, you know, throws money pictures, PDF images, for whatever you want to do this thing. But I'm like a hard drive, pull out the date of the things have been thrown it. And in this case are we also need to be able to delete things, right? We don't want to spend the same. So when you verify that something is in this, accumulator you also want to remove it the same time, which is like the only time you need to delete things on your coyness when you're proving them,

if I first. So it's only into the actual design of how this accumulator works. It's quite simple. It's basically a bunch of Myrtle trees. The only need to store the roof of the Smurf. So what say you want to add note to add items to this accumulator on a normal myrtle? Tree if you only know the route, you can actually have a new note and recompute the route because you don't even know how many things there are. It's maybe there's a hundred things in here and you want to add one? Well, it's not there. So what you do is instead have a forest of

perfect streets Okay, so let's say you have a forest with a single tree with four leaves. I've got one room there. What do you want? Okay, so now there's five elements so you keep one that has 4 in it than one that has a single one in it. So you got to run again. Now you have six elements these new to on their own level in, for their own tree. So you have two routes to represent. Six elements can combine music when you're when you're in this situation. You only know they sort of orange ones but you can come by

to get that. Now you got it and now you're back down to a single rupee you need so you can go to see if you're going to store log to. Ways to log number of ailments and practices log base, 2 / 2 because sometimes you don't have to not that complex. And if you notice, however, it's not too bad but you add sodas on the right. When you said a batch things together and find things together as necessary as you can. Whenever, whenever things are sort of on the

same road as that guy, and all these two things on Saint Row, fun together in a standard Market reconstruction. And then you're going to have you no longer login / 2 Deleting is a little more tricky. What's interesting is that if you sold a combined deletion and proving if it works really well, and in Bitcoin rate because the case is, you only need to delete things as soon as they've been proven and vice versa, one of your proven that exist, so show the sort of intuition you've got these.

So, here's an example where you had seven elements right in three routes you say, Okay, I want to delete the proof Brown a, to all the way up to You can say okay well I'm deleting to I'm going to move 6, right? 6 is this one that's off on its own 6 move to where to was. And now I recompute Route 903 through this part of the proof. I can recompute well, because I know ate it was also part of the. So now I got a new 12 where six has swapped in for the thing. Got deleted, this is great. I know the proof was exactly what I needed to. Recompute the route with this new

substitute almond. And similarly, let's say another example for those and I wanted to leave the same, but this number to this case, I don't have anything that can swap in, so it's like I'm going to do this. Well, the truth is again 3 and 8 in this case, nothing's going to take to his place. However, I do know what, 3 is probably too and if you look at it, while I got to Teresa Rite Aid exists, it can be at the old tree and three of us navigate to trees. So, the intuition is that you've got these proofs. And if there are basically these, these two cases for take these two

examples, actually work all the time because you either have an even number of leaves of the bottom or an odd. Number in the case, where you have an odd number that on one swaps in, If you haven't even number the sibling of the the even one, that was The Sibling of a note, that was deleted. It works and you can bash these delicious together and me, it's quite efficient. Delete and then you always have this log in over two number of routes, which ends up being a few hundred

always less than a kilobyte four billion or a billion utxo. You would never see the light of a sort of it. So the downsides all these, you get those that are getting spent need to be proven that they exist and not that they exactly what they are right? And what is the puppy scripted and all the other aspects can go into this. And the question is, who makes us connected or the other issue is? What if you're getting transactions from someone who has an upgraded, as a use the

software, they don't care about it went too well, you still need a bridge note. I know that stores all the troops and can stack on any proof instantly and push it over to a note that once these trips. So that's one of the hard parts of doing this. As you need to make a bridge notes, it works right at the end up being a couple gigabytes but you do need. Some of them is going to be propagated. Pierre. So you only need a few Bridge note to support potentially many nutrients Donuts. The other downside is there's more to

download. That's a big performance hit here, right? This is to be a lot faster because you don't need to do any disc access. All the data you need to verify. It's right there by 7 most cases. This is faster, but if you're really bandwidth constraints and the worst case you can download with actually twice as much data. So right now, the Bitcoin blockchain is about 300 GB. This could potentially make it six hundred 650. It is a lot you can get that much lower.

How do you minimize this extra download over? You can attach the proofs and I will go into the, the diagrams. But you can see that you got these big merkel's, raising elements of them are moving around. Kind of every block things change, I never block your deleting on, no deer moving things around three or four thousand in a single block. The vast majority are unchanged of parts of the tree that don't change or really we're doing is remember and parts of recently changed because things that most recently changed are likely to change. Again if you just have a

new utxo a new outfit that's just been created a transaction will be deleted and spent very rapidly. In fact we can do better than like most recently is regular Cashing Out Riddim These things have been created recently, I'm going to keep him in Ram or not flushing the desk. Or in this case, keep them in Ram and not require approved because the blocks in it snow before it. So they'll know what you're downloading come from cancer to give you hints and tell you you're as what to keep in your ass because this is going to get the whole history,

you can have this possible. You can look into the future fun graphs that sort of shows the lifetime of these utxo s0 because it's a log scale graph. But when you're here means that this is the number of utx cells that lived a single block wall. So they are created in an unblocked in and then spent in black and white one and that is the most popular most popular with zero and then one of the coins, many of the UK has lived, a short amount of time and then many of them, you know, as of the trails off will live a long time ago.

This is so, you know, optimize Herbalife. I have a good cashing. If I just remember Ten blocks ahead, I get something like that of all the transaction invoice. So you can do is the more memory you dedicate to cashing. These proofs of the less proof you have to download total. So you actually need something like, 11, something gigabytes to not need any proof at all, which is worse than just holding the whole you jacked up that. So once you're getting into it, you know, 6 8 gigs, this whole point is somewhat lost but where you

can also, see, is it right in the beginning, you drop real fast. So, if you only have a few hundred megabytes of memory to dedicate to cashing, you will significantly reduce the number to download over honey. Oh, let's see something like this is the look at him. So the actual way we do it is you look at had a hundred block. Look ahead, $1,000. This is a bit of data but the new stuff looks about the same as if you can dedicate a few hundred megabytes to cash, then you're download over by the only ends up being, which was not a

lot but that's alongside the 300. So not needing to store anything at all, you're less than a pillow using. This right now, you can use it on Chestnut right now with Rich notes And archiving. But it says it's permissionless Innovation, it you're not going to have any arguments over starting this because people can just require me to use this new software, which requires proof And have her adjust was providing Spruce and whatever. Transactions, they're making, it's

really easy to strip out the proof and send it over to the old software. Write the old software will take these new transactions with Bruce and you know, what is there built? What can you do with this? While the obvious benefit is your full load is not. So instead of taking up a lot of space and having a disc while, it's also leads to a lot of cool things you can do. So when the state size of your system is so small it'll fit on a QR code and so you can copy it around you so you can do a lot of cool things you could, for example, Sync your photo using this on

your desktop, computer at home, and you trust your desktop computer and then copy that entire state to yourself. And instead of having your cell phone, work 4 hours of century days. And download hundreds of gigabytes is just losing. You know, you could potentially do that today, right? You can do in the big one in top of your oil changed a folder from one computer to another, but it's for something gigabytes and you know, it's not practical to support.

You could also get so So you can you can do that with it's much easier. Yeah, it's a split up the thinset the validation. So maybe you have a couple computers and you take turns or like you you know, this computer does, the first three hundred thousand blocks this computer does. The next two hundred thousand and transfer states to each other very easily. Basically, the gist of the talk, the idea, maybe like it does help you still using the same amount of CPU, but it does solve a lot of issues. So a good thing to think about

this. I plugged into your router is perfect for that, right? You're not bandwidth. Constraints of an extra is 1520 /, no big deal, but a Raspberry Pi is really bad about having so much faster. Easy to run on a respirator. We currently have coat, it's working. You can download it to Violet, try it on Chestnut. We have weekly call element of this. And more open source. Contribution is definitely welcome or other questions. So that's the end of this recording and I will take questions.