Re: [Lightning-dev] New paper on ant routing
Hello ZmnSCPxj, Thank you for your comments, we are glad for your interest in our work. Below some answers to your comments. Concerning the information that intermediary nodes can gather from counters: We are working under the assumption of a large highly connected network (with thousands of nodes and node connection larger than 10, or nodes connected to highly connected nodes if they are newcomers). Such a network has a very different geometry from the plane. In particular, triangulation is not feasible in general. Typically the distance between the majority of any pair of nodes is between 3 and 7 for a worldwide network. We want to obfuscate the counter to avoid giving information to immediate neighbours (that in principle are more trustable than others) about the origin or end of the transaction. Also, finding the shortest path in a highly connected graph is not our primary concern since most paths are quite short, which is why we are not considering optimization with a Dijkstra type algorithm. Concerning spamming, this is unavoidable (as for the Bitcoin network) and scrutinity from nodes is required. Nodes are free to relay the seeds that they want. In particular, if a node N notices that one of its neighbours, say node M, starts spamming the network with pheromones (with a traffic much larger than its historical average share), then N can choose to ignore the seeds coming from M. It is even in N's best interest to be careful not to relay what he perceives as spams, because N itself could otherwise be branded as "spammer" by its neighbours. For this reason it is advisable for nodes to keep historic data on behaviour of neighbours and close the channels if they suspect them of acting maliciously (which can be revealed with the historical data). Concerning payment failures: it was our understanding that the reason for the high failure rate of the current routing algorithm is because Alice doesn't know the channel balances of other nodes, and thus cannot be sure that her choice of path has enough funds to forward her payment. Ant routing solves this problem during the pheromone phase: a node forwards the pheromone to a neighbour only if the channel balance allows the amount of the transaction to go through. This way, when Alice receives a matched seed, she is certain that the channel balances on the path have enough funds to forward her whole payment. It is also our understanding that the gossip network (that can also be a source of spamming) is used to update the channel balance in the routing tables. Note that the update of these channel balances, which seems necessary with the current routing, reveals and deanonimizes who has made transactions in the last period (and we can even reconstruct very easily a lot of transactions if updates are made often). When you say "Distance measurements need not be in units of hops", I am not sure what you mean here, and why this is a problem; could you elaborate? Concerning your "main objection": as you noticed, the size of pheromones is significantly less than bitcoin transactions (16 Bytes, as we indicate in the paper) and they are deleted after 3 seconds (this keeps the seed mempool small). Pheromone Ids can be so small because they only need to distinguish between the about 30k tx present in the seed mempool (for a regime of about 10k tx/sec). The purpose of our paper is to prove scalability up to 10.000 tx/sec, we don't claim anything else, and certainly not infinite scalability. In that regard,theoretical O-estimates seem irrelevant to us (any O-estimate is dependent of the implicit constants and the hardware used, and is only relevant when we aim for "infinite scalability"). In the paper, we have a more practical and direct approach and we use the Bitcoin network that scales to 5-7 tx/sec as a proxy for the flooding algorithm . The argument is given in Section 6 of the paper. If you have any objection to that section we will be glad to discuss it and we would like to understand why your objection does not apply to the Bitcoin network or the other networks that are given as examples. Best, The authors De : ZmnSCPxj Envoyé : dimanche 9 février 2020 01:57 À : ZmnSCPxj Cc : LEHÉRICY Gabriel ; GRUNSPAN Cyril ; Ricardo Pérez Marco ; lightning-dev@lists.linuxfoundation.org Objet : Re: [Lightning-dev] New paper on ant routing Good morning Gabriel, Some further thinking: -- I notice as well that you propose to add a random number to the initial hop distance counter. This does not quite obscure as much as you might think. Suppose I have two nodes I control in the Lightning Network, which we will pretend is this blank sheet of paper. +--+ | | | | | | |
Re: [Lightning-dev] New paper on ant routing
Good morning The Authors, > Hello ZmnSCPxj, > Thank you for your comments, we are glad for your interest in our work. > Below some answers to your comments. > Concerning the information that intermediary nodes can gather from > counters: We are working under the assumption of a large highly connected > network (with thousands of nodes and node connection larger than 10, or nodes > connected to highly connected nodes if they are newcomers). Such a network > has a very different geometry from the plane. In particular, triangulation is > not feasible in general. Typically the distance between the majority of any > pair of nodes is between 3 and 7 for a worldwide network. We want to > obfuscate the counter to avoid giving information to immediate neighbours > (that in principle are more trustable than others) about the origin or end of > the transaction. Also, finding the shortest path in a highly connected graph > is not our primary concern since most paths are quite short, which is why we > are not considering optimization with a Dijkstra type algorithm. Assuming a space whose dimensionality approaches infinity, yes, you are correct. But not all nodes will have significant numbers of channels, and there may be sections of the network that are more "plane"-like than the assumed inifinite number of dimensions, meaning a limited number of nodes can be used to usefully triangulate. It seems unreasonable to assume an infinite number of dimensions given that each node will only have a finite number of channels, thus I suspect there is *some* number of nodes that can usefully triangulate each and every pheromone. That number could be impractically high for most, but seems to be less than infinity. (In particular, the blocksize limit also limits the number of channels, thus limits how many possible dimensions the graph will have on average.) > Concerning spamming, this is unavoidable (as for the Bitcoin network) and > scrutinity from nodes is required. Nodes are free to relay the seeds that > they want. In particular, if a node N notices that one of its neighbours, say > node M, starts spamming the network with pheromones (with a traffic much > larger than its historical average share), then N can choose to ignore the > seeds coming from M. It is even in N's best interest to be careful not to > relay what he perceives as spams, because N itself could otherwise be branded > as "spammer" by its neighbours. For this reason it is advisable for nodes to > keep historic data on behaviour of neighbours and close the channels if they > suspect them of acting maliciously (which can be revealed with the historical > data). That is doable I suppose, but the details contain the devil. > Concerning payment failures: it was our understanding that the reason for the > high failure rate of the current routing algorithm is because > Alice doesn't know the channel balances of other nodes, and thus cannot be > sure that her choice of path has enough funds to forward her payment. Ant > routing > solves this problem during the pheromone phase: a node forwards the > pheromone to a neighbour only if the channel balance allows the amount of the > transaction to go through. This way, when Alice receives a matched seed, she > is certain that the channel balances on the path have enough funds to forward > her whole payment. It is also our understanding that the gossip network (that > can also be a source of spamming) is used to update the channel balance in > the routing tables. Note that the update of these channel balances, which > seems necessary with the current routing, reveals and deanonimizes who has > made transactions in the last period (and we can even reconstruct very easily > a lot of transactions if updates are made often). This is incorrect --- channel balances, or even hints of channel balances, are currently not broadcasted, and there are now moves to make channel updates very rare to limit the ability to spam gossip. Thus gossip in the current Lightning network is bounded by the transactions-per-second of the blockchain layer. > When you say "Distance measurements need not be in units of hops", I am not > sure what you mean here, and why this is a problem; could you elaborate? This is a random comment and not a problem. Distance measurements might be measured in some other unit than raw hops --- for example, it could be in terms of a flat millisatoshi fee that each node charges for forwarding. It is not clear to me if there is any point to this, but it may be useful to consider other units than just hops, not saying there is, just a random thought that has no true followup (at least for now). > Concerning your "main objection": as you noticed, the size of pheromones is > significantly less than bitcoin transactions (16 Bytes, as we indicate in the > paper) and they are deleted after 3 seconds (this keeps the seed mempool > small). Pheromone Ids can be so
Re: [Lightning-dev] DRAFT: interactive tx construction protocol
> One of the stated goals of implementing PoDLEs was to be "compatible with > JoinMarket", but I believe this compatibility goal only extends as far as the > H2 construction (and not the proof), so we're ok there with this tweak. Good point about H2 being cross-compatible, but I would not tie yourselves down in any way with attempting to keep compatibility with Joinmarket as-is, unless it's trivial to do so ... we will need to pretty much wholesale upgrade our protocol at some relatively soon point, ideally straight to schnorr/taproot, or if not, at least to native segwit, since coinjoin is a fee-heavy protocol. And there's a bunch of legacy stuff (especially in terms of encodings, but other stuff too) that will need to change. If you guys end up finding a stronger and clearer version of this podle/dleq thing and it ends up being useful, we will just tag along (at least, that's likely). And this is why I should not be lazy and try to keep up with this conversation! I wanted to mention something else. Way back, maybe 2 years ago, I remember being interested that there *was* actually at least one use-case of DLEQ to create blinded tokens in the wild apart from our own. I dug up the link; it's really a beautiful idea but it's more based around a client-server model and using 'blind signing' (oblivious PRF based, so not old-style RSA or Chaum), but it's an easy idea to read and grok I think: https://github.com/privacypass/challenge-bypass-extension/blob/master/docs/PROTOCOL.md While it's very different from our use-case (harder because not client-server), it's still interesting that they use a DLEQ to prove correctly formed token construction, and then prevent 'double spend'. I wouldn't be surprised if there is something to learn from this line of thinking. Cheers, waxwing ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] New paper on ant routing
Good morning again The Authors, > > Concerning the information that intermediary nodes can gather from > > counters: We are working under the assumption of a large highly connected > > network (with thousands of nodes and node connection larger than 10, or > > nodes connected to highly connected nodes if they are newcomers). Such a > > network has a very different geometry from the plane. In particular, > > triangulation is not feasible in general. Typically the distance between > > the majority of any pair of nodes is between 3 and 7 for a worldwide > > network. We want to obfuscate the counter to avoid giving information to > > immediate neighbours (that in principle are more trustable than others) > > about the origin or end of the transaction. Also, finding the shortest path > > in a highly connected graph is not our primary concern since most paths are > > quite short, which is why we are not considering optimization with a > > Dijkstra type algorithm. > > Assuming a space whose dimensionality approaches infinity, yes, you are > correct. > But not all nodes will have significant numbers of channels, and there may be > sections of the network that are more "plane"-like than the assumed inifinite > number of dimensions, meaning a limited number of nodes can be used to > usefully triangulate. > It seems unreasonable to assume an infinite number of dimensions given that > each node will only have a finite number of channels, thus I suspect there is > some number of nodes that can usefully triangulate each and every pheromone. > That number could be impractically high for most, but seems to be less than > infinity. > (In particular, the blocksize limit also limits the number of channels, thus > limits how many possible dimensions the graph will have on average.) A reason why I think it is unreasonable to assume that this kind of triangulation is possible is the existence of the Dandelion proposal for the Bitcoin network. Consider that when a Bitcoin node broadcasts a transaction, what it really does is that it selects an arbitrary large number, in units of Planck intervals since the Epoch (i.e. the Big Bang), more commonly known by mere humans as "the current time". Then, surveillance nodes on the Bitoin network receive the transaction with this counter updated by some delta number-of-Planck-intervals-since-the-Epoch. Cooperating surveillance nodes can then compare the number at which they got the transaction with each other, in order to guess which node on the Bitcoin network originally broadcasted the transaction. My understanding is that this triangulation is successful often enough to be a problem for privacy, which is why Dandelion even *exists*. Admittedly, this is just SPV-level verification (I am looking at the fact that people have poured work into Dandelion and from there assume that "people can traingulate the broadcaster of the transaction in the Bitcoin network" is in fact true, without actually validating that myself). Since the same analysis is basically possible with Ant Routing using units of hops rather than Planck-intervals-since-the-Epoch, I think you still have the same basic problem that Dandelion is solving, assuming of course that the fact that Dandelion exists and is being worked on implies the problem actually exists. (I guess this is where the "Distance counters need not be in units of hops" trap card triggers.) More importantly: on the Bitcoin network, a node can drop a connection with a peer and then select a new node to connect with, at very little cost or risk. On the Lightning network, a node closing a channel and then re-opening elsewhere is significantly more costly and time-consuming and risky. This means that any probes on the network topology of Lightning are likely to remain valid for longer than probes on the topology of Bitcoin network, meaning we expect this kind of triangulation to be *easier* on Lightning than on Bitcoin, simply because of the greater permanence of channels vs connections. Fortunately, the fact that Dandelion exists means you can probably just reuse it here. When a payee wants to broadcast a pheromone, it instead sends it to one peer with the "stem" flag set. When a node receives a pheromone with the "stem" flag set, it randomly promotes it to "fluff" stage and broadcasts it itself, or sends it out again to one other peer with the "stem" flag still set. Additional tooling will be needed to ensure a stem does not get stuck, and so on, I am sure the people working on Dandelion can give you additional details. This misleads triangulation and strengthens the obfuscation you add to the distance counters. > > Concerning payment failures: it was our understanding that the reason for > > the high failure rate of the current routing algorithm is because > > Alice doesn't know the channel balances of other nodes, and thus cannot be > > sure that her choice of path has enough funds to forward
Re: [Lightning-dev] DRAFT: interactive tx construction protocol
> Probably so that address reuse is not dinged, i.e. I have two UTXOs with the same address and want to make two different channels with different peers. Having 2 utxos locked to the same pubkey will map to a single H2 value though, which is what is used to flag utxo reuse. With a PoDLE you're proving that you have a *key* for a utxo; the verifier checks that the key you say you know does in fact map to controlling the utxo that you say it's attached to. Whether or not you added the utxo to the signature commitment doesn't add anything to the security of the verification. At worse, it might leak what other utxo that the initiator controls, if they accidentally commit to the wrong utxo and the peer decided to try grinding utxo outpoints on the offchance that one matched. On Tue, Feb 11, 2020 at 10:04 PM ZmnSCPxj wrote: > Good morning niftynei, and waxwing, and list, > > > > s = k + H(kG || kJ || P || P2 || utxo || receiving-node) x > > > > > and as before transfer opening: (P, P2, u, s, e) with receiving-node > implicitly reconstructed to do the verification of the Schnorr sig. It's > basically a message in a signature. > > > > Oh that's *much* nicer than calculating a second commitment. > Verification by any node that's not the intended recipient will fail, as > they'll use the wrong node_id (their own). > > > > It seems unnecessary to me to commit to the utxo, since the pubkey pair > effectively does that. What's the motivation for including it? > > Probably so that address reuse is not dinged, i.e. I have two UTXOs with > the same address and want to make two different channels with different > peers. > > While address reuse Is Bad, you might not have much control over some wog > who is supposed to pay you and decides to give you your money in two > separate UTXOs to the same address. > > Regards, > ZmnSCPxj > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] DRAFT: interactive tx construction protocol
ZmnSCPxj via Lightning-dev writes: > Good morning niftynei, > > >> Rusty had some suggestions about how to improve the protocol messages for >> this, namely adding a serial_id to the inputs and outputs, which can then be >> reused for deletions. >> >> The serial id can then also be used as the ordering heuristic for >> transaction inputs during construction (replacing current usage of BIP69). >> Inputs can be shared amongst peers by flipping the bottom bit of the >> serial_id before relaying them to another peer (as your own). > > What happens if the initiator deliberately provides serial IDs 0x1, 0x3, > while the acceptor naively provides serial IDs from `/dev/urandom`? This is a feature, and one you might need to use if you have some SIGHASH_SINGLE or other weirdness for one input. > Then the balance of probability is that the initiator inputs and outputs are > sorted before the acceptor. > Now, this is probably not an issue, since the initiator and acceptor both > know which inputs and outputs are theirs and not theirs, so they could just > reveal this information to anyone, so an actor providing such lousy serial > IDs is just hurting its own privacy relative to blockchain analysts, so > probably will not happen in practice. > > My initial reaction was to propose adding a secret-sharing round where the > resulting key is XORed to each serial ID before sorting by the XORed serial > ID, but this might be too overweight, and again the initiator is only hurting > its own privacy, and the two participants already know whose money is whose > anyway >> > - nLocktime is always set to 0x >> >> - If a blockheight to be used as nLocktime is communicated in the initiation >> step, is set to blockheight-6; otherwise set to zero- > > I am unsure what is the purpose of this minus 6. > > If you fear blockheight disagreements, this is probably a good time to > introduce block headers. > So for example if the acceptor thinks the initiator blockheight is too high, > it could challenge the initiator to give block headers from its known > blockheight to the initiator blockheight. > If the acceptor thinks the initiator blockheight is too low, it could provide > block headers itself as proof. > This could be limited so that gross differences in blockheight are outright > rejected by the acceptor (it could `error` the temporary channel ID rather > than accept it). Yes, I would just have the initiator specify nLocktime directly, just like feerate. If you don't like it, don't contribute to the tx construction. > This is SPV, but neither side is actually making or accepting a payment > *yet*, just synchronizing clocks, so maybe not as bad as normal SPV. > > Massive chain reorgs cannot reduce blockheight, only increase it (else > the reorg attempt fails in the first place) This is not quite true, due to difficulty adjustments. It's true in practice, however, and not relevant since you'd just have to wait one more block. >> - Serial ids should be chosen at random >> - For multiparty constructions, the initiator MUST flip the bottom bit of >> any received inputs before relaying them to a peer. >> >> - Collisions of serial ids between peers is a protocol error > > I suppose we should define collision to mean "equal in all bits except the > lowest bit". No, literally equal. i.e. you can only make this error by clashing with yourself. Cheers, Rusty. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Decoy node_ids and short_channel_ids
Bastien TEINTURIER writes: > Hi Rusty, > > Thanks for the answer, and good luck with c-lightning 0.8.1-rc1 ;) ... Now -rc2. I actually had a RL use for lightning (OMG!), and sure enough found a bug. > I've been thinking more about improving my scheme to not require any sender > change, but I don't think that's possible at the moment. As with all > Lightning > tricks though, once we have Schnorr then it's really easy to do. > Alice simply needs to use `s * d_a` as her "preimage" (and the payment point > becomes the P_I Bob needs). That may depend on the exact multi-hop locks > construction we end up using though, so I'm not 100% sure about that yet. I was starting to think this whole thing was of marginal benefit: note that solving "private channels need a temp scid" is far simpler[1]. But since your scheme extends to rendevous, it's much more tempting! We would use this for normal private channels as well as private routes aka new rendezvous. Even better, this would be a replacement for current route hints (which lack ability to specify feature bits, which we would add here, and is also grossly inefficient if you just want to use it for Routeboost[2]). Propose we take the `z` to use as bolt11 letter, because even the French don't pronounce it in "rendez-vous"!) Then use TLV inside:[3] * `z` (2): `data_length` variable. One or more entries containing extra routing information; there may be more than one `z` field. Each entry looks like: * `tlv_len` (8 bits) * `rendezvous_tlv` (tlv_len bytes) 1. tlvs: `rendezvous_tlv` 2. types: 1. type: 1 (`pubkey`) 2. data: * [`point`:`nodeid`] 1. type: 2 (`short_channel_id`) 2. data: * [`short_channel_id`:`short_channel_id`] 1. type: 3 (`fee_base_msat`) 2. data: * [`tu32`:`fee_base_msat`] 1. type: 4 (`fee_proportional_millionths`) 2. data: * [`tu32`:`fee_proportional_millionths`] 1. type: 5 (`cltv_expiry_delta`) 2. data: * [`tu16`:`cltv_expiry_delta`] 1. type: 6 (`features`) 2. data: * [`...*byte`:`features`] That probably adds 6 bytes entry, but worth it I think. Cheers, Rusty. [1] Add a new field to 'funding_locked': "private_scid". If both sides support 'option_private_scid' (?) then the "real" scid is no longer valid for routing, and we use the private scid. [2] It's enough to give the scid(s) in this case indicating where you have incoming capacity. [3] I'm really starting to dislike my bolt11 format. We should probably start afresh with a TLV-based one, where signature covers the hash of each entry (so they can be easily externalized!), but that's a big, unrelated task. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] DRAFT: interactive tx construction protocol
Good morning Rusty, niftynei, and list, > > > - Serial ids should be chosen at random > > > > > > - For multiparty constructions, the initiator MUST flip the bottom bit > > > of any received inputs before relaying them to a peer. > > > > > > - Collisions of serial ids between peers is a protocol error > > > > > > > I suppose we should define collision to mean "equal in all bits except the > > lowest bit". > > No, literally equal. i.e. you can only make this error by clashing with > yourself. hmm, I thought the entire point of having the low bit was that you could multifund in such a way that the initiator creates multiple channels simultaneously with multiple nodes? So you would have to take the UTXOs of one peer and give it to the other peer claiming it as your own. Or something. With PoDLE this would not be possible I think, as you would not be able to open the PoDLE commitment with the other node as the target (if we go with the modified PoDLE which also commits to which node an opening is for, to prevent the pouncing venus flytrap attack). Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] DRAFT: interactive tx construction protocol
Good morning waxwing, > > https://github.com/privacypass/challenge-bypass-extension/blob/master/docs/PROTOCOL.md > > While it's very different from our use-case (harder because not > client-server), Am still going through the document, but wanted to react to "not client-server" thing. Generally over the Internet the presumption is that the server just passively lies there in wait, and then a client actively contacts the server to get some service. In terms of Lightning opening protocols, the channel opener is the client, and the acceptor is the server. Similarly, in terms of JoinMarket, the taker is the client, and the maker is the server. Of course the link seems to be very different, am still reading through it. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] DRAFT: interactive tx construction protocol
Good morning niftynei, waxwing, and list, > > Probably so that address reuse is not dinged, i.e. I have two UTXOs with > > the same address and want to make two different channels with different > > peers. > > Having 2 utxos locked to the same pubkey will map to a single H2 value > though, which is what is used to flag utxo reuse. With a PoDLE you're proving > that you have a key for a utxo; the verifier checks that the key you say you > know does in fact map to controlling the utxo that you say it's attached to. > Whether or not you added the utxo to the signature commitment doesn't add > anything to the security of the verification. > > At worse, it might leak what other utxo that the initiator controls, if they > accidentally commit to the wrong utxo and the peer decided to try grinding > utxo outpoints on the offchance that one matched. Right, right, H2 commits to knowledge of the privkey, not a specific UTXO. I suppose the Right Thing to do if somebody foists address reuse on you would be to spend all UTXOs with the same address together. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
