Re: [Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

2019-03-31 Thread Ariel Lorenzo-Luaces
> I am forking this thread as my reply is not at all related to the JIT-Routing.

Sorry I think my last reply was also getting off subject as well.
Thank you for forking the thread

> Nonexistent channels (i.e. channels that do not have some backing UTXO in the 
> Bitcoin blockchain) are not safe to propagate on the network since they are 
> trivially spammable (i.e. can generate a large number of fake channels to 
> waste network bandwidth).

I hadn't considered the effect this gossip would have on the network.
Definitely nodes should not trust one another to tell the truth about
nonexistent channels.

The source node could blindly allow intermediate nodes to create
sub-routes to the next hop.
But I wouldn't favor this blind routing idea because fee calculations
would be a complete guesses.

> A good pruning heuristic is "channel capacity", which can be checked onchain 
> (the value of the UTXO backing the channel is the channel capacity).
> It is good to keep channels with large capacity in the routemap, because such 
> large channels are more likely to successfully route a payment than smaller 
> channels.
> So it is reasonable to delete channels with low capacity when the routemap 
> memory is becoming close to full.

I'm generally concerned about these heuristics because any time nodes
can game a heuristic they will be expected to do so.
Gaming a heuristic can be good or bad depending on the side-effects.
One side effect of the "channel capacity" heuristic is more reliable
payments but another side effect is that low capacity (but possibly
reliable) channels are neglected.

> It seems to me that s/aggregate-channel/high-capacity-channel/g in your idea 
> would still work.
> In effect, the high-capacity channel is very likely to successfully route in 
> either direction.
> But if by chance it falls into a state where it is unable to route in one 
> direction or other, the intermediate node has other, lower-capacity channels 
> that it can use JIT-Routing with to improve the directionality of the 
> high-capacity channel.
> Nothing in the JIT-Routing idea requires that the rebalancing loop is small, 
> only that a loop exists.
>
> Nodes still need to track their direct channels (so they are implicitly 
> always in the routemap).
> But payee nodes making BOLT1 invoices could also provide `r` routes in the 
> invoice, with the given routes being from nodes with high-capacity channels, 
> so that even if the intermediate channels are pruned due to low capacity, it 
> is possible to get paid.

Without low capacity channels spontaneous payments would not work. Or
they would depend on asking for an invoice under the hood.
It feels to me that at some point, someone with complete knowledge of
the network needs to be employed.

Cheers
Ariel Lorenzo-Luaces

On Mar 28, 2019, 9:51 PM, at 9:51 PM, ZmnSCPxj  wrote:
>Good morning Ariel,
>
>I am forking this thread as my reply is not at all related to the
>JIT-Routing.
>
>
>Sent with ProtonMail Secure Email.
>
>> Public nodes could advertise channels which don't actually exist
>directly but are instead hidden paths that the source node doesn't need
>to know or care about. The fees advertised for these aggregate-channels
>would be the aggregate fees expected from the sub-route.
>
>Nonexistent channels (i.e. channels that do not have some backing UTXO
>in the Bitcoin blockchain) are not safe to propagate on the network
>since they are trivially spammable (i.e. can generate a large number of
>fake channels to waste network bandwidth).
>
>> I think the biggest gain from this system is that the network can be
>more abstract. This abstraction allows all possible subsets of public
>nodes to be a clique since all subsets of nodes can be maximally
>connected with aggregate-channels as long as the entire network is well
>connected.
>> This new property of the network could allow a source node to select
>a random privacy-clique and rely on payments to be routed along
>aggregate-channels without the source node needing to compute or even
>know the exact sub-routes. Futhermore, the source node could
>exclusively download and listen to the privacy-clique and ignore the
>rest of the network structure thus reducing the burden of keeping up to
>date network information.
>
>Let me suggest something else.
>
>As the LN grows, the public routemap becomes larger and larger, until
>keeping them in a fast in-memory data structure becomes infeasible on
>cheap hardware.
>In all likelihood, at some point in the future, users will want to be
>able to limit the memory consumed by implementations for routemaps.
>
>So, some pruning heuristic is needed, to reduce the resource usage of
>large routemaps.
>
>A good pruning heuristic is "channel capacity", which can be checked
>onchain (the value of the UTXO backing the channel is the channel
>capacity).
>It is good to keep channels with large capacity in the routemap,
>because such large channels are more likely to successfully route a
>payment than 

Re: [Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

2019-03-31 Thread Ariel Luaces
> I am forking this thread as my reply is not at all related to the JIT-Routing.

Sorry I think my last reply was also getting off subject as well.
Thank you for forking the thread

> Nonexistent channels (i.e. channels that do not have some backing UTXO in the 
> Bitcoin blockchain) are not safe to propagate on the network since they are 
> trivially spammable (i.e. can generate a large number of fake channels to 
> waste network bandwidth).

I hadn't considered the effect this gossip would have on the network.
Definitely nodes should not trust one another to tell the truth about
nonexistent channels.

The source node could blindly allow intermediate nodes to create
sub-routes to the next hop.
But I wouldn't favor this blind routing idea because fee calculations
would be a complete guess.

> A good pruning heuristic is "channel capacity", which can be checked onchain 
> (the value of the UTXO backing the channel is the channel capacity).
> It is good to keep channels with large capacity in the routemap, because such 
> large channels are more likely to successfully route a payment than smaller 
> channels.
> So it is reasonable to delete channels with low capacity when the routemap 
> memory is becoming close to full.

I'm generally concerned about these heuristics because any time nodes
can game a heuristic they will be expected to do so.
Gaming a heuristic can be good or bad depending on the side-effects.
One side effect of the "channel capacity" heuristic is more reliable
payments but another side effect is that low capacity (but possibly
reliable) channels are neglected

> It seems to me that s/aggregate-channel/high-capacity-channel/g in your idea 
> would still work.
> In effect, the high-capacity channel is very likely to successfully route in 
> either direction.
> But if by chance it falls into a state where it is unable to route in one 
> direction or other, the intermediate node has other, lower-capacity channels 
> that it can use JIT-Routing with to improve the directionality of the 
> high-capacity channel.
> Nothing in the JIT-Routing idea requires that the rebalancing loop is small, 
> only that a loop exists.
>
> Nodes still need to track their direct channels (so they are implicitly 
> always in the routemap).
> But payee nodes making BOLT1 invoices could also provide `r` routes in the 
> invoice, with the given routes being from nodes with high-capacity channels, 
> so that even if the intermediate channels are pruned due to low capacity, it 
> is possible to get paid.

Without low capacity channels spontaneous payments would not work. Or
they would depend on asking for an invoice under the hood.
It feels to me that at some point, someone with complete knowledge of
the network needs to eb employed.

Cheers
Ariel Lorenzo-Luaces
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

2019-03-31 Thread ZmnSCPxj via Lightning-dev
Good morning Ariel,



> > A good pruning heuristic is "channel capacity", which can be checked 
> > onchain (the value of the UTXO backing the channel is the channel capacity).
> > It is good to keep channels with large capacity in the routemap, because 
> > such large channels are more likely to successfully route a payment than 
> > smaller channels.
> > So it is reasonable to delete channels with low capacity when the routemap 
> > memory is becoming close to full.
>
> I'm generally concerned about these heuristics because any time nodes
> can game a heuristic they will be expected to do so.
> Gaming a heuristic can be good or bad depending on the side-effects.
> One side effect of the "channel capacity" heuristic is more reliable
> payments but another side effect is that low capacity (but possibly
> reliable) channels are neglected

The heuristic is gameable at the cost of devoting more capacity to Lightning.
It is also quite incentive-compatible to source nodes with limited storage but 
which may need to forward arbitrary amounts to arbitrary nodes.

Low capacity channels cannot be used at all if their capacity is below my 
payment amount, no matter how reliable they may be, unless I do multipart 
payments, which increases base fee paid.

>
> > It seems to me that s/aggregate-channel/high-capacity-channel/g in your 
> > idea would still work.
> > In effect, the high-capacity channel is very likely to successfully route 
> > in either direction.
> > But if by chance it falls into a state where it is unable to route in one 
> > direction or other, the intermediate node has other, lower-capacity 
> > channels that it can use JIT-Routing with to improve the directionality of 
> > the high-capacity channel.
> > Nothing in the JIT-Routing idea requires that the rebalancing loop is 
> > small, only that a loop exists.
> > Nodes still need to track their direct channels (so they are implicitly 
> > always in the routemap).
> > But payee nodes making BOLT1 invoices could also provide `r` routes in the 
> > invoice, with the given routes being from nodes with high-capacity 
> > channels, so that even if the intermediate channels are pruned due to low 
> > capacity, it is possible to get paid.
>
> Without low capacity channels spontaneous payments would not work.

They would not be prevented a priori, only if all channels it has are too small 
to be kept in memory by typical source nodes.

If I truly wanted to help such a node, I might make a large capacity channel to 
it and then send my spontaneous payment.

> Or
> they would depend on asking for an invoice under the hood.

Which I think is better for spontaneous payments.

> It feels to me that at some point, someone with complete knowledge of
> the network needs to eb employed.


Indeed.
See the trampoline payments thread also under discuasion.


Regards,
ZmnSCPxj

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


Re: [Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

2019-03-31 Thread ZmnSCPxj via Lightning-dev
Good morning Rene,

>
> Maybe I oversee something - in that case sorry for spamming the list - but I 
> don't understand how you could know the distance from yourself if you don't 
> know the entire topology? (unless u use it on the pruned view as you 
> suggested) 

That is correct, and the reason that it would still lose determinism (and thus 
be hard to test anyway), as I lamented.
At least for a pruning heuristic like you proposed (i.e. probabilistically 
prune channels) it is possible to make deterministic with a fixed RNG seed.

For instance a node might concatenate its own public key with the 
short-channel-id (in some fixed byte order) of the channel, hash the 
concatenation, then use the hash as the seed of an RNG that gives 1 bit, and 
prune the channel if the bit is cleared (to remove half the channels in the 
routemap).

>
> On the other hand querying for a certain depth would be possible with the 
> suggested `query ask egonetwork` in case for depth 3 one would have to peer 
> with the nodes from the friend of a friend network. 

But for this, you would require that every node also keep every channel with 
depth less than your maximum query amount.

Perhaps for friend-of-friend, it might be sufficient to just query a peer to 
give its own direct public channels, which it needs to remember anyway.
But that is basically only a depth of 2 (if we count depth of 1 as your direct 
channels).

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-03-31 Thread ZmnSCPxj via Lightning-dev
Good morning Rene and Pierre,

An issue here (which I think also affects Rendezvous Routing) is with 
compatibility of the HMAC.

HMAC covers the entire 1300-byte `hops_data` field.

If, in order to reach the next trampoline, more than one intermediate node is 
inserted, would the packet that reaches the next trampoline have a valid HMAC 
still?
Consider that the filler data generated by the current trampoline to 
communicate with intermediate nodes may cause different filler data to be XORed 
with the 0x00 data added to left-shift the data at each intermediate node.
(I am unsure if I express myself coherently here)

So for example, suppose I am the source and I trampoline to nodes B and C, and 
pay to destination D.
Suppose B is a direct neighbor of mine, but I have no idea where C and D are.

Suppose for simplicity that the onion packet is just 6 hops long.
So I initialize as:

[ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]

I right shift and insert destination D:

[ D, here's my payment ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]

Then I encrypt with some shared secret known by me A and D:

[ encrypt(A * D, "D, here's my payment") ] [ encrypt(A * D, 0) ] [ encrypt(A * 
D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ]

Then I right shift and insert trampoline C:

[ C, send this to D ] [ encrypt(A * D, "D, here's my payment") ] [ encrypt(A * 
D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ]

Then I encrypt with some shared secret known by me A and C:

[ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, encrypt(A * D, "D, 
here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, 
encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, 
encrypt(A * D, 0)) ]

Then I right shift and insert trampoline B:

[ B, send this to C ] [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, 
encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] 
[ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ]

And encrypt with A * B:

[ encrypt(A * B, "B, send this to C") ] [ encrypt(A * B, encrypt(A * C, "C, 
send this to D")) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, "D, here's 
my payment"))) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] [ 
encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] [ encrypt(A * B, encrypt(A 
* C, encrypt(A * D, 0))) ]

I send this to B, who removes one layer of encryption:

[ B, send this to C ] [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, 
encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] 
[ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ]

Now B finds the shortest route involves nodes N and O before reaching C.
So B has to insert N and O, pushing out one packet from the end.
But the pushed-out packet will no longer be recoverable and it cannot be 
re-encrypted except by A.

(Unless I misunderstand the onion construction)


Unless we propose to massively change the onion packet construction...?


> 1.) A different fee mechanism. Let us (only as a radical thought experiment) 
> assume we drop the privacy of the final amount in routing.

Please no.

> A sending node could offer a fee for successful routing. Every routing node 
> could decide how much fee it would collect for forwarding. Nodes could try to 
> collect larger fees than the min they announce but that lowers the probably 
> for the payment to be successful. Even more radical: Nodes would not even 
> have to announce min fees anymore. Turning routing and fees to a real 
> interactive market

Would this not also require that intermediate nodes know the ultimate 
destination of the payment?
How would intermediate nodes find out which next hop would be reasonable?

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev