[Lightning-dev] AMP via HD, BN+SS, and TR

[ZmnSCPxj]

Good morning list,

It is possible to mean atomic in multiple meanings:

1.  The payee is completely unable to claim any partial payments until all partial payments arrive at the payee.
2.  The payee is not incentivized to claim partial payments until all partial payments arrive at the payee.

My proposal uses "atomic" in the sense of #2.  As soon as a single partial payment reveals a child key k_i, then with the know public parent key K_par it is possible to compute parent secret key k_par.

This is sufficient if k_par is valuable, for example if it is also the encryption key for valuable digital data such as some megabytes of a streamed movie, game downloadable content, ransomed files, etc. i.e. for ZKCP.  The payee is incentivized to claim payments only if all partial payments reach it, since once it claims any sub-payment, it will also release the valuable secret k_par.

However, it is possible to upgrade from #2 to #1 by adding a secret from the payer to the payee that is sent "in pieces" for each sub-payment.

We add this payer secret p and modify our derivation as follows:

K_i = H(i || p || K_par) * G + K_par

k_i = H(i || p || k_par * G) + k_par

k_par can be derived if we know any i, k_i, p, and K_par:

k_par = k_i - H(i || p || K_par)

When splitting a single payment into two payments, the payer generates a hiding random number x_1.

When sending an onion payment, the onion payload contains pieces of the payer secret p.  For example, in the 2-subpayment case:

sub-payment 1: p ^ x_1
sub-payment 2: x_1

This can be extended to any number of subpayments n:

sub-payment 1: p ^ x_1 ^ ... ^ x_n-1
sub-payment 2: x_1
...
sub-payment n: x_n-1

In this case, the payee truly cannot claim any sub-payment unless all sub-payments have reached it.  When all sub-payments have reached it, it XORs all the pieces of the payer secret together to compute p.

The payee cannot derive k_i unless it knows i, p, and the secret k_par.  Once at least one sub-payment is claimed, then the payer can derive the secret k_par.

Since offers on LN are HTLCs, there is a timelock involved.  As long as the payee does not claim too close to the timelock, it has time to claim all sub-payments, even if only claiming one sub-payment is enough for the payer to derive the (potentially valuable) secret k_par.

Thus this scheme achieves atomicity in the sense "the payee cannot claim partial payments", not just "the payee is disincentivized to claim partial payments".

Regards,
ZmnSCPxj

Sent with [ProtonMail](https://protonmail.com) Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On March 19, 2018 8:25 AM, ZmnSCPxj via Lightning-dev <lightning-dev at lists.linuxfoundation.org> wrote:

> Good morning list,
>
> I sketch here the idea, of making atomic multipath payment (AMP), with the properties:
>
> 1.  Has a proof-of-payment.
> 2.  Multipath decorrelation.
>
> Note: I am not a mathematician.  Thus, it is likely, that there is a mistake here, and we cannot make this work.
>
> First, we look at BIP32 hierarchically derived (HD) keys by Wuille.  Roughly, given a parent private key k_par, we can do derive k_i child keys for integer i by:
>
> k_i = H(i || k_par * G) + k_par
>
> where H(x) is a hash function and G is the generator point. (this it not quite how BIP32 does it, it uses HMAC, maybe that is safer for some reason that my non-mathematician self is unaware of...)
>
> The parent public key K_par = k_par * G.  We can derive K_i public child keys for integer i by:
>
> K_i = H(i || K_par) * G + K_par
>
> (I think)
>
> Note that K_i = k_i * G still, as is usual for elliptic curve asymmetric cryptography:
>
> K_i = k_i * G = (H(i || k_par * G) + k_par) * G = H(i || k_par * G) * G + k_par * G = H(i || K_par) * G + K_par
>
> Of note is that if we know an i, a private child key k_i corresponding to that i, and the public parent key K_par, we can derive the private parent key k_par:
>
> k_i = H(i || K_par) + k_par
>
> k_par = k_i - H(i || K_par)
>
> Now all we need is to have a conditional payment, which can only be performed if the payee provides a private key which matches a public key, i.e. given x * G, the payee must provide x.
>
> Fortunately Poelstra has done this work beforehand in the Scriptless Script (SS) concept, where the payee provides a T = t * G, and the Scriptless Script construction requires that the payee reveal the t in order to claim the payment.  I will not go into the math since there is a good chance I shall make a mistake; look up discussions by better mathematicians by me.  Scriptless Script requires Bellare-Neven (BN) signatures to work.
>
> Note that Scriptless Script handles only the equivalent of hashlocking.  We still need a timelock in case the payee refuses to reveal the proof-of-payment t.
>
> Fortunately, Maxwell has provided a construction, taproot (TR).  This construction has two top-level branches: a Bellare-Neven n-of-n, or a Bitcoin Script.  We know that Scriptless Script can make an equivalent to a hashlock from a Bellare-Neven n-of-n.  The other branch of a taproot construction can now be a simple OP_CLTV+OP_CHECKSIG script, forming the timelock half of an HTLC.
>
> How would a multipath payment work?  The invoice would contain the parent public key K_par.  From this, the payer derives as many K_i, as it needs to split the payment to.  It sets up conditional payments that require revelation of the private child key k_i for each K_i it derives.
>
> When the payee receives a partial payment, it is not incentivized to claim it immediately yet.  This is because revelation of even one child key k_i will, in combination with the parent public key K_par, reveal the parent private key k_par, which serves as proof-of-payment.  The payee will wait for the entire payment to reach it, and then claim all of them.  This reveals all the private child keys k_i, any one of which will let the payer extract the parent private key k_par that serves as proof-of-payment.
>
> Each path has a different k_i, thus providing multipath decorrelation.
>
> (Please check my math --- I am not a mathematician and it is possible I have made a mistake somewhere)
>
> Regards,
> ZmnSCPXj
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180320/fb7f65dd/attachment-0001.html>