<div dir="ltr"><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Olaoluwa Osuntokun</b> <span dir="ltr"><<a href="mailto:laolu32@gmail.com">laolu32@gmail.com</a>></span><br>Date: Sat, Nov 25, 2017 at 1:16 PM<br>Subject: Re: [Lightning-dev] General question on routing difficulties<br>To: Pedro Moreno Sanchez <<a href="mailto:pmorenos@purdue.edu">pmorenos@purdue.edu</a>><br>Cc: <a href="mailto:lightning-dev@lists.linuxfoundation.org">lightning-dev@lists.linuxfoundation.org</a><br><br><br><div dir="ltr">(final try as the prior mail hit the size limit, sorry for the spam!)<div><br></div><div><div>Hi Pedro, </div><div><br></div><div>I came across this paper a few weeks ago, skimmed it lightly, and noted a</div><div>few interesting aspects I wanted to dig into later. Your email reminded me</div><div>to re-read the paper, so thanks for that! Before reading the paper, I</div><div>wasn't aware of the concept of coordinate embedding, nor how that could be</div><div>leveraged in order to provide sender+receiver privacy in a payment network</div><div>using a distance-vector-like routing system. Very cool technique!</div><div><br></div><div><br></div><div>After reading the paper again, my current conclusion is that while the</div><div>protocol presents some novel traits in the design a routing system for</div><div>payment channel based networks, it lends much better to a</div><div>closed-membership, credit network, such as Ripple (which is the focus of</div><div>the paper). </div><div><br></div><div><br></div><div>In Ripple, there are only a handful of gateways, and clients that seek to</div><div>interact with the network must chose their gateways *very* carefully,</div><div>otherwise consensus faults can occur, violating safety properties of the</div><div>network. It would appear that this gateway model nicely translates well to</div><div>the concept of landmarks that the protocol is strongly dependant on.</div><div>Ideally, each gateway would be a landmark, and as there are a very small</div><div>number of gateways within Ripple (as you must be admitted to be a verified</div><div>gateway in the network), then parameter L (the total number of landmarks)</div><div>is kept small which minimizes routing overhead, the average path-length,</div><div>etc.</div><div><br></div><div><br></div><div>When we compare Ripple to LN, we find that the two networks are nearly</div><div>polar opposites of each other. LN is an open-membership network that</div><div>requires zero initial configuration by central administrators(s). It more</div><div>closely resembles *debit* network (a series of tubes of money), as the</div><div>funds within channels must be pre-committed in order to establish a link</div><div>between two nodes, and cannot be increased without an additional on-chain</div><div>control transaction (to add or remove funds). Additionally, AFAIK (I'm no</div><div>expert on Ripple of course), there's no concept of fees within the</div><div>network. While within LN, the fee structure is a critical component of the</div><div>inventive for node operators to lift their coins onto this new layer to</div><div>provider payment routing services. Finally, in LN we rely on time-locks</div><div>in order to ensure that all transactions are atomic which adds another set</div><div>of constraints. Ripple has no such constraint as transfers are based on</div><div>bi-lateral trust.</div><div><br></div><div><br></div><div>With that said, the primary difference between this protocol is that</div><div>currently we utilize a source-routed system which requires the sender to</div><div>know "most" of the path to the destination. I say "most" as currently,</div><div>it's possible for the receiver of a payment to use a poor man's rendezvous</div><div>system to provide the sender with a set of suffix paths form what one can</div><div>consider ad-hoc landmarks. The sender can then concatenate these with</div><div>their own paths, and construct the Sphinx routing package which encodes</div><div>the full route. This itself only gives sender privacy, and the receiver</div><div>doesn't know the identity of the sender, but the sender learns the</div><div>identity of the receiver. </div><div><br></div><div>We have plans to achieve proper sender/receiver privacy by extending our</div><div>Sphinx usage to leverage HORNET, such that the payment descriptor (payment</div><div>request containing details of the payment) also includes several paths</div><div>from rendezvous nodes (Rodrigo's) to the receiver. The rendezvous route</div><div>itself will be nested as a further Anonymous Header (AHDR) which includes</div><div>the information necessary to complete the onion circuit from Rodrigo to</div><div>the receiver. As onion routing is used, only Rodrigo can decrypt the</div><div>payload and finalize the route. With such a structure, the only nodes that</div><div>need to advertise their channels are nodes which seek to actively serve as</div><div>channel routers. All other nodes (phones, laptops, etc), don't need to</div><div>advertise their channels to the greater network, reducing the size of the</div><div>visible network, and also the storage and validation overhead. This serves</div><div>to extend the "scale ceiling" a bit.</div><div><br></div><div><br></div><div>My first question is: is it possible to adapt the protocol to allow each</div><div>intermediate node to communicate their time lock and fee references to the</div><div>sender? Currently, as the full path isn't known ahead of time, the sender</div><div>is unable to properly craft the timelocks to ensure safety+atomicity of</div><div>the payment. This would mean they don't know what the total timelock</div><div>should be on the first outgoing link. Additionally, as they don't know the</div><div>total path and the fee schedule of each intermediate node, then once</div><div>again, they don't know how much to send on the first out going link. It</div><div>would seem that one could extend the probing phase to allow backwards</div><div>communication by each intermediate node back to the sender, such that they</div><div>can properly craft a valid HTLC. This would increase the set up costs of</div><div>the protocol however, and may also increase routing failures as it's</div><div>possible incompatibilities arise at run-time between the preferences of</div><div>intermediate nodes. Additionally, routes may fail as an intermediate node</div><div>consumes too many funds as their fee, causing the funds to be insufficient</div><div>when it reaches the destination. One countermeasure would maybe: the</div><div>sender always sends waaay more than necessary, and gives the receiver a</div><div>one-time payment identifier, requiring that they route the remainder of</div><div>the funds *back* to them.</div><div><br></div><div><br></div><div>To solve this issue presently, we extend the header in Sphinx to include a</div><div>per-hop payload which allows the sender to precisely dictate the</div><div>structure of the route, allows the intermediate nodes to authenticate the</div><div>information given to it, and also allow the intermediate node to verify</div><div>that their policies have properly been respected. These payloads can also</div><div>be utilized by applications to communicate a small-ish amount of data to</div><div>construct higher-level protocols on top of the system. Examples include:</div><div>cross-chain swaps, chance payment games, higher-level B2B protocols,</div><div>flavors of ZKCP's, media streaming, internet access proxying, etc.</div><div><br></div><div><br></div><div>From my point-of-view, when extended to LN, the core component of the</div><div>protocol (landmarks), becomes the weakest component. From my reading,</div><div>*all* nodes need to be ware of an *identical* set of landmarks (more or</div><div>less similar to the desired homogeneity of Gateways), otherwise the</div><div>coordinate embedding scheme breaks down. Currently, there's no requirement</div><div>that all nodes have a globally consistent view of the network. So then an</div><div>important questions arises: who choose the landmarks? A desirable property</div><div>of a routing system for LN (IMO) is that is has close to zero required</div><div>initial set up by a central administrator. With this protocol, it would</div><div>seem that all nodes much ship with a hard coded set of global landmarks</div><div>for the path finding to succeed. This itself pins a hard coordination</div><div>requirement amongst implementers to have something like this deployed.</div><div>Even ignoring this requirement for a minute, I see several other</div><div>downsides:</div><div><br></div><div> * As *all* payments must flow through landmarks (since nodes break up</div><div> their payment into L sub-flows), the landmarks must be very, very</div><div> well capitalized. This would cause strong consolidation of the</div><div> selection of landmarks, as they need extremely large channels in</div><div> order to facilitate transfer within the network.</div><div><br></div><div> * As landmarks must be globally known, this it seems this would</div><div> introduce fragility in the network. If most of the landmarks go down</div><div> (fails stop crashes) due to hardware issues, DoS, exploited bugs,</div><div> etc, then the network's throughput instantly becomes crippled.</div><div><br></div><div> * If all payment flow *must* go through landmarks, and the transfers</div><div> within the network are relatively uni-directional (all payment going</div><div> to Candy Crush Ultra: Lighting Strikes Twice), then their</div><div> channels would become unbalanced very quickly.</div><div><br></div><div><br></div><div>The last point there invokes another component of the network: passive</div><div>channel rebalancing. With source routing, it's possible for nodes to</div><div>passive rebalance their channels, in order to keep the in equilibrium,</div><div>such that on average they'll be able to handle a payment flow coming from</div><div>any direction. This is possible as with source routing, it's easy for a</div><div>node to simply send a payment to himself incoming/outgoing from the pair</div><div>of channels they wish to adjust the available flow of. With</div><div>distance-vector-like protocols, this doesn't seem possible, as the node</div><div>doesn't have any control of the incoming channel that the payment will</div><div>arrive on.</div><div><br></div><div><br></div><div>Finally, the notion of value privacy within the scheme seems a bit weak.</div><div>From this definition, any protocol that didn't broadcast intents to send</div><div>payments to the world would achieve this trait. The base Bitcoin</div><div>blockchain doesn't mask the values of transfers (yet), but even if it did</div><div>unconditionally maintaining value privacy of channel doesn't seem</div><div>compatible with multi-hop payment networks (nodes can simply perform</div><div>probing/tagging attacks to ascertain a range of the size of a channel). A</div><div>possible mitigation would be for nodes to probabilistically drop incoming</div><div>payments, with all nodes sampling from the same distribution. However,</div><div>this would dramatically increase routing failures by senders, removing the</div><div>"low-latency" trait of payment networks that many find desirable. </div><div><br></div><div><br></div><div>Personally, I've very excited to see additional research on the front of</div><div>routing within the network! Excellent work by all authors.</div><div><br></div><div><br></div><div>In the end, I don't think it'll be a one-size fits all solution, as each</div><div>routing protocol delivers with it a set of tradeoffs that should be</div><div>weighed depending on target characteristics, and use-cases. There's no</div><div>strong requirement that the network as a whole uses a *single* routing</div><div>protocol. Instead several distinct protocols can be deployed based on</div><div>use-case requirements, as we only need to share a single end-to-end</div><div>construct: the HTLC. I could see a future in a few years where we have</div><div>several deployed protocols, similar to the wide array of existing routing</div><div>protocols deployed on the Internet. What we have currently gets us from</div><div>Zero to One. We'll definitely need to experiment with additional</div><div>approaches as the size of the network grows, and the true economic flow</div><div>patterns emerge after we all deploy to mainnet.</div><div><br></div><div><br></div><div>-- Laolu</div></div><div><br></div></div>
<br>______________________________<wbr>_________________<br>
Lightning-dev mailing list<br>
<a href="mailto:Lightning-dev@lists.linuxfoundation.org">Lightning-dev@lists.<wbr>linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.<wbr>org/mailman/listinfo/<wbr>lightning-dev</a><br>
<br></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">- Bryan<br><a href="http://heybryan.org/" target="_blank">http://heybryan.org/</a><br>1 512 203 0507</div>
</div>