From rusty at rustcorp.com.au  Tue Dec 15 02:30:52 2015
From: rusty at rustcorp.com.au (Rusty Russell)
Date: Tue, 15 Dec 2015 13:00:52 +1030
Subject: [Lightning-dev] An Alternative Onion-Routing Proposal
In-Reply-To: <CAO3Pvs9kM1W2pM-qE59HeE2wXG-xg1QBRek1RueVqe=3LOAbiQ@mail.gmail.com>
References: <CAO3Pvs9kM1W2pM-qE59HeE2wXG-xg1QBRek1RueVqe=3LOAbiQ@mail.gmail.com>
Message-ID: <87wpsgh28z.fsf@rustcorp.com.au>

Olaoluwa Osuntokun <laolu32 at gmail.com> writes:
> Hi y'all!!

Hi Olaoluwa, welcome to the list!

        I've yet to read the papers, so forgive if I've made an error
below.

> First, I'll give a brief overview of Sphinx. I won't delve into the exact
> details of the protocol, instead I'll highlight the key insight that allows
> for
> *extremely* small mix-headers. If we assume a maximum diameter of 20 hops,
> and a
> 16-byte MAC, then a full onion blob weighs in at only 705 bytes! This is
> considerably smaller (a 4X size reduction) than the 3840 bytes per
> onion-blob in
> current proposal.

Not sure where these numbers come from?  The current header overhead is
sha256 (32 bytes) + pubkey (33 bytes), or 1300 bytes.  (Don't be
confused by the current test implemenation which doesn't serialize the
pubkey).

If we were to cut to a 16 byte MAC (which seems unwise), that would be
980 bytes.

> Alice computes all the blinding factors and shared secrets up front,
> allowing
> her to create the mix-header for each hop using the derived hop shared
> secret
> to derive subsequent decryption and MAC keys. Each node receives a_{i}, and
> prepares a_{i+1} for the next hop by re-randomizing the group element using
> the
> blinding factor.
>
> The formula for computing the size of a mix-header for a given hop count,
> and
> security parameter is (ignoring the final message size):
>   * p + (2r + 2)s
>     * p = pub key size (in bytes, for DH each hop)
>     * r = max number of hops
>     * s = symmetric key size (in bytes)
>
> So, for 20 hops the size is computed as (with a symmetric key size of 16
> bytes):
>   * 33 + (2*20 + 2) * 16 = 705 bytes!
>
> 445% smaller than the 3840 bytes of the current proposal.

Or, if we're standarizing on ChaCha20, with a 32-byte key:

   33 + (2 * 20 + 2) * 32 = 1377 bytes.

> The original version of Sphinx was designed with anonymous mailing in mind.
> So the final mix-header to the destination node includes a final
> destination
> email-address (k-bits), and an Identifier (k-bits) used to generate reply
> messages back to the sender. If we remove these from the mix-net, we save
> 2k-bits arriving at a new formula to compute the mix-header size:
>   * p + (2*r*s)
>
> So with 20 hops the size is reduced to:
>   * 33 + (2*20*16) = 673 bytes

Or 33 + 2 * 20 * 32 = 1313 bytes for ChaCha20.

> With this size reduction the, the base64 encoding of a mix-header for two
> hops
> can fit entirely into a tweet!
>   * 33 + (2*2*16) = 97 bytes

Now, *that* is an important metric :)

More important than the size is the idea of reusing a proven design over
an ad-hoc one, so we should use this anyway.

HORNET seems a bit over-the-horizon for now, so I'll leave that reply
for a future message :)

> We (me+Tadge+Joseph) are planning on publicly releasing our in progress
> implementation of Lightning, sometime near the end of this month (December)
> :).

Great!  Let's argue about protobufs and ChaCha20 vs AES before then :)

Thanks!
Rusty.