m.a.holden [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2019-03-30 to 2020-02-03
💬 Posted a total of 5 messages
📚 Participated in the following categories: Lightning-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-09 12:58:31

- reply

📅 Original date posted:2020-02-03
📝 Original message:
> (I'm seeking a clever way that Bob can assign them and trivially tell
> which ID is assigned to which peer, but I can't figure it out, so I
> guess Bob keeps a mapping and restricts each peer to 256 live scids?).
Hi Rusty.
Here's a potential way for Alice and Bob to agree a set of 256 scids without any additional messages or changes to existing messages beyond a feature flag and a flag in open_channel, but comes with a computational cost.
Alice and Bob agree on a random integer `r`. This could be negotiated on `open_channel`, but we shouldn't need to send additional information because we already have a random integer we can use: the `temporary_channel_id`. This is not known to anybody besides Alice and Bob.
When a channel is locked, Bob computes n=256 scids, using something approximating `concat(n, trunc_bytes(sha256(ec_mult(2^n*r, Q)), 7))`, where `Q` is Alice's public key for the channel funding transaction.
The chance of scid collisions between channels is 2^56, which is probably no cause for concern.
Instead of keeping a map of 256 scids for each channel, Bob can use a cuckoo filter for efficiency. The filter can be used for a quick membership test and also as an associative map from scids to channels. It can also support scid deletion in the event of channel closure (at the cost of recomputing 256 ec_mults again).
So when Bob receives a new HTLC to forward, he tests it against his cuckoo filter and retreives a candidate set of possible channels to which it may refer. For each channel, he takes the most significant byte of the scid as `m` and performs `trunc_bytes(sha256(ec_mult(2^m*r, Q)), 7)` and tests the least-significant 7 bytes of the result against the scid.
Alice does not need to keep all of the scids she may use for invoices because they can be computed on the fly, but she will need to keep a copy of the `temporary_channel_id`.
In the reverse direction of Alice forwarding HTLCs to Bob, Bob's public key for the funding transaction is used instead.
Regards,
Mark Holden

2023-06-09 12:54:44

- reply

📅 Original date posted:2019-04-08
📝 Original message:
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 (0000b U 0001b U 0010b U 0011b). The bucket 0011b is (001100b U 001101b U 001110b 001111b), 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 the opportunity cost for missed routing fees would be increased for nodes nearer the top of the tree, they are incentivized to make the efforts to maintain uptime and try to mitigate DDoS attacks against themselves.
It's hard to say for certain whether the risks would be real cause for concern without testing on real world data, which we don't yet have the scale to test, but I just can't see it being realistic that there would be so few targets which make DDoS feasible to begin with, and that if attacks against a significant number of nodes were successful, the potential degrading of the network would be trivial or even unnoticeable. As the network grows, it seems the attack vector would get even more unrealistic because the number of targets that one would need DDoS would increase.
> What happens if a node near the root of the tree is brought down?
Buckets closer to the root do not hold any exclusive information. If you bring down every node in the root bucket, and every node at depth=1, then nodes at depth>=2 will continue to communicate and still collectively know the entire network map, with still a good probability that any node can find any other node in the network by asking just one other node.
Regards,
Mark H

2023-06-09 12:54:43

- reply

📅 Original date posted:2019-04-05
📝 Original message:
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 0000b, 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, the attacker should need to open many new channels, for which they face obvious constraints on the bitcoin network, and real costs. And since the attack can only attempt to degrade LN at best, and offers no guarantee of censoring, it seems unlikely that an attacker would exhaust significant resources to try and target somebody with a low chance of success.
The attacker would also likely use nominal amounts for the channels they're trying to attack with, as they would not want to lock up significant funding. It may be trivial to filter many tiny capacity channels as they're not likely to be useful for making payments anyway.
---
> 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.
Each node would treat the quadtree as a perfectly balanced one at the depth they're concerned. The buckets themselves vary in capacity, and if the gossip reaches capacity at any depth, the bucket spills to the next depth. If an attacker managed to overflow a leaf bucket, then the potential victim would need to consider another gossip approach.
On determining whether one is being attacked though, it should be possible to detect based on information size before and after spilling. If one is being specifically targeted, then the information before and after spilling will be almost the same, with little saving on gossip, where normally spilling might expect a 50%+ saving. A client could set a low threshold on the minimum saving they expect to get from spilling, and if it is not met, they might determine that they are being targeted, and take countermeasures.
To me it seems like your distance narrowing suffers the same issue. As the size of your gossip grows, you will narrow the distance k for which you concern yourself with gossip - but at some point you must have a minimum k, else it will be too narrow to have any useful information. What happens if you decrease k to some minimum, and the amount of spam still overflows the capacity limits you've set?
> 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.
There are no "octant-mapping nodes". Every node knows about every channel from its own bucket to other buckets. This remains true even after spilling - although the quantity of information is reduced. Performing a DoS on a node who stores the whole network information does not affect other users, because they're not exclusive holder of information. Every single participant of the network could operate at depth=2. There does not need to exist anybody who has the full network map.
Also, if most nodes follow a reasonable autopilot strategy, then every node in a bucket also has at least some channels to other buckets - meaning the target of a DDoS would essentially be the entire bucket to try and completely isolate it. Remember that I'm suggesting half (or more) of the open channels in a bucket are to other buckets.
A node doesn't necessarily need to broadcast the depth at which they gossip, but could indicate a deeper depth, so as to reduce the amount of queries made to it, and hide the truth about the full information they carry. They shouldn't indicate a smaller depth than the one at which they gossip as they'll be unable to answer to a majority of queries.
If a node is being targeted they could specify a large depth at which it would be infeasible for an attacker to target, whilst secretly maintaining information at a smaller depth, but by doing so, they're also stating that they're not going to be widely useful.
I'm also not suggesting this be the only gossip strategy. At minimum I would also want friend-of-a-friend-of-a-friend type gossip in addition to this, because those channels are the ones we'll most likely be routing payments over anyway, so we should have them cached separately from this quadtree proposal. Several other gossip approaches could be used too.
---
> Crucially no node admits to how large an arc of this circle they map out, only that they are more likely to map points nearer to themselves.
> This is because nodes only commit to *probabilistically* being more likely to know nodes near to them, than nodes that are not near to them.
I can see how using a probabilistic approach might mitigate the issue to some extent, but it doesn't seem like a cure. Since the information nearest to you is more proabable to be forwarded to you, an attacker could still try to overwhelm your resources by plaing enough nodes nearby. How is the probability decided? Does your node probabilistically filter incoming information, or do you signal to your peers to probabilisitcally filter it?
In the latter case, while not necessarily admitting what you store, it seems like you'll still leak hints about it. What information are you proposing gets communicated (if any) between peers to filter gossip being sent?
My approach is based on the idea that the broadcaster will always know whether or not to forward you information based on the filter you give them, with the default filter being a bit-mask for the depth of the quadtree matching your PKH. A node will forward you all information about any channel which has one or both nodes matching the bit mask, and both of the nodes for every channel. Everything else gets filtered (unless other filters or strategies are agreed). A node forwarding you gossip you've specifically requested to be filtered could be considered malicious.
The filter a node communicates with its peer does not necessarily need to indicate the amount of the network they actually gossip about. For example, a node wishing to have all information about bucket 00b might request filters for buckets 0000b, 0001b, 0010b and 0011b from different peers. If each peer forwards information for their buckets, then the node will learn of all information in 00b without ever revealing to anybody, at the cost of some duplication.
---
> They do not commit, as in your proposal, to absolutely knowing everything within their committed area.
Ultimately, my proposal is a convention and not a hard rule. Any commitment comes with limits and it isn't to be *assumed* that a node will know everything about their local topology, only that they are very likely to know it under normal circumstances. It doesn't prevent anyone from using other techniques, or to try routing through different buckets (which one might want to try for increasing privacy).
Any feature must be considered the same. Nodes could advertize that they support a feature and then make no commitment to following it.
> 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.
Acknowledged, but I'm not convinced there is a DDoS motive. Disrupting specific nodes doesn't necessarily disrupt other users. Obviously, it can disrupt the friend and friend-of-a-friend of the target, but this will always be true. The gossip network specifically intends to publish friend-of-a-friend information, so targeted DDoS attacks on individuals and their friends are not necessarily avoidable.
---
> * 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.
My main question about your proposal is, given that bandwidth is a key resource constraint, what strategy are you using to prevent the sending/receiving of unwanted gossip information, which also prevents leaking information about which gossip you're interested in?
> * 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.
I'm not sure I agree. I'd prefer to go the opposite way and always fail fast.
It could be specified that if you've indicated that you'll answer queries for a specific bucket, and somebody requests information about a node or channel outside of the bucket, and which there exists no direct channel from within your bucket to that node, then you should automatically fail the query, even if you know the information.
A query will then either return a very likely yes (on information within the bucket), or a definite no (anything not in the bucket). Nothing more than which was previously specified is leaked, even if you keep more gossip information than you have publicized. If probing can only reveal information that is already public, there is nothing to be gained.
---
PS, don't take any of this to be a dismissal of your proposal because I fully acknowledge your perspective and concerns.
I think there are potential useful optimizations in my approach which I'm not sure how equivalent could be acheived with yours.
But if I am convinced there are unresolvable problems with the idea I'll drop it and focus on your approach.
Regards,
Mark H

2023-06-09 12:54:42

- reply

📅 Original date posted:2019-04-04
📝 Original message:
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=00000000, j=00111111. I guess the equivalent distance using your constant would be k=00100000, 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 existing DHTs is that they are suboptimal for the number of queries which must be made to find a route - which is worst-case O(log n) for example, in Chord or Kademlia. This isn't a problem for things like file-sharing where latency isn't a major concern, but we don't really want to be waiting for a bunch of queries if we're stood in queue to pay for a coffee. (Given also that some routes may fail due to inherent constraints of the LN itself). As the network grows, the efficiency of route finding declines too.
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.
The other expense is that this approach will not find the most optimal routes, as it prioiritizes considering the smallest number of buckets. However, it is not possible to know the most optimal path without knowing about the entire network topology anyway, so this problem exists with the DHT too. I've optimized for reduced querying.
> All nodes remain peers, there are no special "flare nodes", no special "knows the entire map" nodes, no "knows my octant" nodes, no "endpoint" nodes, no hubs and spokes.
There are no special nodes in my approach, only a commitment to maintain information about nodes (and their channels) whose PKH prefix matches your own at the depth you have chosen to gossip, regardless of whether or not they've advertized the same feature. A node expressing depth=0 would be a "knows the entire map" node, but it does not give them any special status.
> 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.
All nodes are still equal, but the network isn't entirely homogeneous (in the distribution of channels) because of the autopilot suggestions which prioritize local channels and deprioritize distant channels, with the goal of improving efficiency. I guess there is some trade-off with this approach, but it's still worth considering, because "perfectly unstructured" isn't the end goal - there may be some middle ground between that and other approaches which tend towards centralization.
It may even be harmful to try to keep it perfectly unstructured, because with no structure, the network will effectively be "maximally inefficient" for those not maintaining sufficient gossip information. If by default, it is inefficient to find a route, then there will inevitably be somebody who will fill that market gap. Big players will have no problem keeping knowledge of the whole network and giving information about paths in just one query - in exchange for people's data. Like DNS.
A semi-structured approach might provide enough incentive for everyone to keep as much information locally as realistic for the resources they have, and like Adam Smith's invisible hand, by doing so they not only benefit themselves, but they benefit everybody by improving the efficiency of the network overall. The network would become "reasonably efficient" for everyone, rather than inefficient for most except the few with sufficient resources to maintain a useful routemap.
---
I'll try to convey by example how I think censorship should not be cause for concern with this quadtree, and what savings might be expected. This makes some crude assumptions using the current network size, with my previous suggestions for autopilot (ie, nodes open 1/2 their channels to nodes in their own bucket, and decreasing with distance), and assumes uniform distribution of node ids (we assume there is no numeric bias in the hashes of public keys).
There are currently ~4000 nodes with an average of ~20 channels per node (~40,000 channels) which we need to keep information about at depth=0.
If we spill to depth=1, then ~1,000 nodes will go into each bucket. If each has (on average) ~10 channels to other nodes in the same bucket, then there will be ~5,000 "intra-bucket" channels in each bucket. Each node also has ~10 channels to nodes in other buckets ("inter-bucket" channels), which is another ~10,000 channels it maintains information for.
Note that "intra-bucket" and "inter-bucket" channels are just plain channels - there's nothing special about them and they are merely the difference in perspective which each node will view them based on whether either node's PKH prefix is the same bucket as their own PKH prefix at the depth which they filter gossip.
Since we've filtered out all channels where neither node is in our own bucket, we now only need to know about ~15,000 channels in total, compared to the original 40,000 (~37.5% of total channels in the network). We still need to know about 1,000 nodes in our own bucket, and we keep information about the nodes at the other end of the 10,000 inter-bucket channels we know about, which could still be anything up to 100% of the nodes in the global network, but nodes will be filtered if none of the 10,000 inter-bucket channels we know about belong to them, so nodes we track information about is 1000 < N <= 4000.
We don't suddenly have no fault-tolerance or a censorship threat to find a node in another bucket here. Therea are still ~3,333 known channels on average between our bucket and each of the other 3 buckets at depth=1. Since they keep all of the gossip for their own bucket, then the chance that any of them know the destination for a payment is likely - so the number of queries you would typically need to make is 1 (or several *in parallel*). The node you query should know the remaining route from himself to the destination. You may chose to query more information for potential privacy enhancement.
If we spill to depth=2, then we now have 16 total leaf-buckets, with ~250 nodes each. Each bucket would have ~1250 intra-bucket channels, and ~2500 inter-bucket channels. Information requirement per bucket is now ~3750 channels (~10% of the total network, which is a reasonable saving). Of the inter-bucket channels, 1/2 of them are to the 3 sibling buckets, making ~400 potential routes to any of the siblings, and the other 1/2 are to "cousin" buckets, of which there are 12, resulting in ~100 channels on average to those buckets. Still likely sufficient to have a typical query of 1, with fault-tolerance.
At depth=3 it is ~62 nodes per bucket, ~310 intra-bucket channels, ~620 inter-bucket channels and 64 possible leaf-buckets. resulting in ~100 channels to each sibling, ~13 channels to each cousin, and just 1 or 2 channels to each second-cousin (the most distant buckets).
Only at this point does querying start to become potentially expensive if you want to make the payment to a distant node. You might still have some direct routes to the second-cousin buckets, but not much fault-tolerance. However, your cousins or the siblings of your second-cousin have a higher probability of knowing about a node at that distance than local nodes will, so you still have numerous options for discovering a node but it might take multiple queries. Queries would use a similar greedy algorithm approach to the one you have suggested. It should still be significantly less than worst-case query cost.
Resource constrained devices might spill to these limits at the cost of requiring more queries for payments. In practice, you probably wouldn't go beyond depth=2 as above unless the global network gets sufficiently large that bandwidth requirements at depth=2 are a problem, which probably isn't going to be the case until the network is a magnitude larger than it already is - and in which case the number of "inter-bucket" channels will be tenfold the current amount and spilling to depth=4 or 5 may become plausible.
There is also potential for analysts to find out which buckets do not have any, or have few channels between them, and to take the opportunity to fill that gap to try and benefit from routing fees, as those new channels would be prioritized over longer routes which span multiple buckets. The autopilot suggestions are only a starting point, but eventually it will be mostly market driven.
---
My idea is not fully researched, but since the topic was raised, I decided to share my incomplete thoughts about it. The choice of a quadtree itself was quite arbitrary, but it seemed reasonable after briefly considering alternative arity trees, and the potential for linking this to approximate geographic location to optimize local payments seemed like it could be valuable too.
I'll give some more thought to your suggestions and reconsider my own with these new suggestions.
Regards,
Mark H

2023-06-09 12:54:41

- reply

📅 Original date posted:2019-03-30
📝 Original message:
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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20190330/0441d5ab/attachment-0001.html>