From rusty at rustcorp.com.au  Fri Sep 18 23:39:44 2015
From: rusty at rustcorp.com.au (Rusty Russell)
Date: Sat, 19 Sep 2015 09:09:44 +0930
Subject: [Lightning-dev] Onion routing design.
Message-ID: <8737ybi9fj.fsf@rustcorp.com.au>

Hi all!

        So, we've handwaved that we're going to have onion routing, so
each node can only see the immediate neighbors.

Here's my first attempt; please fix :)

The format of a route looks like so:

        required bytes route;

A node decrypts that using its pubkey (probably some counter mode
scheme, but that's for a different post!), expecting:

        // Sum of this whole thing after decryption.
        required sha256_hash sum = 1;

        // Where to next?
        oneof next {
                // Actually, this is the last one
                bool end = 2;
                // Next lightning node.
                pubkey lightning = 3;
                // Other realms go here...
        }
        
        // How much fee you can take (== all, if last node)
        required int32 fee = 4;

        // Remainder (route blob for next node).
        required bytes route = 5;

If the sum is wrong, the routing has failed (it's been corrupted or was
malformed to start).

Nodes create the route backwards, to calculate the size.  Then picks a
total size randomly between 1024 and 4096, and pads to that size (at
least 32 bytes of random padding).  Then walks backwards to wrap and
encrypt it.

This offers some protection from guessing the route length.

Route Probing Attacks
=====================
Now, there's a weakness here: No MAC!  A nosy node can't corrupt the
routing past the next hop, but it could replace it entirely (this is
fundamental to the scheme of R values).  If it guesses the final
destination right, the HTLC will succeed, otherwise it will fail, so it
can use this to probe.

One partial defence is to fail to allow two HTLCs with the same R value,
forcing probe serialization.  Unfortunately that allows a simple way to
probe back to the source, so we shouldn't do this!

We may be able to do some probabalistic backoff of duplicate R values,
such that you can't tell if I've received one before?  A more
sophisticated probe sequence could get a probability though...

I can't see a fix for this in general. :(

Error Messages
==============
Another issue is that we should try not to leak information to passive
observers on the route due to errors, so signing errors and using the
'sum' field as a secret key seems sensible.  This means your padding in
the original message needs to be "random" so 'sum' is random.

Thoughts welcome!
Rusty.
PS.  As noted before, nodes can trivially correlate HTLCs by R value, so
     onioning the routing only gets you so far...