4 ms·

Please explain how the Lightning Network developers solve an unsolved NP-Hard problem in computer science regarding routing? [1] The Lightning Network design i

by 0wing 9y ago

Please explain how the Lightning Network developers solve an unsolved NP-Hard problem in computer science regarding routing? [1] The Lightning Network design is exactly what the first sentence of Satoshi's Bitcoin whitepaper seeks to avoid - payment processor middlemen. "A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution." [2] The LN design was chosen as a solution by certain investors who want to extract fees as payment hub liquidity providers. LN can't solve the TSP without either publishing a map of all nodes and routes, or having all nodes broadcasts to all nodes. The former significantly reduces decentralization and further removes the "electronic cash" aspect requiring payment processor hubs, while the latter will suffer from latency/scaling issues/DDoS susceptibility. [1] https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem [2] https://bitcoin.org/bitcoin.pdf https://bitcoin.org/bitcoin.pdf

tananaev 9y ago
Personally I don't really mind having a few main hubs because Lightning Network allows trust-less payments. Your hub can never steal your money. It's guaranteed by math and Bitcoin network itself. Lightning Network might not be perfect solution, but it is a solution to scaling problem. Increasing block size is certainly not a long term solution.
- aiCeivi9 9y ago
  > Your hub can never steal your money But it can keep coins that remain in them until the channel expires and for usable channels it will be at least a month or two. So some amount of trust is required. Also, unless I don't know about something, wallet software needs to store additional data for LN to work that can't be just reconstructed from private key/paper wallet.
  - keymone 9y ago
    what incentive does a hub have to do that? it's easy to accuse a hub in doing that but it's trivial for a hub to prove they aren't. if it is ever proven that hub holds on to somebody's channel - the hub loses reputation and customers.
jstanley 9y ago
Fiestly, LN routing is actually closer to a shortest-path problem than the TSP. Secondly, even if it was the TSP, you don't need to 100% solve it in order to have a working system. How do you think actual travelling salesmen can exist? They just pick a good enough route, nobody is checking whether they picked the perfect route, and nobody cares.
- 0wing 9y ago
  Either the Lightning Network has found a solution to the routing problem which the entire internet has relied upon since 1989 [1], or the LN marketing is disingenuous and the actual implementation will be nothing more than an excuse to extract wealth to centralized payment processor hubs, further distancing Bitcoin from the main design of electronic cash: "A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution." [1] http://www.washingtonpost.com/sf/business/2015/05/31/net-of-insecurity-part-2/ http://www.washingtonpost.com/sf/business/2015/05/31/net-of-...
  - SkyMarshal 9y ago
    jstanley makes a very good point, especially considering that Bitcoin itself is a probabilistic good-enough solution to the Byzantine Generals Problem, rather than a perfect deterministic one. But you didn't even address jstanley's question, you just repeated the exact same talking points you posted higher up in this thread, hoping that readers can't tell the difference. That is not an honest debate, but propaganda. The constant repetition of talking points without actually addressing the critiques of those talking points may fool the gullible, but the technologically savvy see it, and it costs you your credibility with them. You guys are like Marco Rubio [1] constantly repeating the same talking points regardless what critiques are thrown your way. [1]:https://www.youtube.com/watch?v=b4-OTvTrw1A https://www.youtube.com/watch?v=b4-OTvTrw1A
    - 0wing 9y ago
      I cited BGP. You've provided no technical details, only an ad hominem fallacy. Feel free to explain actual technical details of how LN does anything interesting, other than further centralize Bitcoin into centralized payment processor hubs? As per the LN white paper: 8.4 Payment Routing It is theoretically possible to build a route map implicitly from observing 2-of-2 multisigs on the blockchain to build a routing table. Note, however, this is not feasible with pay-to-script-hash transaction outputs, which can be resolved out-of-band from the bitcoin protocol via a third party routing service. Building a routing table will become necessary for large operators (e.g. BGP, Cjdns). Eventually, with optimizations, the network will look a lot like the correspondent banking network, or Tier-1 ISPs.
blhack 9y ago
It's kidnof getting creepy to me how much people seem to be treating bitcoin like a religion, especially bcash proponents. Satoshi Nakamoto is not a god. The white paper is not a gospel. This is a technology project. It's okay to rethink the possible ways of solving the problem 8 years into it.
- 0wing 9y ago
  This is why there's thousands of new crypto-currency designs improving on the flaws of Satoshi's implementation. Not only is it easy to start fresh, but it's measurably more fair for new users to avoid BTC/ETH and other early cryptocoins which use manipulative ponzi/pyramid like work:coin production:time algorithms which exploit "late" users.
keymone 9y ago
seems like you've heard the term and quickly decided that it describes something unsolvable in principle. the truth is, that NP-hardness is only true for perfect solution in polynomial time. good-enough solutions can be found in finite time intervals just fine, there are plenty of practical implementations of that. ever heard of this thing called "delivery companies"? well they solve TSP sub-optimally millions of times every day. shocker, i know.
- 0wing 9y ago
  Right... except the internet is not a physical space so tell me how do you measure distance between nodes? Latency? Let's look at the Lightening network white paper: 8.4 Payment Routing It is theoretically possible to build a route map implicitly from observing 2-of-2 multisigs on the blockchain to build a routing table. Note, however, this is not feasible with pay-to-script-hash transaction outputs, which can be resolved out-of-band from the bitcoin protocol via a third party routing service. Building a routing table will become necessary for large operators (e.g. BGP, Cjdns). Eventually, with optimizations, the network will look a lot like the correspondent banking network, or Tier-1 ISPs. So LN cites the need for large liquidity providers to act as hubs, essentially payment processor hubs. Why not just use venmo at that point? Why would someone want to use Bitcoin with the LN, especially if it requires them buying Bitcoin from someone else?
  - keymone 9y ago
    Unsurprisingly your reply has nothing to do with your original speculation that LN can’t work because of TSP.
    - 0wing 9y ago
      ??? The routing problem of internet nodes: the internet is not a physical space so tell me how do you measure distance between nodes? To which you have no answer. As stated in the OP: LN can't solve the TSP without either publishing a map of all nodes and routes, or having all nodes broadcasts to all nodes. Unsurprisingly you didn't read the original post, nor contribute any response to the critique or technical implementation of routing in the LN design. LN relies on hubs and a map. It's setup to extract wealth into centralized liquidity providers. This is antithetical to cash, and at this point why not use a faster centralized service like venmo?

by 0wing 9y ago

tananaev 9y ago

Personally I don't really mind having a few main hubs because Lightning Network allows trust-less payments. Your hub can never steal your money. It's guaranteed by math and Bitcoin network itself. Lightning Network might not be perfect solution, but it is a solution to scaling problem. Increasing block size is certainly not a long term solution.

aiCeivi9 9y ago
> Your hub can never steal your money But it can keep coins that remain in them until the channel expires and for usable channels it will be at least a month or two. So some amount of trust is required. Also, unless I don't know about something, wallet software needs to store additional data for LN to work that can't be just reconstructed from private key/paper wallet.
- keymone 9y ago
  what incentive does a hub have to do that? it's easy to accuse a hub in doing that but it's trivial for a hub to prove they aren't. if it is ever proven that hub holds on to somebody's channel - the hub loses reputation and customers.

jstanley 9y ago

Fiestly, LN routing is actually closer to a shortest-path problem than the TSP. Secondly, even if it was the TSP, you don't need to 100% solve it in order to have a working system. How do you think actual travelling salesmen can exist? They just pick a good enough route, nobody is checking whether they picked the perfect route, and nobody cares.

0wing 9y ago
Either the Lightning Network has found a solution to the routing problem which the entire internet has relied upon since 1989 [1], or the LN marketing is disingenuous and the actual implementation will be nothing more than an excuse to extract wealth to centralized payment processor hubs, further distancing Bitcoin from the main design of electronic cash: "A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution." [1] http://www.washingtonpost.com/sf/business/2015/05/31/net-of-insecurity-part-2/ http://www.washingtonpost.com/sf/business/2015/05/31/net-of-...
- SkyMarshal 9y ago
  jstanley makes a very good point, especially considering that Bitcoin itself is a probabilistic good-enough solution to the Byzantine Generals Problem, rather than a perfect deterministic one. But you didn't even address jstanley's question, you just repeated the exact same talking points you posted higher up in this thread, hoping that readers can't tell the difference. That is not an honest debate, but propaganda. The constant repetition of talking points without actually addressing the critiques of those talking points may fool the gullible, but the technologically savvy see it, and it costs you your credibility with them. You guys are like Marco Rubio [1] constantly repeating the same talking points regardless what critiques are thrown your way. [1]:https://www.youtube.com/watch?v=b4-OTvTrw1A https://www.youtube.com/watch?v=b4-OTvTrw1A
  - 0wing 9y ago
    I cited BGP. You've provided no technical details, only an ad hominem fallacy. Feel free to explain actual technical details of how LN does anything interesting, other than further centralize Bitcoin into centralized payment processor hubs? As per the LN white paper: 8.4 Payment Routing It is theoretically possible to build a route map implicitly from observing 2-of-2 multisigs on the blockchain to build a routing table. Note, however, this is not feasible with pay-to-script-hash transaction outputs, which can be resolved out-of-band from the bitcoin protocol via a third party routing service. Building a routing table will become necessary for large operators (e.g. BGP, Cjdns). Eventually, with optimizations, the network will look a lot like the correspondent banking network, or Tier-1 ISPs.

blhack 9y ago

It's kidnof getting creepy to me how much people seem to be treating bitcoin like a religion, especially bcash proponents. Satoshi Nakamoto is not a god. The white paper is not a gospel. This is a technology project. It's okay to rethink the possible ways of solving the problem 8 years into it.

0wing 9y ago
This is why there's thousands of new crypto-currency designs improving on the flaws of Satoshi's implementation. Not only is it easy to start fresh, but it's measurably more fair for new users to avoid BTC/ETH and other early cryptocoins which use manipulative ponzi/pyramid like work:coin production:time algorithms which exploit "late" users.

keymone 9y ago

seems like you've heard the term and quickly decided that it describes something unsolvable in principle. the truth is, that NP-hardness is only true for perfect solution in polynomial time. good-enough solutions can be found in finite time intervals just fine, there are plenty of practical implementations of that. ever heard of this thing called "delivery companies"? well they solve TSP sub-optimally millions of times every day. shocker, i know.

0wing 9y ago
Right... except the internet is not a physical space so tell me how do you measure distance between nodes? Latency? Let's look at the Lightening network white paper: 8.4 Payment Routing It is theoretically possible to build a route map implicitly from observing 2-of-2 multisigs on the blockchain to build a routing table. Note, however, this is not feasible with pay-to-script-hash transaction outputs, which can be resolved out-of-band from the bitcoin protocol via a third party routing service. Building a routing table will become necessary for large operators (e.g. BGP, Cjdns). Eventually, with optimizations, the network will look a lot like the correspondent banking network, or Tier-1 ISPs. So LN cites the need for large liquidity providers to act as hubs, essentially payment processor hubs. Why not just use venmo at that point? Why would someone want to use Bitcoin with the LN, especially if it requires them buying Bitcoin from someone else?
- keymone 9y ago
  Unsurprisingly your reply has nothing to do with your original speculation that LN can’t work because of TSP.
  - 0wing 9y ago
    ??? The routing problem of internet nodes: the internet is not a physical space so tell me how do you measure distance between nodes? To which you have no answer. As stated in the OP: LN can't solve the TSP without either publishing a map of all nodes and routes, or having all nodes broadcasts to all nodes. Unsurprisingly you didn't read the original post, nor contribute any response to the critique or technical implementation of routing in the LN design. LN relies on hubs and a map. It's setup to extract wealth into centralized liquidity providers. This is antithetical to cash, and at this point why not use a faster centralized service like venmo?