スケーリングビットコイン・ワークショップ: Milan 2016

Unlinkable outsourced channel monitoring

Unlinkable outsourced channel monitoring

Tadge Dryja

http://lightning.network/

https://twitter.com/kanzure/status/784752625074012160

Okay. Hi everyone. Check. Wow. Check one two. Okay it's working. And I have 25 minutes. Great. So I am going to talk about unlinkable outsourced channel modeling. Everyone likes channels. You can update states. You can link them together to make a network. This is really great. There are risks. These are additional risks. The price of scalability is eternal vigilance. You have to keep watching your channels. This is different from bitcoin. Receiver sends in these channels. When you are receiving bitcoin, you have to be signing. Your wallets are mostly hot. There are a lot of different risks. You have to watch your channel with a full node. Don't use bloom filters. The full node providing you with a merkle block could just lie. So if you're connected to a full node and say here's my ... if you don't know-- if you don't find out that you got some coins, you want to find out. In lightning, you need to know as soon as you can, so that you can grab money back from an invalid close.

Maybe you're not online all the time, but you have friends. Maybe you can ask a friend to watch the channel and send you an email if your channel closes so that you could check and make sure everything's okay. Or you could give them your private key; that's probably a really trusted friend. Or you could give them all transactions, potentially invalid closes, fully signed. Maybe you could give them a reward for finding this for you. This never happens, though. Hopefully the channel never closes in an invalid state, so you're giving them a reward for something that's not supposed to happen. So that doesn't work.

So you store O(log n) data. It's never more than 3 or 4 kilobytes. Even if you have a billion different states in your channel, it's very compact. I'm at state 1 billion, but this is at state 500 million. For a third party to do this in log n, you need a flexible signature. Maybe a MAST or a sighash without signing inputs. So that doesn't work right now. You need at least a signature for every state.

What about privacy? We can't get scalability for the outsourcing quite as well. I think privacy really improves safety in this case. You don't have to worry about people seeing your balances and what transactions oyu're doing. If you have to worry about that, then you're much less likely to outsource. People worry about privacy. If the outsourcing is private, you could have someone watch it, and they wont know what the channel is. So let's give it to lots of people. We want to minimize the trust necessary for channel monitoring outsourcing.

It's a different trust model. It's sort of a trusted third party, but it's a minimized trusted third party. You kind of want these people to tell about your channels. There's no way to prove that someone will be online tomorrow. The best way to deal with this is to give it to a bunch of people. You only need one person to be online, if you outsource it to ten people. The basic idea of how to keep this private... the simplest way is that a txid does not necessarily reveal the transaction. A signature doesn't reveal the message it's signing. The simplest most straightforward way is to take your transaction, the one that does the repudiation, so what you do is you encrypt the data in that transaction and you use the first half of your txid as your identifier and the second half as the symmetric key encrypting that data. So you give the first 16 bytes of the txid, then you say the next 16 bytes of the txid are the key to decrypt this blob I'm giving you. Given the first half of a txid, can you calculate the second half?

So you can encrypt the signature and the whole script in HLTC, it's about 130 bytes. The signature would be 64 bytes, you could concatenate it a bit. So then there's variable size, variable timing, it's hard to get it perfect. But what about if we wanted a little bit more scalability? Signature alone could be used in osme cases. You only have to store 64 bytes instead of 130 bytes. So that might be 2x better. If you're doing a lot of states, and then 50% space saving is pretty good.

When the observer sees this invalid transaction and detects it, they are able to generate the public key script when they see it. You have a timelock key, and a delay say 3 days, or a revocation key, and the revocation key would be what's given to the other party, it's an ECDSA combination of two keys where you reveal the secret so that they can spend with the revocation key immediately so the person with the revocation key can spend it immediately. You don't want to give the outsourcer the revocation key yourself. You do want to give them the.... you want to let them know what the timeout public key and timeout revocation key are, so that they can spend it themselves. The revocation key changes each state, hash-tree. Timeout key doesn't need to change, but if it's static, then it can identify the channel. If the timeout key is static across the entire channel for all states, ... state one, state two, state three. The timeout key is always the same. So at state three, say it closes. So say I gave the outsourcer old states only. The outsourcers can see state 1 and state 2. They don't know which channel that's referring to. So now they know after the fact, the balance and everything else like that. So if the timeout key is static throughout the channel, yeah we need to change both pubkeys in each state.

So what if we take the intermediate point and add that to the revocation key and timeout key? We don't need to add any new messages to the network or anything like that. At each state change, you change the revocation key and the timeout key. It looks better, but it also doesn't work. I'll show you why. Given the third state, you can't tell, you have the base for the timeout key, you have the base for the revocation key, but you can't tell what point was used at state 3, right? Well, you can. It's the same point being added to both bases. So you can subtract from the observed public key the base that you know, and you can do this with the revocation key observed and revocation key base. So then you know this is the channel you were watching. So you can't do that either; this breaks the anonymity of the channel. For every channel that closes on the network you would have to do a bunch of ECDSA operations, but you could still figure out what's going on.

You have to add two different points, to your counterparty, each new state. Both of those points are the scalars are derived from a hash of a pairing point. So I only need to keep track of the same hash tree and I can do an HMAC where I take my state nonce and hash it with r, hash it with t to get timeout scalar, and then I construct points from them. When you observe, you have no idea, unless you can get back to the parent hash. So this is the same amount of storage, and it cuts down the storage for the outsourcer by 50%. With HLTCs, you have other issues like timing data and other things. So scalability- this helps with scalability. The scalability to an observer is difficult. The observer database can potentially be much larger than the entire blockchain. Say you are an observer monitoring 10,000 channels, and each channel has 1 million states they have been through; that's 10 billion transactions. At 100 bytes per transactions, that 1 terabytes of storage. Each time you get a block, you have to look at all txids and then look at your own partial txids. You could probably do this... I haven't simulated with 10 billion, I did it with 1 million, and it seems okay. I should try it with billions. Okay this is log n, I like log n kind of thing.

Unlinkability is not perfect. There's always going to be this arm race and attacks here. HLTCs you could ignore them and say I'm making HLTCs making payments multi-hop, and I'll just not tell my outsourcer about those. If they are small, that might be an okay strategy. Bulk of the channel might not be on HLTCs. Say you have a 2 bitcoin HLTC and you say, well they are probably not going to close the channel in the wrong way to get those 2 coins because they would lose 9 coins. You could send them noise; you could make up HLTCs and get them to store them. If you know HLTCs are routing through this channel, and I observed more routing data, and such.......

The other tricky thing is that you don't want to give people too many options. If you have three different... even if you have settings in your client where you outsource certain things, that reveals information about your client and then people can try to use that to link the channel schemes. Everyone should use bip69, it's a canonical ordering of inputs and outputs. That's a wallet-specific thing, it otherwise reveals information about the wallet you're using.

If I have a channel and I close it, and then I tell the person monitoring it hey I closed it and you can stop monitoring it. Well if you tell them that, they might check that hey there's only one channel closing on the blockchain, so then they would know that was the channel related to you. Say someone watches 1 GB of data for you for free, and they delete the oldes tone; and then maybe you never actively tell them when you actually delete or clcose a channel rather. You could also add latency or add lag, where you tell your outsourcer only a few minutes later. That could help. There's a bunch of things you can do in this direction. It's never going to be perfectly anonymous or perfectly outsourceable.

Backups of lightning channels are dangerous. Say you make a backup of state 30, then you make some more transactions, then restore your transaction to state 30, I could quickly lose all my money because I restored a backup. If I connect to my counterparty and say hey I'm trying to make state 31, and they will be sure, and they know the 31st revocation key already, so they can just take money. So it's very risky to restore from a backup.

We could segment the HLTC encrypted blobs such that if I give you one decryption key, you could rollback and get a bunch of the previous decryption keys. Therefore you only need one HLTC at a time. Another thing to prevent spam-- part of the thing about unlinkability is that if I don't tell you which channel I'm monitoring, it might be something I completely made up. I might be spamming you. So there might be some way where you have some kind of group or ring signature to indicate this is a real channel but I'm not telling oyu which one. It's one of the channels curretly open on the networ, but I don't tell you which one. One altruistic node defending the whole network would be good. If the attacker tries to close the channel in the wrong way; they have to think hey is there nobody nice on the network that is going to try to defend that channel? Only then are they going to attack that channel and try to grab the money. Maybe the counterparty is offline and the timeout is this week... I mean maybe there's a node out there is monitoring. Make it anonymous so that nobody has a problem forwarding to everyone their data. Make it hard to spam so that someone will say "I'm the nice guy and I'm going to defend the lightning network and we're going to monitor it".

This is still a work in progress. I think invalid channel closes will be pretty much impossible. There's all this work on transactions that will almost certainly never happen. You will probably never see invalid closes on the network. The risks are so high, and the gains are pretty high. Any questions?

Q&A

Q: Incentive for defenders to watch the network, to spend a small portion of the value of the channel?

A: Not compatible with anonymity. You have to tell them which channel it is and that money is there to get. I don't think it's as useful to do it this way. I just didn't think people would make money off of this. Anonymous with altruistic is probably more realistic.

Q: ...

A: Even if you're not running a full node, you can parse an entire block anyway. You don't necessarily know who is monitoring a channel. If you give the outsourcing data to a node, then they might forward it on to another person. It might be 100 people watching the channel. You lose track of who's monitoring it. You want someone to do it for you, but you-- you want a combination. You probably want a couple friends where you know they run full nodes. And then you have these anonymous unknown nice people also doing this at the same time.

Q: You don't need a full block. You need UTXOs.

A: Right, maybe txid list only. If you are doing it yourself.... unless you create... don't use bloom filters, for third-part outsourcing... I was thinking if you were doing it yourself, you just look at the outpoint. That's like a million txids. Is there a wire protocol message to get all the txids in the block? I guess we could make one. That would be even shorter. Oh then you could do the merkle root. Yeah...

References and other stuff

Scalability of lightning with different BIPs https://scalingbitcoin.org/hongkong2015/presentations/DAY2/1_layer2_2_dryja.pdf

transcript from Hong Kong https://diyhpl.us/wiki/transcripts/scalingbitcoin/hong-kong/overview-of-bips-necessary-for-lightning/

Lightning network as a directed graph: Single-funded channel network topology https://www.youtube.com/watch?v=-lgYYz3y_hY