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