From thomas.huet at acinq.fr  Tue Nov  8 14:22:41 2022
From: thomas.huet at acinq.fr (Thomas HUET)
Date: Tue, 8 Nov 2022 15:22:41 +0100
Subject: [Lightning-dev] Unjamming lightning (new research paper)
In-Reply-To: <CACtNmG4WvYE87W3L7qhsBCxUwHsG7xPpT+ezkPWm2H1fnQmBzQ@mail.gmail.com>
References: <CAFi0HOcmFqh3Zqx1x40VEGVVSp0a+xYvFESAp6C7HsvNqUDxnQ@mail.gmail.com>
 <CALZpt+GJShLGTWVbFYbVn2v9YXgoBb0_Z8Xcq43rCM_whNZHMA@mail.gmail.com>
 <CACtNmG4WvYE87W3L7qhsBCxUwHsG7xPpT+ezkPWm2H1fnQmBzQ@mail.gmail.com>
Message-ID: <CA+n-rRu__kcd5byaPKGhUB8awRK-KHShvy73PGWz=vC7QD_aFg@mail.gmail.com>

Hi,

I agree that the local reputation solution is very promising (I'm less
convinced about the unconditional fee as it changes a core principle of the
network which means that we'll never reach consensus on it). What I really
like about it is that it's quite simple and can be quickly deployed without
even needing to coordinate with others or upgrade the network.
I had a similar idea but your solution adds a "I endorse this payment" bit
which I think can make the method a lot more effective (and unfortunately
breaks the "can be deployed without upgrading the network" but I think it's
worth it). However if we change the protocol, we may as well make it a
continuous risk score instead of a binary low/high-risk. Also, having only
two classes (high and low-risk) protects the the low-risk class but makes
the high-risk class even easier to attack, having a continuous policy
should mitigate this problem.
And while I agree with the general idea of throttling based on a local
reputation, I think we need more work to find a good formula to compute
this reputation. I don't have a good formula myself but relying on "A
satoshis per second" doesn't seem wise. There are huge disparities between
nodes and even for a given node, traffic is fluctuating a lot. I think a
more reliable indicator would be the proportion of successful payments.
The beauty of this solution is that we don't need a standardized formula
for reputation, everyone can use its own. However getting a good one is
hard so we need a default recommandation.

Thanks for your work.
Thomas

Le lun. 7 nov. 2022 ? 19:23, Clara Shikhelman <clara.shikhelman at gmail.com>
a ?crit :

> Hi Antoine,
>
> Thank you for the detailed response!
>
>
>
>> On the framework for mitigation evaluation, there are few other
>> dimensions we have considered in the past with Gleb for our research that
>> could be relevant to integrate. One is "centralization", the solution
>> shouldn't centralize sensibly the LN ecosystem around any of its actors:
>> LSP, Lightning Wallet Providers (e.g watchtower or Greenlight-style infra)
>> or routing node, where centralization could be defined in terms of "market
>> entry cost" for new incumbents. "Protocol evolvability" could be another
>> one, as we don't want a solution rendering the design and operations of
>> things like offline-receive, trampoline, negative fees, etc harder.
>> "Ecosystem impacts" was one more category we thought about, e.g introducing
>> a mass mempool congestion vector (one of the versions of Stakes
>> Certificates did it...).
>>
>
> These are indeed important dimensions. I think that our solution gets
> ?good marks? in all of them, but this should definitely be stated
> explicitly in the future.
>
>
>> For the dimensions of your evaluation framework, the "effectiveness"
>> sounds to be understood as attacker-centric. However few times after in the
>> paper, the viewpoint of the routing nodes sounds to be adopted
>> ("compensating them for the financial damage of jamming", "breakeven point
>> n"). If this distinction is real, the first way would be more searching for
>> a game-theory equilibrium whereas much damage is inflicted to the attacker.
>> The second one would be more to ensure a compensation for the loss income
>> for the routing nodes. I believe the first approach is limited as the
>> attacker's resources could overwhelm the victim's economic sustainability,
>> and rationality might be uneconomic. Maybe those two approaches could be
>> combined, in the sense that loss income compensation should only be borne
>> by "identified" attackers, however this doesn't sound the direction taken
>> by unconditional fees.
>>
>
> The effectiveness evaluation does have a few facets. From the attacker's
> viewpoint, it might be that mitigation makes the attack impossible,
> difficult, or expensive. From the victim's point of view, we can talk about
> protection, compensation, or any combination of the two. Of course, the
> best outcome is when the attack is impossible. As this is oftentimes not
> something we can do, we have to choose one of the other outcomes.
>
>
>> About "incentive compatibility", one element valuable to integrate is how
>> much the existence of scoring algorithms allows the routing nodes to adopt
>> "honest behaviors" and high-level of service availability. I don't know if
>> a jamming solution can be devised without considerations of the inner
>> workings of routing/scoring algorithms, and so far every LN implementation
>> has its own cooking.
>>
>
> We focused on the most basic incentive of not failing transactions that
> could have been forwarded. I'll be happy to discuss other potential
> pitfalls if you have something in mind.
>
>
>>
>> On the structure of the monetary strategy, I think there could be a
>> solution to implement a proof-of-burn, where the fee is captured in a
>> commitment output sending to a provably unspendable output. Theoretically,
>> it's interesting as "unburning" the fee is dependent on counterparty
>> cooperation, the one potentially encumbering the jamming risk.
>> Proof-of-work "fee" has been discussed in the past by LN devs, however it
>> was quickly dismissed, as it would give an edge to the attacker who is able
>> to gather ASICs farms while completely burning the batteries of LN mobile
>> clients. It has also been widely discussed to make the fees conditional on
>> either outgoing HTLC CLTV value or effective duration. For effective
>> duration, an upfront fee shard could be paid after each clock tick (either
>> epoch or block-based).
>>
>
> The main problem with proof of burn or PoW is that it does not compensate
> the victim, we write this explicitly in the newer version of the paper.
> Thanks for this comment, we will add further details on previous
> discussions.
>
>
>> On the structure of reputation strategy, I think one interesting missing
>> point to me is the blurring of the local/global reputation definition in
>> Lightning. At least maybe in a way traditionally defined in P2P
>> litterature. Reputation could be enforced on the HTLC sender, as we've
>> aimed with Stakes Certificates. The upstream peer reputation is not
>> accounted for at all. I think it's an open question if the reputation score
>> of a routing node could be exported across nodes (a behavior that one could
>> expect if you assume web-of-trust, as the current LN network topology is
>> heavily based on). On the statement, that attaching reputation to payment
>> contradicts the LN's privacy-focused goal, I would say it's a light one in
>> regards to the state of cryptography tools like blinded signature, known
>> since the 80s.
>>
>
> I think that further research on assigning the blame to the sender is of
> interest, but as we don't have this right now, it would be good to work
> with the available tools.
>
>
>> On the analysis of the unconditional fee, I think my main objection would
>> be the lack of integration of the time uncertainty of the honest use-cases,
>> making it hard to classify between quick and slow jamming. As you say "The
>> borderline between quick and slow jamming depends on a subjective
>> definition of the maximal honest payment resolution delay" An attacker
>> should hold all its HTLC jamming for a duration of "maximal honest payment
>> resolution delay" minus 1. Without even scoping L2s protocol like swaps or
>> hold-invoice where the effective duration might hold for a few blocks,
>> modern flows like offline receive where the user has to take manual actions
>> to settle the HTLC could far extend beyond a few seconds. To develop my
>> point, fair compensation could aim for the most optimistic flow of
>> short-held 0.1s payment, however a routing policy could qualify as honest
>> payment resolution delay duration of as much as a few minutes. This
>> discrepancy could be exploited by an attacker to inflict an asymmetric
>> damage to the routing nodes. Of course, one fix could be to scale up the
>> unconditional fee amount in function of the maximal honest payment
>> resolution delay accepted by the routing node policy". I wonder if it would
>> be suitable in terms of UX.
>>
>
> For special use cases, where Alice and Bob agree that HTLCs can wait for a
> long time over the channel, they can agree that this would not change their
> reputation with the other party. If Alice decides to knowingly forward to
> Bob an HTLC that will not resolve quickly, without agreeing on this
> beforehand, this is a problem and should be solved through the reputation
> system.
>
>
>> For a routing node, there is the uncertainty of downstream payment path
>> hops, responsible for some failures, I don't know if it's currently
>> accounted for in the evaluation of the unconditional fee. If the
>> unconditional fee paid downstream is too high, there is a moral hazard for
>> the routing node, they can pocket the fee, depending how much they're
>> penalized by the sender scoring algorithm.
>>
>
> This is addressed in inequality 5 in the paper.
> In general, routing algorithms should avoid nodes and channels that
> regularly fail their payments. This is true beyond the scope of upfront
> fees, and as the upfront fees are rather low, this wouldn't be the main
> motivation for avoiding ?bad? nodes.
>
>
>
>> On the analysis of the reputation mechanism, there is one recursive
>> issue: you might constrain the incoming HTLC traffic of your peers, even if
>> they're all honest. Let's say you assign K slots and L satoshis of
>> liquidity to your upstream peer Carioll, Caroll must know divide by (K, L)
>> by two to Alice and Bob, even if Alice and Bob each can offer (K, L) of
>> honest HTLC traffic.
>>
>
> Are we the only node sending anything to Carol? If this is the case, our
> channel is Carol's bottleneck, and indeed whichever limit we choose will be
> the limit she will have to handle (this is a bit of "min-cut max-flow"
> problem for Carol, where our channel is her min-cut)
>
>
>> Further, there is also the attack timing asymmetries, in the sense that a
>> high-reputation score might have been earned in period of low-congestion,
>> and consumed during period of high-congestion, so it sounds to me
>> reputation should be quantitative rather to introduce a low-risk/high-risk
>> binary framework, to account for proportionality. This proportionality
>> issue is a hard thing, especially if I would like concretely to address
>> payments with intentionally delayed resolutions in a non-cooperative-only
>> way.
>>
>
> As reputation policy is determined on the level of an individual node, it
> could be that some will choose to take into account congestion.
>
>
>> Lastly, I wonder if there is not some conceptual issue with the chaining
>> of unconditional fee and local reputation. As I understand the distinction
>> between quick/slow jamming is based on this idea of maximal honest payment
>> resolution delay. However, the bypass of this upper bound is only known
>> _after_ the HTLC forward, and as such it sounds to me the strategie regime
>> (unconditional fee/local reputation) under which a HTLC forward should be
>> evaluated is dependent on the knowledge of a future event.
>>
>
> We use reputation as part of a continuous game. You don't gain or lose
> high reputation based on one HTLC, you evaluate based on the continuous
> behavior of the node. The unconditional fee is always charged.
>
>
> Thanks again,
> Clara
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20221108/dc506636/attachment-0001.html>