From rusty at rustcorp.com.au  Tue Sep 22 10:38:08 2015
From: rusty at rustcorp.com.au (Rusty Russell)
Date: Tue, 22 Sep 2015 20:08:08 +0930
Subject: [Lightning-dev] Onion routing design.
In-Reply-To: <CAM_a8Jy2SyLS9-3PE08OrzSsa9tHQPeH6r2xkyN3APq0LbFm8g@mail.gmail.com>
References: <8737ybi9fj.fsf@rustcorp.com.au>
	<CAM_a8Jy2SyLS9-3PE08OrzSsa9tHQPeH6r2xkyN3APq0LbFm8g@mail.gmail.com>
Message-ID: <87io72oi27.fsf@rustcorp.com.au>

Zooko Wilcox-OHearn <zooko at leastauthority.com> writes:
> Could you please point me to any notes about requirements/desiderata?

They're mainly spread out over the mailing list discussions, but it's
pretty simple:

1) It's a source routing network, so the sender details the payment path.
   Since fees vary with path, and the sender pays, this is the simplest.

2) For financial privacy reasons, minimizing the knowledge of any part
   of the network makes sense.

Thus, an onion routing-style setup where each node only knows prev and
next seems most sensible.  It's not quite as good as you might expect,
because the payment is trivially correlated (it requires the same R
value) so if you control two nodes on the path you can connect them.

I am currently working on some test code which works like so:

  #define MESSAGE_SIZE 128
  #define MAX_HOPS 20

  // One node hop
  struct hop {
	unsigned char hmac[SHA256_DIGEST_LENGTH];
	/* FIXME: Must use parse/serialize functions. */
	secp256k1_pubkey_type pubkey;
	unsigned char msg[MESSAGE_SIZE];
  };

  // Full route description.
  struct onion {
	struct hop hop[MAX_HOPS];
  };

Receive on a node works like so:
1) Use ECDH on onion->hop[0].pubkey and my privkey to extract secret key.
2) Use this to derive
   - enckey (SHA256(seckey || 0)
   - hmackey (SHA256(seckey || 1)
   - iv (SHA256(seckey || 2)
   - pad_iv (SHA256(seckey || 3)
3) Check HMAC of every part of struct onion after hmac (including pubkey,
   why not?).  If wrong, stop.
4) Decrypt (AES 256 CTR mode, using enckey and iv above) struct onion
   from pubkey onwards.
5) First struct hop is for us.
6) To forward, remove first hop, and append padding (thus keeping total
   length the same).
7) Padding is generated by AES-256-CTR encrypting all-zeroes with enckey
   and pad_iv.

The result should be that even final node has no idea of path length.

It's a bit tricky to generate this onion correctly (I know, my code is
still buggy!).  But it's perfectly possible.  Unused hops are filled
with random garbage.

Cheers,
Rusty.