Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning
Hi everyone, I've seen some discussions over losing proofs of payment in the AMP setting, and wanted to address some lingering concerns I have regarding the soundness of using the current invoicing system to prove payments. In general, I think we are ascribing too much weight to simply having a preimage and BOLT 11 invoice. The structure of non-interactive payments definitely poses some interesting challenges in adapting the existing invoicing scheme. However, I believe there exist stronger and better means of doing proofs of payment, and would prefer not to tie our hands by assuming this is the best way to approach the problem. IMHO, the current signed invoice + preimage is a very weak proof of payment. It's the hash equivalent to proving you own a public key by publishing the secret key. There is an assumption that the only way someone could get that preimage is by having made a payment, but this assumption is broken most directly by the proving mechanism. Similarly, any intermediary who acquires an invoice with the appropriate hash could also make this claim since they also have the preimage. Further, I think it's a mistake to conflate 1) me being able to present a valid preimage/invoice pair, with 2) me having received the correct preimage in response to an onion packet that I personally crafted for the receiving node in the invoice. The main issue is that the proof does not bind a specific sender, making statement 1 producible by multiple individuals. I think it would be potentially worthwhile to explore proofs of stronger statements, such as 2, that could utilize the ephemeral keys in the onion packets, or even the onion as a witness, which is more rigidly coupled to having actually completed a payment. Without any modification to the spec, we can always use something like ZKBoo to prove (w/o trusted setup) knowledge of a preimage without totally revealing it to the verifier. This isn't perfect, but at least gives the sender the option to prove the statement without necessarily giving up the preimage. TL;DR: I'm not convinced the signed invoice + hash is really a good yardstick by which to measure provability, and I think doing some research into proofs of payment on stronger statements would be incredibly valuable. Therefore, I'm not sure if AMPs really lose this, so much as force us to reconsider what it actually requires to soundly prove a payment to an external verifier. Best, Conner On Mon, Feb 12, 2018 at 6:56 PM ZmnSCPxj via Lightning-dev < lightning-dev@lists.linuxfoundation.org> wrote: > Good morning Christian and Corne, > > Another idea to consider, is techniques like ZKCP and ZKCSP, which provide > atomic access to information in exchange for monetary compensation. > Ensuring atomicity of the exchange can be done by providing the information > encrypted, a hash of the encryption key, and proofs that the encrypted data > is the one desired and that the data was encrypted with the given key; the > proof-of-payment is the encryption key, and possession of the encryption > key is sufficient to gain access to the information, with no need to bring > in legal structures. > > (admittedly, ZKCP and ZKCSP are dependent on new cryptography...) > > (also, AMP currently cannot provide a proof-of-payment, unlike current > payment routing that has proof-of-payment, but that is an eventual design > goal that would enable use of ZKC(S)P on-Lightning, assuming we eventually > find out that zk-SNARKs and so on are something we can trust) > > Regards, > ZmnSCPxj > > > Sent with ProtonMail Secure Email. > > > Original Message > On February 13, 2018 2:05 AM, Christian Decker < > decker.christ...@gmail.com> wrote: > > >Honestly I don't get why we are complicating this so much. We have a > > system that allows atomic multipath payments using a single secret, and > > future decorrelation mechanisms allow us to vary the secret in such a > > way that multiple paths cannot be collated, why introduce a whole set of > > problems by giving away the atomicity? The same goes for the overpaying > > and trusting the recipient to only claim the owed amount, there is no > > need for this. Just pay the exact amount, by deriving secrets from the > > main secret and make the derivation reproducible by intermediate hops. > > > > Having proof-of-payment be presentable in a court is a nice feature, but > > it doesn't mean we need to abandon all guarantees we have worked so hard > > to establish in LN. > > > > Corné Plooy via Lightning-dev lightning-dev@lists.linuxfoundation.org > >writes: > > > >>I was thinking that, for that use case, a different signed invoice could > >> be formulated, stating > >> - several payment hashes with their corresponding amounts > >> > >> - the obligation of signer to deliver Z if all corresponding payment > >> keys are shown > >> > >> - some terms to handle the case where only a part of the payments was > >> successful, e.g. an obligation to refund > >>The
Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning
Good morning Christian and Corne, Another idea to consider, is techniques like ZKCP and ZKCSP, which provide atomic access to information in exchange for monetary compensation. Ensuring atomicity of the exchange can be done by providing the information encrypted, a hash of the encryption key, and proofs that the encrypted data is the one desired and that the data was encrypted with the given key; the proof-of-payment is the encryption key, and possession of the encryption key is sufficient to gain access to the information, with no need to bring in legal structures. (admittedly, ZKCP and ZKCSP are dependent on new cryptography...) (also, AMP currently cannot provide a proof-of-payment, unlike current payment routing that has proof-of-payment, but that is an eventual design goal that would enable use of ZKC(S)P on-Lightning, assuming we eventually find out that zk-SNARKs and so on are something we can trust) Regards, ZmnSCPxj Sent with ProtonMail Secure Email. Original Message On February 13, 2018 2:05 AM, Christian Deckerwrote: >Honestly I don't get why we are complicating this so much. We have a > system that allows atomic multipath payments using a single secret, and > future decorrelation mechanisms allow us to vary the secret in such a > way that multiple paths cannot be collated, why introduce a whole set of > problems by giving away the atomicity? The same goes for the overpaying > and trusting the recipient to only claim the owed amount, there is no > need for this. Just pay the exact amount, by deriving secrets from the > main secret and make the derivation reproducible by intermediate hops. > > Having proof-of-payment be presentable in a court is a nice feature, but > it doesn't mean we need to abandon all guarantees we have worked so hard > to establish in LN. > > Corné Plooy via Lightning-dev lightning-dev@lists.linuxfoundation.org >writes: > >>I was thinking that, for that use case, a different signed invoice could >> be formulated, stating >> - several payment hashes with their corresponding amounts >> >> - the obligation of signer to deliver Z if all corresponding payment >> keys are shown >> >> - some terms to handle the case where only a part of the payments was >> successful, e.g. an obligation to refund >>The third item is a bit problematic: in order to distinguish this case >> from a complete success, the payee would have to prove absence of >> successful transactions, which is hard. Absence of successful >> transactions can only be declared by the payer, so in order to reliably >> settle without going to court first, the payer should sign a >> declaration stating that certain transactions were canceled and that the >> other ones should be refunded. This can be another invoice. >>So, the original invoice states: >> - several payment hashes with their corresponding amounts >> >> - if all corresponding payment keys are shown: the obligation of >> to deliver Z, UNLESS stated otherwise by an invoice signed by >>-- signed by >>But if a payment partially fails, it can be refunded cooperatively with >> an invoice created by payer: >> - declares which of the original payments were successful (with payment >> keys) and which were not >> >> - replaces the obligation of to deliver Z with an obligation to >> refund the successful transactions >> >> - several payment hashes with their corresponding amounts >> >> - if all corresponding payment keys are shown: cancel the obligation of >> to refund >>-- signed by >>Maybe this can be repeated iteratively if necessary; hopefully the >> not-yet-settled amount will converge to zero. >>Important advantage: this only requires changes to the invoice format, >> not to the network protocol. >>The point is: in this use case, the court is apparently the final point >> of settlement for invoices, just like the blockchain is for the other >> channels in the route. IANAL, but I think the "scripting language" >> accepted by courts is quite flexible, and you can use that to enforce >> atomicity. With the construction described above, you can either refund >> cooperatively (and collect evidence that refund has happened), or, if >> that fails, go to court to enforce settlement there. >>CJP >>Op 12-02-18 om 10:23 schreef Christian Decker: >>>CJP c...@ultimatestunts.nl writes: Can you give a use case for this? Usually, especially in the common case that a payment is done in exchange for some non-cryptographic asset (e.g. physical goods), there already is some kind of trust between payer and payee. So, if a payment is split non-atomically into smaller transactions, and only a part succeeds, presumably they can cooperatively figure out some way to settle the situation. The scenario that is commonly used in these cases is a merchant that provides a signed invoice "if you pay me X with payment_hash Y I will deliver Z". Now the user performs the
Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning
Jim Posenwrites: > If using two hashes to deliver the payment while still getting a proof, I'm > not sure what that provides above just sending regular lightning payments > over multiple routes with one hash. Firstly, if there is a second hash, it > would presumably be the same for all routes, making them linkable again, > which AMP tries to solve. And secondly, the receiver has no incentive to > claim any of the HTLCs before all of them are locked in, because in that > case they are releasing the transaction receipt before fully being paid. Arguably the second concern is not really an issue, if you allow partial claims you'll end up in a whole lot of trouble. It should always be the case that the payment as whole is atomic, i.e., either the entirety of the payment goes through or none of it, independently of whether it was a singlepath or a multipath payment. This is actually one of the really nice features that was enforced using the simple "just reuse the hash"-mechanism, you always had to wait for the complete payment or you'd risk losing part of it. ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning
Good morning Cezary, > That would be great improvement, if AMP could work this way: > > 1. I would like to send 0.1 BTC, so I split this to 5 payment 0.02 BTC each + > one extra 0.02 BTC payment. > 2. When recipient received 6 htlcs, he is able to spend only 5 of them. > If recipient receives, only 5 of them, it is still fine, and payment is > success. > > In such scenario, single route/payment would fail, and payment as whole would > still be success. Do you think that would be possible? It could greatly > increase reliability of LN payments. I will leave it to better mathematicians to answer your direct question, but, my intuition suggests it is not possible as stated. However, let me propose an alternative AMP method instead. -- Roughly, we want to proceed this way. 1. When paying: 1.1. Try to pay. 1.2. If it fails, split it into two smaller payments and recurse into 1. Now we should ensure that the receiver can only receive if it has received all payments, and once it has received all payments, it can claim all payments. So let me first introduce the below dual: * A pseudorandom number generator can be represented by its algorithm and the seed. Alternatively, it can be represented by a stream of numbers. Now, a stream of numbers has no end, but it does have a start (i.e. the first random number generated by the PRNG from the seed). It is possible to "split" a stream into two streams, by taking the 0th, 2nd, 4th... numbers in one stream, and taking the 1st, 3rd, 5th... numbers in the other stream. Each such "split" stream can itself be further split into two streams. Split streams can be re-"merged" by interleaving their members to yield the original pre-split stream. Now, we also want to be able to split a random seed into two seeds. This splitting need not correspond to the stream-split (i.e. the split seeds will NOT generate the split streams); we only need to split seeds to prevent the receiver from claiming partial amounts. This can be done by using another random source to generate a new "seed", and XOR it with the real seed. The split "halves" are then the random number, and seed XOR the random number; the result is two apparently random numbers which, when XORed together, generate the original seed. Let us now sketch our algorithm: 1. def pay(seed, stream, dest, amount): 1.1. try { r = route(dest, amount, randomstuff); offer_htlc(H(stream[0]), r, seed, stream); 1.2. } catch(PaymentFailure) { sd1, sd2 = split_seed(seed); sr1, sr2 = split_stream(stream); pay(sd1, sr1, dest, amount / 2); pay(sd2, sr2, dest, amount / 2); } Now notice that the hash we use is H(stream[0]). That is, the first item in the stream of random numbers. Thus our streams do not actually need to give anything more than the first number in a stream. We can represent a "split" stream simply by the index into the original stream. For example, if we have: s = original stream sl, sr = split_stream(s) sll, slr = split_stream(sl) Then s[0] and sl[0] and sll[0] are simply index 0 into the original stream, sr[0] is index 1, and slr[0] is index 2. We can thus represent streams and their splits by the tuple (seed, index, depth), where depth indicates how many splits the stream has been through. So, for the below: s = (seed, 0, 0) sl, sr = split_stream(s) = (seed, 0, 1), (seed, 1, 1) sll, slr = split_stream(sl) = (seed, 0, 2), (seed, 2, 2) split_stream( (seed, index, depth) ) = (seed, index, depth + 1), (seed, index + 2**depth, depth + 1) Then, for any stream s whose RNG algorithm is PRNG: s[0] = (seed, index, _)[0] = PRNG(seed)[index] Let us now consider how our payment might proceed. 1. First, we generate a random seed, and call pay(seed, (seed, 0, 0), dest, amount) 2. Let us suppose that payment fails for the entire amount. Split the amount into two: 2.1. In one branch we have pay(X, (seed, 0, 1), dest, amount / 2). X is a new random number. 2.2. In other branch we have pay(seed ^ X, (seed, 1, 1), dest, amount / 2). X is the same number as branch 2.1. 2.2.1. Suppose this payment fails. Split it again intow two payments: 2.2.1.1 In one sub-branch we have pay(Y, (seed, 1, 2), dest, amount / 4). 2.2.1.2. In other sub-branch we have pay(seed ^ X ^ Y, (seed, 3, 2), dest, amount / 4). The receiver receives the branches 2.1, 2.2.1.1, and 2.2.1.2., which provide the seeds: 2.1. => X 2.2.1.1 => Y 2.2.1.2. => seed ^X ^ Y Xoring all of the above provides X ^ Y ^ seed ^ X ^ Y = seed. The receiver can claim branch 2.1. by using PRNG(seed)[0], can claim branch 2.2.1.1 using PRNG(seed)[1], and branch 2.2.1.2 using PRNG(seed)[3]. Thus the sender needs only to send the split seed (say 32 bytes) and the index (say 1 byte for up to 8-level splitting into up to 256 payments). The receiver gathers each split seed, XOR them all together to get the original PRNG seed, and runs the PRNG the appropriate number of times to get the