Hey, On Fri, 27 Nov 2020 at 19:18, Bastien TEINTURIER <bast...@acinq.fr> wrote:
> Good morning list, > > This is an interesting approach to solve this problem, I really like the > idea. > It definitely deserves digging more into it: the fact that it doesn't add > an additional > payment makes it largely superior to upfront payment schemes in terms of > UX. > > If we restrict these stake certificates to LN funding txs, which have a > very specific format > (multisig 2-of-2) there are probably smart ways to achieve this. > If for example we're able to do it easily with Schnorr-based funding txs, > it may be worth > waiting for that to happen. > I'm a bit afraid of having to use ZKPs for general statements, I'd prefer > something tailored > to that specific case (it would likely be more efficient and have less new > assumptions - even > though you're right to point out that this is a non-critical system, so > we're freer to experiment > with hot new stuff). > > I completely agree with Z that it should be added to the requirements that > a node cannot > reuse a stake certificate from another node for himself. > > Another constraint is that the proof has to be small, since we have to fit >> it all in a small onion... >> > > I'm not sure that's necessary. If I understand correctly, you're saying > that because in your > model, the sender (Alice) creates one stake certificate for each node in > the route (Bob, Carol) > and puts them in the onion. > > But instead it could be a point-to-point property: each node provides its > own stake certificate > to the next node (and only to that node). Alice provides a stake > certificate to Bob, then Bob > provides a stake certificate to Carol, and so on. If that's the case, it > can be in a tlv field in the > `update_add_htlc` message and doesn't need to be inside the onion. This > also makes it less > likely that Alice is exposing herself to remote nodes in the route (payer > privacy). > If the above paragraph is confirmed, then does this mean StakeCertificates with privacy are possible without ZK proofs? Or did I miss something? > > Of course, this depends on the implementation details we choose, but I > think it's worth stressing > that these two models exist and are quite different. > > Thanks, > Bastien > > Le ven. 27 nov. 2020 à 07:46, ZmnSCPxj via Lightning-dev < > lightning-dev@lists.linuxfoundation.org> a écrit : > >> Good morning Gleb, >> >> > Thank you for your interest :) >> > >> > > Quick question: if I am a routing node and receive a valid stake >> certificate, can I reuse this stake certificate on my own outgoing payments? >> > >> > That probably should be avoided, otherwise a mediocre routing node gets >> a lot of jamming opportunities for no good. >> > >> > You are right, that’s a strong argument for proof “interactivity”: >> every Certificate should probably commit to *at least* public key of the >> routing node it is generated for. >> >> Right, it would be better to have the certificate commit to a specific >> routing node rather than the payment hash/point as I proposed. >> Committing to a payment hash/point allows a random forwarding node to >> probe the rest of the network using the same certificate, lowering the >> score for that certificate on much of the network. >> >> Another constraint is that the proof has to be small, since we have to >> fit it all in a small onion... >> >> Presumably we also want the score to eventually "settle to 0" over time. >> >> Regards, >> ZmnSCPxj >> >> > >> > – gleb >> > On Nov 27, 2020, 2:16 AM +0200, ZmnSCPxj <zmnsc...@protonmail.com>, >> wrote: >> > >> > > Good morning Gleb and Antoine, >> > > >> > > This is certainly interesting! >> > > >> > > Quick question: if I am a routing node and receive a valid stake >> certificate, can I reuse this stake certificate on my own outgoing payments? >> > > >> > > It seems to me that the proof-of-stake-certificate should also >> somehow integrate a detail of the current payment (such as payment >> hash/point) so it cannot be reused by routing nodes for their own outgoing >> payments. >> > > >> > > For example, looking only at your naive privacy-broken proposal, the >> signature must use a `sign-to-contract` where the `R` in the signature is >> actually `R' + h(R' | payment_hash)` with the `R'` also revealed. >> > > >> > > Regards, >> > > ZmnSCPxj >> > > >> > > > Hello list, >> > > > >> > > > In this post, we explore a different approach to channel jamming >> mitigation. >> > > > We won’t talk about the background here, for the problem >> description as well as some proposed solutions (mainly upfront payment >> schemes), see [1]. >> > > > >> > > > We’re suggesting using UTXO ownership proofs (a.k.a. Stake >> Certificates) to solve this problem. Previously, these proofs were only >> used in the Lightning Network at channel announcement time to prevent >> malicious actors from announcing channels they don’t control. One can think >> of it as a “fidelity bond” (as a scarce resource) as a requirement for >> sending HTLCs. >> > > > >> > > > We start by overviewing issues with other solutions, and then >> present a naive, privacy-broken Stake Certificates. Then we examine >> designing a privacy-preserving version, evaluating them. At the end, we >> talk about non-trivial design decisions and open questions. >> > > > >> > > > ## Issues with other proposals >> > > > >> > > > We find unsatisfying that upfront payment schemes come at a cost of >> new fees (forward and/or backward), thus inflating payment cost for *any* >> payment. >> > > > In the future, the upfront base fee might even make “micropayments” >> economically infeasible by exceeding the value they transfer. Thus, a good >> solution should not inflate payment cost while still requiring “burning” a >> scarce resource (so that the attack is not free). >> > > > >> > > > Another issue with upfront payments is a circular trust dependency. >> Ideally, we shouldn’t introduce anything less trust-minimized than the >> Lightning Network itself. >> > > > Upfront payment schemes are not like that, because they in one way >> or another rely on the honest behavior of route participants. >> > > > >> > > > We believe Stake Certificates we are going to introduce are >> satisfactory in both of these directions: they don’t inflate payment costs >> for honest users and don’t require trust. The main disadvantage of Stake >> Certificates seems to be the novel cryptography required. >> > > > See more details in the “Evaluation” section. >> > > > >> > > > ## Channel Ownership Proofs as Routing Credit Balance >> > > > >> > > > Let’s say Alice wants to relay an HTLC to Carol through Bob. Per >> the Stake Certificates scheme, she has to commit to a particular channel >> UTXO by embedding an ownership proof in the onion packet while sending an >> HTLC to Bob. >> > > > >> > > > Bob then unwraps the onion and verifies: >> > > > 1) the channel identifier is pointing unambiguously to an on-chain >> UTXO; >> > > > 2) the ownership proof (e.g., a signature) is valid against the >> previously disclosed UTXO witness script. >> > > > >> > > > If all those checks succeed, Bob should see if Alice hasn’t >> exceeded her credit balance. In case she hasn’t, Bob has to “decrement >> Alice’s credit balance” and relay the HTLC to Carol. >> > > > Decrementing credit balance unconditionally of packet success or >> failure bounds liquidity abuse by malicious HTLC senders. >> > > > Since there is no credit assigned initially, “decrementing the >> credit balance” means just remembering that “Alice spent X out of Y of the >> credit she received for her Stake Certificates”. >> > > > >> > > > Unfortunately, this naive protocol is a privacy nightmare, because >> routing nodes can now easily assign every HTLC they forward to the sender’s >> UTXO. >> > > > >> > > > Let’s first define the terms here one more time, and then proceed >> to the non-naive, private Stake Certificates. >> > > > >> > > > - Stake Certificate. Either means a solution we’re proposing or the >> primitive it is based on, namely proof of UTXO ownership. As we will argue >> later, it actually makes sense to use proof of LN channel UTXO ownership >> specifically rather than any funds ownership. >> > > > - Stake Certificate value. An amount of the corresponding UTXO or a >> ballpark this amount provably belongs to. >> > > > - Credit balance. When Alice provides a routing node Bob with a >> Stake Certificate, Bob should increase Alice’s routing credit balance. >> Alice is then limited in her payments by this balance, and this rule is >> enforced by routing nodes to prevent free channel jamming in the network. >> Note that ideally “Alice’s credit balance“ should be virtual and only known >> to Alice, while routing nodes should only observe per-UTXO credit balance. >> We currently assume that each routing node keeps track of per-UTXO credit >> balance separately, see “Design decisions” for more details. >> > > > - Stake-to-credit function defines how much credit balance is given >> per a Stake Certificate of a given value. This function is a policy of a >> routing node, and it should be announced. >> > > > - Credit-to-value-transferred function defines how much value a >> sender can transfer along a given channel considering how much credit they >> might claim. The function may also consider different factors (e.g., the >> available capacity of a channel being used) to provide extra robustness. >> > > > >> > > > ## Privacy-preserving Stake Certificates >> > > > >> > > > The presented scheme could preserve privacy if it relied on >> zero-knowledge proofs of UTXO ownership by avoiding pointing to a >> particular UTXO. >> > > > More specifically, the verifier should be able to check that: >> > > > a) The staked UTXO is an element of the current UTXO set >> > > > b) The prover knows the witness script committed by the UTXO >> witness program >> > > > c) The prover knows a valid witness for the witness script >> > > > d) The staked UTXO was not used to produce a different Stake >> Certificate which is currently in use as well. >> > > > >> > > > The verifier should also have a way to see a Stake Certificate >> value to properly account for the credit. This can be achieved by >> restricting the UTXO set being proved upon to only those UTXOs with a >> specific range of values: “I will prove that I own a UTXO among all UTXOs >> between 0.5 BTC and 1 BTC”. >> > > > >> > > > Unfortunately, steps (b) and (c) require zero-knowledge protocols >> for general statements, which are more experimental primitives than most of >> the stuff we have in Bitcoin protocols, >> > > > although we assume it’s feasible to consider them for non-consensus >> stuff. >> > > > >> > > > ## Evaluation >> > > > >> > > > Stake Certificates, upfront payment schemes, and other potential >> solutions (given a particular configuration) may be compared along the >> following axis: >> > > > 1) Economic feasibility >> > > > 1a) What is the cost of overcoming the protection for an attacker? >> Likely a non-linear function: sats_spent =f(channels_to_jam, […]) >> > > > 1b) How does this solution limit honest users? >> > > > 2) How sophisticated is this solution in terms of integration and >> making good UX? >> > > > 3) How complex is this solution in terms of protocol >> design/implementation? >> > > > >> > > > When it comes to (1a), both Stake Certificates and upfront payments >> are probably equal, in a way that they’re just best-effort ideas to >> increase the attack cost. Unfortunately, we currently don’t know how to >> design something as economically powerful as PoW in Bitcoin [3]. >> > > > This aspect can be properly evaluated by applying these ideas to >> different hypothetical kinds of LN in a simulation and observing the >> resulting trade-off between (1a) and (1b) considering different attack >> strategies. >> > > > >> > > > In the previous sections of this post, we have argued that Stake >> Certificates may provide a much better (1b) for the cost of (3) because it >> relies on zero-knowledge. >> > > > When it comes to (2), the design of Stake Certificates may vary in >> terms of UX burden, from completely automatic to requiring custom actions >> with private keys from users. >> > > > >> > > > Some of these trade-offs along with other interesting questions are >> discussed in the following section. >> > > > >> > > > ## Design decisions and questions >> > > > >> > > > #### Should the credit spending be gossipped across the entire >> network, or should only the routing nodes involved in the payment know? >> > > > >> > > > Economically, these two approaches are likely to be equivalent, and >> it’s just a matter of stake-to-credit ratio. >> > > > However, announcing credit spending to the network results in a >> privacy leak. It also imposes bandwidth and CPU overhead on the routing >> nodes. >> > > > >> > > > #### Which zero-knowledge system should be used for Stake >> Certificates? >> > > > >> > > > Choosing a ZK system boils down to picking the right trade-offs of >> proving and verifying time, and assumptions. As we mentioned previously, we >> would need proving general statements. >> > > > At the same time, we need something cheap in both proving and >> verification, because Lightning is supposed to be fast. >> > > > At the same time, the setup probably doesn’t matter, because proofs >> are supposed to be verified only by one participant, a routing node this >> proof is generated for. >> > > > Perhaps we can also pick any cryptographic assumptions we want >> since this stuff is not mission-critical and can be easily updated if >> someone breaks a cryptographic assumption and we observe an attack. >> > > > >> > > > #### Should we allow holding *any* Bitcoins (not just LN channels) >> for Stake Certificates? >> > > > >> > > > This idea might make sense if we’re worried that some LN users >> might want to send more payments than they can afford per their credit. >> However, we believe that allowing any UTXO would give an attacker more >> opportunities to use their cold funds for this attack, or even have a >> secondary market where holders sell their proofs (they have nothing to >> loose). >> > > > Instead, we should a) design the credit-to-stake-functions better; >> b) encourage users send payments across different routing nodes (since >> credits are not tracked globally) [4]. >> > > > >> > > > #### What’s the best credit-to-value-transferred function? >> > > > >> > > > We reckon that this function should be not just linear to provide >> maximum security against malicious channel jammers. For example, we can >> charge more credit for the last 20% of the capacity of the *channel used >> for routing*. Alternatively, we could discourage making too many payments >> from the same UTXO within a short period of time by charging more credit in >> this case. >> > > > >> > > > #### What about the interactivity and lifetime of Stake >> Certificates? >> > > > >> > > > Interactive proofs mean that they are constructed on demand of a >> routing node, non-interactive means constructed by a payment sender ahead >> of time. >> > > > Both interactivity and lifetime have something to do with the ease >> of producing proof and accessing keys. >> > > > We will omit the details of the trade-off we consider, but it >> remains an open question. >> > > > >> > > > #### If Stake Certificates are valid for N blocks after proof >> generation, does it mean that if the UTXO is spent during those N blocks, >> new proof can be generated from the same coins without invalidating the old >> proof? >> > > > >> > > > Yes, but an attacker would, first of all, have to pay an on-chain >> fee for this. If we’re still worried about this problem, there are >> workaround ideas. >> > > > For example, we could have epochs of 100 blocks (every epoch starts >> at #XYZXYZ00 block). If at the start of an epoch, a channel wasn’t in the >> UTXO set, it provides very little credit. >> > > > Alternatively, we could expand the zero-knowledge part to proving >> that the coins were not yet spent. >> > > > >> > > > #### Should spending a UTXO reveal all Stake Certificates generated >> from it? >> > > > >> > > > This would also solve the problem in the previous question, but it >> would mean a retrospective privacy leak again. To avoid a privacy leak, we >> should prevent this. >> > > > >> > > > #### What if malicious Sybil *routing* nodes failing payments >> causing other honest routing nodes to reduce the credit of an honest >> payment sender? >> > > > >> > > > Both Stake Certificates and upfront payment schemes suffer from >> malicious routing nodes failing the payments and “wasting” the sender’s >> credit or fees. This problem even applies out of the channel jamming >> context, when considering payment failure rate. >> > > > This problem can be addressed by reducing the reputation of faulty >> links and routing nodes on the payment sender node. When payment routing >> becomes a for-profit activity, this would encourage routing nodes to >> sanitize their links. >> > > > The mitigation can be even stronger by using “provable blaming” >> introduced in [2]. >> > > > >> > > > ## Conclusion >> > > > >> > > > We propose Stake Certificates, a new solution to channel jamming. >> Perhaps, it might not be the best near-term solution due to the complexity, >> but the zero satoshi overhead for honest payments is an appealing argument >> to switch to it in the future. >> > > > This proposal also illustrates how stake-based protocols can solve >> Sybil challenges in the Bitcoin ecosystem. Since this might be useful in >> other contexts (Sybil-resistance of many kinds, proof-of-ownership), >> discussing Stake Certificates is even more useful. >> > > > The next step is a discussion of Stake Certificates. If the >> community finds it interesting, then we should discuss the design questions >> mentioned above, and choose a cryptosystem. >> > > > >> > > > Cheers, >> > > > Gleb Naumenko and Antoine Riard >> > > > >> > > > ——— >> > > > >> > > > References and footnotes: >> > > > 1. >> https://github.com/t-bast/lightning-docs/blob/master/spam-prevention.md >> > > > 2. >> https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-August/000135.html >> > > > 3. We don’t actually suggest PoW to solve these issues, because a) >> the trade-off between honest user cost and attacker cost is misaligned due >> to specialized hardware and b) smartphones would die too fast if they have >> to compute PoW; PoW is just an unreachable example of system robustness due >> to well-aligned game theory. >> > > > 4. Secondary markets are still possible even if we restrict >> acceptable proofs to only LN channels, but supply would be much smaller, >> and markets would work much worse for an attacker. >> >> >> _______________________________________________ >> Lightning-dev mailing list >> Lightning-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev >> > _______________________________________________ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev >
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
