Episode 25: Compact Client Side Filtering (Neutrino)

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

Sjors Provoost Hello.

Aaron van Wirdum Van Wirdum Sjorsnado. That's right. Did I say it right this time?

Sjors Provoost I don't know. We're not going to check again. This is take number three. Now you're going to ask me whether I rioted, and I'm going to say no.

Aaron van Wirdum You're like psychic.

Sjors Provoost Yes.

Aaron van Wirdum You're able to predict the future. Okay, so let's skip all the rioting jokes and all the pronunciation jokes and get to it.

Sjors Provoost Yes.

Aaron van Wirdum What are we going to discuss?

Sjors Provoost I think we're going to talk about compact block filters.

Aaron van Wirdum Yes, aka neutrino.

Sjors Provoost Yes.

Aaron van Wirdum First of all, so yeah, these are a new type of filters for light clients. So first... Let's start at the beginning, Sjors. What are light clients?

Sjors Provoost Yeah, and we should also caveat that by new type, we mean from 2018 or something.

Aaron van Wirdum It's not brand new, but it's still fairly new.

Sjors Provoost Yeah, we mentioned in the last episode that we were going to talk about that at some point.

Aaron van Wirdum Yeah, we did, because we did a Bitcoin Core 21 episode, and it's one of the new features in Bitcoin Core 21.

Sjors Provoost That's right.

Aaron van Wirdum And now we're going to get more in depth about Neutrino. Okay. So what are light clients?

Sjors Provoost So the idea of a light client is that you don't want to download the whole blockchain. And Satoshi made some remarks about that in the original white paper, how you could avoid downloading the entire blockchain. Maybe if you were on a mobile device.

Aaron van Wirdum Yeah, you want to be able to use bitcoin that is send and receive bitcoins for example satoshis but you don't want to have to download the entire blockchain which you normally would have to do in order to know what the current state of balances of UTXOs is which you need to know in order to know if transactions are valid and so forth The downside is it takes about two days, I think, nowadays, depending on how fast your computer is, but something like that on a reasonably fast computer.

Sjors Provoost Yeah, I think I can do it in five hours.

Aaron van Wirdum Yeah, because you've got like a wizard's computer. But normal people would take like two days. But even on your phone, you couldn't do it in five hours.

Sjors Provoost No, on a phone, it's horrible. It's days, if not weeks.

Aaron van Wirdum Yeah, so that's where light clients come in. So what are light clients?

Sjors Provoost Yeah, so of course there are different ways to do it. The very lightest of lightest clients would be a custodial wallet, but we don't want to talk about that. But here what we're talking about is something that uses SPV, so Simplified Payment Verification.

Aaron van Wirdum Oh yeah, so custodial is one way to do it. The other way is to sort of connect a wallet to a full node, which you're running on some other device. But what we're going to discuss here is yet another... solution which yeah spv as you mentioned

Sjors Provoost Yeah, so simplified payment verification as it says it is a simple way to verify payments and why do you care about that because the real one of the things you care about when using bitcoin is that you actually got the coins that you think you have Right, that may be something you want to verify and there's actually a way to do that which involves knowing the headers and the headers are 80 bytes each per block so it's pretty small.

Aaron van Wirdum Yeah, the block headers.

Sjors Provoost And then in addition to that a proof a Merkle proof that shows that this transaction is actually inside the block. So if you know what a transaction is and you know that it's in the block, then you know you've received it, assuming that the rest of the block was valid and nobody did any shenanigans with the history, etc.

Aaron van Wirdum Yeah, so in a way, you're kind of trusting hash power. You're trusting... that whoever invested all this energy and hash power did so because it would be too expensive to do this while mining an invalid block.

Sjors Provoost Exactly. So you're trusting other people to do the verification. The other thing is that somebody can prove that you did receive a transaction this way. They can give you that proof. For example, the person who paid you, but also the wallet has a way to fetch it, which we'll talk about. But it doesn't work the other way around. So just because nobody's giving you a proof doesn't mean that you did not receive the transaction. You cannot prove that a transaction does not exist.

Aaron van Wirdum Right. So let's say I'm running an SPV client and someone told me they paid me, then I... wants to know if that's really true. So I would ask you, Sjors, who's running a full node. You could tell me I didn't receive anything, even if I did. I'm still trusting you in that way.

Sjors Provoost Yeah. We can go into a little bit more detail about how that works. So the naive way would be, okay, if somebody makes a payment to you, then that person should send the proof. That's possible, but it's not very convenient. So what instead happens is something called bloom filters. And what your lightweight wallet does is it creates a filter which says, give me all the transactions that relate to this address. But it doesn't really say which address it is. But there's some magic math going on so that when a node sees a certain address, it'll know that it has to send you a signal. So for example, it would say, give me all the transactions in which an address starts with an A.

Aaron van Wirdum Right.

Sjors Provoost And that's not exactly how it works. It's mathematically more sophisticated than that.

Aaron van Wirdum Sure.

Sjors Provoost But you can understand intuitively what the privacy benefit of that is. Like, I'm not telling you that which address I have. I'm just telling you, tell me everything that has an A in it. And you can configure that. So you can say, well, give me every address with A, B, C, D, E, F, some more specific things. So you get only the transactions you care about. If you care a bit more about privacy, you ask for a bit more, but it comes at the cost of bandwidth.

Aaron van Wirdum Yeah, so the thing is, your actual addresses are a subset of the addresses you're asking about.

Sjors Provoost Exactly. So in practice, your light wallet sends a message to a full node somewhere on the network, one of its peers, and this full node will then keep an eye on that. As long as you're connected to it, it will keep an eye on those addresses and it will send you... It'll actually send you a block, but with only those transactions in it that match. And each of those transactions will have the correct proof that it actually belongs in the block.

Aaron van Wirdum Right, which the light client is then able to check. So the light client checks, okay, is this actually the address I cared about or is this a false positive? Is the block valid as far as hash power goes? And then is the transaction valid, I guess. And if that all checks out, then the light client sort of knows. fairly sure that it has been paid even though they're still trusting hash power

Sjors Provoost Yeah, so there's a couple of issues with this and we talked about one already

Aaron van Wirdum Yeah, just to be clear in case any listeners are confused this is not what the rest of the episode is going to be about this is like a trick that exists has been existing for the past what is it eight years something like that yeah probably longer than that what we're actually going to discuss is improvements on this solution. Because there are problems with this solution, and that's what Sjors is going to explain now. What are the problems with this solution?

Sjors Provoost Yeah, so one problem is privacy. And particularly, because you don't want to use too much data, there apparently are quite a few wallets out there that will use the lowest false positive rate possible. So you can say, okay, do I want lots of false positives? So lots of information about other addresses, so I have good privacy. but you can also set it very low and apparently they use a very low one, which means that you're really just telling the full node that you're talking to, okay, this is the address I care about.

Aaron van Wirdum Yeah.

Sjors Provoost And that's a problem because that full node you're talking to might be, I don't know, chain analysis.

Aaron van Wirdum Yeah, and I think it's not just that. I think there's also some additional puzzling the full nodes can do. Like if he would be interested in this address, he wouldn't be asking about this or with change or something. I don't know the details. I just know that this solution, this SPV solution is broken privacy -wise. I think Nick Jonas broke it a long time ago. He works for Blockstream now. And since then, everyone... agrees that this is broken privacy-wise. If you're using SPV in this way, you're essentially giving away all of your addresses to a random node on the Bitcoin network.

Sjors Provoost Okay, so that's also bad.

Aaron van Wirdum Or several, probably even several nodes. You're just giving away your privacy. It's broken. It's broken.

Sjors Provoost Yeah. The other problem is that it's pretty intense on the node that has to do this, that has to provide these filters. Because if you're running a full node, now some random node starts talking to you and says, hey, please give me updates about these addresses.

Aaron van Wirdum Right.

Sjors Provoost And so you need to do a bunch of CPU use for people and you're just doing it voluntarily. And it turns out that that's even exploitable. If you create a special filter, you can create a lot of CPU load for somebody, even though you don't actually care about those transactions. So you can, especially those Raspberry Pis, which just turn into steaming, you know.

Aaron van Wirdum Yeah. So in this case, the light client, the SPV client is making the filter for the addresses it cares about plus false positives, gives this filter to a full node on a network, and then this full node has to decipher which addresses the light client is interested in, and this is costing the full node CPU power. So it's costly. And the full node isn't earning anything by it, unless it's a spy node, and then we're back to problem one.

Sjors Provoost Well, yeah, and that creates a perverse incentive, of course, because for normal people, there is really no reason to do this other than altruism. But for spy nodes, there is a financial motive to do this. So, you know, guess who are serving this. So, okay, let's move on to a new approach that was produced, I believe, proposed around 2018, maybe 2019.

Aaron van Wirdum By Laolu.

Sjors Provoost Yep, roasbeef.

Aaron van Wirdum Lightning Labs' CTO.

Sjors Provoost Exactly. I cannot mimic his speaking face, but somebody could edit it.

Aaron van Wirdum Nobody can.

Sjors Provoost This is often referred to as Neutrino, but technically Neutrino is an implementation of that.

Aaron van Wirdum Of the general idea.

Sjors Provoost Yeah, of the idea of compact block filters. The BIPs you want to look for are BIP -157 and BIP-158.

Aaron van Wirdum Okay.

Sjors Provoost So, I think we should first talk about high-level what's going on and why it's good. And then I'll try to do a quick explainer on what it's actually doing at a more nitty-gritty technical level. Because it's kind of cool, I think.

Aaron van Wirdum Sounds good to me. Start with the high-level stuff.

Sjors Provoost So the high-level stuff, if you're running a full node, you're no longer getting custom filters from the peers that connect to you. There is only one filter. Basically, what you do as a full node is you process all your blocks and you create an index. For every block, there is a couple kilobytes of information that you need to keep track of. and you do that once and then peers can ask for it and you just give it to them. So every peer gets the same information from you.

Aaron van Wirdum I think what you're trying to say is with the SPV solution we discussed a minute ago, the light client creates a filter that includes the addresses it cares about plus false positives. And in this neutrino solution or compact block side filters or whatever it was called officially, this is reversed. And the full node actually creates the filter.

Sjors Provoost That's right. And the filter just covers everything.

Aaron van Wirdum Right. Basically. Everything that's in the block.

Sjors Provoost Well, every output script that's in the block. And for every input, the output script that corresponds to it, which would be in the previous block that it's spending from.

Aaron van Wirdum So this means that... Any full node, especially now with Bitcoin Core 21, any full node can create a filter, right?

Sjors Provoost That's right.

Aaron van Wirdum And they would all be the same because they're all seeing the same block.

Sjors Provoost Yes.

Aaron van Wirdum Okay.

Sjors Provoost And now on the client side, what you do is you connect to any peer and you say, give me the filters.

Aaron van Wirdum Yeah.

Sjors Provoost You know, you're not giving away any information when you're doing that other than that you're a light client.

Aaron van Wirdum The light client just asks for the filter.

Sjors Provoost Right, and in theory it could ask multiple peers and make sure that they get the same filter.

Aaron van Wirdum Then what does the light client do with the filter?

Sjors Provoost So what the light client is going to do is it's going to go through its own addresses and it's going to see, does the filter match any of those addresses? So basically you can see for every block you run your addresses through the filter and it'll say, yes, this block contains transactions pertaining to the filter.

Aaron van Wirdum Or there are still false positives. So what you really, what the light clients really do is they use the filter, they have their addresses, they put their addresses through this filter or whatever they actually do technically. You're going to explain it in a minute. And then a computer is going to tell them... yes, there might be relevant transactions in this block. Or no, there are definitely no relevant transactions for you in this block.

Sjors Provoost Yeah, and so this false positive story, as far as I know, is not because of privacy. It's just because math can't do better.

Aaron van Wirdum Right.

Sjors Provoost And this has to do with like, if you want less false positives, then the files that the node need to keep track of need to be bigger.

Aaron van Wirdum Right.

Sjors Provoost So if you make the filters really, really, really big, then you never get false positives. then you might as well download the whole block. right so when you so

Aaron van Wirdum if, if the, if computer says no, if computer says no, there are definitely no relevant transactions in this block for you then the light client Just ignores the block.

Sjors Provoost Exactly, which is, you can do that. Assuming the filters are not a lie, it should work.

Aaron van Wirdum What if the computer says yes?

Sjors Provoost If the computer says yes, you have to download this block.

Aaron van Wirdum Then you download the full block. So even a light client in that case downloads, well, whatever it is, two megabytes of data, just downloads the whole block. And then searches in this block to see if there was actually a transaction pertaining to that light client in the block.

Sjors Provoost Yeah, so if your wallet is tracking thousands of addresses, then maybe you have to download one in a hundred blocks as a false positive, even though you haven't done anything. Right. So this depends on how many addresses you're watching. You get a little bit more false positives. But yeah, you have to download a bunch of blocks.

Aaron van Wirdum Yeah, so you actually have to download slightly more data, I guess, compared to the previous privacy-broken SPV solution.

Sjors Provoost Yeah, but you get much better privacy.

Aaron van Wirdum Yeah, because now sometimes you need to download a block. Even sometimes if there's a false positive, so sometimes you download a block for nothing, but sometimes you've got to download a block. but then you get much better privacy.

Sjors Provoost Yeah, and you could even be smarter about it. You could request one block per peer so that the only thing each peer knows is that you may care about something in that block, which is not a lot of information. Maybe you fetch them over Tor if you want to be even better. So that's kind of nice privacy-wise, but yeah, it uses a bit more bandwidth.

Aaron van Wirdum Is that a high-level part?

Sjors Provoost No, so we can also talk about some of the downsides. So the biggest problem is that the filters can be fake, as in a node can just give you complete nonsense, and then you start asking for blocks. First of all, then it would match at the wrong block, so you wouldn't be able to find the blocks that pertain to you. Of course, at some point, maybe you can figure that out if you ask multiple peers for their filters, and then you start comparing which one is lying. But that's a can of worms. The good news is it is being used by a lot of the especially lightning mobile wallets. And they seem to work, but maybe we still live in this happy time. So I think we talked about that last time, right? Where now everybody's being nice to each other, but maybe one day people stop being nice to each other and then I don't know what's going to happen.

Aaron van Wirdum Yeah, we spoke about it in the podcast, but I think in a different context, right?

Sjors Provoost Yeah.

Aaron van Wirdum Or not. Well, anyways, yeah. So one problem is that you're a light client. I'm a light client. I'm downloading this filter from you, Sjors, who's running a full node. And then I actually have no idea if this filter is actually a filter or just gibberish. Is that what you're telling me?

Sjors Provoost Yeah, not just gibberish, but just wrong. Like it has the wrong transactions in it. It will match the wrong things.

Aaron van Wirdum Right. And there's no way for me to tell the difference.

Sjors Provoost No, and unfortunately, it's also not the case that if you download a block, you cannot recreate the filter. So the only way to create the filter is to download the entire blockchain. And the reason for that is that the filter contains not just the outputs, because the outputs you know, right? If you download a block, you know what outputs are in that block. But it also contains the outputs for every input. And so that refers to earlier blocks. So the only way to really check whether it's not lying would be to find a block and then make sure that you find all the blocks for those inputs and it would just be a mess. So that's unfortunate.

Aaron van Wirdum This sounds like a very big downside. It sounds like if someone would want to attack these kind of light clients.

Sjors Provoost Yeah, but then you have to maybe compare it to the earlier situation that we had with the Bloom filters. It's kind of also about lying by omission. That's really the problem, right? And it's sort of a DOS factor this time on the client, because the client could be having to download every single block. because it doesn't know which one to download.

Aaron van Wirdum All right. Is that a high-level part?

Sjors Provoost Yeah, I think in the long run, one of the thoughts is to turn that into a commitment into the block, but that itself is controversial, but that would at least solve this trust problem because if the filters are committed in a block, then you do know that they're correct. At least you're back to SPV proof.

Aaron van Wirdum You're at least back to trusting the hash power.

Sjors Provoost Yeah, so then you're at the same trust as you were with the Bloom filters in terms of trusting hash power. Okay, so let's maybe talk about how this works.

Aaron van Wirdum Yeah, you want to get more technical?

Sjors Provoost Yeah, so like I said, so here's the recipe. If you're serving these filters, what you do is you go through a block, for each block, you take all the output scripts, except op return, because that's not interesting, and you take all the, for every input, you take all the output scripts it refers to, and you just put those in a row. And now, for every item, you're going to hash it. there's a special hash function for it. We talked about hash functions, I think, in another episode. So now you have these hashes, which are just essentially all semi -random, right? Just looks like noise. And then you're going to...

Aaron van Wirdum Looks like random numbers.

Sjors Provoost Yes. They're deterministically random, so if you take an output script, you will get the same hash. And then you're going to sort those hashes. And you're going to calculate the difference between the hashes. Because hashes are just big numbers. So you can subtract. You sort them and then you subtract them. And it turns out that this is something you can compress with Golomb. I don't know how to pronounce it. Encoding. And this is just some mathematical trick that I don't understand. But it turns out that if you have a pattern like this. A bunch of sorted random things. You can compress it very efficiently. And so you do that, and now the client gets this compressed piece of data, and what it's going to do is it's going to look at the addresses that it is interested in, or the scripts that it is interested in, and it's going to hash its own scripts. And remember, the hashes were sorted, so now you can actually check the filter for the first hash, and then the second hash, and the third hash, etc., and see if you have a match. And then you can stop when your hash is higher, is a greater number than the last hash you checked.

Aaron van Wirdum I don't understand that at all, but sounds interesting.

Sjors Provoost Okay, well, that's fine. It wasn't the best explanation probably, but you can find it on the internet. But basically, it's kind of cool fancy math that lets you very efficiently communicate a lot of information.

Aaron van Wirdum Love it. Right. Okay, so that was the high-level explanation. And then after that, the mathematical explanation, which I didn't understand, but maybe some of our listeners did. Probably only if they already understood it. Next question. You just mentioned embedding the filters into blocks. Why is this not already the case? To just put it bluntly.

Sjors Provoost First of all, because it's a soft fork and we've talked about... you know, soft forks are the kind of things you want to be very careful with, but also because it's controversial.

Aaron van Wirdum Why is it controversial?

Sjors Provoost Well, probably for several reasons, but one reason would be how easy do you want to make it for people not to verify the whole chain?

Aaron van Wirdum Right. Even if you're using this neutrino solution, just like the SPV solution, which we discussed at first, you're still not getting full security. You're still... trusting hash power as I've mentioned in both cases, so you're trusting that at least the majority of miners isn't lying to you, essentially.

Sjors Provoost Yeah.

Aaron van Wirdum Right? So then the question is, okay, we can make it very easy to run light clients, but do we actually want to make it very easy for people to run light clients because that way they're all going to trust the miners and maybe that's not such a good idea in the first place.

Sjors Provoost Exactly. And there's kind of two forces where people are drawn to, right? On the one hand, you could say, well, if it's difficult to run a light client, maybe more people will run a full node on a good computer. But there's another attracting force that will just get people to use custodial wallets or some other thing.

Aaron van Wirdum Yeah, or not Bitcoin at all.

Sjors Provoost Exactly.

Aaron van Wirdum Right.

Sjors Provoost And it's hard to say, and in the long run, maybe it's different, right? Maybe in the short run, by supporting this, you get lots of mobile adoption of people who at least use Bitcoin, at least check the headers, rather than check absolutely nothing. But maybe on the very long run, that doesn't happen. Now, in the longer run, we have Moore's Law. So if the block size doesn't increase, and if networks and computers do get better, then maybe in a couple of decades, I think Luke Dashjr did a calculation on it, maybe in a couple of decades it becomes real practical to run this thing on your phone.

Aaron van Wirdum Yeah, and I guess this would also assume Moore's law holding up, right?

Sjors Provoost Yeah, or at least somewhat holds up. Otherwise it takes even longer.

Aaron van Wirdum We could also decrease the block size limit, as Luke suggests. And that way it would be shorter. That way we could use full nodes on our phone sooner.

Sjors Provoost Yeah, I don't know if that's worth having a giant civil war over though. And there was another thing.

Aaron van Wirdum I think only Luke thinks that. Yeah. Well, not just Luke. There's a couple more people, but it's probably not going to happen.

Sjors Provoost So this goes back to our Utreexo episode, where we discussed another way to verify blocks that takes less RAM. And one particular advantage of that approach is that you could sync a node on your computer and then just have a QR code on your computer because you trust your own computer. You scan it with your phone and boom, your node on your mobile phone is synced. So that gets rid of the initial sync problem. And this Utreexo technique allows you to work with very little RAM, which probably means that you can sync your phone on Wi-Fi and it'll be fast. And then maybe, you know, you use some of these light client techniques if you're outside doing something. So, you know, when you're outside, you make a payment or you receive a payment and you kind of trust it. But when you get home, you can immediately see if something went wrong.

Aaron van Wirdum Yeah. So the episode is short. Neutrino compact side block filters. They're new type of light clients that offer more privacy. They are being used in lightning wallets, but they're not specifically for lightning wallets, right? Are they using any other? Are they using normal light wallets by now?

Sjors Provoost I don't know.

Aaron van Wirdum I don't think so.

Sjors Provoost I haven't kept track of new normal light wallets, but I guess most of them are lightning wallets nowadays, the new wallets, aren't they?

Aaron van Wirdum New wallets, sure, but I think Electrum, they would be interested to maybe implement it as well, but I don't think they have yet.

Sjors Provoost That might be worth a brief mention too, right? The third solution that people are using is Electrum.

Aaron van Wirdum Yeah, that is another sort of in-between solution.

Sjors Provoost Yeah, as far as I know, Electrum will just say, here are my addresses, give me transactions. And then it will get SPV proofs. So you get less privacy than Bloom filters, but we already discussed that the privacy might be zero. But you do get the same security in terms of proving that these transactions are real. Right. And the same lying by omission and the same problem with potential spy nodes. Yeah, I guess that's all we've got here.

Aaron van Wirdum I think so.

Sjors Provoost In that case, thank you for listening to the Van Wirdum Sjorsnado.

Aaron van Wirdum There you go.