📅 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
m.a.holden [ARCHIVE] /
npub1ck…pxq6d
2023-06-09 12:54:43
in reply to nevent1q…0n5q
Author Public Key
npub1ckky60snl9kapavqar0utymcyn7ngvmtqaxr7rpgch9ps6wx3wwqypxq6dPublished at
2023-06-09 12:54:43Event JSON
{
"id": "3851219b3cc290921e8398d11f24277e47c02752e65cdfff5ffa9c0fa1aa4c35",
"pubkey": "c5ac4d3e13f96dd0f580e8dfc5937824fd34336b074c3f0c28c5ca1869c68b9c",
"created_at": 1686315283,
"kind": 1,
"tags": [
[
"e",
"8e4c35cd4e4d6b988c371e901727ca2c2b53df6f6e16dbaf0daabadc6349028e",
"",
"root"
],
[
"e",
"9eb7bb96d7197c2ced1c6943aaceffb674a0576ac9c98d0b90d24fc258652f58",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "📅 Original date posted:2019-04-05\n📝 Original message:\nGood morning ZmnSCPxj,\n\nI'll try to clarify my proposal further, but also have some questions about yours.\n\n---\n\n\u003e Now, it seems to me what you propose, is to have octrees contain octrees, and so on.\n\nThere'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 \u003c8). 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.\n\n\u003e Now let us return, to my proposal of a distance measurement.\n\u003e This effectively maps the LN universe onto a circle.\n\u003e 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.\n\nThe 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.\n\nAlthough 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.\n\n---\n\n\u003e I can overload those N nodes by generating node addresses that also lie in that octant.\n\u003e By just iterating over scalars, about 1/8 of the generated node addresses will lie in the target octant.\n\nIf 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).\n\nHowever, 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.\n\n\u003e 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.\n\u003e However, I need to generate fake nodes that are nearer to that node than genuine honest nodes.\n\u003e 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.\n\nI 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.\n\n\u003e 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.\n\nSince 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.\n\n---\n\n\u003e 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.\n\nThe 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.\n\nBOLT#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\u003eX, 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.\n\nTo 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.\n\nThe 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.\n\n---\n\n\u003e This unbalances the octree such that one octant has a far lerger number of nodes inside it than the other octants.\n\u003e 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.\n\u003e Eventually, the N nodes start dropping out of this responsibility since they run out of resources.\n\nEach 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.\n\nOn 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.\n\nTo 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?\n\n\u003e 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.\n\u003e Now the octant becomes hard to access for 7/8 of the network.\n\u003e I have successfully executed a partitioning attack and disrupted the operation of an entire octant.\n\nThere 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.\n\nAlso, 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.\n\nA 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.\n\nIf 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.\n\nI'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.\n\n---\n\n\u003e 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.\n\n\u003e 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.\n\nI 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?\n\nIn 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?\n\nMy 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.\n\nThe 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.\n\n---\n\n\u003e They do not commit, as in your proposal, to absolutely knowing everything within their committed area.\n\nUltimately, 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).\n\nAny feature must be considered the same. Nodes could advertize that they support a feature and then make no commitment to following it.\n\n\u003e Nodes that openly broadcast that they know the nodes within the same octant they are, are nodes that want to be DDoS'ed.\n\u003e Thus, my definition of a \"special\" node is a lot looser than you seem to define it.\n\u003e 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.\n\nAcknowledged, 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.\n\n---\n\n\u003e * 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.\n\nMy 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?\n\n\u003e * 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.\n\nI'm not sure I agree. I'd prefer to go the opposite way and always fail fast.\n\nIt 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.\n\nA 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.\n\n---\n\nPS, don't take any of this to be a dismissal of your proposal because I fully acknowledge your perspective and concerns.\nI think there are potential useful optimizations in my approach which I'm not sure how equivalent could be acheived with yours.\nBut if I am convinced there are unresolvable problems with the idea I'll drop it and focus on your approach.\n\nRegards,\nMark H",
"sig": "e6dee6fe164a0f131b0d3bb0ffe3490fc708ea3a2d3da51f4ea9229a99cfb6fa98c63c1e9872dabc2138e2d5308e51ee110b7ae0be11169c5af052637825daf9"
}