Decorrelation of Lightning Payments
One idea which got cut from the 1.0 version of the lightning spec (which we’re busy working on) was ensuring that payments across the lightning network can’t be trivially linked by two nodes which are sharing information. So I cringed when a paper exploited that flaw to optimize the protocol!
So, what’s going on? Well, nodes in the lightning network relay an enforceable exchange of some secret preimage for some bitcoins: “Alice’s transaction lets Bob take $10 if you present something which hashes to X within 6 blocks”. This is the simplest atomic-exchange protocol, and you can chain it trivially across nodes (Bob can say to Carol “$9 for preimage of X within 5 blocks” etc).
Now, we went to great lengths to hide the original and destination of payments in the lightning protocol, which is slightly undermined by this: if Bob and Dave are two collaborating nodes on the path from Alice to Emily, they can trivially see the same offer for X and know it’s the same payment. We call this payment correlation, and it doesn’t need tricky stuff like measuring packet timing or expiry and payment amounts. We will eventually end up in an arms race tackling those things, but there’s little point with this trivial correlation.
Buried in an obscure old thread on the mailing list is the solution to this: Mats Jerratsch came up with it. You use a secret key and pubkey in place of the preimage and hash for X; give Carol the secret key and Bob gets the money. Bob can then use this secret key (plus a random pre-defined constant) to get the secret key he needs to collect from Alice. Alice provides the initial random constants (aka “blinding factors”) for each hop, so nobody else can even tell they’re related.
Now, there’s no obvious way to do this “give me the private key” in bitcoin’s script language, but Anthony Towns, Greg Maxwell and Andrew Poelstra helped refine it to the final form seen in that post. Basically, they torture bitcoin scripts into a puzzle which can only be solved by reusing the signing “r” value, which exposes the secret key.
The resulting script is pretty expensive though, and so this more complex approach was deferred (we have enough work to do!). I felt horrible when I read the Andrew Miller paper which used this linkage to reduce the payment timeout for Ethereum. I mean, that’s what academics do (produce ideas), but this seems a terrible tradeoff. Clearly, I thought, we should have just added it into the 1.0 protocol to avoid this kind of thing…
But there’s a twist! Andrew Poelstra (one of my colleagues here at Blockstream, BTW) has been working on lightning over Mimblewimble, which has no scripts. He came up with a scheme using Schnorr signatures, and I asked him if we could use something similar for bitcoin (once we get Schnorr signatures too). I was pretty sure the answer was “no”, but he’s the math guy, and I like to seem smart by asking impossible questions. About three weeks later, the answer came back: yes. Yes we can.
We can actually use the signature itself! By merely signing Bob’s the transaction, Carol reveals enough for Bob to sign Alice’s transaction. Schnorr signatures are already magic: two parties can sign a transaction by adding their signatures together, halving the space taken by the signatures. This lets us get rid of the explicit preimage, too, saving even more space. And we can use the same blinding scheme we did before to remove the correlation, so you can’t even tell the payments are related. It’s beautiful.
This is the most exciting thing I’ve encountered for quite a while. And frankly, results like this are the reason I’m so happy to work for Blockstream.
