Re: [Lightning-dev] Do we really want users to solve an NP-hard problem when they wish to find a cheap way of paying each other on the Lightning Network?
Hi list, On 8/31/21 5:01 AM, Anthony Towns wrote: >> "Do we really want users to solve an NP-hard problem when >> they wish to find a cheap way of paying each other on the Lightning >> Network?" > FWIW, my answer to this is "sure, if that's the way it turns out". > > Another program which solves an NP-hard problem every time it runs is > "apt-get install". > [I]f it fails too often, > you re-analyse what's going on manually and add a new heuristic to cope > with it. I've been following the conversation with interest and I acknowledge this is a thorny issue. I am a bit worried with a path which relies on constantly finding new heuristics to approximate a solution to an NP-hard problem: * It allows too much room for nonconstructive disagreement between LN developers in the future. - In a worst case scenario, all implementations end up using different, incompatible heuristics because each group of developers thinks that they have the best one, leading to a suboptimal performance for everyone. Heuristics are less of an exact science after all. * It makes the job of node operators less predictable, since it would depend more on the decisions of said developers with no guarantee of convergence to a single solution. - Node operators may perceive this as loss of decentralization to the developers. Such an approach is much more suitable to debian, since they have full control and a complete view over their "network" of packages, as opposed to LN, which is decentralized, nodes come and go at will and they can be private (even from developers!). Best, Orfeas The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] [bitcoin-dev] On the scalability issues of onboarding millions of LN mobile clients
>If everyone runs such a privately-owned server, on the other hand, this >is not so different from having a Lightning node you run at your home >that has a fullnode as well and which you access via a remote control >mobile device, and it is the inconvenience of having such a server at >your home that prevents this in the first place. Private full nodes serving headers to a handful of weak devices have been mentioned many times as a good solution against all sorts of problems in a future full of LN + SPV nodes. I agree. It should be therefore a top priority to make the UX of connecting my mobile LN client to my home full node extremely easy, so that centralised services can't improve much on that step. Especially if I already run a full node. Could someone briefly describe how this UX looks currently? And if it's not as seamless as it could, what blockers are there? Best, Orfeas -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Time-Dilation Attacks on Offchain Protocols
I guess the sophisticated attacks try to trick the victim into believing that no attack is underway, but I may be wrong. Orfeas On 14 December 2019 19:54:19 CET, "David A. Harding" wrote: >On Mon, Dec 09, 2019 at 01:04:07PM -0500, Antoine Riard wrote: >> Time-Dilation Attacks on Offchain Protocols >> === > >What is the advantage of these sophisticated attacks over the eclipse >attacker simply not relaying the honest user's commitment or penality >transactions to miners? > >-Dave The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] A proposal for up-front payments.
Hi ZmnSCPxj, >>> requiring a fee is equivalent to requiring proof-of-work, incentive-wise. >> >> Not necessarily, given that >> 1) there is a finite bitcoin supply but an eventually infinite PoW >> supply (relevant in the unlikely case fees are burned) >> 2) sats are transferrable, whereas PoW isn't (relevant in the case fees >> are paid) > > Not actually. > Again, let me point out that PoW can be *bought*, that is precisely what > Bitcoin blockchain layer does. > And the blockchain layer PoW is bought with two things: fees and subsidies > (inflation). > Thus PoW, being purchaseable, is incentive-wise equivalent to paying somebody > to spend electricity (possibly with efficiencies at scale). > Just cut the middleman. I wasn't clear enough, sorry for that. I agree that in general PoW can be bought. However if I understand this particular PoW proposal correctly, a brand-new PoW has to be created for each intermediary. These PoWs cannot be reused by the intermediary for later payments (or for anything else). I will now show that there exist spam-prevention schemes that differ only on whether the payer gives sats or PoWs to intermediaries, such that economically rational agents are incentivized to cheat in the case of sats but not so in the case of PoWs. This proves that fees are *not* equivalent to PoWs incentive-wise. In our model, an intermediary can follow one of three possible strategies (we make the assumption that other strategies are strictly dominated by one of the three). Each strategy results in different resource utilization and proceeds from fees. (A) do nothing. This results in resources_A = 0 and sats_A = 0 (B) play honestly. resources_B < 0 (negative because they constitute an operating cost) and sats_B = anti_spam_fee + routing_fee (C) mount a plausibly deniable attack. Here resources_C < 0 and sats_C = anti_spam_fee. We assume that resources_C > resources_B + routing_fee (1). In case intermediaries receive PoWs as an anti-spam measure, it is anti_spam_fee = 0 which means that resources_C + sats_C < 0 = resources_A + sats_A, therefore strategy C is strictly dominated by A. (The fact that A also strictly dominates B is an interesting observation, but beside the point for the argument made.) OTOH, in the case of anti-spam sats, it is anti_spam_fee > 0. Therefore we have resources_C + sats_C > resources_B + sats_B (using (1)) and for a big enough anti_spam_fee, it is resources_C + sats_C > 0, therefore strategy C strictly dominates both A and B. In other words, by just changing whether we use anti-spam PoWs or fees, we change the economically rational behavior. I apologize for the previous ambiguity and I hope this has made my argument clearer. Best, Orfeas -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] A Payment Point Feature Family (MultiSig, DLC, Escrow, ...)
Good morning, > * Sub-payment - one or more attempts, each of which semantically pay for "the same thing" for "the same value", set up in parallel. > a sub-payment may have multiple attempts running in parallel, but only one attempt will be claimable. > * Payment - one or more sub-payments, each of which semantically pay for "different parts of an entire thing", set up in parallel. > a payment may have multiple sub-payments, and all sub-payments will be claimed atomically. This can be also thought of as: Payment = ONE-OF(attempt_11, ..., attempt_m1) AND ... AND ONE-OF(attempt_n1, ..., attempt_m'n) Its dual also deserves some thought: Payment = ONE-OF(attempt_11 AND ... AND attempt_m1), ..., (attempt_n1 AND ... AND attempt_m'n)) or in words, "A payment is an atomic value transfer through many paths, each of which carry a part of the entire value -- many alternative groups of paths are available to be used, but only one of the groups eventually goes through." Is there a reason to design in preference of one of the two? Speaking of generalization, it would be nice to have arbitrary AND-OR combinations, but this needs further exploration: > If we want to create more complex access structures then we use verifiable secret sharing where the discrete log of B is split up into shares and distributed according the the desired structure. One possible milestone of this generalisation would be to enable atomic payments where the paying wallet says "there are all these known paths, each with such and such capacity; I want some to go through such that the desired value is transferred in aggregate, no more, no less (possibly within a margin of error)". Kindly ignore me if I'm regurgitating already discussed stuff. Best, Orfeas -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
[Lightning-dev] Fwd: Paper: A Composable Security Treatment of the Lightning Network
-- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Forwarded Message Subject: Re: [Lightning-dev] Paper: A Composable Security Treatment of the Lightning Network Date: Thu, 18 Jul 2019 17:47:20 +0100 From: Orfeas Stefanos Thyfronitis Litos To: Lloyd Fournier Hi Lloyd, > Thanks for formally modelling lightning Thanks for the constructive questions. > I found F_PayNet to be rather difficult to follow I completely agree. F_PayNet is too complex for anyone's liking. Long story short, this was the result of: * staying in the UC model (easier said than done) * building on top of G_Ledger (with all its complexity) * the modelling of the entire LN as a single functionality (minimizing abstraction leak) * not depending on the `clock` functionality (thus not obstructing G_Ledger and other protocols that use it) * possibly many other reasons (such as me being a noob dev) FWIW, it's still much simpler than the real-world protocol Pi_LN (e.g. half its length). I'm currently exploring alternative models where e.g. there's one functionality per channel. It may make things more modular, but may also expose more gory details to the "user" of the functionality (i.e. the cryptographer who builds on top of those channels). > "F_PayNet checks that for each payment the charged party was one of > the following: (a) the one that initiated the payment, (b) a malicious > party or (c) an honest party that is negligent" > > Why not assume that (b) never happens because a malicious party never > wants to lose the funds from a party they've corrupted[?] In security proofs we usually let the Adversary be any polynomial machine. In particular, this includes the case where the Adversary does silly things, such as not fulfilling HTLCs. Sure, it's not a rational thing to do, but rationality is of interest in a game-theoretic analysis. (BTW, LN is a fine example of a protocol that requires both a cryptographic and a game-theoretic analysis, each of which could uncover different flaws.) We could restrict the adversary to always fulfilling the HTLCs it can, but that would immediately exile us from UC territory. > [Why not assume] (c) never happens because honest parties follow the > protocol and check each ledger update for malicious channel closes? If activated at the correct moment and with the correct command, honest parties indeed check the ledger. However, parties are activated by the Environment (another polynomial machine), which may simply refuse to activate them in time. This is why honest parties may end up being negligent. We could tie the advancement of the protocol to the clock functionality to avoid the above, but that would bring a big degree of coupling of LN with other protocols that use the clock. E.g. G_Ledger could stall because the Environment decided not to let some LN parties advance, which is very counterintuitive. > I am not convinced that the ideal and real worlds aren't easily > distinguishable from each other by an Environment that just looks at > the transactions in the blockchain (G_ledger). Good point, it's not explained well enough in the main body, we should update the description (pp. 10-11). We indeed take care to have the exact same transactions end up on-chain in both worlds (otherwise the proof of security wouldn't work). F_PayNet checks at several moments that the ledger really contains the txs that would be there in the real world. The trick is that instead of having F_PayNet prepare all necessary transactions itself (i.e. "speak LN"), it forces the Simulator to do it by halting (and thus allowing the Environment to distinguish) in case it doesn't find the txs. > I don't understand this "receipt" mechanism. The receipt is to let the environment know which channels were successfully opened/closed and which payments were made. Importantly, it doesn't contain any keys. As such, it is unrelated to the keypair that can spend Alice's coins (the coins that Alice has before opening any channel). > In the ideal world, the ideal functionality should be the one with the > private key signing the funding transaction directly In the real world, Alice's key is created by the protocol instance when she receives REGISTER (Fig. 19, line 9), whereas in the ideal world, this key is created by the Simulator when it receives REGISTER from F_PayNet (Fig. 40, line 5). It's a bit counterintuitive on first thought, but F_PayNet shouldn't be managing private keys or doing signatures. It should just ensure that Alice's public key contains the promised coins upon channel closing. Note that our approach is different from that mentioned by Andrew Miller. Since we ensure that on-chain txs are the same in both worlds, we don't need to hide the ledger contents from the Environment. Let me know if I left an
[Lightning-dev] Paper: A Composable Security Treatment of the Lightning Network
Hi all, The promise for fast, scalable, user-friendly and trustless use of bitcoin that the Lightning Network offers motivated us to author a paper where we formalize LN in the cryptographic framework of Universal Composition and prove its security. It can be found here: https://eprint.iacr.org/2019/778 We believe that a formal proof of security was needed to specify the exact operating parameters that safeguard the funds and transactions of users against arbitrary attackers, to abstract, modularize and validate the underlying cryptography that is used in LN, to incorporate LN in the body of cryptographic protocols that have been abstracted within the Universal Composition framework (and thus can be safely composed and run in parallel) and to increase the trust of the wider community to LN. We view this work as a small contribution to the amazing effort that the Lightning community has expended both on the theoretical and the practical front throughout the last years. The paper is authored by my PhD supervisor Prof. Aggelos Kiayias and me. Any feedback will be greatly appreciated. Best regards, Orfeas Stefanos Thyfronitis Litos -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev