Lightning unchained?

There's a relatively well known problem to engineers in the Lightning network, which few users or wallet developers have probably thought about (or maybe they have? I'm very glad to be wrong!).

The problem is that being a Lightning user forces you to publish the utxos you used to open channels. Imagine if we could stop doing that, and how much better your privacy would be, as a user of Lightning.

Lightning's on chain underbelly

To explain it, I have to sidetrack slightly, and describe one important feature of how the Lightning network protocol works, starting with something called the `short-channel-id` and why it matters.

The short-channel-id is an 8 byte string which encodes a utxo. In Bitcoin's own protocol, utxos are referred to as a tuple (outpoint, index) where outpoint is the txid of the transaction being spent from, and index is the index of the output of that same transaction. This is unambiguous but uses 36 bytes (32 + 4; 4 for the index is overkill but, that's how it is...). In a moment we'll understand that the designers of Lightning's protocol made a point of creating a more efficient (8 bytes vs 36) encoding. If you're wondering how it's only 8 bytes, consider that to specify a utxo you only need to specify: a block (when it was created), a transaction number (because blocks contain ordered lists of transactions), and then an output in that transaction. Each of these three integers has a maximum value, so you can use sane encodings for each (3, 3 and 2 bytes respectively).

Why does it matter? Let's rewind a bit. "Lightning Network", as I often like to say, has two parts. The first is "Lightning" - meaning Poon-Dryja channels between two parties, and the second is "Network" - meaning HTLCs enforced across multiple connected channels (paths for money). And it's that second "Network" part that's relevant here. To construct paths, you need to know that the relevant channels exist (even worse, you have to know or guess how much money is available in them!). To do that you have to somehow be told that they exist. And so we have Lightning gossip, most of which is telling your peers that channels exist.

Now lying is a thing in untrusted groups, so there is a slight problem here - why can't I just tell you a pack of lies? There are 10000 channels with 1 BTC, here is a list of all of them ... this can function to waste your time, force you to consume useless CPU cycles, and moreover, you might end up with a completely incorrect picture of where the channels are, so that when you try to route money through the "Network", you always fail.

And so we have short-channel-ids which are, as discussed, just utxos written out compactly. Utxos are not free to create, though you can create one very cheaply (1-2 sats/vb at the extreme, which at today's prices might be 10-30 cents of value), the cost is linear to create a few hundred, and, if you wanted to create 100K very quickly the cost might be essentially infinite (this is an important point that I think is under-discussed - the natural brake on utxos-created-per-second coming from Bitcoin's spectacularly high hash rate creates not just a non-linearity but almost a singularity in cost - and that is exactly what you need to create a good anti-DOS measure for a public service).

To answer an earlier question, the utxos are written out compactly because they have to be gossiped. If there are 10s or 100s of thousands of channels, that is suddenly a lot of utxo data being spread around, and if it needed 36 bytes for each of them it would be, well, a few times worse than it is today, with short-channel-ids.

The problem in detail

The problem is easy to describe - privacy. Announcing to the entire network, which means announcing to the entire world - especially if, as many "serious" nodes do, you make your announcement from a public, plaintext IPv4/6 address - which utxo(s) you own is an invitation to snoopers to start chain-analysing your onchain activity. This can be a business threat, but it will always be a security threat. This information can be cross-correlated with other information, for example connected to your IP address, to start sniffing out who you are, where you are, what you own, etc. etc.

So it's basically the case that the canonical conflict of P2P networks has shown itself. What "canonical conflict"? - I hear you ask. Well it's pretty simple:

The resource-usage requirement to defend against Sybil attacks in open peer-to-peer networks conflicts with the security requirement of users to be anonymous

If there is a "canonical solution" to the "canonical conflict", then, in my opinion it's the requirement to use a scarce resource to participate. (The other "solution" is to enforce non-anonymity but that is a brittle approach that will always fail over time - personal opinion, but since it's the correct personal opinion that's OK).

You see all of the above play out in the recent drama over Tor onion service failures due to resource consumption by Sybils, addressed with a proof of work solution. I will leave the discussion of whether compute-cycle proof of work actually will solve this problem, for another day, because I want to get on to Lightning gossip again!

So short-channel-ids directly reveal utxos. We've decided it's bad. But what else could we do? Well we can at least try to do the following:

I have a channel. I am going to prove that I have a channel-opening utxo holding roughly X sats or at least X sats, but I am not going to give any information on which of the channels with that many sats, is mine

This idea is, first, pretty appealing, but also sounds a bit crazy if you're not a ZKP aficionado. Before delving into the ZKP aspect though, we first have to address a very tricky piece of logic:

Is the fact a utxo is actually used to open a channel, public knowledge or not? In the case of current p2wsh outputs, it technically isn't revealed even on closing, but there are tell tale signs (LN engineers please correct me). For taproot channels, then at least in the MuSig2 envisioned future, we would hope or expect that channels never even reveal that they're 2-2 multisig, let alone channels. Reminding ourselves that this discussion is about imposing cost to prevent DOS, I would assert that trying to "prove you are a channel" so to speak, is a false trail. Simply utxo ownership is enough.

(Disagree? OK, let's think more carefully. I claim that a channel exists, I publish (or gossip) it. To back that up, I give a short-channel-id. This refers to a real utxo on chain, but how do you know that utxo refers to a channel? If my goal is to lie, I only have to make the utxo "look like a channel". As we discussed above, in some scenarios all utxos look like channels (taproot, MuSig2). Even more, as an attacker, I could actually make a real channel if I like, and then just not operate it correctly. The ultimate point is that "proving a channel" with short-channel-id in gossip is really "proving I created a utxo".)

But it gets even more subtle. On who or what are you trying to impose a cost? In this old post, Rusty Russel proposes imposing the cost at the node level, not the channel level. The main reason I agree with that point of view, no matter the technical challenges involved, of which I am blissfully semi-ignorant, is that disconnecting the cost from the resource it entitles you, further promotes actual privacy for the individual channels (e.g. consider creating an unusually large channel and then immediately publishing a ZKP that it exists, where ZKP here means "I prove I own a channel that's at least 2 BTC in size" just as a 2.2 BTC utxo appears on chain; just an example, you get the point).

But this is not the end of the story re: "channel utxos or not channel utxos?". See comments at the end of this blog.

OK it's useful, but is it even possible? ZKP sci-fi?

So is it even possible? As a reminder, from the above, we are now trying to prove:

I own a currently-existent utxo in some amount range, let's say taproot only but no restriction "of channel type" (ideally you can't even know that), but I am not telling you which one

For reasonable amount ranges this can be anything from a few 100K utxos to 10s of millions. Is that possible? It certainly doesn't sound like it.

I investigated this question for 3 years, on and off (though, clarification: I wasn't entirely focused on Lightning, it was more general anti-Sybil with privacy). Early on, I started by focusing on ring signatures, realising that structures exist that can be O(log N) in size (i.e. the proof, in bytes). The problem is that they are O(N) in verify and compute. Bulletproofs also have this problem. But what doesn't have this problem is Merkle trees - an insight that Andrew Poelstra gave me back at that time (i.e. Merkle proofs are O(log N) in verification), and around the same time (2022), Curve Trees was published, which embodies the combination - you can use bulletproofs for compact proofs, and an algebraic version of a Merkle tree (using the extremely lucky secp-secq curve cycle.. details) to get logarithmic scaling for verification. The realistic upshot is that for sets of 1M utxos or more, you can verify proofs (using my code or hopefully something better!) in 50-100ms, you can prove in 1-2 seconds and the proof sizes are 2-3 kB. As a reminder, what these proofs prove is something like "I own one of these 1M utxos, but I am not telling you which one". For a signficantly more developed version of the same ideas, see the FCMP++ project, though it's focused on Monero.

More recently, J T Halseth has published output-zero which is a significantly different approach to tackling the problem. It is another type of ZKP, in particular it uses zkSTARKs not Bulletproofs (see risc0 for implementation details), and then uses a Groth16 wrapper to create a compact proof.

If it interests you, I'd strongly recommend the recent discussion on delving bitcoin about his project/idea.

My current (not sure if accurate) summary is as follows: the big advantage of the output-zero approach is that it creates an O(1) size proof (Groth16), at about 260 bytes I believe. This is obviously way better than my 3kB or so. On the other hand, both from testing it myself (see here) and from the overview given, I am not really convinced that there's a viable proving time here. The arguments are that routing nodes are decently powerful machines and, more importantly, proving (unlike verifying, which is in the 50-200ms for both ZKP approaches) is not a real-time operation so it's fine if it takes multiple minutes (it seems to be way faster with GPU acceleration but, maybe it's me being old-fashioned, but I don't think that should be considered(?)). I have a suspicion that in practice, proving times longer than say 10s are just somehow a bit "off". I could be wrong.

But I'll just end by saying I think one of the most fascinating things here is that there is disagreement about whether these ZKPs should be tied specifically to channel utxos. If you read through the above delving-bitcoin discussion, you'll see me struggling with this point. I think it's much better for privacy to not try to use channel utxos, but on the other hand, why do you want utxos that aren't channels, if you devote your liquidity to channels? And if you use channel utxos for the ZKP, then you should/must support that the ZKP comes out of a MuSig2 utxos, which not only must be accounted for in the ZKP design (it's clearly more tricky if there isn't just one owner!), but raises an uncertainty about who can or should use that ZKP as a resource token. As just one example of how the ZKP is impacted, consider that output-zero's current design uses

hash(bitcoin-pubkey-1||bitcoin-pubkey-2)

as its "key image" (I mean, the thing that prevents you from reusing the same utxo over and over again), which is very different from the normal "the key image is some irreversible hash of the private key"). I realise that this is too in-the-weeds for most, but just an illustration of where the uncertainties lie, here.