Bastien TEINTURIER [ARCHIVE] on Nostr: 📅 Original date posted:2020-11-27 📝 Original message: Good morning list, This ...

📅 Original date posted:2020-11-27
📝 Original message:
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).

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 at 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 <ZmnSCPxj at 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 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/20201127/89af90d4/attachment-0001.html>;