Nadav Kohen [ARCHIVE]

Last Notes

2023-06-09 15:01:58 CEST

- reply

📅 Original date posted:2021-02-08
📝 Original message:
Hi Andrés,
> Am I correct in understanding that this is a proposal to change the spec
(maybe add a new BOLT) so that all lightning implementations can try to
support this feature.
Yes, the proposal relies on the use of PTLCs in place of HTLCs which is a
popular change that will (hopefully) be brought about by Taproot. It is
worth noting that this change is not specific to this protocol and that
only the end nodes (buyer and seller) would need any special code in order
to execute these contracts if the underlying Lightning Network was using
PTLCs.
> If the above is true, then I'm wondering: could a Lightning-based escrow
system be implemented that doesn't require to modify the existing
implementations? Maybe if we simplify the requirements a bit? Like,
removing the "Escrow only learns of dispute cases, never learns non-dispute
case" aspect? That is, the third-party S always knows about an escrow
between A and B taking place.
At a high level, what is required here is that the payment goes through iff
[Seller AND (Buyer OR Escrow)] agree to it. Lifting restrictions so that
the Escrow is allowed to be more interactive can allow the Buyer and Escrow
to do an interactive shared secret generation and this secret could then be
used in a spontaneous payment to the Seller (meaning the payment hash is
generated by the Buyer and not the Seller) and then the Seller would have
to obtain a ZKP from the Escrow that the payment hash is the hash of a
secret known to the Escrow. If all of this were done, then the Seller could
execute given the shared secret from either the Buyer or the Escrow. Of
note, another downside to this scheme beyond Escrow involvement is that
there is no proof of payment/reciept over the Lightning Network for this
payment because it is a spontaneous payment.
Like ZmnSCPxj's proposal, this would only require special code for the "end
nodes" (Buyer and Seller) and the underlying HTLC-based lightning network
would require no changes. Also note that this scheme relies on the
existence of a Zero Knowledge Proof of Knowledge (ZKPoK) of a hash which is
not a trivial piece of work but certainly do-able.
Hi Pedro,
I actually did have a question for you about Virtual Channels: The first
time I read the paper it struck me that while on the surface things look
pretty nice for the virtual channel participants, the intermediary has to
lock up a lot of collateral (in total, the size of the channel) in order to
enable this and subsequently this channel could stay open for a very long
time. As such, to the intermediary this seems very similar to having to
route a (potentially very large) hodl HTLC which means they will be
charging a very large fee for both the setup and the duration of the
channel. Because of this, I'm having trouble thinking of almost any use
cases where this is preferable to just routing payments the normal way
other than if the in-between node is not reliable and there are no other
cheap routes (in which case it might be worth it to pay a premium). Did you
or your colleagues have other use cases in mind? And have you done any fee
analysis for this scheme?
Best,
Nadav
On Mon, Feb 8, 2021 at 2:43 AM Pedro Moreno-Sanchez <
pedrorechezmailinglists at gmail.com> wrote:
> Hello,
>
> While reading this thread I realized that my colleagues and I have been
> working on a construction called “Bitcoin-compatible Virtual Channels” [1]
> that, at a first glance, highly resembles the use case and requirements
> that you put forward in this thread. In a nutshell, a Virtual Channel is
> built on top of two payment channels and use them to construct its own
> “funding transaction”. Imagine that Buyer and Seller do not have a payment
> channel between them, but they both have a payment channel with a common
> node (e.g., Escrow in your example). Alice and Bob can create a Virtual
> Channel between them using fundings from both: channel Alice-Escrow and
> channel Escrow-Bob. After created, the Virtual Channel offers the same
> functionality as a direct payment channel between Alice and Bob (i.e.,
> Escrow is no longer involved for payments). Our construction makes sure
> that no party losses funds when the Virtual Channel needs to be closed
> (either when Alice and Bob collaborate or any of the 3 parties cheat).
>
> This construction is compatible with the current Bitcoin script (e.g.,
> taproot is not required although perhaps useful when available) and with
> the Lightning Network. In the paper, we describe our construction assuming
> that a payment-channel follows the design in “Generalized
> Bitcoin-Compatible Channels” [2], however the Virtual Channel construction
> can seamlessly work using the current Lightning payment channels.
>
> I would be glad to hear any feedback that you may have.
>
> Cheers,
> Pedro Moreno-Sanchez
>
> ==
>
> [1] https://eprint.iacr.org/2020/554
> [2] https://eprint.iacr.org/2020/476.pdf
>
> > On Feb 8, 2021, at 9:09 AM, Andrés G. Aragoneses <knocte at gmail.com>
> wrote:
> >
> > Hey ZmnSCPxj,
> >
> > Am I correct in understanding that this is a proposal to change the spec
> (maybe add a new BOLT) so that all lightning implementations can try to
> support this feature.
> >
> > If the above is true, then I'm wondering: could a Lightning-based escrow
> system be implemented that doesn't require to modify the existing
> implementations? Maybe if we simplify the requirements a bit? Like,
> removing the "Escrow only learns of dispute cases, never learns non-dispute
> case" aspect? That is, the third-party S always knows about an escrow
> between A and B taking place.
> >
> > I understand that the above requirement is a good to have, but if
> removing it allows a simpler version of escrow be implemented, then at
> least there could be an interim solution for non-custodial exchanges to
> start adopting this (otherwise they have to resort to custodial-based
> escrows, which is worse than lacking the escrow privacy brought by the
> requirement above).
> >
> > Thanks
> > _______________________________________________
> > 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/20210208/89782223/attachment.html>

2023-06-09 14:59:53 CEST

- reply

📅 Original date posted:2020-04-23
📝 Original message:
Hi Laolu,
Thanks for the response :)
I agree that some more framing probably would have been good to have in my
update.
First, I want to clarify that my intention is not to implement a PTLC-based
lightning network on top of ECDSA adaptor signatures, as I do believe that
using Schnorr will be superior, but rather I wish to get some PoC sandbox
with which to start implementing and testing out the long list of currently
theoretical proposals surrounding PTLCs, most of which are implementation
agnostic (to a degree anyway). I think it would be super beneficial to have
more fleshed out with respect to what some challenges of a Payment Point LN
are going to be than we understand now, before Schnorr is implemented and
it is time to commit to some PTLC scheme for real.
Second, I agree that I've probably understated somewhat the changes that
will be needed in most implementations as I was mostly thinking about what
would need to change in the BOLTs, which does actually seem relatively
minimal (although as you mention, these minimal changes to the BOLTs do
trigger large changes in many implementations). Also, good point on how
BOLT 11 (invoicing) will have to be altered as well, must've slipped my
mind.
Best,
Nadav
On Wed, Apr 22, 2020 at 8:17 PM Olaoluwa Osuntokun <laolu32 at gmail.com>
wrote:
> Hi Nadav,
>
> Thanks for the updates! Super cool to see this concept continue to evolve
> and integrate new technologies as they pop up.
>
> > I believe this would only require a few changes to existing nodes:
>
> Rather than a "few changes", this would to date be the largest
> network-level
> update undertaken to the Lightning Network thus far. In the past, we rolled
> out the new onion blob format (which enables changes like this), but none
> of
> the intermediate nodes actually need to modify their behavior. New payment
> types like MPP+AMP only needed the _end points_ to update making this an
> end-to-end update that has been rolled out so far in a de-synchronized
> manner.
>
> Re-phrasing deploying this requires changes to: the core channel state
> machine (the protocol we use to make commitment updates), HTLC scripts,
> on-chain HTLC handling and resolution, path finding algorithms (to only see
> out the new PTLC-enabled nodes), invoice changes and onion blob processing.
> I'd caution against underestimating how long all of this will take in
> practice, and the degree of synchronization required to pull it all off
> properly.
>
> For a few years now the question we've all been pondering is: do we wait
> for
> scnhorr to roll out multi-hop locks, or just use the latest ECDSA based
> technique? As dual deployment is compatible (we can make the onion blobs
> for
> both types the same), a path has always existed to first roll out with the
> latest ECDSA based technique then follow up later to roll out the schnorr
> version as well. However there's also a risk here as depending on how
> quickly things can be rolled out, schnorr may become available
> mid-development, which would possibly cause us to reconsider the ECDSA path
> and have the network purely use scnhorr to make things nice and uniform.
>
> Zooming out for a bit, the solution space of "how channels can look post
> scriptless-scripts + taproot" is rather large [1], and the addition of this
> new technique allows for an even larger set of deployment possibilities.
> This latest ECDSA variant is much simpler than the prior ones (which had a
> few rounds of more involved ZKPs), but since it still uses OP_CMS, it can't
> be used to modify the funding output.
>
> [1]:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002375.html
>
> -- Laolu
>
>
> On Wed, Apr 22, 2020 at 8:13 AM Nadav Kohen <nadav at suredbits.com> wrote:
>
>> Hello all,
>>
>> I'd like to give an update on the current state of thinking and coding
>> surrounding replacing Hash-TimeLock Contracts (HTLCs) with Point-TimeLock
>> Contracts (PTLCs) (aka Payment Hashes -> Payment Points) in hopes of
>> sparking interest, discussion, development, etc.
>>
>>
>> We Want Payment Points!
>> -----------------------
>>
>> Using point-locks (in PTLCs) instead of hash-locks (in HTLCs) for
>> lightning payments is an all around improvement. HTLCs require the use of
>> the same hash across payment routes (barring fancy ZKPs which are inferior
>> to PTLCs) while PTLCs allow for payment de-correlation along routes. For an
>> introduction to the topic, see
>> https://suredbits.com/payment-points-part-1/.
>>
>> In addition to improving privacy in this way and protecting against
>> wormhole attacks, PTLC-based lightning channels open the door to a large
>> variety of interesting applications that cannot be accomplished with HTLCs:
>>
>> Stuckless (retry-able) Payments with proof of payment (
>> https://suredbits.com/payment-points-part-2-stuckless-payments/)
>>
>> Escrow contracts over Lightning (
>> https://suredbits.com/payment-points-part-3-escrow-contracts/)
>>
>> High/DLOG AMP (
>> https://docs.google.com/presentation/d/15l4h2_zEY4zXC6n1NqsImcjgA0fovl_lkgkKu1O3QT0/edit#slide=id.g64c15419e7_0_40
>> )
>>
>> Stuckless + AMP (an improvement on Boomerang) (
>> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-October/002239.html
>> )
>>
>> Pay-for-signature (
>> https://suredbits.com/payment-points-part-4-selling-signatures/)
>>
>> Pay-for-commitment (
>> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002166.html
>> )
>>
>> Monotonic access structures on payment completion (
>> https://suredbits.com/payment-points-monotone-access-structures/)
>>
>> Ideal Barrier Escrow Implementation (
>> https://suredbits.com/payment-points-implementing-barrier-escrows/)
>>
>> And allowing for Barrier Escrows, we can even have
>>
>> Atomic multi-payment setup (
>> https://suredbits.com/payment-points-and-barrier-escrows/)
>>
>> Lightning Discreet Log Contract (
>> https://suredbits.com/discreet-log-contracts-on-lightning-network/)
>>
>> Atomic multi-payment update (
>> https://suredbits.com/updating-and-transferring-lightning-payments/)
>>
>> Lightning Discreet Log Contract Novation/Transfer (
>> https://suredbits.com/transferring-lightning-dlcs/)
>>
>> There are likely even more things that can be done with Payment Points so
>> make sure to respond if I've missed any known ones.
>>
>>
>> How Do We Get Payment Points?
>> -----------------------------
>>
>> Eventually, once we have Taproot, we can use 2p-Schnorr adaptor
>> signatures in Lightning channels. For a detailed thread by ZmnSCPxj, see
>> here
>> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002375.html
>>
>> In the meantime, Lloyd has written about a way to do 1p-ECDSA adaptor
>> sigs (https://github.com/LLFourn/one-time-VES) which can be paired with
>> OP_CHECKMULTISIG to allows us to execute PTLCs on Bitcoin today!
>>
>> Nickler has implemented this in a branch of secp256k1 (
>> https://github.com/jonasnick/secp256k1/pull/14) and I have implemented
>> it in Bouncy Castle in Bitcoin-S with some testing against this branch (
>> https://github.com/nkohen/bitcoin-s-core/tree/bouncy-adaptor). Do note
>> that as nickler states on his PR, "IT IS EXTREMELY DANGEROUS AND RECKLESS
>> TO USE THIS MODULE IN PRODUCTION. DON'T!"
>>
>> A demo of an on-chain PTLC I executed using nickler's implementation on
>> the backend + bitcoin-s can be seen here https://youtu.be/w9o4v7Idjno
>>
>> And waxwing did a lovely write-up about the crypto itself
>> https://joinmarket.me/blog/blog/schnorrless-scriptless-scripts/
>>
>> I would be very interested in having a fork of (at least) one lightning
>> implementation (or Rust Lightning) to be a proof of concept ECDSA-PTLC node
>> with which we can test and play with the plethora of PTLC-based proposals
>> above.
>>
>> I believe this would only require a few changes to existing nodes:
>>
>> 1) update_add_ptlc will have a 32 byte x-coordinate (of a point) rather
>> than a 32 byte hash. Additionally the onion's hop_data will contain a 32
>> byte scalar tweak for each hop. As per [link multi-hop locks]. The last
>> hop_data will instead include a 32 byte scalar equal to the sum of all
>> tweaks.
>>
>> 2) commitment_signed will have 162 byte adaptor ptlc_signatures rather
>> than valid (71/72 byte) ECDSA signatures on PTLC-success transactions.
>>
>> 3) The in-flight outputs on the commitment transaction itself become a
>> little simpler as we no longer need to explicitly check the payment
>> pre-image against a hash. Instead, delete all instances of "OP_HASH160
>> <RIPEMD160(payment_hash)> OP_EQUALVERIFY" in the scripts (leaving the rest
>> the same) and require no pre-image in the witness, only a valid signature.
>> The pre-image check is implicitly enforced by the <remoteptlc_sig> witness
>> since only an adaptor signature was provided by remote so that the payment
>> pre-image is required to create the valid signature (from which the
>> pre-image can be then deduced by comparing adaptor and valid signatures).
>>
>> If I've missed any other changes that need to happen, do respond with
>> them!
>>
>> I hope that as a community we can work towards having a PTLC-based
>> Lightning Network that is safe and stable as soon as possible, and so I
>> encourage further thinking, development and expirementation with PTLCs now
>> so that when Taproot is finally at our disposal we can cleanly start moving
>> towards a more ideal Lightning :)
>>
>> Best,
>> Nadav
>> _______________________________________________
>> 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/20200423/a75c29ad/attachment-0001.html>

2023-06-09 14:59:23 CEST

- reply

📅 Original date posted:2020-04-02
📝 Original message:
Good morning ZmnSCPxj,
> The consideration is that much of the cost of a channel is with the setup
and teardown --- E could always just reopen the CE channel again later.
> Thus, the cost that E bears in setting up EE and tearing down EE would be
still similar to the cost of losing CE and reestablishing it again.
> Further, any amount it places in the EE channel would be an amount it
could have been using as liquidity on Lightning, but which it cannot use
for forwarding (because it is a channel to nowhere).
> Ultimately, proof-of-closure is an economic mechanism, not an
information-theoretic one.
Okay, I see what you mean now but I'm still a bit worried due to the
following: although it is true that the same nominal penalty is incurred,
the real economic value for the attacker in channel E-E' is significantly
less than that in A-E, which can be used for routing. As such, a rich
attacker who wishes to crowd out their competition might occasionally open
channels with themselves equal to the value needed to lock up a
competitor's channels, then do such a payment to themselves (with a high
"hard" locktime) and close their temporary channel, but still hold their
competitor's funds hostage, and still have enough liquidity in the channels
they didn't have to close in order to facilitate all routing that was done
by their competitor. Furthermore this route (for self-payment) could attack
multiple competitors at the same time (likely leaving some funds to all but
the least liquid competitor).
I could be missing something, but it seems to me like the proposal to close
channels after a soft timeout unless non-cooperation can be proven upstream
adds a cost to the attacker of two on-chain transactions, which they can
immediately revoke (as they know both pieces to the revocation priv key),
but still allows very long lock-ups of other's funds (with a 10x multiplier
if they choose a long route). I do think that this is certainly an
improvement on what we have now but I'm not sure it properly punishes the
attacker in its current form.
> Since this is a proof-of-***closure***, this is indeed an actual closing
of the channel.
Ah I see, I was misunderstanding a couple things, but I get it now, makes
sense :)
Best,
Nadav
On Wed, Apr 1, 2020 at 7:43 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Nadav,
>
>
> > Love the idea! I have a couple questions though:
> >
> > I'm not convinced that "Purely Falsified Proof-Of-Closure" aren't
> effective. Consider a similar network to the one you described where we
> have channels A - B - C and A - E - C but where we add a "fake" channel E -
> E'. Now if the attacker sets up a payment from E to E' using the route E -
> C - B - A - E - E', then the attacker can successfully lock up all of B's
> channels (as is desirable to get rid of competition) and also generate a
> false proof of closure for the E - E' channel. Even if this false proof
> (which is a commitment tx) ends up being published on chain, E has lost no
> ability to route and has successfully made B unable to route between A and
> C. If my understanding of the proposal is correct, and it may not be, then
> the punishment for grieving payments is the threat of closing channels that
> would benefit from the grieving attack. But adding a new channel on the end
> to be closed seems to invalidate this punishment?
>
> The consideration is that much of the cost of a channel is with the setup
> and teardown --- E could always just reopen the CE channel again later.
> Thus, the cost that E bears in setting up EE and tearing down EE would be
> still similar to the cost of losing CE and reestablishing it again.
> Further, any amount it places in the EE channel would be an amount it
> could have been using as liquidity on Lightning, but which it cannot use
> for forwarding (because it is a channel to nowhere).
> Ultimately, proof-of-closure is an economic mechanism, not an
> information-theoretic one.
>
> So the mere existence of EE, to be later sacrificed, is enough punishment
> on E.
> I think.
>
> >
> > A second question I have is if you think that it would be advisable to
> use up-front payments (pay for attempt, not just success) on payments with
> abnormally high soft timeouts? If all this works, this combination seems to
> be a way to enable hodl invoices under the proof of closure proposal.
>
> Possibly, though this increases the complexity of the proposal even more.
>
> >I just thought of a potentially more serious problem, at least for
> Poon-Dryja channels, isn't it true that giving a proof of closure is
> equivalent to actually closing the channel since once other parties have
> copies of the fully signed commitment transaction, it cannot be safely
> revoked since other parties now have the ability to publish an old state? I
> might be missing something but this seems like a big problem.
>
> Since this is a proof-of-***closure***, this is indeed an actual closing
> of the channel.
> It would not be proof-of-closure if the channel was not being closed, but
> proof-of-something-else.
>
> What is desired is simply that C can plausibly say "I punished somebody
> else by closing on them, please do not punish me for punishing them".
>
> Regards,
> ZmnSCPxj
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200402/b6b6749a/attachment.html>

2023-06-09 14:59:21 CEST

- reply

📅 Original date posted:2020-04-01
📝 Original message:
Hi ZmnSCPxj and list,
Love the idea! I have a couple questions though:
I'm not convinced that "Purely Falsified Proof-Of-Closure" aren't
effective. Consider a similar network to the one you described where we
have channels A - B - C and A - E - C but where we add a "fake" channel E -
E'. Now if the attacker sets up a payment from E to E' using the route E -
C - B - A - E - E', then the attacker can successfully lock up all of B's
channels (as is desirable to get rid of competition) and also generate a
false proof of closure for the E - E' channel. Even if this false proof
(which is a commitment tx) ends up being published on chain, E has lost no
ability to route and has successfully made B unable to route between A and
C. If my understanding of the proposal is correct, and it may not be, then
the punishment for grieving payments is the threat of closing channels that
would benefit from the grieving attack. But adding a new channel on the end
to be closed seems to invalidate this punishment?
A second question I have is if you think that it would be advisable to use
up-front payments (pay for attempt, not just success) on payments with
abnormally high soft timeouts? If all this works, this combination seems to
be a way to enable hodl invoices under the proof of closure proposal.
Best,
Nadav
On Wed, Apr 1, 2020 at 1:19 AM ZmnSCPxj via Lightning-dev <
lightning-dev at lists.linuxfoundation.org> wrote:
> Introduction
> ============
>
> Given the fact that contracts on offchain protocols need to be enforceable
> onchain as well, timelocks involved in multi-hop payments are measured in
> blocks.
> This is because the blockchain can only (third-party-verifiably) enforce
> timeouts in units of entire blocks.
> This leads to very long timeouts for payment delivery, thus multi-hop
> offchain payment attempts can be, deliberately or accidentally, be in a
> "pending" state up to the very large timeouts involved.
>
> Deliberately setting up a multi-hop payment such that it will be in a
> "pending" state for long periods of time is colloquially known as a
> "griefing attack".
> In this article, we assess various proposed solutions to mitigate the
> effects of griefing attacks, and propose a particular solution,
> proof-of-closure, as well, that requires significant changes to the update
> state machine.
>
> Digression: Why Grief?
> ======================
>
> Before embarking on our investigation for solutions to the griefing
> problem, we should first wonder if griefing is, in fact, a problem.
>
> This brings up the question of: why would anybody grief at all?
>
> Humans, like cats and other less-sapient pieces of walking meat, often
> find enjoyment in causing the suffering of others for no immediate direct
> gain to themselves, as a public demonstration of dominance over those they
> make suffer (aka "shits and giggles", which, if executed correctly, can
> lead to eventual direct gains to themselves or their progeny or relatives
> or allies, but such details are often outside the ken of the very beings
> who execute such survival strategies: brains are pieces of meat that have
> been hacked to act as action-reaction engines, but are not sophisticated
> enough to execute as pure rationality engines at all times).
> Fortunately, in the Bitcoin world, only purely rational beings of pure
> selfishness can exist in the long run, thus we can neglect such motivations
> as mere noise.
>
> First, let us investigate *how* griefing attacks can be performed.
>
> * An intermediate node in a multi-hop attempt can delay forwarding or
> failing an incoming HTLC.
> * A final node in a payment attempt can delay claiming an incoming HTLC.
>
> Let us consider a purely rational intermediate node of pure selfishness:
>
> * If it forwards as soon as possible, it can earn fees, and also speed up
> the release of the HTLC-locked funds so that they can reuse those funds as
> liquidity for further payment attempts.
> * Thus, delaying an HTLC is not selfishly-rational for an intermediate
> node.
>
> Thus, for an intermediate node, it seems there is no selfishly-rational
> motivation to execute a griefing attack on an arbitrary payment attempt.
> We can then conclude that an intermediate that delays a payment would do
> so, not of its own rational self-interest, but as an accident, such as an
> unforeseen connectivity or power failure.
>
> However, things are different when we consider a non-arbitrary payment.
> Suppose a node were to make a payment attempt to itself, and deliberately
> delay claiming this self-payment.
> This lets any single node, *who happens to own large liquidity*, to lock
> up the liquidity of other nodes.
>
> The motivation to lock up the liquidity of other nodes is to *eliminate
> competition*.
> Suppose we have a network as below:
>
> A -- B -- C
> \ /
> \ /
> \ /
> E
>
> When A and C want to transact with one another, they may choose to route
> via either B or E.
> B and E are therefore competitors in the business of forwarding payments.
>
> But suppose E has much larger channels AE and CE than the channels of AB
> and CB.
> For example, suppose E has 100mBTC perfectly-balanced channels while B has
> only 10mBTC perfectly-balanced channels, as all things should be in
> simplified models of reality.
> E can then "take out the competition" by making a 5mBTC self-payment along
> E->A->B->C->E and a 5mBTC self-payment along E->C->B->A->E, then refusing
> to claim the payment, tying up all the liquidity of the channels of B.
> By doing so, it can ensure that A and C will always fail to pay via B,
> even if they wish to transact in amounts less than 5mBTC.
> E thereby eliminates B as a competitor.
>
> This demonstrates that griefing attacks will be motivated, such that such
> attacks will be performed by payers and payees *against intermediate nodes*.
> Intermediate nodes have no motivation to attack payers and payees (those
> are their potential customers in the business of forwarding payments, and
> attacking potential customers is bad business: such attacking intermediate
> nodes will be removed economically in the long run).
> However, payers and payees can become motivated to attack intermediate
> nodes, if the "payer" and "payee" are actually competitor intermediate
> nodes.
>
> (We can observe that this is always a possibility even outside of
> Lightning: a service or product provider has no incentive to attack its
> customers ("the customer is always right"), but have an incentive to
> *pretend* to be a customer of a competitor and attack them.)
>
> We will keep this fact in mind: active griefing attacks are attacks *on*
> intermediate nodes, not *by* intermediate nodes, because there is no
> economic incentive for intermediate nodes to attack their customers.
>
> Previous Proposed Solutions
> ===========================
>
> Time-Spent Reporting
> --------------------
>
> At each channel along the route, the time spent by a node to handle its
> forwarding is recorded, and reported upstream in the route.
>
> Unfortunately, this solution protects payers from intermediate nodes and
> payees: it does not protect intermediate nodes from colluding payers and
> payees.
> Even if an intermediate node knows that a particular node is consistently
> slow via a previous time-spent report, it will not be able, with our
> current onion routing, determine if an onion packet it just received will
> or will not go through the known-slow node.
> Thus, an intermediate node would not be able to defend against distant
> payees that, with a colluding payer, will not claim a particular payment.
>
> As we have established, an active griefing atttack will never be
> deliberately performed by a selfishly-rational intermediate node.
> Thus, this solution protects against the wrong thing: it protects payers
> against slow/unreliable intermediate nodes, it does not protect
> intermediate nodes against malicious payer/payee collusions.
> It protects only against intermediate nodes that inadvertently go offline
> during forwarding, but such nodes will inevitably lose out on the
> forwarding market anyway, and will disappear in the long run.
>
> Up-Front Payment
> ----------------
>
> Payers pay for an attempt, not just the successful completion of an
> attempt.
>
> A variation on this is that the payer (or payee) continuously pays as long
> as the payment is pending.
> Further variations include paying by other means, such as just locking
> funds or paying with proof-of-work.
>
> While it certainly erects economic barriers against payer/payee collusions
> attacking intermediate nodes, it *also* erects economic barriers against
> normal, non-malicious payments.
>
> We can consider that economic barriers against non-malicious, low-value,
> high-frequency payments ("micropayments") may be enough that such payments
> become infeasible if we impose up-front payment for mere attempts.
> Thus, while this solution is certainly something we can consider, we must
> be reluctant to use it due to its up-front, strict-evaluation behavior.
>
> Proof-Of-Closure
> ================
>
> Observing the above, we want the properties for a "good" solution to
> griefing attacks to be:
>
> * It should protect intermediate nodes against payer/payee collusions.
> * It should only come into play upon detection of an attack.
>
> We now present proof-of-closure, which (we hope) has the above properties.
>
> We can consider instead a softer timeout, distinct from the HTLC
> block-based timeout.
> This softer timeout is measurable in fractions of a second, e.g. units of
> 0.1 seconds.
>
> Each node on the network advertises, in addition to a block-based
> `cltv_delta`, a `timeout_delta` in units of 0.1 seconds.
> Further, each invoice contains, in addition to a block-based `final_cltv`,
> a `final_timeout` in units of 0.1 seconds.
>
> Thus, there are two timeouts:
>
> * The current "hard" block-based timeout that is enforceable onchain.
> * A new "soft" sidereal-time-based timeout that is not onchain enforceable.
>
> The soft timeout, as mentioned, is not enforceable onchain.
> Instead, enforcement of the soft timeout *is* the act of putting the
> channel state onchain.
>
> Now, for the current "hard" block-based timeout, we already have a
> reaction.
> If the HTLC "hard" timeout is approaching:
>
> * Drop the channel onchain and enforce the hard timeout onchain to reclaim
> the funds in the HTLCs.
> * Wait for the onchain action to be deeply resolved (either timelock or
> hashlock branch is confirmed deeply) and report the result (success or
> fail) upstream.
>
> What happens if the "soft" timeout is violated?
>
> * Drop the channel onchain.
> * Report the channel closure upstream.
>
> The "hard" timeout is cancelled in any of these two conditions:
>
> * A success is reported via `update_fulfill_htlc`, OR,
> * A failure is reported via `update_fail_htlc` AND the HTLC is irrevocably
> removed from the latest commitments/state(s) of the channel.
>
> The "soft" timeout is cancelled in any of these three conditions, the
> first two of which are the same as above:
>
> * A success is reported via `update_fulfill_htlc`, OR,
> * A failure is reported via `update_fail_htlc` AND the HTLC is irrevocably
> removed from the latest commitments/state(s) of the channel, OR
> * A channel closure is reported.
>
> Let us fill this in more detail.
>
> Suppose we have a payment route A->B->C->E.
>
> Both the "hard" block timeouts and the "soft" second timeouts decrement
> monotonically at each hop.
> Thus, the payee E has the shortest "hard" and "soft" timeouts (as normal).
>
> * Suppose E then delays claiming the payment and violates the "soft"
> timeout.
> * C then drops the CE channel onchain.
> * C reports, before its own timeout (slightly larger than the timeout
> imposed on E), the closing of the channel CE, to B.
> * B validates this report, and if valid, propagates the report to A.
> * A validates this report, and if valid, accepts that the payment will be
> "stuck" for up to the hard timeout it imposed on B.
>
> C has to report back to B in order to prevent B from closing the BC
> channel, and B has to report back to A in order to prevent A from closing
> the AB channel.
> The decrementing seconds-unit timeouts are needed for each hop, for the
> same reason that decrementing block-unit timeouts are needed.
>
> Since E is motivated to attack intermediate nodes because it wants to
> redirect payment forwards through itself rather than its competitotrs,
> having one of its channels closed (which prevents it from being used for
> forwarding) is directly opposed to its end goal of getting more money,
> thus, we can believe the action of closing a channel involved in a griefing
> attack is sufficient disincentive.
>
> The major drawback is that enforcement of the soft timeout *is* a channel
> closure, which is generally a negative for the network.
> This is not a remote attack vector, since a node can only trigger this
> closure if it is able to stall the fulfillment or failure of an HTLC on a
> channel, which generally means the node triggering this closure can only do
> so for its own channels (or it is able to, via a separate mechanism,
> remotely crash a different node).
>
> Proving Channel Closes
> ----------------------
>
> What C *really* needs to prove is that:
>
> * It is *willing* to close a channel due to a violation of the soft
> timeout.
> * The channel it is willing to close was, in fact, involved in the same
> payment attempt.
>
> With the above, B can believe that C was innocent of wrongdoing, because:
>
> * C would only be wiling to close a channel in case of a protocol
> violation, in this case, a violation of the soft timeout.
> * The channel it closed was closed because of this payment attempt, and
> not because of another payment attempt, or some other unrelated channel
> being unilaterally closed.
>
> First, what C needs to prove is *NOT*, in fact, actual channel closure: it
> needs to prove a *willingness* to close a channel.
> Thus, it does not require the channel to actually be *closed* yet, i.e. it
> does not have to wait for onchain activity that the channel closure is in a
> mempool and is confirmed deeply onchain etc etc.
>
> Thus, to prove a *willingness to close* rather than an actual close, C can
> provide the unilateral close of the channel CE.
> The act of unilaterally closing a channel is the publication of the
> transaction(s) making up the unilateral close.
> Thus, if C is *willing* to close the channel, it is willing to publish the
> transaction(s) involved, and thus, providing the unilateral close to B and
> further upstream, shows a willingness to close the channel.
>
> B then validates the provided proof-of-closure by checking that the
> unilateral close transaction is either onchain, in the mempool, or that it
> spends a TXO that is not currently spent by another transaction.
> In the case the unilateral close transaction is not confirmed and in the
> mempool, B can speed up its propagation on the Bitcoin layer by putting it
> in its own mempool as well --- after all, C is willing to close the channel
> to exonerate itself and punish the actual culprit, and B putting the
> unilateral close in its own mempool can only help C in what it is willing
> to do.
>
> Secondly, C needs to prove that the channel it is willing to close
> involves the payment attempt, and is not some other channel closure that it
> is attempting to use to fulfill its own soft timeout.
> Since the unilateral close transaction *is* the proof-of-closure, B (and
> A) can inspect the transaction outputs and see (with some additional data
> from C) that one of the outputs is to an HTLC that matches the payment hash.
>
> Thus, B (and A) can believe that the proof-of-closure proves that whoever
> is presenting it is free of wrongdoing, as whoever is actually causing the
> delay has been punished (by someone being willing to close a channel with
> the culprit), and that the proof-of-closure commits to this particular
> payment attempt and no other (because it commits to a particular payment
> hash).
>
> Further, if CE is closed by E dropping it onchain rather than C, C will
> still be able to fulfill its own soft timeout by taking the closing
> transaction from E, which should still contain the HTLC.
> Indeed, neither A nor B will particularly care (nor need to know) who
> dropped the channel onchain, or (for A) that the channel participants are C
> and E.
>
> Update State Shenanigans
> ------------------------
>
> Bitcoin update mechanisms are complicated things, and it may be possible
> for an attacking payee E to fool around with the update state machine to
> make it difficult for C to report a willingness to close CE.
>
> In particular, I quote here the relevant passages from `lightning-rfc`,
> `02-peer-protocol.md`, which is an implementation of the Poon-Dryja update
> mechanism:
>
> > Thus each update traverses through the following states:
> >
> > 1. pending on the receiver
> > 2. in the receiver's latest commitment transaction
> > 3. ... and the receiver's previous commitment transaction has been
> revoked,
> > and the update is pending on the sender
> > 4. ... and in the sender's latest commitment transaction
> > 5. ... and the sender's previous commitment transaction has been revoked
>
> The payee E is the "receiver" in this context.
>
> In this case, once the update has reached step 2, then E has a commitment
> transaction that it can put onchain, that contains an HTLC it can claim.
> From this step onward, C cannot send a failure (i.e. it cannot send back
> an `update_fail_htlc`) back to B, because E could drop its latest
> commitment onchain and claim the HTLC onchain.
>
> However, until step 4, C does not have a unilateral close containing the
> HTLC, and thus cannot provide a proof-of-closure that contains an HTLC that
> refers to the payment.
>
> Thus, between steps 2 to 4, C cannot safely respond to its own soft
> timeout.
> C cannot respond with a failure, as E could then drop its latest
> commitment transaction onchain and claim the payment from C, and extract
> money from C that way.
> C also cannot respond with a proof-of-closure, as it does not have a
> transaction that it can use to provide this proof.
>
> The best that C can do would be to impose an even shorter timeout between
> steps 2 and 4 above, and to drop its current commitment transaction (which
> does not contain the HTLC yet and thus does not constitute a valid
> proof-of-closure) onchain.
> In between the time it drops the commitment transaction and its own
> incoming soft timeout, there is a chance, however small, that this
> transaction will be confirmed, and the channel will (with high probability)
> settle in a state where the HTLC is not instantiated, thus C can safely
> fail its incoming HTLC (not show a proof-of-closure, since that is not
> possible for C to do) without risk of loss, just prior to its own soft
> timeout.
>
> Of course, C is still at risk here: E could collude with miners via a
> side-channel fee offer to confirm its commitment transaction with the HTLC
> present, and ensure that C is liable for the HTLC value.
>
> With Decker-Russell-Osuntokun, we can remove this risk by requiring a
> ritual as follows:
>
> 1. C requests exclusive access to update their single shared state.
> * This can be done via a variety of sub-protocols, including a fair coin
> toss in case of near-simultaneous requests for exclusive locks on both
> sides.
> 2. C provides the details of the new HTLC to E.
> 3. C and E generate the new state transaction and exchange signatures for
> it.
> 4. C and E generate (without signing) the new update transaction.
> 5. E provides the signature (or share of signature, if MuSig) for the new
> update transaction to C.
> 6. C provides the signature for the new update transaction to E, which
> releases the exclusive lock on the shared state atomically with the
> finalization of the new update transaction.
>
> Prior to step 5, C can simply fail the incoming HTLC from B in case its
> own soft timeout is near.
> Even if E performs step 5 after C has already failed the incoming HTLC
> from B, C can simply not perform step 6 and drop the channel onchain with
> the previous update and state transactions.
>
> With Poon-Dryja, we will have to rearrange the order in which we perform
> things, effectively adding an extra communications turnaround between the
> participants.
> Specifically, the order would have to be revised to:
>
> > 1. pending on the sender
> > 2. in the sender's latest commitment transaction
> > 3. ... and the sender's previous commitment transaction has been revoked,
> > and the update is pending on the receiver
> > 4. ... and in the receiver's latest commitment transaction
> > 5. ... and the receiver's previous commitment transaction has been
> revoked
>
> This allows the sender (C in our context) to provide a proof-of-closure
> after step 2, and before step 2, C can safely return a failure with
> `update_fail_htlc` (and refuse to proceed beyond step 2, thus ensuring it
> can still use the previous commitment that still has no HTLC).
>
> Of course, this change will require redesigning the update state machine,
> increasing the number of communication turnarounds, and creating a subtle
> incompatbility when transitioning a payment from a hop that knows only the
> old update state machine to a hop that knows the new update state machine.
>
> Purely Falsified Proof-Of-Closure
> ---------------------------------
>
> Of course, the attacking node E might want to create a false
> proof-of-closure.
> E can do this by simulating a Lightning channel: lock an amount of funds
> in a 2-of-2 (where E controls both keys), then spend it in a set of
> transactions mimicking the unilateral close.
>
> We observe, however, that the overhead of simulating a Lightning channel
> is the same as the overhead of actually creating and closing a Lightning
> channel.
> Since the punishment of proof-of-closure is to force attackers to have
> their channels closed, we can consider that this simulation of a channel
> open and close is sufficient as well.
>
> Future-Proofing
> ---------------
>
> This sketch of proof-of-closure can be used for any update mechanism:
>
> * With Poon-Dryja, C can use its own commitment transaction as the
> proof-of-closure.
> * With Decker-Wattenhofer, C can give all the offchain transactions up to
> the last stage in the multi-stage decrementing-`nSequence` mechanism.
> * With Deckker-Russell-Osuntokun, C can give the latest update and state
> trnsaction.
>
> Basically, we expect that for now, and in the future, any update mechanism
> worth consideration will have a concept of "unilateral close" where a
> channel can be dropped onchain, using data that only one of the channel
> participants holds.
>
> Such a unilateral close will be a sequence of one or more valid
> transactions, terminating in a transaction containing an HTLC-like contract
> in one of its outputs.
>
> Thus, to validate the unilateral close, it is only required to validate
> all the transactions contained in the proof-of-closure, and see that the
> last transaction has an HTLC output.
>
> The limitations are thus:
>
> * The acceptable forms of HTLC would need to be agreed-upon by the entire
> network.
> * Implementations would need to be able to assess, in a
> Bitcoin-consensus-compatible way, whether a transaction is valid or not.
>
> Payment Decorrelation and Payment Points
> ----------------------------------------
>
> Of course, having a single payment hash for the entire payment attempt is
> a privacy loss, which we intend to fix in the near future by using payment
> points, and adding a blinding scalar at each hop, aka. payment
> decorrelation.
>
> Thus, in the future, there will not be any HTLC, but instead a PTLC.
> Further, the payment point at each hop will be changed at each hop, in
> order to prevent decorrelation.
>
> Thus, C needs to provide proofs:
>
> * That an apparent singlesig on the unilateral close output is in fact a
> PTLC.
> C needs to provide:
> * A target point P.
> * A partial signature that would spend that singlesig for a particular
> sighash.
> * An adaptor signature which, with knowledge of the completed signature,
> adaptor signature, and sighash message, would have revealed the scalar
> behind P.
> * That the PTLC belongs to the same payment attempt as what B offered to C.
> C needs to provide:
> * The C-only blinding factor that is the difference between the payment
> point of the B-to-C PTLC and the C-to-E PTLC on the unilateral close.
>
> Then, when B needs to propagate the proof-of-closure back to A, B simply
> adds its own blinding factor to the reported blinding factor, in order to
> convince A that this is the same payment attempt.
>
> As we have brought up privacy, we observe that, when this mechanism
> triggers, there is a mild privacy loss, in that intermediate nodes now know
> some channel closure that is related to this payment, and can thus
> determine the exact path that the payment attempt went through, at least
> until the channel being closed.
> However, proof-of-closure is only propagated in case of violation of the
> soft timeout, so for normal non-malicious payments, proof-of-closure does
> not cause any privacy loss.
> _______________________________________________
> 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/20200401/082a44f1/attachment-0001.html>

2023-06-09 14:59:21 CEST

- reply

📅 Original date posted:2020-04-01
📝 Original message:
I just thought of a potentially more serious problem, at least for
Poon-Dryja channels, isn't it true that giving a proof of closure is
equivalent to actually closing the channel since once other parties have
copies of the fully signed commitment transaction, it cannot be safely
revoked since other parties now have the ability to publish an old state? I
might be missing something but this seems like a big problem.
Best,
Nadav
On Wed, Apr 1, 2020 at 1:07 PM Nadav Kohen <nadav at suredbits.com> wrote:
> Hi ZmnSCPxj and list,
>
> Love the idea! I have a couple questions though:
>
> I'm not convinced that "Purely Falsified Proof-Of-Closure" aren't
> effective. Consider a similar network to the one you described where we
> have channels A - B - C and A - E - C but where we add a "fake" channel E -
> E'. Now if the attacker sets up a payment from E to E' using the route E -
> C - B - A - E - E', then the attacker can successfully lock up all of B's
> channels (as is desirable to get rid of competition) and also generate a
> false proof of closure for the E - E' channel. Even if this false proof
> (which is a commitment tx) ends up being published on chain, E has lost no
> ability to route and has successfully made B unable to route between A and
> C. If my understanding of the proposal is correct, and it may not be, then
> the punishment for grieving payments is the threat of closing channels that
> would benefit from the grieving attack. But adding a new channel on the end
> to be closed seems to invalidate this punishment?
>
> A second question I have is if you think that it would be advisable to use
> up-front payments (pay for attempt, not just success) on payments with
> abnormally high soft timeouts? If all this works, this combination seems to
> be a way to enable hodl invoices under the proof of closure proposal.
>
> Best,
> Nadav
>
> On Wed, Apr 1, 2020 at 1:19 AM ZmnSCPxj via Lightning-dev <
> lightning-dev at lists.linuxfoundation.org> wrote:
>
>> Introduction
>> ============
>>
>> Given the fact that contracts on offchain protocols need to be
>> enforceable onchain as well, timelocks involved in multi-hop payments are
>> measured in blocks.
>> This is because the blockchain can only (third-party-verifiably) enforce
>> timeouts in units of entire blocks.
>> This leads to very long timeouts for payment delivery, thus multi-hop
>> offchain payment attempts can be, deliberately or accidentally, be in a
>> "pending" state up to the very large timeouts involved.
>>
>> Deliberately setting up a multi-hop payment such that it will be in a
>> "pending" state for long periods of time is colloquially known as a
>> "griefing attack".
>> In this article, we assess various proposed solutions to mitigate the
>> effects of griefing attacks, and propose a particular solution,
>> proof-of-closure, as well, that requires significant changes to the update
>> state machine.
>>
>> Digression: Why Grief?
>> ======================
>>
>> Before embarking on our investigation for solutions to the griefing
>> problem, we should first wonder if griefing is, in fact, a problem.
>>
>> This brings up the question of: why would anybody grief at all?
>>
>> Humans, like cats and other less-sapient pieces of walking meat, often
>> find enjoyment in causing the suffering of others for no immediate direct
>> gain to themselves, as a public demonstration of dominance over those they
>> make suffer (aka "shits and giggles", which, if executed correctly, can
>> lead to eventual direct gains to themselves or their progeny or relatives
>> or allies, but such details are often outside the ken of the very beings
>> who execute such survival strategies: brains are pieces of meat that have
>> been hacked to act as action-reaction engines, but are not sophisticated
>> enough to execute as pure rationality engines at all times).
>> Fortunately, in the Bitcoin world, only purely rational beings of pure
>> selfishness can exist in the long run, thus we can neglect such motivations
>> as mere noise.
>>
>> First, let us investigate *how* griefing attacks can be performed.
>>
>> * An intermediate node in a multi-hop attempt can delay forwarding or
>> failing an incoming HTLC.
>> * A final node in a payment attempt can delay claiming an incoming HTLC.
>>
>> Let us consider a purely rational intermediate node of pure selfishness:
>>
>> * If it forwards as soon as possible, it can earn fees, and also speed up
>> the release of the HTLC-locked funds so that they can reuse those funds as
>> liquidity for further payment attempts.
>> * Thus, delaying an HTLC is not selfishly-rational for an intermediate
>> node.
>>
>> Thus, for an intermediate node, it seems there is no selfishly-rational
>> motivation to execute a griefing attack on an arbitrary payment attempt.
>> We can then conclude that an intermediate that delays a payment would do
>> so, not of its own rational self-interest, but as an accident, such as an
>> unforeseen connectivity or power failure.
>>
>> However, things are different when we consider a non-arbitrary payment.
>> Suppose a node were to make a payment attempt to itself, and deliberately
>> delay claiming this self-payment.
>> This lets any single node, *who happens to own large liquidity*, to lock
>> up the liquidity of other nodes.
>>
>> The motivation to lock up the liquidity of other nodes is to *eliminate
>> competition*.
>> Suppose we have a network as below:
>>
>> A -- B -- C
>> \ /
>> \ /
>> \ /
>> E
>>
>> When A and C want to transact with one another, they may choose to route
>> via either B or E.
>> B and E are therefore competitors in the business of forwarding payments.
>>
>> But suppose E has much larger channels AE and CE than the channels of AB
>> and CB.
>> For example, suppose E has 100mBTC perfectly-balanced channels while B
>> has only 10mBTC perfectly-balanced channels, as all things should be in
>> simplified models of reality.
>> E can then "take out the competition" by making a 5mBTC self-payment
>> along E->A->B->C->E and a 5mBTC self-payment along E->C->B->A->E, then
>> refusing to claim the payment, tying up all the liquidity of the channels
>> of B.
>> By doing so, it can ensure that A and C will always fail to pay via B,
>> even if they wish to transact in amounts less than 5mBTC.
>> E thereby eliminates B as a competitor.
>>
>> This demonstrates that griefing attacks will be motivated, such that such
>> attacks will be performed by payers and payees *against intermediate nodes*.
>> Intermediate nodes have no motivation to attack payers and payees (those
>> are their potential customers in the business of forwarding payments, and
>> attacking potential customers is bad business: such attacking intermediate
>> nodes will be removed economically in the long run).
>> However, payers and payees can become motivated to attack intermediate
>> nodes, if the "payer" and "payee" are actually competitor intermediate
>> nodes.
>>
>> (We can observe that this is always a possibility even outside of
>> Lightning: a service or product provider has no incentive to attack its
>> customers ("the customer is always right"), but have an incentive to
>> *pretend* to be a customer of a competitor and attack them.)
>>
>> We will keep this fact in mind: active griefing attacks are attacks *on*
>> intermediate nodes, not *by* intermediate nodes, because there is no
>> economic incentive for intermediate nodes to attack their customers.
>>
>> Previous Proposed Solutions
>> ===========================
>>
>> Time-Spent Reporting
>> --------------------
>>
>> At each channel along the route, the time spent by a node to handle its
>> forwarding is recorded, and reported upstream in the route.
>>
>> Unfortunately, this solution protects payers from intermediate nodes and
>> payees: it does not protect intermediate nodes from colluding payers and
>> payees.
>> Even if an intermediate node knows that a particular node is consistently
>> slow via a previous time-spent report, it will not be able, with our
>> current onion routing, determine if an onion packet it just received will
>> or will not go through the known-slow node.
>> Thus, an intermediate node would not be able to defend against distant
>> payees that, with a colluding payer, will not claim a particular payment.
>>
>> As we have established, an active griefing atttack will never be
>> deliberately performed by a selfishly-rational intermediate node.
>> Thus, this solution protects against the wrong thing: it protects payers
>> against slow/unreliable intermediate nodes, it does not protect
>> intermediate nodes against malicious payer/payee collusions.
>> It protects only against intermediate nodes that inadvertently go offline
>> during forwarding, but such nodes will inevitably lose out on the
>> forwarding market anyway, and will disappear in the long run.
>>
>> Up-Front Payment
>> ----------------
>>
>> Payers pay for an attempt, not just the successful completion of an
>> attempt.
>>
>> A variation on this is that the payer (or payee) continuously pays as
>> long as the payment is pending.
>> Further variations include paying by other means, such as just locking
>> funds or paying with proof-of-work.
>>
>> While it certainly erects economic barriers against payer/payee
>> collusions attacking intermediate nodes, it *also* erects economic barriers
>> against normal, non-malicious payments.
>>
>> We can consider that economic barriers against non-malicious, low-value,
>> high-frequency payments ("micropayments") may be enough that such payments
>> become infeasible if we impose up-front payment for mere attempts.
>> Thus, while this solution is certainly something we can consider, we must
>> be reluctant to use it due to its up-front, strict-evaluation behavior.
>>
>> Proof-Of-Closure
>> ================
>>
>> Observing the above, we want the properties for a "good" solution to
>> griefing attacks to be:
>>
>> * It should protect intermediate nodes against payer/payee collusions.
>> * It should only come into play upon detection of an attack.
>>
>> We now present proof-of-closure, which (we hope) has the above properties.
>>
>> We can consider instead a softer timeout, distinct from the HTLC
>> block-based timeout.
>> This softer timeout is measurable in fractions of a second, e.g. units of
>> 0.1 seconds.
>>
>> Each node on the network advertises, in addition to a block-based
>> `cltv_delta`, a `timeout_delta` in units of 0.1 seconds.
>> Further, each invoice contains, in addition to a block-based
>> `final_cltv`, a `final_timeout` in units of 0.1 seconds.
>>
>> Thus, there are two timeouts:
>>
>> * The current "hard" block-based timeout that is enforceable onchain.
>> * A new "soft" sidereal-time-based timeout that is not onchain
>> enforceable.
>>
>> The soft timeout, as mentioned, is not enforceable onchain.
>> Instead, enforcement of the soft timeout *is* the act of putting the
>> channel state onchain.
>>
>> Now, for the current "hard" block-based timeout, we already have a
>> reaction.
>> If the HTLC "hard" timeout is approaching:
>>
>> * Drop the channel onchain and enforce the hard timeout onchain to
>> reclaim the funds in the HTLCs.
>> * Wait for the onchain action to be deeply resolved (either timelock or
>> hashlock branch is confirmed deeply) and report the result (success or
>> fail) upstream.
>>
>> What happens if the "soft" timeout is violated?
>>
>> * Drop the channel onchain.
>> * Report the channel closure upstream.
>>
>> The "hard" timeout is cancelled in any of these two conditions:
>>
>> * A success is reported via `update_fulfill_htlc`, OR,
>> * A failure is reported via `update_fail_htlc` AND the HTLC is
>> irrevocably removed from the latest commitments/state(s) of the channel.
>>
>> The "soft" timeout is cancelled in any of these three conditions, the
>> first two of which are the same as above:
>>
>> * A success is reported via `update_fulfill_htlc`, OR,
>> * A failure is reported via `update_fail_htlc` AND the HTLC is
>> irrevocably removed from the latest commitments/state(s) of the channel, OR
>> * A channel closure is reported.
>>
>> Let us fill this in more detail.
>>
>> Suppose we have a payment route A->B->C->E.
>>
>> Both the "hard" block timeouts and the "soft" second timeouts decrement
>> monotonically at each hop.
>> Thus, the payee E has the shortest "hard" and "soft" timeouts (as normal).
>>
>> * Suppose E then delays claiming the payment and violates the "soft"
>> timeout.
>> * C then drops the CE channel onchain.
>> * C reports, before its own timeout (slightly larger than the timeout
>> imposed on E), the closing of the channel CE, to B.
>> * B validates this report, and if valid, propagates the report to A.
>> * A validates this report, and if valid, accepts that the payment will be
>> "stuck" for up to the hard timeout it imposed on B.
>>
>> C has to report back to B in order to prevent B from closing the BC
>> channel, and B has to report back to A in order to prevent A from closing
>> the AB channel.
>> The decrementing seconds-unit timeouts are needed for each hop, for the
>> same reason that decrementing block-unit timeouts are needed.
>>
>> Since E is motivated to attack intermediate nodes because it wants to
>> redirect payment forwards through itself rather than its competitotrs,
>> having one of its channels closed (which prevents it from being used for
>> forwarding) is directly opposed to its end goal of getting more money,
>> thus, we can believe the action of closing a channel involved in a griefing
>> attack is sufficient disincentive.
>>
>> The major drawback is that enforcement of the soft timeout *is* a channel
>> closure, which is generally a negative for the network.
>> This is not a remote attack vector, since a node can only trigger this
>> closure if it is able to stall the fulfillment or failure of an HTLC on a
>> channel, which generally means the node triggering this closure can only do
>> so for its own channels (or it is able to, via a separate mechanism,
>> remotely crash a different node).
>>
>> Proving Channel Closes
>> ----------------------
>>
>> What C *really* needs to prove is that:
>>
>> * It is *willing* to close a channel due to a violation of the soft
>> timeout.
>> * The channel it is willing to close was, in fact, involved in the same
>> payment attempt.
>>
>> With the above, B can believe that C was innocent of wrongdoing, because:
>>
>> * C would only be wiling to close a channel in case of a protocol
>> violation, in this case, a violation of the soft timeout.
>> * The channel it closed was closed because of this payment attempt, and
>> not because of another payment attempt, or some other unrelated channel
>> being unilaterally closed.
>>
>> First, what C needs to prove is *NOT*, in fact, actual channel closure:
>> it needs to prove a *willingness* to close a channel.
>> Thus, it does not require the channel to actually be *closed* yet, i.e.
>> it does not have to wait for onchain activity that the channel closure is
>> in a mempool and is confirmed deeply onchain etc etc.
>>
>> Thus, to prove a *willingness to close* rather than an actual close, C
>> can provide the unilateral close of the channel CE.
>> The act of unilaterally closing a channel is the publication of the
>> transaction(s) making up the unilateral close.
>> Thus, if C is *willing* to close the channel, it is willing to publish
>> the transaction(s) involved, and thus, providing the unilateral close to B
>> and further upstream, shows a willingness to close the channel.
>>
>> B then validates the provided proof-of-closure by checking that the
>> unilateral close transaction is either onchain, in the mempool, or that it
>> spends a TXO that is not currently spent by another transaction.
>> In the case the unilateral close transaction is not confirmed and in the
>> mempool, B can speed up its propagation on the Bitcoin layer by putting it
>> in its own mempool as well --- after all, C is willing to close the channel
>> to exonerate itself and punish the actual culprit, and B putting the
>> unilateral close in its own mempool can only help C in what it is willing
>> to do.
>>
>> Secondly, C needs to prove that the channel it is willing to close
>> involves the payment attempt, and is not some other channel closure that it
>> is attempting to use to fulfill its own soft timeout.
>> Since the unilateral close transaction *is* the proof-of-closure, B (and
>> A) can inspect the transaction outputs and see (with some additional data
>> from C) that one of the outputs is to an HTLC that matches the payment hash.
>>
>> Thus, B (and A) can believe that the proof-of-closure proves that whoever
>> is presenting it is free of wrongdoing, as whoever is actually causing the
>> delay has been punished (by someone being willing to close a channel with
>> the culprit), and that the proof-of-closure commits to this particular
>> payment attempt and no other (because it commits to a particular payment
>> hash).
>>
>> Further, if CE is closed by E dropping it onchain rather than C, C will
>> still be able to fulfill its own soft timeout by taking the closing
>> transaction from E, which should still contain the HTLC.
>> Indeed, neither A nor B will particularly care (nor need to know) who
>> dropped the channel onchain, or (for A) that the channel participants are C
>> and E.
>>
>> Update State Shenanigans
>> ------------------------
>>
>> Bitcoin update mechanisms are complicated things, and it may be possible
>> for an attacking payee E to fool around with the update state machine to
>> make it difficult for C to report a willingness to close CE.
>>
>> In particular, I quote here the relevant passages from `lightning-rfc`,
>> `02-peer-protocol.md`, which is an implementation of the Poon-Dryja update
>> mechanism:
>>
>> > Thus each update traverses through the following states:
>> >
>> > 1. pending on the receiver
>> > 2. in the receiver's latest commitment transaction
>> > 3. ... and the receiver's previous commitment transaction has been
>> revoked,
>> > and the update is pending on the sender
>> > 4. ... and in the sender's latest commitment transaction
>> > 5. ... and the sender's previous commitment transaction has been revoked
>>
>> The payee E is the "receiver" in this context.
>>
>> In this case, once the update has reached step 2, then E has a commitment
>> transaction that it can put onchain, that contains an HTLC it can claim.
>> From this step onward, C cannot send a failure (i.e. it cannot send back
>> an `update_fail_htlc`) back to B, because E could drop its latest
>> commitment onchain and claim the HTLC onchain.
>>
>> However, until step 4, C does not have a unilateral close containing the
>> HTLC, and thus cannot provide a proof-of-closure that contains an HTLC that
>> refers to the payment.
>>
>> Thus, between steps 2 to 4, C cannot safely respond to its own soft
>> timeout.
>> C cannot respond with a failure, as E could then drop its latest
>> commitment transaction onchain and claim the payment from C, and extract
>> money from C that way.
>> C also cannot respond with a proof-of-closure, as it does not have a
>> transaction that it can use to provide this proof.
>>
>> The best that C can do would be to impose an even shorter timeout between
>> steps 2 and 4 above, and to drop its current commitment transaction (which
>> does not contain the HTLC yet and thus does not constitute a valid
>> proof-of-closure) onchain.
>> In between the time it drops the commitment transaction and its own
>> incoming soft timeout, there is a chance, however small, that this
>> transaction will be confirmed, and the channel will (with high probability)
>> settle in a state where the HTLC is not instantiated, thus C can safely
>> fail its incoming HTLC (not show a proof-of-closure, since that is not
>> possible for C to do) without risk of loss, just prior to its own soft
>> timeout.
>>
>> Of course, C is still at risk here: E could collude with miners via a
>> side-channel fee offer to confirm its commitment transaction with the HTLC
>> present, and ensure that C is liable for the HTLC value.
>>
>> With Decker-Russell-Osuntokun, we can remove this risk by requiring a
>> ritual as follows:
>>
>> 1. C requests exclusive access to update their single shared state.
>> * This can be done via a variety of sub-protocols, including a fair
>> coin toss in case of near-simultaneous requests for exclusive locks on both
>> sides.
>> 2. C provides the details of the new HTLC to E.
>> 3. C and E generate the new state transaction and exchange signatures
>> for it.
>> 4. C and E generate (without signing) the new update transaction.
>> 5. E provides the signature (or share of signature, if MuSig) for the
>> new update transaction to C.
>> 6. C provides the signature for the new update transaction to E, which
>> releases the exclusive lock on the shared state atomically with the
>> finalization of the new update transaction.
>>
>> Prior to step 5, C can simply fail the incoming HTLC from B in case its
>> own soft timeout is near.
>> Even if E performs step 5 after C has already failed the incoming HTLC
>> from B, C can simply not perform step 6 and drop the channel onchain with
>> the previous update and state transactions.
>>
>> With Poon-Dryja, we will have to rearrange the order in which we perform
>> things, effectively adding an extra communications turnaround between the
>> participants.
>> Specifically, the order would have to be revised to:
>>
>> > 1. pending on the sender
>> > 2. in the sender's latest commitment transaction
>> > 3. ... and the sender's previous commitment transaction has been
>> revoked,
>> > and the update is pending on the receiver
>> > 4. ... and in the receiver's latest commitment transaction
>> > 5. ... and the receiver's previous commitment transaction has been
>> revoked
>>
>> This allows the sender (C in our context) to provide a proof-of-closure
>> after step 2, and before step 2, C can safely return a failure with
>> `update_fail_htlc` (and refuse to proceed beyond step 2, thus ensuring it
>> can still use the previous commitment that still has no HTLC).
>>
>> Of course, this change will require redesigning the update state machine,
>> increasing the number of communication turnarounds, and creating a subtle
>> incompatbility when transitioning a payment from a hop that knows only the
>> old update state machine to a hop that knows the new update state machine.
>>
>> Purely Falsified Proof-Of-Closure
>> ---------------------------------
>>
>> Of course, the attacking node E might want to create a false
>> proof-of-closure.
>> E can do this by simulating a Lightning channel: lock an amount of funds
>> in a 2-of-2 (where E controls both keys), then spend it in a set of
>> transactions mimicking the unilateral close.
>>
>> We observe, however, that the overhead of simulating a Lightning channel
>> is the same as the overhead of actually creating and closing a Lightning
>> channel.
>> Since the punishment of proof-of-closure is to force attackers to have
>> their channels closed, we can consider that this simulation of a channel
>> open and close is sufficient as well.
>>
>> Future-Proofing
>> ---------------
>>
>> This sketch of proof-of-closure can be used for any update mechanism:
>>
>> * With Poon-Dryja, C can use its own commitment transaction as the
>> proof-of-closure.
>> * With Decker-Wattenhofer, C can give all the offchain transactions up to
>> the last stage in the multi-stage decrementing-`nSequence` mechanism.
>> * With Deckker-Russell-Osuntokun, C can give the latest update and state
>> trnsaction.
>>
>> Basically, we expect that for now, and in the future, any update
>> mechanism worth consideration will have a concept of "unilateral close"
>> where a channel can be dropped onchain, using data that only one of the
>> channel participants holds.
>>
>> Such a unilateral close will be a sequence of one or more valid
>> transactions, terminating in a transaction containing an HTLC-like contract
>> in one of its outputs.
>>
>> Thus, to validate the unilateral close, it is only required to validate
>> all the transactions contained in the proof-of-closure, and see that the
>> last transaction has an HTLC output.
>>
>> The limitations are thus:
>>
>> * The acceptable forms of HTLC would need to be agreed-upon by the entire
>> network.
>> * Implementations would need to be able to assess, in a
>> Bitcoin-consensus-compatible way, whether a transaction is valid or not.
>>
>> Payment Decorrelation and Payment Points
>> ----------------------------------------
>>
>> Of course, having a single payment hash for the entire payment attempt is
>> a privacy loss, which we intend to fix in the near future by using payment
>> points, and adding a blinding scalar at each hop, aka. payment
>> decorrelation.
>>
>> Thus, in the future, there will not be any HTLC, but instead a PTLC.
>> Further, the payment point at each hop will be changed at each hop, in
>> order to prevent decorrelation.
>>
>> Thus, C needs to provide proofs:
>>
>> * That an apparent singlesig on the unilateral close output is in fact a
>> PTLC.
>> C needs to provide:
>> * A target point P.
>> * A partial signature that would spend that singlesig for a particular
>> sighash.
>> * An adaptor signature which, with knowledge of the completed
>> signature, adaptor signature, and sighash message, would have revealed the
>> scalar behind P.
>> * That the PTLC belongs to the same payment attempt as what B offered to
>> C.
>> C needs to provide:
>> * The C-only blinding factor that is the difference between the payment
>> point of the B-to-C PTLC and the C-to-E PTLC on the unilateral close.
>>
>> Then, when B needs to propagate the proof-of-closure back to A, B simply
>> adds its own blinding factor to the reported blinding factor, in order to
>> convince A that this is the same payment attempt.
>>
>> As we have brought up privacy, we observe that, when this mechanism
>> triggers, there is a mild privacy loss, in that intermediate nodes now know
>> some channel closure that is related to this payment, and can thus
>> determine the exact path that the payment attempt went through, at least
>> until the channel being closed.
>> However, proof-of-closure is only propagated in case of violation of the
>> soft timeout, so for normal non-malicious payments, proof-of-closure does
>> not cause any privacy loss.
>> _______________________________________________
>> 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/20200401/068762fe/attachment-0001.html>

2023-06-09 14:56:33 CEST

- reply

📅 Original date posted:2019-10-09
📝 Original message:
Hi list,
I'm back again with another idea about Payment Points and fun things to do
with them! Hopefully this time I'm not entirely just hashing out old ideas
in public like an out-of-the-loop person :)
*TLDR: Adding and ECDH-ing points gives us AND and OR functionality which
we can compose to make cool lightning contracts like Multisig, Escrow, and
DLCs*
So when looking at the following (likely incomplete) list of things you can
do with payment points:
1) Payment De-correlation
2) "Stuckless" Payments
3) High AMP
4) Selling Signatures
5) Selling Pedersen De-commitment
6) Escrow Contracts
I started of trying to classify what kind of thing these new features are
in hopes of coming across new ones. The first three I clumped into a group
I called "Payment point addition allows us to do cool things while
maintaining the Proof of Payment (PoP) property". The next two (4 and 5) I
called "Commitment applications where point is public". But ZmnSCPxj's
proposal for lightning escrow contracts (
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002028.html)
struck me as something different that might somehow be made more general.
Essentially the idea is to use the point S + ECDH(B, E) where S is the
seller's point, B is the buyer's point and E is the escrow's point. This
means that the scalar can be discovered by the seller in collaboration with
the buyer or the escrow, that is, S AND (B OR E). I propose that under
certain circumstances (such as the parties involved being able to
interact), this can be generalized to have payments conditioned on
arbitrary AND/OR circuits.
I believe that AND is very straightforward as you simply take two
conditions A and B and add them together to get a point that requires both
of their scalars are discoverable (except maybe under certain bad
circumstances that can be avoided where like B = C - A, this must be
guarded against).
OR is harder but I think that it can be achieved in the two party case by
ECDH and in the n-party case by multi-party key exchanges (which I know
pretty much nothing about other than that they exist). Given some key
exchange protocol (preferably non-interactive), KE, KE(A_1, ..., A_n)
should result in a number known only to those who know any scalar a_1, ...,
a_n and no one else. Assuming this exists and we can manage to trustlessly
(in some possibly stretched sense of the word) compute shared keys
(including such things as KE(A+B, C)), then KE(A, B) acts as A OR B in our
payment condition contract.
To restate the escrow contract idea in this setting, the payment is
conditioned on S + KE(B, E). Important to note is that not all parties must
know about the details of the payment itself: the Escrow in this example
knows nothing about this payment (other than that some payment exists)
unless there is a dispute.
Lastly, note that contracts following this scheme look indistinguishable to
normal payments on the network, and are fully compatible with High AMPs
since we can simply take the payment point specified by our contract and
add that point to each partial payment point.
Well this is all nice in theory, but is there anything that will actually
come out of this thinking? I'll detail the two things I've thought of so
far for which I'd love critique! I'd also love to hear if anyone else
things of any cool application using this line of thought (or really
anything cool with payment points :P).
Idea 1: "MultiSignature" Lightning Contracts
I mean "MultiSignature" here only in the sense that m-of-n parties must
agree to the payment in order for it to happen, no actual signatures are
used. A "MultiSignature" contract is simply a bunch of ANDs and ORs! For
example a 2-of-3 multisig between parties A, B, and C can be represented as
(A AND B) OR (B AND C) OR (C AND A). As such, if some seller has a point S
and three parties have points A, B, and C where a certain payment must go
through if any two of them think it should, then the payment point used for
the payment should be S + KE(A + B, B + C, C + A). We add S to this point
so that the scalar, s, can act as proof of payment. And that's it! I
haven't thought long enough to come up with any situation where this might
be useful but hoping someone who reads this will!
Idea 2: DLCs Routed over Lightning
Say that some DLC oracle will either broadcast s_A or s_B whose public
points are S_A and S_B (which can be computed from public information as
per the DLC scheme). Then say that Alice and Bob enter into a contract
under which Alice wins some amount if s_A is broadcasted and Bob if s_B is
broadcasted. Say Alice has a point A and Bob has a point B. They each send
the other a payment with the amount that party must receive if they win
with the payment point A + S_A for Bob's payment to Alice and B + S_B for
Alice's payment to Bob. And this is it! If s_A is broadcasted then Alice
gets paid (and Bob gets proof of payment a, which is the scalar to A),
otherwise s_B is broadcasted and Bob gets paid (with Alice receiving b as
PoP). An interesting note is that under this scheme neither party is forced
to pay extra on-chain fees in the case of a counter-party who doesn't
cooperate whilst in the wrong.
One wrinkle with this scheme is that setup isn't trustless. Although it is
generally true that one party must sign the funding transaction for a DLC
before the other party for on-chain DLCs, at least there is the mitigation
that when your counter-party goes silent, you can move your input funds
invalidating the funding transaction you signed (at a cost because fees).
So what can we do here to ensure that both payments are setup at the same
time in the case that Alice and Bob don't trust each other?
Say that although they don't trust each other, they're both willing to
trust some escrow entity who generates some point E for their payment.
Alice's payment point to Bob becomes B + S_B + E and Bob's to Alice becomes
A + S_A + E. The escrow now waits to hear from Alice and Bob that they have
incoming payments setup and only once both of them attest to this (using
signatures, for example) does the escrow release the scalar to E to them
both. The escrow can also have a timeout at which it will never reveal the
scalar to E: forcing both parties to commit to the contract well before the
DLC event. In this way, trust has been moved from counter-party to
trustworthy (hopefully) escrow in such a way that the Escrow learns nothing
about the contract itself (other than that there is one of some kind).
I believe that this scheme can be extended to more events through the use
of multiple payments being setup (usually in both directions) but this
seems complicated and I've rambled for long enough. One last note is that
DLC oracles can be composed in the usual way under this scheme (by
addition) and potentially even threshold multi-oracles can be supported in
this way, although this would require the oracles to attest to some shared
key's points with other oracles which isn't necessarily optimal.
Best,
Nadav
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20191009/630cee2b/attachment.html>

2023-06-09 14:55:37 CEST

- reply

📅 Original date posted:2019-07-17
📝 Original message:
Hi All,
I recently posted a proposal here for a scheme through which a trusted data
provider can utilize the Lightning Network to privately sell data where
data is received atomically with purchase.
I've more recently been thinking about situations where a party, that is
*not* trusted, is attempting to sell its signature to a known message. One
example of a situation where this would be useful is if someone is trying
to offer a DLC-like Option contract where they are essentially
collateralizing themselves in a funding transaction and then selling their
signatures to Contract Execution Transactions (CETs). In this example, we
must ensure that the buyer of the signatures pays if and only if they
receive valid signatures for the CETs which are known.
I believe that this is achievable in a relatively straightforward way if we
were to use ZmnSCPxj's proposed payment points with scalars (as opposed to
payment hashes with pre-images). The (Schnorr) signature seller could give
the buyer their one-time public key, `R = k*G`, through which the buyer
could compute the payment point whose scalar is the seller's signature:
`sig*G = R + h(m, R)*A` where `A` is the seller's public key. Using this
value as the payment point, the buyer could be assured that they pay if and
only if they receive `sig` from the seller, where `sig` is the desired
valid signature of `m`!
Best,
Nadav
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20190717/95c848fb/attachment.html>

2023-06-07 20:26:20 CEST

- reply

📅 Original date posted:2020-08-12
📝 Original message:Hello Pieter and all,
I am one of the maintainers of Bitcoin-S[1] and I maintain our secp256k1
bindings (via JNI) as well as our (inefficient) bouncy castle fallback
implementations of all secp256k1 functionality we depend on including
Schnorr signatures. In light of this new information that there is no real
downside to using evenness as the nonce tie-breaker, I am personally very
in favor of this change as it strictly simplifies things as well as making
types consistent between nonces and persistent signing keys (I can get rid
of our SchnorrNonce type :). An additional minor benefit not already
mentioned is that in places in our codebase where deserialized data is just
being passed around and not used, we currently require a computation to go
from a (x-only) SchnorrNonce to an ECPublicKey whereas going from a
SchnorrPublicKey simply requires pre-pending a 0x02 byte.
I am likely not aware of the entire impact that changing the BIP at this
stage would have but from my view (of having to update bindings and test
vectors and my fallback implementation, as well as wanting to get a stable
branch on secp256k1-zkp containing both ECDSA adaptor signatures and
Schnorr signatures for use in Discreet Log Contracts), I think this change
is totally worth it and it will only become harder to make this
simplification in the future. The schnorrsig branch has not yet been merged
into secp256k1 (and is nearing this stage I think) and so long as making
this change doesn't set us back more than a month (which seems unlikely) I
am personally in favor of making this change. Glad to hear other's thoughts
on this of course but I figured I'd voice my support :)
Best,
Nadav
[1] https://github.com/bitcoin-s/bitcoin-s/
On Wed, Aug 12, 2020 at 2:04 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hello all,
>
> The current BIP340 draft[1] uses two different tiebreakers for conveying
> the Y coordinate of points: for the R point inside signatures squaredness
> is used, while for public keys evenness is used. Originally both used
> squaredness, but it was changed[2] for public keys after observing this
> results in additional complexity for compatibility with existing systems.
>
> The reason for choosing squaredness as tiebreaker was performance: in
> non-batch signature validation, the recomputed R point must be verified to
> have the correct sign, to guarantee consistency with batch validation.
> Whether the Y coordinate is square can be computed directly in Jacobian
> coordinates, while determining evenness requires a conversion to affine
> coordinates first.
>
> This argument of course relies on the assumption that determining whether
> the Y coordinate is square can be done more efficiently than a conversion
> to affine coordinates. It appears now that this assumption is incorrect,
> and the justification for picking the squaredness tiebreaking doesn't
> really exist. As it comes with other trade-offs (it slows down signing, and
> is a less conventional choice), it would seem that we should reconsider the
> option of having the R point use the evenness tiebreaker (like public keys).
>
> It is late in the process, but I feel I owe this explanation so that at
> least the possibility of changing can be discussed with all information. On
> the upside, this was discovered in the context of looking into a cool
> improvement to libsecp256k1[5], which makes things faster in general, but
> specifically benefits the evenness variant.
>
>
> # 1. What happened?
>
> Computing squaredness is done through the Jacobi symbol (same inventor,
> but unrelated to Jacobian coordinates). Computing evenness requires
> converting points to affine coordinates first, and that needs a modular
> inverse. The assumption that Jacobi symbols are faster to compute than
> inverses was based on:
>
> * A (possibly) mistaken belief about the theory: fast algorithms for both
> Jacobi symbols and inverses are internally based on variants of the same
> extended GCD algorithm[3]. Since an inverse needs to extract a full big
> integer out of the transition steps made in the extgcd algorithm, while the
> Jacobi symbol just extracts a single bit, it had seemed that any advances
> applicable to one would be applicable to the other, but inverses would
> always need additional work on top. It appears however that a class of
> extgcd algorithms exists (LSB based ones) that cannot be used for Jacobi
> calculations without losing efficiency. Recent developments[4] and a
> proposed implementation in libsecp256k1[5] by Peter Dettman show that using
> this, inverses in some cases can in fact be faster than Jacobi symbols.
>
> * A broken benchmark. This belief was incorrectly confirmed by a broken
> benchmark[6] in libsecp256k1 for the libgmp-based Jacobi symbol calculation
> and modular inverse. The benchmark was repeatedly testing the same constant
> input, which apparently was around 2.5x faster than the average speed. It
> is a variable-time algorithm, so a good variation of inputs matters. This
> mistake had me (and probably others) convinced for years that Jacobi
> symbols were amazingly fast, while in reality they were always very close
> in performance to inverses.
>
>
> # 2. What is the actual impact of picking evenness instead?
>
> It is hard to make very generic statements here, as BIP340 will hopefully
> be used for a long time, and hardware advancements and algorithmic
> improvements may change the balance. That said, performance on current
> hardware with optimized algorithms is the best approximation we have.
>
> The numbers below give the expected performance change from squareness to
> evenness, for single BIP340 validation, and for signing. Positive numbers
> mean evenness is faster. Batch validation is not impacted at all.
>
> In the short term, for block validation in Bitcoin Core, the numbers for
> master-nogmp are probably the most relevant (as Bitcoin Core uses
> libsecp256k1 without libgmp, to reduce consensus-critical dependencies).
> If/when [5] gets merged, safegcd-nogmp will be what matters. On a longer
> time scale, the gmp numbers may be more relevant, as the Jacobi
> implementation there is certainly closer to the state of the art.
>
> * i7-7820HQ: (verify) (sign)
> - master-nogmp: -0.3% +16.1%
> - safegcd-nogmp: +6.7% +17.1%
> - master-gmp: +0.6% +7.7%
> - safegcd-gmp: +1.6% +8.6%
>
> * Cortex-A53: (verify) (sign)
> - master-nogmp: -0.3% +15.7%
> - safegcd-nogmp: +7.5% +16.9%
> - master-gmp: +0.3% +4.1%
> - safegcd-gmp: 0.0% +3.5%
>
> * EPYC 7742: (verify) (sign)
> - master-nogmp: -0.3% +16.8%
> - safegcd-nogmp: +8.6% +18.4%
> - master-gmp: 0.0% +7.4%
> - safegcd-gmp: +2.3% +7.8%
>
> In well optimized cryptographic code speedups as large as a couple percent
> are difficult to come by, so we would usually consider changes of this
> magnitude relevant. Note however that while the percentages for signing
> speed are larger, they are not what is unexpected here. The choice for the
> square tiebreaker was intended to improve verification speed at the cost of
> signing speed. As it turns out that it doesn't actually benefit
> verification speed, this is a bad trade-off.
>
>
> # 3. How big a change is it
>
> * In the BIP:
> - Changing both invocations of `has_square_y` to `has_even_y`.
> - Changing the `lift_x_square_y` invocation to `lift_x_even_y`.
> - Applying the same change to the test vector generation code, and the
> resulting test vectors.
> * In the libsecp256k1:
> - An 8-line patch to the proposed BIP340 implementation[7]: see [8]
> * In Bitcoin Core:
> - Similarly small changes to the Python test reimplementation[9]
> * Duplicating these changes in other draft implementations that may
> already exist.
> * Review for all the above.
>
>
> # 4. Conclusion
>
> We discovered that the justification for using squaredness tiebreakers in
> BIP340 is based on a misunderstanding, and recent developments show that it
> may in fact be a somewhat worse choice than the alternative. It is a
> relatively simple change to address this, but that has be weighed against
> the impact of changing the standard at this stage.
>
> Thoughts?
>
>
> # 5. References
>
> [1]
> https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#design
> [2]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017639.html
> [3] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
> [4] https://gcd.cr.yp.to/safegcd-20190413.pdf
> [5] https://github.com/bitcoin-core/secp256k1/pull/767
> [6] https://github.com/bitcoin-core/secp256k1/pull/797
> [7] https://github.com/bitcoin-core/secp256k1/pull/558
> [8]
> https://github.com/sipa/secp256k1/commit/822311ca230a48d2c373f3e48b91b2a59e1371d6
> [9] https://github.com/bitcoin/bitcoin/pull/17977
>
>
> Cheers,
>
> --
> Pieter
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200812/e77abbbc/attachment-0001.html>

2023-06-07 20:26:13 CEST

- reply

📅 Original date posted:2020-08-20
📝 Original message:Hey Chris and all,
Looking good :) I have one major concern though
> q = EC privkey generated by maker
> Q = q.G = EC pubkey published by maker
>
> p = nonce generated by taker
> P = p.G = nonce point calculated by taker
>
> R = Q + P = pubkey used in bitcoin transaction
> = (q + p).G
If I'm understanding this correctly (which I'm not sure I ame), it seems
like the plan is to put R on-chain as the key to an output? As stated this
is completely insecure as Q is known in advance so the taker can always
choose a nonce p but then claim that their nonce point is p.G - Q so that
the key that goes on-chain is (p.G - Q + Q) = p.G allowing them to steal
the funds. If the plan is not to use full-fledged 2-ECDSA (which I think is
actually necessary as I still don't understand how the HTLC signatures are
generated) you have to, at the very least, force the taker to provide a
Zero Knowledge Proof of Knowledge (ZKPoK) of the discrete log to the point
they advertise as their nonce point to avoid this. Alternatively, I think
you can use the following key as is done in MuSig:
R = H(Q || P || Q)*Q + H(Q || P || P)*P
But I still don't see how signatures can be generated for HTLCs from this
key.
Of course all of this complexity more or less goes away once we have
Schnorr signatures and can use MuSig with adaptor signatures.
Best,
Nadav
On Thu, Aug 20, 2020 at 6:17 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Good morning Chris,
>
> Great to see this!
>
> Mostly minor comments.
>
>
>
> >
> > == Direct connections to Alice ===
> >
> > Only Alice, the taker, knows the entire route, Bob and Charlie just know
> > their previous and next transactions. Bob and Charlie do not have direct
> > connections with each other, only with Alice.
> >
> > Diagram of Tor connections:
> >
> > Bob Charlie
> > | /
> > | /
> > | /
> > Alice
> >
> > When Bob and Charlie communicate, they are actually sending and
> > receiving messages via Alice who relays them to Charlie or Bob. This
> > helps hide whether the previous or next counterparty in a CoinSwap route
> > is a maker or taker.
> >
> > This doesn't have security issues even in the final steps where private
> > keys are handed over, because those private keys are always for 2-of-2
> > multisig and so on their own are never enough to steal money.
>
> This has a massive advantage over CoinJoin.
>
> In CoinJoin, since all participants sign a single transaction, every
> participant knows the total number of participants.
> Thus, in CoinJoin, it is fairly useless to have just one taker and one
> maker, the maker knows exactly which output belongs to the taker.
> Even if all communications were done via the single paying taker, the
> maker(s) are shown the final transaction and thus can easily know how many
> participants there are (by counting the number of equal-valued outputs).
>
> With CoinSwap, in principle no maker has to know how many other makers are
> in the swap.
>
> Thus it would still be useful to make a single-maker CoinSwap, as that
> would be difficult, for the maker, to diferentiate from a multi-maker
> CoinSwap.
>
> There are still a few potential leaks though:
>
> * If paying through a CoinSwap, the cheapest option for the taker would be
> to send out a single large UTXO (single-output txes) to the first maker,
> and then demand the final payment and any change as two separate swaps from
> the final maker.
> * Intermediate makers are likely to not have exact amounts, thus is
> unlikely to create a single-output tx when forwarding.
> * Thus, the first maker could identify the taker.
> * The makers can try timing the communications lag with the taker.
> The general assumption would be that more makers == more delay in taker
> responses.
>
>
>
> >
> > === Miner fees ===
> >
> > Makers have no incentive to pay any miner fees. They only do
> > transactions which earn them an income and are willing to wait a very
> > long time for that to happen. By contrast takers want to create
> > transactions far more urgently. In JoinMarket we coded a protocol where
> > the maker could contribute to miner fees, but the market price offered
> > of that trended towards zero. So the reality is that takers will pay all
> > the miner fees. Also because makers don't know the taker's time
> > preference they don't know how much they should pay in miner fees.
> >
> > The taker will have to set limits on how large the maker's transactions
> > are, otherwise makers could abuse this by having the taker consolidate
> > maker's UTXOs for free.
>
> Why not have the taker pay for the *first* maker-spent UTXO and have
> additional maker-spent UTXOs paid for by the maker?
> i.e. the taker indicates "swap me 1 BTC in 3 bags of 0.3, 0.3, and 0.4
> BTC", and pays for one UTXO spent for each "bag" (thus pays for 3 UTXOs).
>
> Disagreements on feerate can be resolved by having the taker set the
> feerate, i.e. "the customer is always right".
> Thus if the maker *has to* spend two UTXOs to make up the 0.4 BTC bag, it
> pays for the mining fees for that extra UTXO.
> The maker can always reject the swap attempt if it *has to* spend multiple
> UTXOs and would lose money doing so if the taker demands a too-high feerate.
>
>
> > == Contract transaction definitions ==
> >
> > Contract transactions are those which may spend from the 2-of-2 multisig
> > outputs, they transfer the coins into a contract where the coins can be
> > spent either by waiting for a timeout or providing a hash preimage
> > value. Ideally contract transactions will never be broadcast but their
> > existence keeps all parties honest.
> >
> > M~ is miner fees, which we treat as a random variable, and ultimately
> > set by whichever pre-signed RBF tx get mined. When we talk about the
> > contract tx, we actually mean perhaps 20-30 transactions which only
> > differ by the miner fee and have RBF enabled, so they can be broadcasted
> > in sequence to get the contract transaction mined regardless of the
> > demand for block space.
>
> The highest-fee version could have, in addition, CPFP-anchor outputs, like
> those being proposed in Lightning, so even if onchain fees rise above the
> largest fee reservation, it is possible to add even more fees.
>
> Or not.
> Hmm.
>
>
> Another thought: later you describe that miner fees are paid by Alice by
> forwarding those fees as well, how does that work when there are multiple
> versions of the contract transaction?
>
> >
> > (Alice+timelock_A OR Bob+hash) = Is an output which can be spent
> > either with Alice's private key
> > after waiting for a relative
> > timelock_A, or by Bob's private key by
> > revealing a hash preimage value
>
> The rationale for relative timelocks is that it makes private key turnover
> slightly more useable by ensuring that, after private key turnover, it is
> possible to wait indefinitely to spend the UTXO it received.
> This is in contrast with absolute timelocks, where after private key
> turnover, it is required to spend received UTXO before the absolute timeout.
>
> The dangers are:
>
> * Until it receives the private key, if either of the incoming or outgoing
> contract transactions are confirmed, every swap participant (taker or
> maker) should also broadcast the other contract transaction, and resolve by
> onchain transactions (with loss of privacy).
> * After receiving the private key, if the incoming contract transaction is
> confirmed, it should spend the resulting contract output.
> * It is possible to steal from a participant if that participant goes
> offline longer than the timeout.
> This may imply that there may have to be some minimum timeout that
> makers indicate in their advertisements.
> * The taker can detect if the first maker is offline, then if it is
> offline, try a contract transaction broadcast, if it confirms, the taker
> can wait for the timeout; if it times out, the taker can clawback the
> transaction.
> * This appears to be riskless for the taker.
> * Against a similar attack, Lightning requires channel reserves, which
> means the first hop never gains control of the entire value, which is a
> basic requirement for private key turnover.
> * On the other hand, the taker has the largest timeout before it can
> clawback the funds, so it would wait for a long time, and at any time in
> between the first maker can come online and spend using the hashlock branch.
> * But the taker can just try on the hope it works; it has nothing to
> lose.
> * This attack seems to be possible only for the taker to mount.
> Other makers on the route cannot know who the other makers are,
> without cooperation of the taker, who is the only one who knows all the
> makers.
> * On the other hand, the last maker in the route has an outgoing HTLC
> with the smallest timelock, so it is the least-risk and therefore a maker
> who notices its outgoing HTLC has a low timeout might want to just do this
> anyway even if it is unsure if the taker is offline.
> * Participants might want to spend from the UTXO to a new address after
> private key turnover anyway.
> Makers could spend using a low-fee RBF-enabled tx, and when another
> request comes in for another swap, try to build a new funding tx with a
> higher-fee bump.
>
>
> > A possible attack by a malicious Alice is that she chooses M1 to be very
> > low (e.g. 1 sat/vbyte) and sets M2 and M3 to be very high (e.g. 1000
> > sat/vb) and then intentionally aborts, forcing the makers to lose much
> > more money in miner fees than the attacker. The attack can be used to
> > waste away Bob's and Charlie's coins on miner fees at little cost to the
> > malicious taker Alice. So to defend against this attack Bob and Charlie
> > must refuse to sign a contract transaction if the corresponding funding
> > transaction pays miner fees greater than Alice's funding transaction.
>
> Sorry, I do not follow the logic for this...?
>
> > The timelocks are staggered so that if Alice uses the preimage to take
> > coins then the right people will also learn the preimage and have enough
> > time to be able to get their coins back too. Alice starts with knowledge
> > of the hash preimage so she must have a longest timelock.
>
> More precisely:
>
> * The HTLC outgoing from Alice has the longest timelock.
> * The HTLC incoming into Alice has the shortest timelock.
>
> For the makers, they only need to ensure that the incoming timelock is
> much larger than the outgoing timelock.
>
>
> >
> > == EC tweak to reduce one round trip ==
> >
> > When two parties are agreeing on a 2-of-2 multisig address, they need to
> > agree on their public keys. We can avoid one round trip by using the EC
> > tweak trick.
> >
> > When Alice, the taker, downloads the entire offer book for the liquidity
> > market, the offers will also contain a EC public key. Alice can tweak
> > this to generate a brand new public key for which the maker knows the
> > private key. This public key will be one of the keys in the 2-of-2
> > multisig. This feature removes one round trip from the protocol.
> >
> > q = EC privkey generated by maker
> > Q = q.G = EC pubkey published by maker
> >
> > p = nonce generated by taker
> > P = p.G = nonce point calculated by taker
> >
> > R = Q + P = pubkey used in bitcoin transaction
> > = (q + p).G
>
> Whoa whoa whoa whoa.
>
> All this time I was thinking you were going to use 2p-ECDSA for all
> 2-of-2s.
> In which case, the private key generated by the taker would be sufficient
> tweak to blind this.
>
> In 2p-ECDSA, for two participants M = m * G; T = t * G, the total key is m
> * t * G = m * T = t * M.
>
> Are you going to use `2 <T> <Q+P> 2 OP_CHECKMULTISIG` instead of 2p-ECDSA?
> Note that you cannot usefully hide among Lightning mutual closes, because
> of the reserve; Lightning mutual closes are very very likely to be spent in
> a 1-input (that spends from a 2-of-2 P2WSH), 2-output (that pays to two
> P2WPKHs) tx.
>
> >
> > == Protocol ==
>
> > ---8<------
>
> The protocol looks correct to me.
>
> LOL.
>
> Give me a little more time to check it in detail hahaha.
>
>
>
> > ==== Retaliation as DOS-resistance ====
> >
> > In some situations (e.g. step 8.) if one maker in the coinswap route
> is
> > the victim of a DOS they will retaliate by DOSing the previous maker
> in
> > the route. This may seem unnecessary and unfair (after all why waste
> > even more time and block space) but is actually the best way to
> resist
> > DOS because it produces a concrete cost every time a DOS happens.
>
> I agree.
>
> >
> > == Analysis of deviations ==
> >
> > This section discusses what happens if one party deviates from the
> > protocol by doing something else, for example broadcasting a htlc
> > contract tx when they shouldnt have.
> >
> > The party name refers to what that party does, followed by other
> party's
> > reactions to it.
> > e.g. Party1: does a thing, Party2/Party3: does a thing in reaction
> >
> > If multiple deviations are possible in a step then they are numbered
> > e.g. A1 A2 A2 etc
> >
> > 0-2. Alice/Bob/Charlie: nothing else is possible except following the
> > protocol or aborting
> >
> > 8. Alice: broadcasts one or more of the A htlc txes. Bob/Charlie/Dennis:
> > do nothing, they havent lost any time or money.
> > 4-6. Bob/Charlie: nothing else is possible except following the
> protocol
> > or aborting.
> >
> > 9. Bob: broadcasts one or more of the B htlc txes, Alice: broadcasts all
> > her own A htlc txes and waits for the timeout to get her money back.
> > Charlie: do nothing
> >
> > 10. Charlie: nothing else is possible except following the protocol or
> > aborting.
> >
> > 11. Alice: broadcasts one or more of the A htlc txes. Bob: broadcasts
> all
> > his own A htlc txes and waits for the timeout.
> > A. same as 8.
> > B. Charlie: broadcasts one or more of the C htlc txes, Alice/Bob:
> > broadcasts all their own htlc txes and waits for the timeout to get
> > their money back.
> > C-E1. Alice: broadcasts all of C htlc txes and uses her knowledge of
> the
> > preimage hash to take the money immediately. Charlie: broadcasts
> > all of B htlc txes and reading the hash value from the blockchain,
> > uses it to take the money from B htlc immediately. Bob: broadcasts
> > all of A htlc txes, and reading hash from the blockchain, uses it
> > to take the money from A htlc immediately.
> > C-E2. Alice: broadcast her own A htlc txes, and after a timeout take
> the
> > money. Bob: broadcast his own B htlc txes and after the timeout
> > take their money. Charlie: broadcast his own C htlc txes and after
> > the timeout take their money.
> > F1. Bob: broadcast one or more of A htcl txes and use the hash
> preimage
> > to get the money immediately. He already knows both privkeys of the
> > multisig so this is pointless and just damages privacy and wastes
> > miner fees. Alice: blacklist Bob's fidelity bond.
> > F2. Bob: broadcast one or more of the C htlc txes. Charlie: use
> preimage
> > to get his money immediately. Bob's actions were pointless. Alice:
> > cant tell whether Bob or Charlie actually broadcasted, so blacklist
> > both fidelity bonds.
> > G1. Charlie: broadcast one or more of B htcl txes and use the hash
> > preimage to get the money immediately. He already knows both
> > privkeys of the multisig so this is pointless and just damages
> > privacy and wastes miner fees. Alice: cant tell whether Bob or
> > Charlie actually broadcasted, so blacklist both fidelity bonds.
> > G2. Charlie: broadcast one or more of the A htlc txes. Alice:
> broadcast
> > the remaining A htlc txes and use preimage to get her money
> > immediately. Charlies's actions were pointless. Alice: blacklist
> > Charlie's fidelity bond.
> >
> > The multisig outputs of the funding transactions can stay unspent
> > indefinitely. However the parties must always be watching the network
> > and ready to respond with their own sweep using a preimage. This is
> > because the other party still possesses a fully-signed contract tx.
> The
> > parties respond in the same way as in steps C-E1, F2 and G2. Alice's
> > reaction of blacklisting both fidelity bonds might not be the right
> way,
> > because one maker could use it to get another one blacklisted (as
> well
> > as themselves).
>
> Looks OK, though note that a participant might try to do so (as pointed
> out above) in the hope that the next participant is offline.
>
> Thank you very much for your writeup!
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200820/d782e2d1/attachment-0001.html>