[Lightning-dev] AMP via HD, BN+SS, and TR
ZmnSCPxj
ZmnSCPxj at protonmail.com
Mon Mar 19 00:25:13 UTC 2018
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/20180318/ce9decae/attachment.html>
More information about the Lightning-dev
mailing list