MIME-Version: 1.0
In-Reply-To: <CAO3Pvs-bxAQKcfsXo+-uA9XbFtYZxT8qVM-5pFeYvEGEqk_scw@mail.gmail.com>
References: <CAEbFcLv_Eye-Z9mHCEuRt70mWMFL9a_659cFJ0DwuJjvOYE7yQ@mail.gmail.com>
	<CANVuFb3bL9v2Cs8-jPqFXAZ-=sr2F5d8oXZwaQaxa-nyVB55Kw@mail.gmail.com>
	<CALxbBHWJk+VY8LtJNQ5PVcByXabx5YkxdcH+Vg9o8sCyNgoUBg@mail.gmail.com>
	<CANVuFb1Fm21R48KOunAqRopSLYFqYfMndy9fzjzZVL7U+wXPPA@mail.gmail.com>
	<CALxbBHXQaenE36zgwiWv1ntQHk+Y=f5MqcZ0A06n3REEYaWcnA@mail.gmail.com>
	<CACHbmQ3DdFHj5qFShZ6cO0UBRf8hHMFGUnawfvgSiYZkO+NPmw@mail.gmail.com>
	<49e10ec4-83ef-df0e-ae87-598bbf7e0784@purdue.edu>
	<CAO3Pvs-bxAQKcfsXo+-uA9XbFtYZxT8qVM-5pFeYvEGEqk_scw@mail.gmail.com>
From: Bryan Bishop <kanzure@gmail.com>
Date: Sat, 25 Nov 2017 13:21:55 -0600
Message-ID: <CABaSBaz9zUb5OD8Gu-FJaY1SBmYM86b_Gjr0kdjqkN0ubF8ukQ@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>,
	Bryan Bishop <kanzure@gmail.com>
Content-Type: multipart/alternative; boundary="001a1140a95e26f4b8055ed395de"
Subject: [bitcoin-dev] Fwd: [Lightning-dev] General question on routing
	difficulties
Precedence: list

--001a1140a95e26f4b8055ed395de
Content-Type: text/plain; charset="UTF-8"

---------- Forwarded message ----------
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Sat, Nov 25, 2017 at 1:16 PM
Subject: Re: [Lightning-dev] General question on routing difficulties
To: Pedro Moreno Sanchez <pmorenos@purdue.edu>
Cc: lightning-dev@lists.linuxfoundation.org


(final try as the prior mail hit the size limit, sorry for the spam!)

Hi Pedro,

I came across this paper a few weeks ago, skimmed it lightly, and noted a
few interesting aspects I wanted to dig into later. Your email reminded me
to re-read the paper, so thanks for that! Before reading the paper, I
wasn't aware of the concept of coordinate embedding, nor how that could be
leveraged in order to provide sender+receiver privacy in a payment network
using a distance-vector-like routing system. Very cool technique!


After reading the paper again, my current conclusion is that while the
protocol presents some novel traits in the design a routing system for
payment channel based networks, it lends much better to a
closed-membership, credit network, such as Ripple (which is the focus of
the paper).


In Ripple, there are only a handful of gateways, and clients that seek to
interact with the network must chose their gateways *very* carefully,
otherwise consensus faults can occur, violating safety properties of the
network. It would appear that this gateway model nicely translates well to
the concept of landmarks that the protocol is strongly dependant on.
Ideally, each gateway would be a landmark, and as there are a very small
number of gateways within Ripple (as you must be admitted to be a verified
gateway in the network), then parameter L (the total number of landmarks)
is kept small which minimizes routing overhead, the average path-length,
etc.


When we compare Ripple to LN, we find that the two networks are nearly
polar opposites of each other. LN is an open-membership network that
requires zero initial configuration by central administrators(s). It more
closely resembles *debit* network (a series of tubes of money), as the
funds within channels must be pre-committed in order to establish a link
between two nodes, and cannot be increased without an additional on-chain
control transaction (to add or remove funds). Additionally, AFAIK (I'm no
expert on Ripple of course), there's no concept of fees within the
network. While within LN, the fee structure is a critical component of the
inventive for node operators to lift their coins onto this new layer to
provider payment routing services.  Finally, in LN we rely on time-locks
in order to ensure that all transactions are atomic which adds another set
of constraints. Ripple has no such constraint as transfers are based on
bi-lateral trust.


With that said, the primary difference between this protocol is that
currently we utilize a source-routed system which requires the sender to
know "most" of the path to the destination. I say "most" as currently,
it's possible for the receiver of a payment to use a poor man's rendezvous
system to provide the sender with a set of suffix paths form what one can
consider ad-hoc landmarks. The sender can then concatenate these with
their own paths, and construct the Sphinx routing package which encodes
the full route. This itself only gives sender privacy, and the receiver
doesn't know the identity of the sender, but the sender learns the
identity of the receiver.

We have plans to achieve proper sender/receiver privacy by extending our
Sphinx usage to leverage HORNET, such that the payment descriptor (payment
request containing details of the payment) also includes several paths
from rendezvous nodes (Rodrigo's) to the receiver. The rendezvous route
itself will be nested as a further Anonymous Header (AHDR) which includes
the information necessary to complete the onion circuit from Rodrigo to
the receiver. As onion routing is used, only Rodrigo can decrypt the
payload and finalize the route. With such a structure, the only nodes that
need to advertise their channels are nodes which seek to actively serve as
channel routers. All other nodes (phones, laptops, etc), don't need to
advertise their channels to the greater network, reducing the size of the
visible network, and also the storage and validation overhead. This serves
to extend the "scale ceiling" a bit.


My first question is: is it possible to adapt the protocol to allow each
intermediate node to communicate their time lock and fee references to the
sender? Currently, as the full path isn't known ahead of time, the sender
is unable to properly craft the timelocks to ensure safety+atomicity of
the payment. This would mean they don't know what the total timelock
should be on the first outgoing link. Additionally, as they don't know the
total path and the fee schedule of each intermediate node, then once
again, they don't know how much to send on the first out going link. It
would seem that one could extend the probing phase to allow backwards
communication by each intermediate node back to the sender, such that they
can properly craft a valid HTLC. This would increase the set up costs of
the protocol however, and may also increase routing failures as it's
possible incompatibilities arise at run-time between the preferences of
intermediate nodes. Additionally, routes may fail as an intermediate node
consumes too many funds as their fee, causing the funds to be insufficient
when it reaches the destination. One countermeasure would maybe: the
sender always sends waaay more than necessary, and gives the receiver a
one-time payment identifier, requiring that they route the remainder of
the funds *back* to them.


To solve this issue presently, we extend the header in Sphinx to include a
per-hop payload which allows the sender to precisely dictate the
structure of the route, allows the intermediate nodes to authenticate the
information given to it, and also allow the intermediate node to verify
that their policies have properly been respected. These payloads can also
be utilized by applications to communicate a small-ish amount of data to
construct higher-level protocols on top of the system. Examples include:
cross-chain swaps, chance payment games, higher-level B2B protocols,
flavors of ZKCP's, media streaming, internet access proxying, etc.


From my point-of-view, when extended to LN, the core component of the
protocol (landmarks), becomes the weakest component. From my reading,
*all* nodes need to be ware of an *identical* set of landmarks (more or
less similar to the desired homogeneity of Gateways), otherwise the
coordinate embedding scheme breaks down. Currently, there's no requirement
that all nodes have a globally consistent view of the network. So then an
important questions arises: who choose the landmarks? A desirable property
of a routing system for LN (IMO) is that is has close to zero required
initial set up by a central administrator. With this protocol, it would
seem that all nodes much ship with a hard coded set of global landmarks
for the path finding to succeed.  This itself pins a hard coordination
requirement amongst implementers to have something like this deployed.
Even ignoring this requirement for a minute, I see several other
downsides:

   * As *all* payments must flow through landmarks (since nodes break up
     their payment into L sub-flows), the landmarks must be very, very
     well capitalized. This would cause strong consolidation of the
     selection of landmarks, as they need extremely large channels in
     order to facilitate transfer within the network.

   * As landmarks must be globally known, this it seems this would
     introduce fragility in the network. If most of the landmarks go down
     (fails stop crashes) due to hardware issues, DoS, exploited bugs,
     etc, then the network's throughput instantly becomes crippled.

   * If all payment flow *must* go through landmarks, and the transfers
     within the network are relatively uni-directional (all payment going
     to Candy Crush Ultra: Lighting Strikes Twice), then their
     channels would become unbalanced very quickly.


The last point there invokes another component of the network: passive
channel rebalancing. With source routing, it's possible for nodes to
passive rebalance their channels, in order to keep the in equilibrium,
such that on average they'll be able to handle a payment flow coming from
any direction. This is possible as with source routing, it's easy for a
node to simply send a payment to himself incoming/outgoing from the pair
of channels they wish to adjust the available flow of. With
distance-vector-like protocols, this doesn't seem possible, as the node
doesn't have any control of the incoming channel that the payment will
arrive on.


Finally, the notion of value privacy within the scheme seems a bit weak.
From this definition, any protocol that didn't broadcast intents to send
payments to the world would achieve this trait. The base Bitcoin
blockchain doesn't mask the values of transfers (yet), but even if it did
unconditionally maintaining value privacy of channel doesn't seem
compatible with multi-hop payment networks (nodes can simply perform
probing/tagging attacks to ascertain a range of the size of a channel). A
possible mitigation would be for nodes to probabilistically drop incoming
payments, with all nodes sampling from the same distribution. However,
this would dramatically increase routing failures by senders, removing the
"low-latency" trait of payment networks that many find desirable.


Personally, I've very excited to see additional research on the front of
routing within the network! Excellent work by all authors.


In the end, I don't think it'll be a one-size fits all solution, as each
routing protocol delivers with it a set of tradeoffs that should be
weighed depending on target characteristics, and use-cases. There's no
strong requirement that the network as a whole uses a *single* routing
protocol. Instead several distinct protocols can be deployed based on
use-case requirements, as we only need to share a single end-to-end
construct: the HTLC. I could see a future in a few years where we have
several deployed protocols, similar to the wide array of existing routing
protocols deployed on the Internet. What we have currently gets us from
Zero to One. We'll definitely need to experiment with additional
approaches as the size of the network grows, and the true economic flow
patterns emerge after we all deploy to mainnet.


-- Laolu


_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


-- 
- Bryan
http://heybryan.org/
1 512 203 0507

--001a1140a95e26f4b8055ed395de
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_quote">---------- Forwarded messag=
e ----------<br>From: <b class=3D"gmail_sendername">Olaoluwa Osuntokun</b> =
<span dir=3D"ltr">&lt;<a href=3D"mailto:laolu32@gmail.com">laolu32@gmail.co=
m</a>&gt;</span><br>Date: Sat, Nov 25, 2017 at 1:16 PM<br>Subject: Re: [Lig=
htning-dev] General question on routing difficulties<br>To: Pedro Moreno Sa=
nchez &lt;<a href=3D"mailto:pmorenos@purdue.edu">pmorenos@purdue.edu</a>&gt=
;<br>Cc: <a href=3D"mailto:lightning-dev@lists.linuxfoundation.org">lightni=
ng-dev@lists.linuxfoundation.org</a><br><br><br><div dir=3D"ltr">(final try=
 as the prior mail hit the size limit, sorry for the spam!)<div><br></div><=
div><div>Hi Pedro,=C2=A0</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>w=
asn&#39;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 pay=
ment network</div><div>using a distance-vector-like routing system. Very co=
ol technique!</div><div><br></div><div><br></div><div>After reading the pap=
er again, my current conclusion is that while the</div><div>protocol presen=
ts some novel traits in the design a routing system for</div><div>payment c=
hannel based networks, it lends much better to a</div><div>closed-membershi=
p, credit network, such as Ripple (which is the focus of</div><div>the pape=
r).=C2=A0</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 th=
e network must chose their gateways *very* carefully,</div><div>otherwise c=
onsensus faults can occur, violating safety properties of the</div><div>net=
work. It would appear that this gateway model nicely translates well to</di=
v><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 ve=
ry small</div><div>number of gateways within Ripple (as you must be admitte=
d 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-membersh=
ip network that</div><div>requires zero initial configuration by central ad=
ministrators(s). It more</div><div>closely resembles *debit* network (a ser=
ies 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 can=
not be increased without an additional on-chain</div><div>control transacti=
on (to add or remove funds). Additionally, AFAIK (I&#39;m no</div><div>expe=
rt on Ripple of course), there&#39;s no concept of fees within the</div><di=
v>network. While within LN, the fee structure is a critical component of th=
e</div><div>inventive for node operators to lift their coins onto this new =
layer to</div><div>provider payment routing services.=C2=A0 Finally, in LN =
we rely on time-locks</div><div>in order to ensure that all transactions ar=
e atomic which adds another set</div><div>of constraints. Ripple has no suc=
h constraint as transfers are based on</div><div>bi-lateral trust.</div><di=
v><br></div><div><br></div><div>With that said, the primary difference betw=
een this protocol is that</div><div>currently we utilize a source-routed sy=
stem which requires the sender to</div><div>know &quot;most&quot; of the pa=
th to the destination. I say &quot;most&quot; as currently,</div><div>it=
9;s possible for the receiver of a payment to use a poor man&#39;s rendezvo=
us</div><div>system to provide the sender with a set of suffix paths form w=
hat one can</div><div>consider ad-hoc landmarks. The sender can then concat=
enate these with</div><div>their own paths, and construct the Sphinx routin=
g package which encodes</div><div>the full route. This itself only gives se=
nder privacy, and the receiver</div><div>doesn&#39;t know the identity of t=
he sender, but the sender learns the</div><div>identity of the receiver.=C2=
=A0</div><div><br></div><div>We have plans to achieve proper sender/receive=
r privacy by extending our</div><div>Sphinx usage to leverage HORNET, such =
that the payment descriptor (payment</div><div>request containing details o=
f the payment) also includes several paths</div><div>from rendezvous nodes =
(Rodrigo&#39;s) to the receiver. The rendezvous route</div><div>itself will=
 be nested as a further Anonymous Header (AHDR) which includes</div><div>th=
e 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 no=
des that</div><div>need to advertise their channels are nodes which seek to=
 actively serve as</div><div>channel routers. All other nodes (phones, lapt=
ops, etc), don&#39;t need to</div><div>advertise their channels to the grea=
ter network, reducing the size of the</div><div>visible network, and also t=
he storage and validation overhead. This serves</div><div>to extend the &qu=
ot;scale ceiling&quot; a bit.</div><div><br></div><div><br></div><div>My fi=
rst question is: is it possible to adapt the protocol to allow each</div><d=
iv>intermediate node to communicate their time lock and fee references to t=
he</div><div>sender? Currently, as the full path isn&#39;t known ahead of t=
ime, the sender</div><div>is unable to properly craft the timelocks to ensu=
re safety+atomicity of</div><div>the payment. This would mean they don&#39;=
t know what the total timelock</div><div>should be on the first outgoing li=
nk. Additionally, as they don&#39;t know the</div><div>total path and the f=
ee schedule of each intermediate node, then once</div><div>again, they don&=
#39;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 c=
osts of</div><div>the protocol however, and may also increase routing failu=
res as it&#39;s</div><div>possible incompatibilities arise at run-time betw=
een the preferences of</div><div>intermediate nodes. Additionally, routes m=
ay 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 des=
tination. One countermeasure would maybe: the</div><div>sender always sends=
 waaay more than necessary, and gives the receiver a</div><div>one-time pay=
ment identifier, requiring that they route the remainder of</div><div>the f=
unds *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>stru=
cture of the route, allows the intermediate nodes to authenticate the</div>=
<div>information given to it, and also allow the intermediate node to verif=
y</div><div>that their policies have properly been respected. These payload=
s 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 game=
s, higher-level B2B protocols,</div><div>flavors of ZKCP&#39;s, media strea=
ming, internet access proxying, etc.</div><div><br></div><div><br></div><di=
v>From my point-of-view, when extended to LN, the core component of the</di=
v><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), ot=
herwise the</div><div>coordinate embedding scheme breaks down. Currently, t=
here&#39;s no requirement</div><div>that all nodes have a globally consiste=
nt view of the network. So then an</div><div>important questions arises: wh=
o 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 th=
at all nodes much ship with a hard coded set of global landmarks</div><div>=
for the path finding to succeed.=C2=A0 This itself pins a hard coordination=
</div><div>requirement amongst implementers to have something like this dep=
loyed.</div><div>Even ignoring this requirement for a minute, I see several=
 other</div><div>downsides:</div><div><br></div><div>=C2=A0 =C2=A0* As *all=
* payments must flow through landmarks (since nodes break up</div><div>=C2=
=A0 =C2=A0 =C2=A0their payment into L sub-flows), the landmarks must be ver=
y, very</div><div>=C2=A0 =C2=A0 =C2=A0well capitalized. This would cause st=
rong consolidation of the</div><div>=C2=A0 =C2=A0 =C2=A0selection of landma=
rks, as they need extremely large channels in</div><div>=C2=A0 =C2=A0 =C2=
=A0order to facilitate transfer within the network.</div><div><br></div><di=
v>=C2=A0 =C2=A0* As landmarks must be globally known, this it seems this wo=
uld</div><div>=C2=A0 =C2=A0 =C2=A0introduce fragility in the network. If mo=
st of the landmarks go down</div><div>=C2=A0 =C2=A0 =C2=A0(fails stop crash=
es) due to hardware issues, DoS, exploited bugs,</div><div>=C2=A0 =C2=A0 =
=C2=A0etc, then the network&#39;s throughput instantly becomes crippled.</d=
iv><div><br></div><div>=C2=A0 =C2=A0* If all payment flow *must* go through=
 landmarks, and the transfers</div><div>=C2=A0 =C2=A0 =C2=A0within the netw=
ork are relatively uni-directional (all payment going</div><div>=C2=A0 =C2=
=A0 =C2=A0to Candy Crush Ultra: Lighting Strikes Twice), then their</div><d=
iv>=C2=A0 =C2=A0 =C2=A0channels would become unbalanced very quickly.</div>=
<div><br></div><div><br></div><div>The last point there invokes another com=
ponent of the network: passive</div><div>channel rebalancing. With source r=
outing, it&#39;s possible for nodes to</div><div>passive rebalance their ch=
annels, in order to keep the in equilibrium,</div><div>such that on average=
 they&#39;ll be able to handle a payment flow coming from</div><div>any dir=
ection. This is possible as with source routing, it&#39;s easy for a</div><=
div>node to simply send a payment to himself incoming/outgoing from the pai=
r</div><div>of channels they wish to adjust the available flow of. With</di=
v><div>distance-vector-like protocols, this doesn&#39;t seem possible, as t=
he node</div><div>doesn&#39;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&#39;t broadcast in=
tents to send</div><div>payments to the world would achieve this trait. The=
 base Bitcoin</div><div>blockchain doesn&#39;t mask the values of transfers=
 (yet), but even if it did</div><div>unconditionally maintaining value priv=
acy of channel doesn&#39;t seem</div><div>compatible with multi-hop payment=
 networks (nodes can simply perform</div><div>probing/tagging attacks to as=
certain a range of the size of a channel). A</div><div>possible mitigation =
would be for nodes to probabilistically drop incoming</div><div>payments, w=
ith all nodes sampling from the same distribution. However,</div><div>this =
would dramatically increase routing failures by senders, removing the</div>=
<div>&quot;low-latency&quot; trait of payment networks that many find desir=
able.=C2=A0</div><div><br></div><div><br></div><div>Personally, I&#39;ve ve=
ry excited to see additional research on the front of</div><div>routing wit=
hin the network! Excellent work by all authors.</div><div><br></div><div><b=
r></div><div>In the end, I don&#39;t think it&#39;ll be a one-size fits all=
 solution, as each</div><div>routing protocol delivers with it a set of tra=
deoffs that should be</div><div>weighed depending on target characteristics=
, and use-cases. There&#39;s no</div><div>strong requirement that the netwo=
rk as a whole uses a *single* routing</div><div>protocol. Instead several d=
istinct 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 deplo=
yed protocols, similar to the wide array of existing routing</div><div>prot=
ocols deployed on the Internet. What we have currently gets us from</div><d=
iv>Zero to One. We&#39;ll definitely need to experiment with additional</di=
v><div>approaches as the size of the network grows, and the true economic f=
low</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=3D"mailto:Lightning-dev@lists.linuxfoundation.org">Lightning-dev@li=
sts.<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev=
" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>o=
rg/mailman/listinfo/<wbr>lightning-dev</a><br>
<br></div><br><br clear=3D"all"><div><br></div>-- <br><div class=3D"gmail_s=
ignature" data-smartmail=3D"gmail_signature">- Bryan<br><a href=3D"http://h=
eybryan.org/" target=3D"_blank">http://heybryan.org/</a><br>1 512 203 0507<=
/div>
</div>

--001a1140a95e26f4b8055ed395de--