{"type":"rich","version":"1.0","author_name":"npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4","author_url":"https://nostr.ae/npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-06-29\n📝 Original message:\nHi t-bast,\n\nHappy to see this finally written up! With this, we have two classes of\nproposals for rate limiting onion messaging:\n\n  1. Back propagation based rate limiting as described here.\n\n  2. Allowing nodes to express a per-message cost for their forwarding\n  services, which is described here [1].\n\nI still need to digest everything proposed here, but personally I'm more\noptimistic about the 2nd category than the 1st.\n\nOne issue I see w/ the first category is that a single party can flood the\nnetwork and cause nodes to trigger their rate limits, which then affects the\nusability of the onion messages for all other well-behaving parties. An\nexample, this might mean I can't fetch invoices, give up after a period of\ntime (how long?), then result to a direct connection (perceived payment\nlatency accumulated along the way).\n\nWith the 2nd route, if an attacker floods the network, they need to directly\npay for the forwarding usage themselves, though they may also directly cause\nnodes to adjust their forwarding rate accordingly. However in this case, the\nattacker has incurred a concrete cost, and even if the rates rise, then\nthose that really need the service (notifying an LSP that a user is online\nor w/e) can continue to pay that new rate. In other words, by _pricing_ the\nresource utilization, demand preferences can be exchanged, leading to more\nefficient long term resource allocation.\n\nW.r.t this topic, one event that imo is worth pointing out is that a very\npopular onion routing system, Tor, has been facing a severe DDoS attack that\nhas lasted weeks, and isn't yet fully resolved [2]. The on going flooding\nattack on Tor has actually started to affect LN (iirc over half of all\npublic routing nodes w/ an advertised address are tor-only), and other\nrelated systems like Umbrel that 100% rely on tor for networking traversal.\nFunnily enough, Tor developers have actually suggested adding some PoW to\nattempt to mitigate DDoS attacks [3]. In that same post they throw around\nthe idea of using anonymous tokens to allow nodes to give them to \"good\"\nclients, which is pretty similar to my lofty Forwarding Pass idea as relates\nto onion messaging, and also general HTLC jamming mitigation.\n\nIn summary, we're not the first to attempt to tackle the problem of rate\nlimiting relayed message spam in an anonymous/pseudonymous network, and we\ncan probably learn a lot from what is and isn't working w.r.t how Tor\nhandles things. As you note near the end of your post, this might just be\nthe first avenue in a long line of research to best figure out how to handle\nthe spam concerns introduced by onion messaging. From my PoV, it still seems\nto be an open question if the same network can be _both_ a reliable\nmicro-payment system _and_ also a reliable arbitrary message transport\nlayer. I guess only time will tell...\n\n\u003e The `shared_secret_hash` field contains a BIP 340 tagged hash\n\nAny reason to use the tagged hash here vs just a plain ol HMAC? Under the\nhood, they have a pretty similar construction [4].\n\n[1]:\nhttps://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/003498.html\n[2]: https://status.torproject.org/issues/2022-06-09-network-ddos/\n[3]: https://blog.torproject.org/stop-the-onion-denial/\n[4]: https://datatracker.ietf.org/doc/html/rfc2104\n\n-- Laolu\n\n\n\nOn Wed, Jun 29, 2022 at 1:28 AM Bastien TEINTURIER \u003cbastien at acinq.fr\u003e wrote:\n\n\u003e During the recent Oakland Dev Summit, some lightning engineers got together to discuss DoS\n\u003e protection for onion messages. Rusty proposed a very simple rate-limiting scheme that\n\u003e statistically propagates back to the correct sender, which we describe in details below.\n\u003e\n\u003e You can also read this in gist format if that works better for you [1].\n\u003e\n\u003e Nodes apply per-peer rate limits on _incoming_ onion messages that should be relayed (e.g.\n\u003e N/seconds with some burst tolerance). It is recommended to allow more onion messages from\n\u003e peers with whom you have channels, for example 10/seconds when you have a channel and 1/second\n\u003e when you don't.\n\u003e\n\u003e When relaying an onion message, nodes keep track of where it came from (by using the `node_id` of\n\u003e the peer who sent that message). Nodes only need the last such `node_id` per outgoing connection,\n\u003e which ensures the memory footprint is very small. Also, this data doesn't need to be persisted.\n\u003e\n\u003e Let's walk through an example to illustrate this mechanism:\n\u003e\n\u003e * Bob receives an onion message from Alice that should be relayed to Carol\n\u003e * After relaying that message, Bob stores Alice's `node_id` in its per-connection state with Carol\n\u003e * Bob receives an onion message from Eve that should be relayed to Carol\n\u003e * After relaying that message, Bob replaces Alice's `node_id` with Eve's `node_id` in its\n\u003e per-connection state with Carol\n\u003e * Bob receives an onion message from Alice that should be relayed to Dave\n\u003e * After relaying that message, Bob stores Alice's `node_id` in its per-connection state with Dave\n\u003e * ...\n\u003e\n\u003e We introduce a new message that will be sent when dropping an incoming onion message because it\n\u003e reached rate limits:\n\u003e\n\u003e 1. type: 515 (`onion_message_drop`)\n\u003e 2. data:\n\u003e    * [`rate_limited`:`u8`]\n\u003e    * [`shared_secret_hash`:`32*byte`]\n\u003e\n\u003e Whenever an incoming onion message reaches the rate limit, the receiver sends `onion_message_drop`\n\u003e to the sender. The sender looks at its per-connection state to find where the message was coming\n\u003e from and relays `onion_message_drop` to the last sender, halving their rate limits with that peer.\n\u003e\n\u003e If the sender doesn't overflow the rate limit again, the receiver should double the rate limit\n\u003e after 30 seconds, until it reaches the default rate limit again.\n\u003e\n\u003e The flow will look like:\n\u003e\n\u003e Alice                      Bob                      Carol\n\u003e   |                         |                         |\n\u003e   |      onion_message      |                         |\n\u003e   |------------------------\u003e|                         |\n\u003e   |                         |      onion_message      |\n\u003e   |                         |------------------------\u003e|\n\u003e   |                         |    onion_message_drop   |\n\u003e   |                         |\u003c------------------------|\n\u003e   |    onion_message_drop   |                         |\n\u003e   |\u003c------------------------|                         |\n\u003e\n\u003e The `shared_secret_hash` field contains a BIP 340 tagged hash of the Sphinx shared secret of the\n\u003e rate limiting peer (in the example above, Carol):\n\u003e\n\u003e * `shared_secret_hash = SHA256(SHA256(\"onion_message_drop\") || SHA256(\"onion_message_drop\") || sphinx_shared_secret)`\n\u003e\n\u003e This value is known by the node that created the onion message: if `onion_message_drop` propagates\n\u003e all the way back to them, it lets them know which part of the route is congested, allowing them\n\u003e to retry through a different path.\n\u003e\n\u003e Whenever there is some latency between nodes and many onion messages, `onion_message_drop` may\n\u003e be relayed to the incorrect incoming peer (since we only store the `node_id` of the _last_ incoming\n\u003e peer in our outgoing connection state). The following example highlights this:\n\u003e\n\u003e  Eve                       Bob                      Carol\n\u003e   |      onion_message      |                         |\n\u003e   |------------------------\u003e|      onion_message      |\n\u003e   |      onion_message      |------------------------\u003e|\n\u003e   |------------------------\u003e|      onion_message      |\n\u003e   |      onion_message      |------------------------\u003e|\n\u003e   |------------------------\u003e|      onion_message      |\n\u003e                             |------------------------\u003e|\n\u003e Alice                       |    onion_message_drop   |\n\u003e   |      onion_message      |                    +----|\n\u003e   |------------------------\u003e|      onion_message |    |\n\u003e   |                         |--------------------|---\u003e|\n\u003e   |                         |                    |    |\n\u003e   |                         |                    |    |\n\u003e   |                         |                    |    |\n\u003e   |    onion_message_drop   |\u003c-------------------+    |\n\u003e   |\u003c------------------------|                         |\n\u003e\n\u003e In this example, Eve is spamming but `onion_message_drop` is propagated back to Alice instead.\n\u003e However, this scheme will _statistically_ penalize the right incoming peer (with a probability\n\u003e depending on the volume of onion messages that the spamming peer is generating compared to the\n\u003e volume of legitimate onion messages).\n\u003e\n\u003e It is an interesting research problem to find formulas for those probabilities to evaluate how\n\u003e efficient this will be against various types of spam. We hope researchers on this list will be\n\u003e interested in looking into it and will come up with a good model to evaluate that scheme.\n\u003e\n\u003e To increase the accuracy of attributing `onion_message_drop`, more data could be stored in the\n\u003e future if it becomes necessary. We need more research to quantify how much accuracy would be\n\u003e gained by storing more data and making the protocol more complex.\n\u003e\n\u003e Cheers,\n\u003e Bastien\n\u003e\n\u003e [1] https://gist.github.com/t-bast/e37ee9249d9825e51d260335c94f0fcf\n\u003e\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220629/be1c82d7/attachment-0001.html\u003e"}