From laolu32 at gmail.com Mon Dec 14 22:04:01 2015 From: laolu32 at gmail.com (Olaoluwa Osuntokun) Date: Mon, 14 Dec 2015 22:04:01 +0000 Subject: [Lightning-dev] An Alternative Onion-Routing Proposal Message-ID: Hi y'all!! So I've been drafting up some schemes for the design of onion routing within the Lightning Network myself. Rather than create my own mixing format, and onion routing protocol, I've instead turned to some of the existing academic literature concerning the subject. I found two schemes, the first building upon the other, which seem to fit elegantly into our problem domain, directly solving many problems we've encountered along the way. The two schemes of interest are first Sphinx[1]: a compact mixing format, and HORNET[2][3], which leverages Sphinx to build a low-latency, high-bandwidth onion routing protocol. Alright, let's jump into and overview of both schemes! (heads up, this post is a bit long as it includes a brain dump of ideas I've been been floating around in my head for the past two months or so) 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. I recommend consulting the paper for the proper specifics. Additionally the paper includes a formal proof of security in the Universal Composability model[4], achieving each of the 4 properties outlined for a secure onion routing protocol in [5]. (btw, don't dismiss figures 1 and 2 in the Sphinx paper. They may look strange, but finally grokking them resulted in a break through allowing me to finish my implementation) So, at this point, y'all may be wondering how Sphinx achieves such compact mix-headers. Well, Rather, than including a group element to perform DH with for *each* hop in the route, mix-headers in Sphinx only contain a single group element. This single group element is then deterministically re-randomized by each hop in the route, preparing the group element for the hop directly following it. Here's a brief sketch of the mechanism (covering only the DH aspects): Say Alice wants to route a payment to Bob (Y_b) over Lightning. Alice consults her routing/service table, and finds a route via Carol and Dave. Next, to create the mix-header, Alice grabs key-pairs for Carol (Y_c) and Dave (Y_d). She then generates an ephemeral DH key-pair (a_0 = g^x) then proceeds to derive a shared secret for each hop in the route. Using multiplicative notation, the DH derivation looks something like this (s = shared key, b = blinding factor): * a_0 = g^x, s_0 = (Y_c)^x, b_0 = hash(a_0, s_0) * a_1 = (a_0)^b_0, s_1 = (Y_d)^x*b_0, b_1 = hash(a_1, s_1) * a_2 = (a_1)^b_1, s_2 = (Y_b)^x*b_0*b_1, b_2 = hash(a_2, s_2) ......... continued if more hops were in the route .......... 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. 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 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 However, it occurred to me that the final destination address may be useful in the context of a more hub-and-spoke-y network. In this scheme the payment would be routed to a "shared node", who would then use the destination address to demultiplexing the payment to one of its connected links in a "host:port" fashion. Finally, Sphinx has built-in protection for replay attacks. Meaning an adversary is unable to force a node to process a previously processed mix-header. It achieves this protection by having all nodes remember every derived shard secret it has ever come across. However, within the paper, the extent of the past with which a node is to recall is unspecified, leading to potentially large storage overhead. However, it's worth noting that the paper recommends frequent key rotation, during which this table may be safely cleared. Additionally, nodes may also employ a decaying bloom-filter/hash-set [6] for use in-between key rotations to create an upper bound on the storage overhead. With that said, Sphinx is much more compact than the current proposal, carries a formal proof of security, and specifies replay protection. It was recently brought up in [7], that allowing nodes to use onion routing with Lightning as an end-to-end messaging interface. This is where HORNET comes in. One could use Sphinx's Single-Use-Reply-Blocks to allow the recipient to communicate with the sender after a dummy onion circuit has been set up. However, this introduces some performance considerations, due to Sphinx requiring each hop to perform 2 asymmetric crypto operations (shared secret derivation + group element blinding) before forwarding. HORNET gets around this performance issue by first using Sphinx to set up a duplex onion circuit between sender and receiver, which after set up, only requires nodes to compute purely symmetric crypto operations before forwarding. Continuing, both Sphinx and the current proposal only provide sender anonymity. Meaning that only the source maintains unlinkability, therefore it learns the destination's location. The addition of HORNET allows both side to retain full unlinkability. HORNET has a built-in, an optional rendezvous protocol, which is a bit similar to the way Hidden Services in TOR work. With that said, what follows is a brief high-level overview of the HORNET onion-routing protocol (focusing on the initial set up, instead of data transmission). Unlike Sphinx, which is essentially a "fire-and-forget" onion routing protocol from the view of the sender, HORNET requires a cumulative circuit round-trip as a set up phase before messaging can begin. Once completed, this set up phase creates a duplex onion circuit between the sender and destination, allowing a level of throughput approaching 93 Gb/s as reported experimentation section within the paper. The primary addition to Sphinx's mix-header format is something they've dubbed the Anonymous Header (AHDR). Instead of requiring each node in the mix-net to store per-session state (which would prohibit scale in large networks), all session-state is instead stored within the onion-packet itself. Therefore, each node only needs to maintain a local secret. A full AHDR contains contains a series of Forwarding Segments (FSes) for each hop, allowing them to decrypt the per-hop onion, revealing the next hop in the path. Each FS contains: the next hop in the route, a TTL value, and a derived shared secret. A full AHDR has the following format: * (FS, MAC, Onion wrapped FSes) First, let's go over how a duplex onion circuit is achieved, maintaining sender unlinkability (once again, using multiplicative notation): * Sender Set Up: * The sender obtains the current keys for each hop in the path, constructing a forward, and backwards path (the reverse of the forward path). * The sender then generates a per-session ephemeral DH key-pair: (x, g^x) * Using the Sphinx protocol described above, then sender then generates two Sphinx mix-headers: one for the forwards path, and another for the backwards path. At this point, the source has derived shared secrets for each node along both paths. * The message payload (SP) of the forward Sphinx mix-header (encrypted to the destination), is the backwards Sphinx mix-header which allows the destination to reply to the sender. * The Sphinx mix-header (SHDR) is then extended with two additions: * A empty list of FSes (P_fs), which each intermediate node can populate without learning the total path length, nor their position within the route. * The Sphinx per-hop MAC is also extended over the HORNET Common Header (CHDR): (packet type, hops, TTL) * The sender then sends this set up packet to the first node in the route: (CHDR, SHDR, SP, P_fsf) * Intermediate Node Set Up: * Upon receipt of the Sphinx packet, each node processes it as normal (according to Sphinx): deriving the shared secret, recovering the next hop's ID, and re-blinding the group element. * Next, the node verifies the next-hop is correct, and that the packet hasn't yet expired according to its TTL. * In order to provide forward secrecy for the messaging phase, the node then derives a new DH key-pair (y, g^y), and then derives a new shared secret to be included within the FS: (a_i)^y * Using it's local shared secret (SV_i), the node creates a FS that only it can decrypt, adding this to the FS payload. This payload entry additionally includes the new ephemeral DH-key pair (y, g^y), allowing the source to derive the shared secret which will be used for the FS's MAC (and also when transmitting data). * Finally the node re-assembles the packet (CHDR', SHDR', SP, P_fsf'), and forwards it to the next hop. * Destination Set Up: * The destination initially processes the packet identically to the intermediate nodes described above. * It then decrypts the Sphinx payload, uncovering the backwards SHDR. The node then creates a new payload each of the completed FSes in the payload. destined to the source. * At this point, the destination has no knowledge of any of the derived shared secrets, other than the one it has derived with the source. * Next, it creates a new FS list P_fsb, to collect FSes along the backwards path. * Finally, it creates the backwards set up packet (CHDR, SHDR, SP_b, P_fsb), and sends it to the first node on the backwards path. * Each intermediate node then processes the backwards packet just as before. * Data Transfer (brief overview, consult the paper for proper details) * The source node then recovers the Sphinx payload SP_b, recovering the forwarding segments for the forward (P_fsf) and backwards path (P_fsb) * At this point, set up has been completed! * The source node then constructs two initial AHDR's, one so it can send messages to the destination via the circuit, and the other which will allow the destination to reply to the source. * After the first message from S -> D, D obtains the backwards AHDR, allowing it to reply without knowing the actual route. The, the following modifications are necessary to achieve sender-receiver unlinkability as described earlier. The modification to allow send-receiver unlinkability is relatively straight forward. It involves nested AHDRs. Lets say Alice wants to send a message (or a payment in our case) to Bob while maintaining full unlinkability. Bob will first need to select a rendezvous point (RP), let's call him Rodriguez. Bob then executes the set up protocol detailed above between himself and Rodriguez. As a result, Bob obtains a AHDR allowing Rodriguez to route messages (via some specified path) to Bob (R -> B). Bob then publishes this AHDR_rb to some "public bulletin board", or in the case that Alice has a hidden service set up, directly to Alice. Alice then obtains the AHDR_rb, routing as normal to Rodriguez, but then includes AHDR_rb, nested within the regular AHDR_ar (Alice -> Bob). Once this mix-header reaches Bob, he recovers the nested AHDR, allowing him to complete the route to Bob. Additionally, its possible for Bob to specify several rendezvous points, allowing Alice to select the closest/cheapest route to her. As a side effect, the usage of this nested AHDR doubles the bandwidth required for each node to forward along the path. With this duplex onion route set up (with or without the RP), Alice can send a message to Bob, asking for R (along with other payment details), then propagate HTLCs along the full path in order to pay Bob. In order to mitigate the potential DoS attacks introduced by adding a message layer for control signals, we can either introduce a payment system (as suggested in [8]), or a required Hashcash challenge (avoiding SHA-256, using either SHA-3 or BLAKE2). However, seeing as we'd like to maintain the responsiveness of the network, I'm personally leaning towards payments (if we do in fact deem in network messaging attractive). Okay, so that concludes my first post on the mailing list! So at this point y'all may be wondering where the implementation I mentioned above is? Well, so far I have a working implementation of Sphinx by itself, not yet integrating the aspects of HORNET, but, it's not yet publicly released. We (me+Tadge+Joseph) are planning on publicly releasing our in progress implementation of Lightning, sometime near the end of this month (December) :). 1. http://www.cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf 2. http://arxiv.org/pdf/1507.05724v1.pdf (HORNET w/ forward secrecy) 3. http://www.scion-architecture.net/pdf/2015-HORNET.pdf 4. https://eprint.iacr.org/2000/067.pdf 5. http://cs.brown.edu/~anna/papers/cl05-full.pdf 6. https://moderncrypto.org/mail-archive/messaging/2015/001906.html 7. http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-December/000369.html 8. http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-December/000371.html -------------- next part -------------- An HTML attachment was scrubbed... URL: