npub13e…tkq6u

📅 Original date posted:2020-11-27
📝 Original message:
Hey,
On Fri, 27 Nov 2020 at 19:18, Bastien TEINTURIER <bastien at 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 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
>>
> _______________________________________________
> 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/ca1ded55/attachment-0001.html>