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-04-09 Thread ZmnSCPxj via Lightning-dev
Good morning m.a.holden,


> > Let me clarify: When you say "node" here, do you mean Lightning Network 
> > node?
> > Or do you mean instead an in-memory node?
>
> Neither. I meant a node in a tree. I tried to use the term bucket to make the 
> distinction between this and Lightning node.
> The tree is not strictly in-memory. There is a purely conceptual global 
> quadtree.

Can you then be more specific what is the behavior of a specific node?
Note I use the term "node" specifically to refer to Lightning Network Node.

Given the node has space for N channels or N nodes (or whatever), how does the 
node prune its routemap?
What gossip messages do it ignore and which ones do it check?

If that node has to pay to a node that is not in its routemap, how does it 
perform the routemap lookup?

>
> Each bucket is essentially a view over the union of its 4 children. The 
> bucket 00b is (b U 0001b U 0010b U 0011b). The bucket 0011b is (001100b U 
> 001101b U 001110b 00b), etc. Each client choses a suitable max_depth <= 
> HASHLEN/2, and the leaves of their tree contain a set of all PKH whose prefix 
> matches the bucket index. A client will keep, at minimum, a subtree of the 
> global quadtree (and both nodes for all channels where at least one of the 
> nodes is in the same subtree).

When you refer to "sub-tree", do you mean each node stores a tree of certain 
maximum height, with the root of that tree being some random node on the global 
tree?

When you refer to "bucket spilling", what does it mean when the buvket has to 
spill beyond the maximum height of the tree that the node is willing to store?
Obviously some kind of pruning has to be done.
That is the whole point of this exercise.

I still do not see the benefit of your lookup scheme if the lookup scheme is 
just in-memory.
That is not what is interesting at all.
What is interesting is remote lookup, over the network.
It is what must be carefully designed, as the network cannot be trusted and 
anyone can be an attacker and anyone can be a victim.

Suppose a node decides to store the prefix 0b, storing the subtree at 
that point with a height of only 2 (for simplicity).
What happens when it needs to look for a node with prefix 0b01101101?
Does it mean the node has to somehow store nodes that are outside of the prefix 
it decides to store?
Just what data does it have to store?
And why not just use a dist() measure like I proposed?

> > As I understand your proposal, taking over or taking down a node near the 
> > root of the tree will make it difficult to look up several nodes at once.
> > This is because the tree nature makes nodes near the root of the tree (top 
> > of the hierarchy) much more important than leaf nodes, which only worry 
> > about themselves.
>
> If a node advertises itself near the top of the tree then it will be a better 
> information provider than others, but this is never at the exclusion of 
> others below it. All of the information a node in the parent bucket holds is 
> held in part by the nodes in the child buckets. The parent does not know 
> anything that other people don't know too. No nodes are "more important", but 
> they might potentially be "more optimal".

We should face the fact that nodes that know more about the network are "more 
important", really.
Thus, they should be protected.
The simplest protection is to anonymize them by never revealing how much each 
node actually knows of the network.
This enforces that all nodes are peers, with nobody being easily visible as 
more important than anyone else.


Instead, each node that is used in lookup can simply silently delegate (without 
informing whoever is asking) the lookup to some other arbitrary node that it 
knows is more likely to know the destination.
That node might know more than this node, or less, but it is immaterial --- no 
node knows how much each node knows.


>
> If you know about some nodes in bucket 0011b, but none in 0001b where a 
> payment destination is, then you could query any node in 0011b and ask about 
> any nodes in bucket 0001b. Since the buckets are nearby, there is a greater 
> probability that they'll know about more nodes than somebody further away. 
> This would be similar to how your proposal operates.

Then just use my proposal.
It is simpler and I already presented the algorithms used by each node in 
detail, including how each node limits the memory it uses for routemap.

As I mentioned, the point is to provide anonymity by not revealing how much you 
know.
There is a tradeoff between anonymity and some measure of efficiency.
Obviously, I prioritize anonymity, else I would not be ZmnSCPxj.


> you could query any node in 0011b and ask about any nodes in bucket 0001b

In order to query a node, you need to know that node, meaning it (and at least 
one route to it) is stored somewhere in your (limited) memory.

Note that even now in the network, some nodes do not provide a way to contact 
them directly --- you can 

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-04-08 Thread m.a.holden via Lightning-dev
Hi ZmnSCPxj,

> Let me clarify: When you say "node" here, do you mean Lightning Network node?
> Or do you mean instead an in-memory node?

Neither. I meant a node in a tree. I tried to use the term bucket to make the 
distinction between this and Lightning node.
The tree is not strictly in-memory. There is a purely conceptual global 
quadtree.

Each bucket is essentially a view over the union of its 4 children. The bucket 
00b is (b U 0001b U 0010b U 0011b). The bucket 0011b is (001100b U 001101b 
U 001110b 00b), etc. Each client choses a suitable max_depth <= HASHLEN/2, 
and the leaves of their tree contain a set of all PKH whose prefix matches the 
bucket index. A client will keep, at minimum, a subtree of the global quadtree 
(and both nodes for all channels where at least one of the nodes is in the same 
subtree).

As you state, you can use any data structure for storing this in memory, but 
there are obvious benefits to using a quadtree-index to mirror the conceptual 
global one in terms of efficient querying, filtering, spilling, aggregating 
branch sizes.

If many clients follow the convention then the optimisation opportunities 
arise, because the majority of routes will be discoverable with a single 
(possibly parallel) query to the network. Gossip size can be reduced and 
unwanted gossip can be eliminated, which alleviates the most constrained 
resource, bandwidth. If the conventions are widely followed, the benefits are 
maximized for everybody. Not following convention does not break things, it 
just limits the potential wins.

---

> As I understand your proposal, taking over or taking down a node near the 
> root of the tree will make it difficult to look up several nodes at once.
> This is because the tree nature makes nodes near the root of the tree (top of 
> the hierarchy) much more important than leaf nodes, which only worry about 
> themselves.

If a node advertises itself near the top of the tree then it will be a better 
information provider than others, but this is never at the exclusion of others 
below it. All of the information a node in the parent bucket holds is held in 
part by the nodes in the child buckets. The parent does not know anything that 
other people don't know too. No nodes are "more important", but they might 
potentially be "more optimal".

If you know about some nodes in bucket 0011b, but none in 0001b where a payment 
destination is, then you could query any node in 0011b and ask about any nodes 
in bucket 0001b. Since the buckets are nearby, there is a greater probability 
that they'll know about more nodes than somebody further away. This would be 
similar to how your proposal operates. If somebody did advertise being in 
bucket 00b, then they're able to find a potentially better (shorter) path to 
the destination because they know more information and you don't need to find a 
path through multiple buckets. If they are under DDoS, it doesn't bring down 
the network or limit access to the child buckets - it just makes it trivially 
less optimal to route because it *might* (low probability) require more queries 
to reach the destination.

When querying, it is expected that if you know about any nodes in the same 
bucket as the payment destination, then there's a high probability that they 
will know a route to the destination. A parent bucket of that bucket is not any 
more likely to know about the destination, they have the same information. I've 
shown that at small depth, there's a high probability that you will have 
knowledge about a reasonable quantity of paths to every other bucket in the 
global network - so the majority of payments will only need to visit one bucket 
outside your own. The reason to specifically query parent buckets is limited, 
and not ultimately necessary.

The only way I can see the problem you raise being a concern is if 
misconfigured clients have an unreasonably large depth for the amount of 
information in the network, such that there are few, or no channels from their 
own bucket to other buckets. In that case, they might become over-reliant on 
the parent's buckets to receive payments, but there are likely to be numerous 
parents at every depth of the tree (correctly configured clients), meaning 
there isn't a clear-cut target that an attacker could DDoS to try and disrupt a 
bucket.

Nodes do not need to present the real depth at which they keep gossip, but 
there are potentially greater fee-earning opportunities if publicly advertising 
their maximum information capability. Nodes could counterbalance potential DDoS 
risk with higher routing fees, where people might pay more to have a greater 
chance of finding shorter routes in fewer queries, but a frugal client would 
simply chose the cheapest routes, and the more expensive routes via parent 
buckets would be less desirable to them - meaning DDoS on nodes in parent 
buckets may be wasted effort because it would drive people towards saving money 
on fees. Also, since 

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-04-07 Thread ZmnSCPxj via Lightning-dev
Good morning m.a.holden,


Sent with ProtonMail Secure Email.

‐‐‐ Original Message ‐‐‐
On Saturday, April 6, 2019 10:39 AM, m.a.holden m.a.hol...@protonmail.com wrote:

> Good morning ZmnSCPxj,
> I'll try to clarify my proposal further, but also have a few questions about 
> yours.
>
> > Now, it seems to me what you propose, is to have octrees contain octrees, 
> > and so on.
>
> There's one global tree, which is the same for all users. Every node in the 
> tree has a bucket and exactly 4 child nodes, except leaves have no children. 
> The tree has a max depth, which each client sets itself. The theoretical 
> maximum being HASHLEN/2 (In practice, we're likely to be concerned about <8). 
> Note that every parent's bucket contains all of the information of all of its 
> children's buckets - meaning the root node of the global quadtree is 
> equivalent to the unfiltered global network. Nodes pick a depth and concern 
> themselves with the bucket at that depth, unless it overflows, in which case 
> they increase the depth by 1.

Let me clarify: When you say "node" here, do you mean Lightning Network node?
Or do you mean instead an in-memory node?

If you mean "Lightning Network Node", then how can lookup proceed if a node 
that should be looked through at some step is brought down by a targeted DDoS?
What happens if a node near the root of the tree, which is handling lookup for 
much more of the network, is brought down?
In my mechanism, the answer is: you try another node, and as long as that node 
has a dist(that node, target node) lower than yours, the algorithm will 
progress.
This is because in my mechanism, each node does not have some fixed set of 4 
other nodes that are the only nodes referred to when doing lookup.

If you mean in-memory node, then I do not see how relevant it is, the structure 
that some implementation uses.
You can use a bag, set, tree, or whatever base structure.
But the number of Lightning Network nodes and channels any one node can store 
is finite since the memory available to that node is finite.
The issue is how to get help from some other node(s) when the target node is 
not in your routemap.

--

Any tree structure is, looking only at the nodes and edges, indistinguishable 
from a hierarchy.
And takeovers of hierarchies are simple: simply attack the easiest target near 
the top of the hierarchy / root of the tree.
Hierarchies are excessively centralized and we should avoid them on the public 
network in order to prevent attacks.
Thus I consider my proposal much more resilient compared to yours.

One might say, that my approach creates a circle where all nodes are equal, and 
where the removal of some node is survivable.
Or: ZmnSCPxj and the nodes of the round table.

> > I can overload those N nodes by generating node addresses that also lie in 
> > that octant.
> > By just iterating over scalars, about 1/8 of the generated node addresses 
> > will lie in the target octant.
>
> If you target the first layer of the tree only, then once nodes spill to the 
> second layer, they will filter out any gossip which does not concern them. It 
> isn't sufficient to just brute force the first 2 bits, but you need to do it 
> for 2^depth, where depth is the target's maximum they're willing to spill to 
> (which is not shared).
> However, commodity hardware can attempt millions of ec_mult/hash per second, 
> so getting a node into the bucket you want is trivial anyway for small depth.
>
> > In order to disrupt a particular node, I must place fake nodes near that 
> > node, in an attempt to force its neighbors to reduce the arc of the circle 
> > that they can map.
> > However, I need to generate fake nodes that are nearer to that node than 
> > genuine honest nodes.
> > This means the probability of me generating such node addresses are much 
> > lower than 1/8, thus requiring that I devote more energy to generating the 
> > falsified attack nodes.
>
> I would argue that the above is also true in your approach. It would still be 
> trivial to brute force the prefixes which minimize the distance between 
> themselves and the target, even with a network of tens of millions of nodes. 
> The amount of energy which would need devoting does not seem like it would a 
> deciding factor for this attack.

The issue is not how difficult to attack a single node is.

The issue is: it should be easier to attack a single node, than to attack 
several nodes simultaneously.
This is how all things should be.

As I understand your proposal, taking over or taking down a node near the root 
of the tree will make it difficult to look up several nodes at once.
This is because the tree nature makes nodes near the root of the tree (top of 
the hierarchy) much more important than leaf nodes, which only worry about 
themselves.

The rest of your argument only answers the specific problem I brought up.
But the issue is simply this:

What happens if a node near the root of the tree is brought down?

In my 

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-04-05 Thread m.a.holden via Lightning-dev
Good morning ZmnSCPxj,

I'll try to clarify my proposal further, but also have some questions about 
yours.

---

> Now, it seems to me what you propose, is to have octrees contain octrees, and 
> so on.

There's one global tree, which is the same for all users. Every node in the 
tree has a bucket and exactly 4 child nodes, except leaves have no children. 
The tree has a max depth, which each client sets itself. The theoretical 
maximum being HASHLEN/2 (In practice, we're likely to be concerned about <8). 
Note that every parent's bucket contains all of the information of all of its 
children's buckets - meaning the root node of the global quadtree is equivalent 
to the unfiltered global network. Nodes pick a depth and concern themselves 
with the bucket at that depth, unless it overflows, in which case they increase 
the depth by 1.

> Now let us return, to my proposal of a distance measurement.
> This effectively maps the LN universe onto a circle.
> Each node commits itself to storing an arc of this circle, and possibly 
> various other nodes it happens to be directly connected to that may be far 
> from the arc near it.

The quadtree can also be looked at from the perspective of a circle, assuming 
there is a reference point P on it. Each bucket is represented by an arc of 
size 2pi/(4^depth), and the PKH-prefix represents a displacement of the arc 
from P (Eg, the bucket 00b would represent an arc from P to pi/2+P). Bucket 00b 
includes all gossip information for the buckets b, 0001b, 0010b and 0011b, 
which are sub-arcs of it, and so forth. Spilling a bucket is the same as 
narrowing the arc to 1/4 its previous size.

Although different from your arbitrary distance k (arc size 2*k?), they're not 
too dissimilar in the kind of distance covered - with the primary distinction 
being that mine proposes using set interval ranges (based on powers of 4), and 
the node picks the range which it's PKH fits into, rather than the range being 
centred on the node.

---

> I can overload those N nodes by generating node addresses that also lie in 
> that octant.
> By just iterating over scalars, about 1/8 of the generated node addresses 
> will lie in the target octant.

If you target the first layer of the tree only, then once nodes spill to the 
second layer, they will filter out any gossip which does not concern them. It 
isn't sufficient to just brute force the first 2 bits, but you need to do it 
for 2^depth, where depth is the target's maximum they're willing to spill to 
(which is not shared).

However, commodity hardware can attempt millions of ec_mult/hash per second, so 
getting a node into the bucket you want is trivial anyway for small depth.

> In order to disrupt a particular node, I must place fake nodes near that 
> node, in an attempt to force its neighbors to reduce the arc of the circle 
> that they can map.
> However, I need to generate fake nodes that are nearer to that node than 
> genuine honest nodes.
> This means the probability of me generating such node addresses are much 
> lower than 1/8, thus requiring that I devote more energy to generating the 
> falsified attack nodes.

I would argue that the above is also true in your approach. It would still be 
trivial to brute force the prefixes which minimize the distance between 
themselves and the target, even with a network of tens of millions of nodes. 
The amount of energy which would need devoting does not seem like it would a 
deciding factor for this attack.

> Further, in executing this attack, while I disrupt one node very well, and 
> nearby nodes somewhat, my effect will be far less than disrupting 1/8 of the 
> network.

Since the attack needs to target the maximum depth that nodes might spill to, 
then the amount of the network which could be affected by the attack would be 
1/4^depth. I can't imagine it being very different in your distance based 
approach, since we're considering the same kind of distances, from a different 
perspective.

---

> Once I get a node address in the targeted octant, I can commit a nominal 
> amount of Bitcoin into some 2-of-2 with an existing actual node I control and 
> the generated node address, then synthesize some node gossip containing those 
> node addresses.

The way I see it, this potential attack affects the global network generally. 
Somebody could try this regardless of our proposals, and try to flood the whole 
network with spam.

BOLT#7 only states that a node MAY forward information about nodes for which it 
does not know any channels. One could reconsider this approach if constrainted 
on resources, such as to say if depth>X, MUST NOT forward any information about 
nodes with no known channels, or perhaps have a variation of gossip which 
combines node information into channel broadcasts to ensure that such node spam 
can't occur. I think the vagueness of the spec on this rule is inidicative that 
it needs addressing.

To try and mount an attack with greater chance of success, 

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-04-04 Thread ZmnSCPxj via Lightning-dev
Good morning m.a.holden,

>
> I think you might have misunderstood what I was proposing, but it's probably 
> my fault for not expressing it well. With my suggestion, all nodes continue 
> to be equal participants and there are no special nodes. I used the term 
> "endpoint" previously to mean one of the two nodes which a regular channel 
> belongs to, and not to mean some kind of special node. Any node can open 
> channels to any other node - the "buckets" are merely a strategy for locally 
> organizing gossip so that it can be made more efficient. The term "buckets" 
> is used in the descriptions of other DHTs such as Kademlia too, and they 
> don't refer to splitting up the global network, they merely provide a 
> perspective for looking at subsections of it.

This "bucket"ization, unfortunately, allows the possibility of targeted attacks 
within particular buckets (which I will describe later below).
It is this I refer to, when I bring up the possibility of politically-motivated 
attacks.

> I came up with the idea of using the quadtree specifically for trying to 
> reduce the maxmimum (or typical) route length to query where possible, at the 
> expense of storing much more information than existing DHTs, but trying to 
> get reasonable savings on resources. Although the worst-case query cost is 
> still O(log n), it seems that this is unlikely to occur and O(1) seems 
> plausible for small depth.

I believe that for trees, lookup is only O(log n) if perfectly balanced, as all 
things should be.
For trees, worst case is always O(n) if the possibility of unbalanced trees 
exists.
And in a scenario where nobody controls the data that can be placed in a tree, 
you can always expect unbalanced trees in attacks.

Now, it seems to me what you propose, is to have octrees contain octrees, and 
so on.
Some node promises to keep track of the map, at some level of octree fineness.

Suppose there is a node I wish to attack, for whatever reason (probably 
politically-motivated).
Now, I know there are N nodes that have promised to keep track of the octant 
the target is on.

I can overload those N nodes by generating node addresses that also lie in that 
octant.
By just iterating over scalars, about 1/8 of the generated node addresses will 
lie in the target octant.
Once I get a node address in the targeted octant, I can commit a nominal amount 
of Bitcoin into some 2-of-2 with an existing actual node I control and the 
generated node address, then synthesize some node gossip containing those node 
addresses.
This unbalances the octree such that one octant has a far lerger number of 
nodes inside it than the other octants.

The N nodes that promised to keep track of the routemap within the octant find 
that they need to take up more and more memory to store the octant data because 
of this targeted attack.
Eventually, the N nodes start dropping out of this responsibility since they 
run out of resources.

Once the number of nodes that hold that octant drops, I can then switch to 
targeted DDoS attacks on the remaining octant-mapping nodes, especially easy to 
locate them since they openly broadcast the fact that they promise to map the 
octant they are in.

Now the octant becomes hard to access for 7/8 of the network.
I have successfully executed a partitioning attack and disrupted the operation 
of an entire octant.

This is not a situation I would like to enable, especially since we can expect 
politically-motivated attacks on Bitcoin and Lightning.

Now it is possible I misunderstand what you are proposing.
Is the above attack scenario plausible?

This is the primary reason why I think it is dangerous to split the network, 
even by just considering subsections of the network.
While we must at some point operate on network subsections as the network 
grows, I think we should hold the following position when designing:

* No node shall reveal the extent of its knowledge of the network, since if it 
reveals that it knows the entire network, it may become a target for attack in 
order to degrade the network.
   * This also implies that if a node does not know the location of some node, 
instead of admitting its ignorance, it should instead delegate to another node 
that might have better information; otherwise it would be possible to profile 
nodes to determine how much of the network they know.

The intent is not to have targets.
Nodes that openly broadcast that they know the nodes within the same octant 
they are, are nodes that want to be DDoS'ed.

Thus, my definition of a "special" node is a lot looser than you seem to define 
it.
Anything that makes it possible to point to a node and say "this is a good node 
to attack, in order to disrupt Lightning" is special.

I expressed, a similar opinion in the Trampoline Routing thread: 
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-April/001967.html


> There are currently ~4000 nodes with an average of ~20 channels per node 
> (~40,000 channels) which 

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-04-04 Thread m.a.holden via Lightning-dev
Good morning ZmnSCPxj, thanks for the response.


> I would be hesitant to divide the world in such manner.
> I understand that in typical computer science, splitting your objects up into 
> smaller parts is a long-accepted method of doing things.

> However, when it comes to finances and political power (the power to censor 
> or disrupt), such splitting is highly undesirable.

> Thus I am strongly allergic to things that would "hierarchical"ize or 
> "bucket"ize or even just have a separation between "endpoint" and "core" 
> network.

> I would rather propose for acceptance into BOLT, such proposals that would 
> keep the network homogeneous.

Firstly, I completely agree with you that we should not be splitting up the 
network in any way which nodes or channels can be politically targeted, or in 
which any node is designated special privelege or status. I have the same 
allergy as you and took this into considerations when proposing this, and some 
of your suggestions are along a simlar  line of thinking as mine.

I think you might have misunderstood what I was proposing, but it's probably my 
fault for not expressing it well. With my suggestion, all nodes continue to be 
equal participants and there are no special nodes. I used the term "endpoint" 
previously to mean one of the two nodes which a regular channel belongs to, and 
not to mean some kind of special node. Any node can open channels to any other 
node - the "buckets" are merely a strategy for locally organizing gossip so 
that it can be made more efficient. The term "buckets" is used in the 
descriptions of other DHTs such as Kademlia too, and they don't refer to 
splitting up the global network, they merely provide a perspective for looking 
at subsections of it.

I'm certainly interested in any solutions which keep the network permissionless 
because we really don't want to end up with DNS 2.0 or similar.

> Various nodes may have different resources (BTC, CPU, memory, bandwidth, 
> latency).
> Such inequalities are inevitable in this universe.
> But these nodes should still, as much as we can, remain peers on the network.

My suggestion accounts for the difference in computational requirements, as 
each node can determine its own depth in  the tree based on the approximate 
quantity of information it wishes to gossip. A node could filter information to 
whichever depth of the tree they wished, by setting the bucket size at which 
they spill. This also allows for the size of gossip to dynamically shrink as 
the network grows, and is similar to garbage collection, in which anything 
which isn't part of the destination bucket on spilling is purged.

Nodes could also pick (multiple) specific quadtree buckets to communicate all 
gossip about through filters they negotiate (the filter being the hash prefix 
of the desired bucket). It might be desirable to broadcast their filter as part 
of the gossip itself, so that other nodes can learn who are the better 
information providers, but again this would be completely optional.

---

> This rule can be probabilistically fulfilled by having each node N know *at 
> least* routes to some nodes Ls..., where for all L <- Ls, dist(N, L) < some 
> constant.
> The constant here can be selected by each node independently, depending on 
> its memory and CPU capacity.
(the node knowing more routes than that is perfectly fine)

The quadtree proposes a similar idea, but instead of using some constant, N 
knows about routes to Ls, where each L is within the same bucket. Essentially, 
i < dist(N, L) <= j, where i=BUCKET_MIN and j=BUCKET_MAX. For example, if using 
8-bit ids and the first two bits identify the bucket, then i=, 
j=0011. I guess the equivalent distance using your constant would be 
k=0010, to cover the same range but without discriminating the results 
based on any boundaries like my suggestion does.

> Then, we can have the following global rule:
> * Given three nodes X, Y, and Z, and dist(X, Z) < dist(Y, Z), then X SHOULD 
> be more likely to know a route from itself to Z, than Y to know a route from 
> itself to Z, is also met for nodes which are in different buckets.

This rule is essentially the same as what I was thinking for the distance 
between buckets. With the autopilot suggestion of decreasing the number of 
channels opened as distance increases, the probability of knowing about a 
neighbouring bucket is increased compared with a distant one.

---

> It looks for any node L <- Ls such that dist(L, D) < dist(N, D).
> In fact, it can just sort those nodes according to dist(L, D) and start with 
> the lowest distance, and fail once it reaches a dist(L, D) that exceeds its 
> own dist(N, D).
> The above algorithm converges since dist(N, D) for each N that is delegated 
> to will progressively get smaller until we reach some N that knows the 
> destination D.

This proposal also seems very similar to how existing DHTs work, unless I'm 
mistaken. My problem with the approach of 

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-04-02 Thread ZmnSCPxj via Lightning-dev
Good morning list,

> One way you could have both determinism and encourage a diverse distribution 
> of network maps is to treat it as a spatial indexing problem, where the space 
> we use is the lexicographical space of the node ids (or hashes of), borrowing 
> some similarities from DHTs.
>
> If for example, we take a quadtree, you can take the 2 most-significant bits 
> of the public key hash, which would put your node into one of 4 buckets. 
> Nodes could advertise a feature bit indicating that they are committed to 
> keeping the entire routemap of the bucket which matches their own public key 
> hash, which would be all of the nodes in the same bucket - and all of the 
> channels with one or both of their endpoints in the bucket.

I would be hesitant to divide the world in such manner.
I understand that in typical computer science, splitting your objects up into 
smaller parts is a long-accepted method of doing things.

However, when it comes to finances and political power (the power to censor or 
disrupt), such splitting is highly undesirable.

Thus I am strongly allergic to things that would "hierarchical"ize or 
"bucket"ize or even just have a separation between "endpoint" and "core" 
network.

I would rather propose for acceptance into BOLT, such proposals that would keep 
the network homogeneous.

Various nodes may have different resources (BTC, CPU, memory, bandwidth, 
latency).
Such inequalities are inevitable in this universe.

But these nodes should still, as much as we can, remain peers on the network.

(I am not responding m.a.holden specifically, but am addressing the entire list)


Thus let me propose instead:

1.  Nodes already have "addresses" - the public key that identifies the node.
2.  We can hash this address, then treat the hash as a 256-bit signed number in 
two's complement notation.
3.  From this, we can synthesize an artificial "distance" measure: dist(x, y) = 
abs(as_signed(hash(x)) - as_signed(hash(y)).


Then, we can have the following global rule:

* Given three nodes X, Y, and Z, and dist(X, Z) < dist(Y, Z), then X SHOULD be 
more likely to know a route from itself to Z, than Y to know a route from 
itself to Z.

This rule can be probabilistically fulfilled by having each node N know *at 
least* routes to some nodes Ls..., where for all L <- Ls, dist(N, L) < some 
constant.
The constant here can be selected by each node independently, depending on its 
memory and CPU capacity.
(the node knowing more routes than that is perfectly fine)


Thus, suppose some node N is selected as trampoline.
It is unable to locate the next node D in the trampoline onion.
However, it knows some nodes Ls in its local routemap.
It looks for any node L <- Ls such that dist(L, D) < dist(N, D).
In fact, it can just sort those nodes according to dist(L, D) and start with 
the lowest distance, and fail once it reaches a dist(L, D) that exceeds its own 
dist(N, D).

Then it can delegate the routing to D to L, by rewrapping the onion to tell L 
to give it to D.
If node L itself does not know D, it does the same algorithm.

The above algorithm converges since dist(N, D) for each N that is delegated to 
will progressively get smaller until we reach some N that knows the destination 
D.


At the same time, nodes are equal and there are no a priori 
divisions/distinctions between nodes.
All nodes remain peers, there are no special "flare nodes", no special "knows 
the entire map" nodes, no special "knows my octant" nodes, no "endpoint" nodes, 
no hubs and spokes.
The network remains homogeneous and all are still peers, some might have 
smaller routemaps than others, but all are still equal in the network, as all 
things should be.


It does require that trampoline routing allow a trampoline to delegate 
searching for the next trampoline to another node.


--


Now, we want to be able to consider, how can each node N prune its routemap Ls 
such that it prioritizes keeping routes to those nodes with low dist(N, L)?

I present here an algorithm inspired by mark-and-sweep garbage collection.
Improvements in GC algorithms might be possible to adapt to this algorithm.
For instance, it might be useful to be able to perform the marking operation 
concurrently with gossiping.

We define two thresholds, T1, and T2, on the number of channels+nodes in the 
routemap.
(this can be changed to the number of bytes each channel/node takes up in the 
routemap, plus whatever bytes are needed for whatever bookkeeping structures 
are needed for fast routing through the routemap, but the principle remains the 
same)

T1 and T2 must be reasonably far from each other.

Each channel and node includes a "mark" bit.

While gossiping, we allocate new channels and nodes and keep track of how many 
are allocated.
Once the number reaches T2, we trigger the mark-and-sweep algorithm.

1.  Clear all mark bits and set a "number of marked objects" variable to 0.
2.  Sort nodes from smallest to largest dist(N, L), where N is your own node 

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-04-01 Thread m.a.holden via Lightning-dev
Hi ZmnSCPxj & René.

One way you could have both determinism and encourage a diverse distribution of 
network maps is to treat it as a spatial indexing problem, where the space we 
use is the lexicographical space of the node ids (or hashes of), borrowing some 
similarities from DHTs.

If for example, we take a quadtree, you can take the 2 most-significant bits of 
the public key hash, which would put your node into one of 4 buckets. Nodes 
could advertise a feature bit indicating that they are committed to keeping the 
entire routemap of the bucket which matches their own public key hash, which 
would be all of the nodes in the same bucket - and all of the channels with one 
or both of their endpoints in the bucket.

I'd estimate that with a quadtree, information held by each node could be 
reduced to about 40% of that of the parent node in the quadtree, although the 
real amounts would depend on such things as autopilot defaults (ie, how many 
channels you open to nodes within your bucket versus channels to nodes in other 
buckets). Nodes could decide their own bucket capacities on which they wish to 
spill and reduce the amount of gossip by taking the 2 next most significant 
bits of the PKH, and could go several layers deep.

A node which needs to make a payment to another node within its bucket should 
be able to do so without querying (unless there are no routes with the required 
capacity). If making a payment to another bucket, then there would still exist 
a decent number of channels in the local routemap to nodes in those other 
buckets, and these nodes could be queried to find the second half of a route to 
the destination, or could use JIT routing for the second half, assuming the 
first half of the route can be selected from the local routemap.

In terms of relating this to "locality" in the geographical sense, one could 
create a convention where each bucket represents an approximate physical 
location. The globe can be spatially-indexed as a quadtree by taking a 
tetrahedral map projection (eg, Lee conformal projection[1]). The 4 equalateral 
triangles of the tetrahedron can be infinitely split again into 4 smaller 
equal-sized equalateral triangles for however many layers deep the quadtree 
might be. With this, it might be possible to have a convention where there is a 
relation between the lexicographical space and the geographical space, and 
wallet software would essentially brute force a private key to put you into the 
corresponding bucket to your physical location (trivial for the small number of 
bits we're talking about). Routing would be improved for local trade because 
you would have the entire local topology stored, and would only need to query 
when making payment at distance. (This may raise some privacy concerns which 
would need discussing.)

One issue is that it would result in a very unbalanced tree given that 
population is dense in some areas and sparse in others. To overcome this, 
instead of using a conformal or equal-area projection, we might be able to use 
an equal-population-per-area projection, which I had never heard of such 
projection before but have found some research in regards to producing them[2]. 
Nodes would need to agree on the projection in order for this to work, but the 
work could be done once and the results open sourced and shared between the 
implementations.

Autopilot implementations might also need adjusting to consider distance too. 
As a starting point I would suggest a geometric distribution, where half of 
opened channels should be within the same bucket, a quarter should be to 
sibling buckets, and an eight to cousin buckets, etc. This would result in 
increased probability of routing and reduced querying for local payments - 
paying your local coffee shop should be query-free - and payments to the other 
side of the world might require increased querying.

There are also privacy considerations if nodes indicate their approximate 
locations which would need discussing. What do you think?

Also, this method does not need the be the exclusive way in which gossip is 
communicated between nodes, and one might also combine with something like 
ZmnSCPxj has suggested, for gossiping about the highest capacity nodes. It 
might be also possible to share information about the highest capacity channels 
in a bucket too.

[1]:https://en.wikipedia.org/wiki/Lee_conformal_world_in_a_tetrahedron
[2]:https://www.pnas.org/content/101/20/7499.full

(PS, sorry for the separate thread, LML will not let me subscribe to the list)___
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] 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 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 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
___
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 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 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-29 Thread René Pickhardt via Lightning-dev
Good morning ZmnSCPxj,

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)

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.

Best Rene


ZmnSCPxj  schrieb am Fr., 29. März 2019, 09:47:

> Good morning Rene,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Friday, March 29, 2019 1:54 PM, René Pickhardt <
> r.pickha...@googlemail.com> wrote:
>
> > Dear ZmnSCPxj and fellow lightning developers,
> >
> > I want to point out two things and make a suggestion for a new gossip
> message.
> >
> > > 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.
> >
> > Intuitively (without simulation). I encourage to make that process not
> deerministic but rather probabilistic. It would be good if everyone had a
> different set of channels. (which is somewhat achieved with everyone
> keeping their local view)
>
> At a software engineer point-of-view, probabilistic can be difficult to
> test.
> This can be made deterministic by including an RNG seed in the input to
> this code.
>
> However, let me propose instead, in combination with your later thought:
>
> >
> > > Nodes still need to track their direct channels (so they are
> implicitly always in the routemap).
> >
> > I strongly advice that the local view should be extended. Every node
> should always track their friends of a friend network.
>
> Perhaps the pruning rule can be modified to include *distance from self*
> in addition to channel capacity.
> The nearer the channel is, the more likely it is retained.
> The further, the less likely.
> The larger the channel is, the more likely it is retained.
> The smaller, the less likely.
>
> The capacity divided by the distance can be used as a sorting key, and if
> pruning is needed, the smallest "score" is pruned until the routemap fits.
>
> This will lead to everyone having a different set of channels, while being
> likely to track their friend-of-friend network compared to more distant
> nodes.
>
> Of course, the pruning itself would affect the distance of the channel to
> the "self" node.
> So determinism may be difficult to achieve here anyway.
>
> 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-29 Thread ZmnSCPxj via Lightning-dev
Good morning Rene,


Sent with ProtonMail Secure Email.

‐‐‐ Original Message ‐‐‐
On Friday, March 29, 2019 1:54 PM, René Pickhardt  
wrote:

> Dear ZmnSCPxj and fellow lightning developers,
>
> I want to point out two things and make a suggestion for a new gossip 
> message. 
>
> > 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.
>
> Intuitively (without simulation). I encourage to make that process not 
> deerministic but rather probabilistic. It would be good if everyone had a 
> different set of channels. (which is somewhat achieved with everyone keeping 
> their local view) 

At a software engineer point-of-view, probabilistic can be difficult to test.
This can be made deterministic by including an RNG seed in the input to this 
code.

However, let me propose instead, in combination with your later thought:

>
> > Nodes still need to track their direct channels (so they are implicitly 
> > always in the routemap).
>
> I strongly advice that the local view should be extended. Every node should 
> always track their friends of a friend network.

Perhaps the pruning rule can be modified to include *distance from self* in 
addition to channel capacity.
The nearer the channel is, the more likely it is retained.
The further, the less likely.
The larger the channel is, the more likely it is retained.
The smaller, the less likely.

The capacity divided by the distance can be used as a sorting key, and if 
pruning is needed, the smallest "score" is pruned until the routemap fits.

This will lead to everyone having a different set of channels, while being 
likely to track their friend-of-friend network compared to more distant nodes.

Of course, the pruning itself would affect the distance of the channel to the 
"self" node.
So determinism may be difficult to achieve here anyway.

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-28 Thread René Pickhardt via Lightning-dev
Dear ZmnSCPxj and fellow lightning developers,

I want to point out two things and make a suggestion for a new gossip
message.

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.
>

Intuitively (without simulation). I encourage to make that process not
deerministic but rather probabilistic. It would be good if everyone had a
different set of channels. (which is somewhat achieved with everyone
keeping their local view)

Nodes still need to track their direct channels (so they are implicitly
> always in the routemap).
>

I strongly advice that the local view should be extended. Every node should
always track their friends of a friend network. Maybe we could even create
a new gossip query message `query_ask_egonetwork` that asks for the
egonetwork of a node (the egonetwork are all the direct friends of a node
together with their friendships) every node knows at least the nodes in
their ego network and over time also the edges between them.

If I was interested in my friend of a friend network I could just send the
`query_ask_egonetwork` message to all my peers.

Best Rene






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.
>
> Regards,
> ZmnSCPxj
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev