Bastien TEINTURIER [ARCHIVE] on Nostr: 📅 Original date posted:2023-07-03 🗒️ Summary of this message: The sender is ...
📅 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>;
🗒️ 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>;