📅 Original date posted:2023-07-03
🗒️ Summary of this message: The sender is confused about the use of a different mechanism in the schnorr multi-hop locks proposal. They suggest using trampoline nodes without impacting the protocol.
📝 Original message:
Hey Zman,
I'm a bit confused because you use a different mechanism than the one
specified in the latest schnorr multi-hop locks proposal that I know of,
which can be found in [1].
If we use the construction from [1], it seems straightforward that using
trampoline doesn't have any impact on the protocol: the sender follows
the exact steps of that protocol and sends the left/right locks in the
trampoline onion.
Then intermediate trampoline nodes can draw their blinding factors
randomly, using the exact same steps, but using the right lock they
received as the secret they're trying to learn (from their point of
view, they're simply doing a normal session of this protocol with a
different secret - and don't learn anything about the "real" secret).
If this doesn't seem straightforward, I can create the same kind of
diagram as the one in [1] but for a trampoline scenario to show that
the maths checks out, let me know if that would be useful.
Cheers,
Bastien
[1]
https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/multi-hop-locks.md
Le jeu. 29 juin 2023 à 16:49, ZmnSCPxj via Lightning-dev <
lightning-dev at lists.linuxfoundation.org> a écrit :
> Good morning list,
>
> Here is a simple mathematical demonstration of a particular way to compute
> blinding factors such that:
>
> * All non-Trampoline intermediate nodes only need to know one blinding
> factor.
> * The receiver only needs to know one blinding factor.
> * Trampoline nodes can provide the nodes on the sub-routes they decide the
> blinding factors without the non-Trampoline intermediate nodes knowing they
> are on a trampoline and not a "direct" source-to-dest route.
>
> First, let us start with:
>
> * The ultimate receiver has a secret `r`.
> * The ultimate receiver gives the ultimate sender the point `R`, such that
> `R = r * G`.
>
> Now, suppose the ultimate sender is directly channeled with the ultimate
> receiver.
>
> The ultimate sender chooses a fresh random scalar `e`, the "error"
> blinding factor that reaches the ultimate receiver.
> It then constructs an onion with `e` decryptable by the ultimate receiver.
> Together with that onion, the ultimate sender offers a PTLC with the point
> `e * G + R`.
>
> The ultimate receiver can claim that PTLC by revealing `e + r`, as it
> learns `e` from the onion, and knows `r` and the contract is to give `r` in
> exchange for payment.
>
> That is the simplest case.
>
> --
>
> Now let us suppose that the ultimate receiver needs to got through an
> intermediate node, Carol.
> The ultimate sender still needs to choose a final error scalar, `e`, by
> random.
> However, it also needs to generate two scalars, `c` and `d`, such that `c
> + d = e`.
> This can be done by selecting a random `d` and computing `c = e - d` (by
> algebra).
> By algebra, `d = e - c`.
> The ultimate sender then encrypts the onion:
>
> * `e` encrypted to the ultimate receiver.
> * The above ciphertext, and `d` encrypted to intermediate node Carol.
>
> The ultimate sender then sends the PTLC with point `c * G + R` to Carol.
>
> Each intermediate non-Trampoline node --- such as Carol --- then gets the
> input point, adds its per-hop blinding factor times `G`, and uses the
> result as the output point to the next hop.
>
> So Carol receives `c * G + R`.
> Carol then adds `d * G` (which is the `d` error it got from the onion).
> Carol then sends a PTLC (with one less onion hop layer as well) with the
> point `c * G + R + d * G`.
>
> Note that `e = c + d`, so we can re-arrange the PTLC sent by Carol to the
> ultimate sender as `(c + d) * G + R`.
> This is equal to `e * G + R`, the exact same as in the case where the
> ultimate sender is directly channeled with ultimate receiver.
>
> The ultimate receiver therefore cannot know whether it received from
> Carol, or from a further node, as in both the direct case and the indirect
> case, the ultimate receiver sees `e * G + R`.
>
> When the ultimate receiver releases `e + r`, Carol can compute `c + r` by
> taking `e + r - d`, and since `c = e - d`, `e + r - d = e - d + r = c + r`.
> It can then claim the incoming `c * G + R` with scalar `c + r`.
> Carol does not know `c`, it only knows `d`, and thus it cannot compute `r`.
>
> --
>
> Now let us instead suppose that Carol is a Trampoline node, and that the
> ultimate sender does not provide a detailed route from Carol to the next
> Trampoline hop.
> In this next example, the ultimate receiver is actually the final
> Trampoline hop after Carol, but Carol does not know this fact (and should
> not be able to learn this fact).
>
> The ultimate sender learns `R`, then selects a random `e`.
> It then selects `c` and `d` such that `c + d = e`, using the same
> technique as above (i.e. random-pick `d` and compute `c = e - d`).
>
> Now the ultimate sender computes a Trampoline-level onion, with the
> following:
>
> * `e` encrypted to the ultimate receiver.
> * the above ciphertext, `d`, and the next Trampoline hop (i.e. the node ID
> of ultimate receiver), encrypted to Carol.
>
> The ultimate sender then sends a PTLC with the above onion, with point `c
> * G + R`, to Carol.
>
> Carol then decrypts the onion, and gets `d`.
> It then has to search for a route from Carol to the ultimate receiver (the
> next Trampoline hop).
>
> Let us suppose that Carol finds a route Carol -> Alice -> ultimate
> receiver.
> Carol now needs to make `c * G + d * G + R` reach the ultimate receiver.
> It can do that by selecting two scalars, `a` and `b`, such that `a + b =
> d`.
> It knows `d`, and can random-pick` b` and then compute `a = d - b`.
>
> Carol then creates the onion:
>
> * It copies the ciphertext from ultimate sender: `e` encrypted to the
> ultimate receiver.
> * The above ciphertext, and `b`, encrypted to Alice.
>
> Carol then sends the PTLC with point `c * G + R + a * G` to Alice.
>
> Alice decrypts the onion and learns `b`.
> Forwarding, it gives the PTLC with point `c * G + R + a * G + b * G` to
> the next hop, the ultimate receiver.
>
> Now, `a + b = d` therefore `a * G + b * G = d * G`.
> And `c + d = e`, therefore `c * G + d * G = e * G`.
> Thus:
>
> c * G + R + a * G + b * G
> = c * G + a * G + b * G + R; commutative property
> = c * G + (a + b) * G + R; associative property
> = c * G + d * G + R; d = a + b by construction
> = (c + d) * G + R; associative property
> = e * G + R; e = c + d by construction
>
> Thus, again, the ultimate receiver gets the same `e * G + R` and cannot
> differentiate whether it was reached via a Trampoline, via a non-Trampoline
> intermediate, or directly.
>
> Similarly, on claiming, every intermediate (Trampoline and non-Trampoline)
> node has enough data to claim its incoming PTLC.
> And only the ultimate sender knows `c`, which allows it to recover the `r`.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> 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/20230703/35ae1f9d/attachment.html>;
Bastien TEINTURIER [ARCHIVE] /
npub17f…ntr0s
2023-07-03 12:53:35
in reply to nevent1q…efph
Author Public Key
npub17fjkngg0s0mfx4uhhz6n4puhflwvrhn2h5c78vdr5xda4mvqx89swntr0sPublished at
2023-07-03 12:53:35Event JSON
{
"id": "7c5046b282140b4eb2d828f1a7488a18c6b7508d509c5710dcfb1389b890ae8b",
"pubkey": "f26569a10f83f6935797b8b53a87974fdcc1de6abd31e3b1a3a19bdaed8031cb",
"created_at": 1688388815,
"kind": 1,
"tags": [
[
"e",
"68622ed15b393cd12500d7bbd89a35624811ac0e91923344172a22a329f52fd6",
"",
"reply"
],
[
"p",
"9456f7acb763eaab2e02bd8e60cf17df74f352c2ae579dce1f1dd25c95dd611c"
]
],
"content": "📅 Original date posted:2023-07-03\n🗒️ Summary of this message: The sender is confused about the use of a different mechanism in the schnorr multi-hop locks proposal. They suggest using trampoline nodes without impacting the protocol.\n📝 Original message:\nHey Zman,\n\nI'm a bit confused because you use a different mechanism than the one\nspecified in the latest schnorr multi-hop locks proposal that I know of,\nwhich can be found in [1].\n\nIf we use the construction from [1], it seems straightforward that using\ntrampoline doesn't have any impact on the protocol: the sender follows\nthe exact steps of that protocol and sends the left/right locks in the\ntrampoline onion.\n\nThen intermediate trampoline nodes can draw their blinding factors\nrandomly, using the exact same steps, but using the right lock they\nreceived as the secret they're trying to learn (from their point of\nview, they're simply doing a normal session of this protocol with a\ndifferent secret - and don't learn anything about the \"real\" secret).\n\nIf this doesn't seem straightforward, I can create the same kind of\ndiagram as the one in [1] but for a trampoline scenario to show that\nthe maths checks out, let me know if that would be useful.\n\nCheers,\nBastien\n\n[1]\nhttps://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/multi-hop-locks.md\n\nLe jeu. 29 juin 2023 à 16:49, ZmnSCPxj via Lightning-dev \u003c\nlightning-dev at lists.linuxfoundation.org\u003e a écrit :\n\n\u003e Good morning list,\n\u003e\n\u003e Here is a simple mathematical demonstration of a particular way to compute\n\u003e blinding factors such that:\n\u003e\n\u003e * All non-Trampoline intermediate nodes only need to know one blinding\n\u003e factor.\n\u003e * The receiver only needs to know one blinding factor.\n\u003e * Trampoline nodes can provide the nodes on the sub-routes they decide the\n\u003e blinding factors without the non-Trampoline intermediate nodes knowing they\n\u003e are on a trampoline and not a \"direct\" source-to-dest route.\n\u003e\n\u003e First, let us start with:\n\u003e\n\u003e * The ultimate receiver has a secret `r`.\n\u003e * The ultimate receiver gives the ultimate sender the point `R`, such that\n\u003e `R = r * G`.\n\u003e\n\u003e Now, suppose the ultimate sender is directly channeled with the ultimate\n\u003e receiver.\n\u003e\n\u003e The ultimate sender chooses a fresh random scalar `e`, the \"error\"\n\u003e blinding factor that reaches the ultimate receiver.\n\u003e It then constructs an onion with `e` decryptable by the ultimate receiver.\n\u003e Together with that onion, the ultimate sender offers a PTLC with the point\n\u003e `e * G + R`.\n\u003e\n\u003e The ultimate receiver can claim that PTLC by revealing `e + r`, as it\n\u003e learns `e` from the onion, and knows `r` and the contract is to give `r` in\n\u003e exchange for payment.\n\u003e\n\u003e That is the simplest case.\n\u003e\n\u003e --\n\u003e\n\u003e Now let us suppose that the ultimate receiver needs to got through an\n\u003e intermediate node, Carol.\n\u003e The ultimate sender still needs to choose a final error scalar, `e`, by\n\u003e random.\n\u003e However, it also needs to generate two scalars, `c` and `d`, such that `c\n\u003e + d = e`.\n\u003e This can be done by selecting a random `d` and computing `c = e - d` (by\n\u003e algebra).\n\u003e By algebra, `d = e - c`.\n\u003e The ultimate sender then encrypts the onion:\n\u003e\n\u003e * `e` encrypted to the ultimate receiver.\n\u003e * The above ciphertext, and `d` encrypted to intermediate node Carol.\n\u003e\n\u003e The ultimate sender then sends the PTLC with point `c * G + R` to Carol.\n\u003e\n\u003e Each intermediate non-Trampoline node --- such as Carol --- then gets the\n\u003e input point, adds its per-hop blinding factor times `G`, and uses the\n\u003e result as the output point to the next hop.\n\u003e\n\u003e So Carol receives `c * G + R`.\n\u003e Carol then adds `d * G` (which is the `d` error it got from the onion).\n\u003e Carol then sends a PTLC (with one less onion hop layer as well) with the\n\u003e point `c * G + R + d * G`.\n\u003e\n\u003e Note that `e = c + d`, so we can re-arrange the PTLC sent by Carol to the\n\u003e ultimate sender as `(c + d) * G + R`.\n\u003e This is equal to `e * G + R`, the exact same as in the case where the\n\u003e ultimate sender is directly channeled with ultimate receiver.\n\u003e\n\u003e The ultimate receiver therefore cannot know whether it received from\n\u003e Carol, or from a further node, as in both the direct case and the indirect\n\u003e case, the ultimate receiver sees `e * G + R`.\n\u003e\n\u003e When the ultimate receiver releases `e + r`, Carol can compute `c + r` by\n\u003e taking `e + r - d`, and since `c = e - d`, `e + r - d = e - d + r = c + r`.\n\u003e It can then claim the incoming `c * G + R` with scalar `c + r`.\n\u003e Carol does not know `c`, it only knows `d`, and thus it cannot compute `r`.\n\u003e\n\u003e --\n\u003e\n\u003e Now let us instead suppose that Carol is a Trampoline node, and that the\n\u003e ultimate sender does not provide a detailed route from Carol to the next\n\u003e Trampoline hop.\n\u003e In this next example, the ultimate receiver is actually the final\n\u003e Trampoline hop after Carol, but Carol does not know this fact (and should\n\u003e not be able to learn this fact).\n\u003e\n\u003e The ultimate sender learns `R`, then selects a random `e`.\n\u003e It then selects `c` and `d` such that `c + d = e`, using the same\n\u003e technique as above (i.e. random-pick `d` and compute `c = e - d`).\n\u003e\n\u003e Now the ultimate sender computes a Trampoline-level onion, with the\n\u003e following:\n\u003e\n\u003e * `e` encrypted to the ultimate receiver.\n\u003e * the above ciphertext, `d`, and the next Trampoline hop (i.e. the node ID\n\u003e of ultimate receiver), encrypted to Carol.\n\u003e\n\u003e The ultimate sender then sends a PTLC with the above onion, with point `c\n\u003e * G + R`, to Carol.\n\u003e\n\u003e Carol then decrypts the onion, and gets `d`.\n\u003e It then has to search for a route from Carol to the ultimate receiver (the\n\u003e next Trampoline hop).\n\u003e\n\u003e Let us suppose that Carol finds a route Carol -\u003e Alice -\u003e ultimate\n\u003e receiver.\n\u003e Carol now needs to make `c * G + d * G + R` reach the ultimate receiver.\n\u003e It can do that by selecting two scalars, `a` and `b`, such that `a + b =\n\u003e d`.\n\u003e It knows `d`, and can random-pick` b` and then compute `a = d - b`.\n\u003e\n\u003e Carol then creates the onion:\n\u003e\n\u003e * It copies the ciphertext from ultimate sender: `e` encrypted to the\n\u003e ultimate receiver.\n\u003e * The above ciphertext, and `b`, encrypted to Alice.\n\u003e\n\u003e Carol then sends the PTLC with point `c * G + R + a * G` to Alice.\n\u003e\n\u003e Alice decrypts the onion and learns `b`.\n\u003e Forwarding, it gives the PTLC with point `c * G + R + a * G + b * G` to\n\u003e the next hop, the ultimate receiver.\n\u003e\n\u003e Now, `a + b = d` therefore `a * G + b * G = d * G`.\n\u003e And `c + d = e`, therefore `c * G + d * G = e * G`.\n\u003e Thus:\n\u003e\n\u003e c * G + R + a * G + b * G\n\u003e = c * G + a * G + b * G + R; commutative property\n\u003e = c * G + (a + b) * G + R; associative property\n\u003e = c * G + d * G + R; d = a + b by construction\n\u003e = (c + d) * G + R; associative property\n\u003e = e * G + R; e = c + d by construction\n\u003e\n\u003e Thus, again, the ultimate receiver gets the same `e * G + R` and cannot\n\u003e differentiate whether it was reached via a Trampoline, via a non-Trampoline\n\u003e intermediate, or directly.\n\u003e\n\u003e Similarly, on claiming, every intermediate (Trampoline and non-Trampoline)\n\u003e node has enough data to claim its incoming PTLC.\n\u003e And only the ultimate sender knows `c`, which allows it to recover the `r`.\n\u003e\n\u003e Regards,\n\u003e ZmnSCPxj\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20230703/35ae1f9d/attachment.html\u003e",
"sig": "65da68156f6351216cef2ee70dcfbbc391e21047eef8cc76319c5dc4b3218fcaf6ac2f8df5ce392ab8687314d30aa196d4b1873a6b8a8e5d4308a020312c3df5"
}